Множества

Определения

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

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

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

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

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

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

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

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

Рис. 1. Сверху порядок перечисления не влияет на равенство: [math]\displaystyle{ \{2,4,6\} = \{4,2,6\} }[/math]. Снизу [math]\displaystyle{ \{a,b\} }[/math] — элемент множества [math]\displaystyle{ \{\{a,b\}\} }[/math], поэтому [math]\displaystyle{ a }[/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] элементов.

Рис. 1. Все восемь подмножеств [math]\displaystyle{ A=\{a,b,c\} }[/math] расположены по числу элементов; линия означает включение. Каждый элемент либо входит, либо нет, поэтому [math]\displaystyle{ |2^A| = 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]

Рис. 1. Базовые операции над множествами. Заштрихована область, которая является результатом операции; прямоугольник [math]\displaystyle{ U }[/math] — универсальное множество.

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

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

Рис. 2. Симметрическая разность: объединение разностей [math]\displaystyle{ A \setminus B }[/math] и [math]\displaystyle{ B \setminus A }[/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]

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

Рис. 3. Законы де Моргана: дополнение объединения — это пересечение дополнений, а дополнение пересечения — объединение дополнений. Заштрихован результат.

Прямое произведение множеств

Пусть $A=\{a_1,a_2,...,a_k\}$, $B=\{b_1,b_2,...,b_l\}$, $A\times B = \{(a_1,b_1),(a_1,b_2),...,(a_1,b_l),(a_2,b_1),...,(a_k,b_l)\}= \{(a,b) | a\in A, b\in B\}$ — прямое (декартово) произведение множеств $A$ и $B$.

Во многих случаях порядок проведения операций произведения не важен. Тогда считают, что $A\times(B\times C) = (A\times B) \times C = \{(a,b,c) | a\in A, b\in B, c\in C\}.$

Аналогично определяется прямое произведение любого конечного числа множеств. $A_1\times A_2 \times ... \times A_t = \{(a_1,a_2,...,a_t) | a_i\in A_i, i=\overline{1,t} \}$ Если речь будет идти о прямом произведении множества на себя, то будем заменять запись нескольких множеств на знак степени: $\underbrace{A\times A \times ... \times A}_t = A^t.$

Рис. 1. Каждая клетка таблицы — упорядоченная пара [math]\displaystyle{ (a_i, b_j) }[/math]. Три строки на две колонки дают [math]\displaystyle{ 3\cdot 2 = 6 }[/math] пар; порядок внутри пары важен.

Конспект: Дискретная математика