Sets

Sets

'’Множество’’ - совокупность различных предметов объединённых в одно целое по некоторому признаку.

Объекты, из которых состоит множество, называют ‘‘элементами’’ множества. Во множестве не может быть более одного одинакового элемента.

• $a \in A$ - элемент a принадлежит множеству $A$
• $a \notin A$ - элемент a не принадлежит множеству $A$

'’Пустое множество’’ - множество, не содержащее ни одного элемента. Обозначается $\varnothing$

Sets делят на ‘‘конечные’’ множества (например, число жителей города Биробиджана) и на ‘‘бесконечные’’ (число точек на отрезке).

Способы задания

• Перечисление:

  $A = {a_1, a_2, …, a_n}$

• Характеристические свойства:

  $A = { x | P(x) }$, где $P(x)$ - свойство, которым обладают элементы $x \in A$ и не обладают $x \notin A$. |: Например, $X = {x | x^2 - 3x + 2 = 0}$ |

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

  Если каждый элемент множества $A$ является так же и элементом множества $B$, то $A$ - ‘‘подмножество’’ $B$. Обозначается $A \subset B$.

Каждое непустое множество $A$ имеет хотя бы два подмножества: само $A$ и $\varnothing$. Эти множества являются ‘‘несобственными’’ подмножествами $A$, а все остальные подмножества (если существуют) - ‘‘собственными’’.

Если $A \subset B$ и $B \subset C$, то $A \subset C$. Т.е. свойство быть подмножеством удовлетворяет условию ‘‘транзитивности’’.

Если $A \subset B$ и $B \subset A$, то $A$ и $B$ ‘‘равны’’.

'’Универсальное множество’’ $U$ - множество, включающее все возможные элементы. Т.е. для любого множества $A$, $A \subset U$.

Круги Эйлера

'’Круги Эйлера’’ - геометрическая схема для наглядного изображения отношения между подмножествами.

Операции

Пересечение

'’Пересечением’’ (произведением) множеств $A$ и $B$ называется множество, состоящее из элементов, принадлежащих одновременно и $A$ и $B$.

$A \cap B = { x | x \in A \mbox{~and~} x \in B}$ |

Объединение

'’Объединением’’ (сложением) $A$ и $B$ является множество всех элементов, принадлежащих хотя бы $A$ или $B$.

$A \cup B = { x | x \in A \mbox{~and~} x \in B}$ |

Разность

'’Разностью’’ $A$ и $B$ называют множество, состоящее из всех элементов, не принаджежащих $B$ и принадлежащих $A$.

$A \backslash B = { x | x \in A \mbox{~or~} x \notin B}$ | ‘‘Симметричной разностью’’ $A$ и $B$ называют множество, принадлежащее либо $A$, либо $B$, но не сразу и $A$ и $B$.

'’Дополнением’’ множества А до универсального множества U называют множество всех элементов не принадлежащих множеству A и обозначается $\bar{A}$.

$\bar{A} = U \backslash A = { x | x \in A \mbox{~and~} x \notin U }$ |

Декартово произведение

Декартовым произведением множеств $A$ и $B$ называют множество таких упорядоченных пар $(a, b)$, что $x \in A, y \in B$:

$A \times B = { (x, y) | x \in A, y \in B }$ | Пусть задано $n$ множеств $X_1, X_2, …, X_n$. Декартовым произведением $X_1 \times X_2 \times … \times X_n$ называют множество возможных упорядоченных наборов $\alpha = (x_1, x_2, …, x_n)$, таких, что $x_1 \in X_1, x_2 \in X_2, …, x_n \in X_n$:

$X_1, X_2, …, X_n = { (x_1, x_2, …, x_n) | x_i \in X_i, i = 1, …, n }$ | Каждый набор $\alpha = (x_1, x_2, …, x_n)$ называется кортежем длины $n$, составленный из элементов множества $X^n = X \times X \times … \times X$. Элемент $x_i$ называется $i$-ой компонентой кортежа.

Отличия кортежа от множества:

• во множестве порядок не имеет значения, а в кортеже имеет;
• во множестве все элементы различны а в кортеже могут повторяться

Алгебра множеств

• Объединения и пересечения коммутативны

  $A \cup B = B \cup A$

  $A \cap B = B \cap A$

• Объединения и пересечения ассоциативны

  $(A \cup B) \cup C = A \cup (B \cup C)$

  $(A \cap B) \cap C = A \cap (B \cap C)$

• Свойства дистрибутивности объединения относительно пересечения и дистрибутивности пересечения отностительно объединения

  $(A \cap B) \cup C = (A \cup C) \cap (D \cup C)$

  $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$

