Множества

Определения

Определение:

Множество — любая совокупность элементов одной природы, мыслимая как единое целое.

Определение:

Пустое множество — множество, не содержащее элементов. Обозначается [math]\displaystyle{ \varnothing }[/math].

Определение:

Множества считаются равными, если они состоят из одних и тех же элементов.

Определение:

Два множества называются равномощными, если каждому элементу одного множества взаимно-однозначно сопоставляется один и только один элемент другого.

Определение:

Множество, равномощное множеству всех натуральных чисел [math]\displaystyle{ \N }[/math], называют счетным множеством.

Определение:

Мощность множества — количество элементов множества. Обозначают [math]\displaystyle{ \vert A \vert }[/math]. Используется для конечных множеств.

Подмножества

Определение:

Обозначают [math]\displaystyle{ A \subseteq B }[/math] и говорят, что множество [math]\displaystyle{ A }[/math] является подмножеством множества [math]\displaystyle{ B }[/math], если каждый элемент множества [math]\displaystyle{ A }[/math] является элементом множества [math]\displaystyle{ B }[/math].

Если также известно, что [math]\displaystyle{ A \neq B }[/math], говорят, что [math]\displaystyle{ A }[/math] является собственным (или строгим) подмножеством множества [math]\displaystyle{ }[/math] и пишут [math]\displaystyle{ A \subset B }[/math].

Пример

1) [math]\displaystyle{ \{ 1,\ 3 \} \subset \{ 3,\ 5,\ 1,\ 4 \} }[/math]
2) [math]\displaystyle{ \{ k,\ l,\ j \} \subseteq \{ l,\ j,\ k \} }[/math]

Определение:

Множество всех подмножеств множества [math]\displaystyle{ A }[/math] будем обозначать [math]\displaystyle{ 2^A }[/math]. Мощность множества всех подмножеств множества с [math]\displaystyle{ n }[/math] элементами равна [math]\displaystyle{ 2^n\colon \ \vert 2^A \vert = 2^{\vert A \vert} }[/math].

Пример

Пусть [math]\displaystyle{ A = \{ a,\ b,\ c \} }[/math]. Тогда [math]\displaystyle{ 2^A = \{ \varnothing,\ \{a\},\ \{b\},\ \{c\},\ \{a,\ b\},\ \{a,\ c\},\ \{b,\ c\},\ \{A\} \} }[/math]. Видно, что в этом множестве [math]\displaystyle{ 2^{\vert A \vert} = 2^3 = 8 }[/math] элементов.

Операции над множествами

Объединение множеств

[math]\displaystyle{ A \cup B = \{ x \mid x \in A\ }[/math] или [math]\displaystyle{ \ x \in B \} }[/math]

Пересечение множеств

[math]\displaystyle{ A \cap B = \{ x \mid x \in A\ }[/math] и [math]\displaystyle{ \ x \in B \} }[/math]

Дополнение множества

[math]\displaystyle{ \overline{A} = \{ x \mid x \in U\ }[/math] и [math]\displaystyle{ \ x \notin A \} }[/math], где [math]\displaystyle{ U }[/math] — универсальное множество.

Разность множеств

[math]\displaystyle{ A\ \backslash\ B = \{ x \mid x \in A\ }[/math] и [math]\displaystyle{ \ x \notin B \} }[/math]

Симметрическая разность множеств

[math]\displaystyle{ A\ \dot - \ B = \left ( A\ \backslash\ B \right ) \cup \left ( B\ \backslash\ A \right ) }[/math]

Утверждение (Основные тождества алгебры множеств):

Пусть [math]\displaystyle{ A,\ B,\ C,\ }[/math] произвольные подмножества множества [math]\displaystyle{ U }[/math], тогда выполняются следующие тождества:

[math]\displaystyle{ 1)\ }[/math] Коммутативность: [math]\displaystyle{ \ a)\ }[/math] [math]\displaystyle{ A \cup B = B \cup A ;\quad }[/math] [math]\displaystyle{ b)\ A \cap B = B \cap A }[/math]

[math]\displaystyle{ 2)\ }[/math] Ассоциативность: [math]\displaystyle{ \ a)\ A \cup \left ( B \cup C \right ) = \left ( A \cup B \right ) \cup C ; \quad }[/math] [math]\displaystyle{ b)\ A \cap \left ( B \cap C \right ) = \left (A \cap B \right ) \cap C }[/math];

[math]\displaystyle{ 3)\ }[/math] [math]\displaystyle{ a) }[/math] Дистрибутивность [math]\displaystyle{ \cup }[/math] относительно [math]\displaystyle{ \cap: \ }[/math] [math]\displaystyle{ A \cup \left ( B \cap C \right ) = \left ( A \cup B \right ) \cap \left ( A \cup C \right ) }[/math]

[math]\displaystyle{ \quad\ \ b) }[/math] Дистрибутивность [math]\displaystyle{ \cap }[/math] относительно [math]\displaystyle{ \cup: \ }[/math] [math]\displaystyle{ A \cap \left ( B \cup C \right ) = \left ( A \cap B \right ) \cup \left ( A \cap C \right ) }[/math]

[math]\displaystyle{ 4)\ }[/math] [math]\displaystyle{ A \cup \varnothing = A }[/math]; [math]\displaystyle{ \quad A \cap \varnothing = \varnothing }[/math]

[math]\displaystyle{ 5)\ }[/math] [math]\displaystyle{ A \cup U = U }[/math]; [math]\displaystyle{ \ A \cap U = A }[/math]

[math]\displaystyle{ 6)\ }[/math] [math]\displaystyle{ A \cup \overline{A} = U }[/math]; [math]\displaystyle{ \quad A \cap \overline{A} = \varnothing }[/math]

[math]\displaystyle{ 7)\ }[/math] Законы де Моргана: [math]\displaystyle{ \overline{A \cup B} = \overline{A} \cap \overline{B} }[/math]; [math]\displaystyle{ \quad \overline{A \cap B} = \overline{A} \cup \overline{B} }[/math]

[math]\displaystyle{ 8)\ }[/math] Идемпотентность: [math]\displaystyle{ A \cup A = A }[/math]; [math]\displaystyle{ \quad A \cap A = A }[/math]

[math]\displaystyle{ 9)\ }[/math] Законы поглощения [math]\displaystyle{ A \cap \left ( A \cup B \right ) = A; }[/math] [math]\displaystyle{ \quad A \cup \left ( A \cap B \right ) = A }[/math]

[math]\displaystyle{ 10)\ }[/math] Инволютивный закон [math]\displaystyle{ \overline{\overline{A}} = A }[/math]

Доказательства тождеств следуют из определений операций над множествами.