• $A \cup A = A$
• $A \cup U = U$ и $A \cap U = A$
• $A \cup \varnothing = A$ и $A \cap \varnothing = \varnothing$
• $\Bar{\Bar{A}} = A$
• $\bar{U} = \varnothing$ и $\bar{\varnothing} = U$

• Законы де-Моргана

  $\overline{A \cup B} = \overline{A} \cap \overline{B}$ и

  $\overline{A \cap B} = \overline{A} \cup \overline{B}$

Формула включений и исключений

Дано $m$ предметов $x_1, x_2, …, x_m$ и $n$ множеств $\alpha_1, \alpha_2, …, \alpha_n$. При этом элементы $x_i$ могут принадлежать любому произвольному $\alpha_i$, а могут не принадлежать.

Введём обозначения

• $N$ - число всех предметов, $N = m$
• $N(\alpha_i \alpha_j … \alpha_k)$ - количество элементов, принадлежащих множеству $\alpha_i \cup \alpha_j \cup … \cup \alpha_k$,
• $N(\overline{\alpha_i \alpha_j … \alpha_k})$ - количество не принадлежащих ни одному из $\alpha_i \alpha_j … \alpha_k$ (т.е. не принадлежащих $\alpha_i \cap \alpha_j \cap … \cap \alpha_k$).

Вычислим $N(\overline{\alpha_1 \alpha_2 … \alpha_n})$ - т.е. посчитаем число элементов, не принадлежащих ни одному из множеств.

$N(\overline{\alpha_1 \alpha_2 … \alpha_n}) = N - N(\alpha_1) - N(\alpha_2) - … - N(\alpha_n) + N(\alpha_1 \alpha_2) + N(\alpha_1 \alpha_3) + N(\alpha_1 \alpha_4) + … N(\alpha_1 \alpha_n) + … + N(\alpha_{n-1} \alpha_n) - N(\alpha_1 \alpha_2 \alpha_3) - … + (-1)^n N(\alpha_1 \alpha_2 … \alpha_n)$

Причем слагаемое $N(…)$ имеет знак “+”” если число множеств чётно, и “-“, если нечётно.

Эту формулу можно записать схематично, как $N(\overline{\alpha \beta … \omega})$ = $N(1 - \alpha)(1 - \beta)…(1 - \omega)$, а после раскрытия скобок заменить $N\alpha\beta…\omega$ на $N(\alpha\beta…\omega)$.

Доказательство

По индукции:

1 шаг: для 1

$N(\overline{\alpha_1}) = N - N(\alpha_1})$

2 шаг: для $n - 1$

$N(\overline{\alpha_1 \alpha_2 … \alpha_{n - 1}}) = N - N(\alpha_1) - … + N(\alpha_1 \alpha_2) + … - N(\alpha_1 \alpha_2 \alpha_3) - … + (-1)^{n-1} N(\alpha_1 \alpha_2 … \alpha_{n-1})$

3 шаг: для $n$

Рассмотрим группу элементов, принадлежащих $\alpha_n$

$N(\overline{\alpha_1 \alpha_2 … \alpha_{n - 1}} \alpha_n) = N(\alpha_n) - N(\alpha_1 \alpha_n) - … + N(\alpha_1 \alpha_2 \alpha_n) + … - N(\alpha_1 \alpha_2 \alpha_3 \alpha_n) - … + (-1)^{n-1} N(\alpha_1 \alpha_2 … \alpha_{n-1} \alpha_n)$

Вычтем $N(\overline{\alpha_1 \alpha_2 … \alpha_{n - 1}} \alpha_n)$ из $N(\overline{\alpha_1 \alpha_2 … \alpha_{n - 1}})$

• $N(\overline{\alpha_1 \alpha_2 … \alpha_{n - 1}})$ - число элементов, которые могут принадлежать \alpha_n, а могут и не принадлежать
• $N(\overline{\alpha_1 \alpha_2 … \alpha_{n - 1}} \alpha_n)$ - число элементов, которые наверняка принадлежат \alpha_n
• Т.е. их разность как раз равна числу элементов, не принадлежащих ни одному из $\alpha_1 \alpha_2 … \alpha_n$

Таким образом, $N(\overline{\alpha_1 \alpha_2 … \alpha_n}) = N(\overline{\alpha_1 \alpha_2 … \alpha_{n - 1}}) - N(\overline{\alpha_1 \alpha_2 … \alpha_{n - 1}} \alpha_n)$.

’'’Q.E.D.’’’

Sources

• Киреенко С.Г., Гриншпон И.Э. Элементы теории множеств (учебное пособие). Томск, 2003. http://portal.tpu.ru/lyceum/innovacion/workroom/sets.pdf
• Виленкин Н.Я. Комбинаторика. М., Наука, 1969.