Теория множеств
Кратко
- Множество – это совокупность различных объектов, называемых элементами, выделенных по какому-то признаку.
Пример: множество натуральных чисел \(\mathbb{N} = \{1,2,3,\dots\}\). - Элемент множества – объект, который принадлежит множеству.
«\(a \in A\)» читается как «a принадлежит множеству A». - Пустое множество – множество, не содержащее ни одного элемента.
Обозначение: \(\varnothing\). - Подмножество – множество \(A\) является подмножеством множества \(B\), если все элементы \(A\) принадлежат \(B\).
\(A \subseteq B\) - Равенство множеств – множества \(A\) и \(B\) равны, если они содержат одни и те же элементы.
\(A = B \iff (A \subseteq B \wedge B \subseteq A)\) - Объединение множеств – множество всех элементов, которые принадлежат хотя бы одному из множеств.
\(A \cup B = \{x \mid x \in A \text{ или } x \in B\}\) - Пересечение множеств – множество всех элементов, которые принадлежат обоим множествам.
\(A \cap B = \{x \mid x \in A \text{ и } x \in B\}\) - Разность множеств – множество всех элементов, которые принадлежат первому множеству, но не второму.
\(A \setminus B = \{x \mid x \in A \text{ и } x \notin B\}\) - Дополнение множества – множество всех элементов универсального множества \(U\), которых нет в \(A\).
\(\overline{A} = \{x \in U \mid x \notin A\}\) - Декартово произведение множеств – множество всех упорядоченных пар элементов.
\(A \times B = \{(a,b) \mid a \in A, b \in B\}\)
Основные понятия
- Множество — это совокупность элементов (объектов), объединённых по какому-то признаку.
Обозначается:
\[
A = \{a_1, a_2, a_3, \dots\}
\]
- Принадлежность элемента множеству: \(a \in A \quad \text{— элемент } a \text{ принадлежит множеству } A\) \(a \notin A \quad \text{— элемент } a \text{ не принадлежит множеству } A\)
Основные обозначения
| Обозначение | Значение |
|---|---|
| \(A \cup B\) | объединение множеств: все элементы, которые есть в \(A\) или в \(B\) |
| \(A \cap B\) | пересечение множеств: только те элементы, которые есть и в \(A\), и в \(B\) |
| \(A \setminus B\) | разность множеств: элементы, которые есть в \(A\), но нет в \(B\) |
| \(A \times B\) | декартово произведение: все пары \((a, b)\), где \(a \in A\), \(b \in B\) |
| \(\overline{A}\) или \(A'\) | дополнение множества \(A\) относительно универсального множества \(U\) |
| \(\emptyset\) | пустое множество (не содержит элементов) |
| \(A \subseteq B\) | \(A\) — подмножество \(B\) (может быть равно) |
| \(A \subset B\) | строгое подмножество \(B\) (\(A \subseteq B\), но \(A \neq B\)) |
| \(A = B\) | множества равны (одинаковые элементы) |
| \(U\) | универсальное множество, всё, что рассматриваем |
| \(\vert A\vert\) | мощность множества (количество элементов) |
| \(A \triangle B\) | симметрическая разность: элементы, которые есть только в одном из множеств |
Конечные, счётные и несчётные множества
- Конечное множество — содержит конечное число элементов.
\[
|A| = n, \quad n \in \mathbb{N}
\]
Пример:
\[
A = \{1,2,3,4,5\}
\]
- Счётное множество — его элементы можно занумеровать натуральными числами (установить биекцию с \(\mathbb{N}\)).
\[
|A| = \aleph_0
\]
Примеры:
\[
\mathbb{N}, \mathbb{Z}, \mathbb{Q}
\]
- Несчётное множество — его элементы нельзя пронумеровать натуральными числами.
Мощность больше, чем у счётных.
Пример:
\(\mathbb{R}, \; [0,1]\) \(|\mathbb{R}| = \mathfrak{c} > \aleph_0\)Комбинаторика
Правило суммы
Если событие \(A\) может произойти \(n\) способами, а событие \(B\) — \(m\) способами,
и они не пересекаются, то одно из них может произойти \(n + m\) способами:
\[
N = n + m
\]
Если пересекаются, то из суммы нужно вычесть пересечение:
\[
N = n + m - |A \cap B|
\]
Правило произведения
Если действие \(A\) выполняется \(n\) способами,
а после него действие \(B\) — \(m\) способами,
то оба вместе выполняются \(n \times m\) способами:
\[
N = n \cdot m
\]
Для \(k\) независимых действий:
\[
N = n_1 \cdot n_2 \cdot \dots \cdot n_k
\]
Формула включения–исключения
Формула включения–исключения — комбинаторная формула, позволяющая определить мощность объединения конечного числа множеств, которые в общем случае могут пересекаться друг с другом.
Для двух множеств:
\[
|A \cup B| = |A| + |B| - |A \cap B|
\]
Для трёх множеств:
\[
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|
\]
В общем виде (для \(n\) множеств):
\[
\left|\bigcup_{i=1}^{n} A_i\right|
= \sum_{i=1}^{n} |A_i|
- \sum_{1 \le i < j \le n} |A_i \cap A_j|
+ \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k|
- \dots
+ (-1)^{n+1} |A_1 \cap A_2 \cap \dots \cap A_n|
\]
Пример 2: Два множества
В классе 30 учеников:
- 18 любят математику (\(A\))
- 12 любят физику (\(B\))
- 5 любят и математику, и физику (\(A \cap B\))
Сколько всего учеников любят математику или физику (\(A \cup B\))?
Решение:
По формуле включения–исключения для двух множеств:
\[
|A \cup B| = |A| + |B| - |A \cap B|
\]
Подставляем числа:
\[
|A \cup B| = 18 + 12 - 5 = 25
\]
Ответ: 25 учеников любят математику или физику.
Пример 2: Три множества
В группе 40 студентов:
- 20 изучают математику (\(A\))
- 15 изучают физику (\(B\))
- 10 изучают информатику (\(C\))
- 5 изучают математику и физику (\(A \cap B\))
- 4 изучают математику и информатику (\(A \cap C\))
- 3 изучают физику и информатику (\(B \cap C\))
- 2 изучают все три предмета (\(A \cap B \cap C\))
Сколько студентов изучают хотя бы один предмет (\(A \cup B \cup C\))?
Решение:
\[
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|
\]
Подставляем числа:
\[
|A \cup B \cup C| = 20 + 15 + 10 - 5 - 4 - 3 + 2 = 35
\]
Ответ: 35 студентов изучают хотя бы один предмет.
Операции над множествами
Объединение
\[
A \cup B = \{x \mid x \in A \text{ или } x \in B\}
\]
— элементы, которые есть хотя бы в одном из множеств.
Пересечение
\[
A \cap B = \{x \mid x \in A \text{ и } x \in B\}
\]
— элементы, которые есть в обоих множествах.
Разность
\[
A \setminus B = \{x \mid x \in A \text{ и } x \notin B\}
\]
— элементы, которые есть в \(A\), но нет в \(B\).
Симметрическая разность
\[
A \triangle B = (A \setminus B) \cup (B \setminus A)
\]
— элементы, которые есть только в одном из множеств.
Декартово произведение
Определение:
Декартово произведение двух множеств \(A\) и \(B\) — это множество всех упорядоченных пар \((a, b)\), где \(a \in A\), \(b \in B\):
\[
A \times B = \{(a, b) \mid a \in A,\, b \in B\}
\]
Свойства:
- Каждая пара состоит из первого элемента из \(A\) и второго элемента из \(B\).
- Количество элементов: \(|A \times B| = |A| \cdot |B|\).
- Можно обобщить на \(k\) множеств: \(A_1 \times A_2 \times \dots \times A_k\).
Пример
\[
\begin{aligned}
A &= \{1, 2\} \\
B &= \{x, y\} \\
A \times B &= \{(1,x), (1,y), (2,x), (2,y)\}
\end{aligned}
\]
Дополнение (относительно универсального множества U)
\[
\overline{A} = U \setminus A
\]
— всё, что не входит в \(A\).
Пример
Пусть \(A = \{1,2,3\}\), \(B = \{2,3,4\}\)
- Объединение:
\[
A \cup B = \{1,2,3,4\}
\]
- Пересечение:
\[
A \cap B = \{2,3\}
\]
- Разность:
\[
A \setminus B = \{1\}, \quad B \setminus A = \{4\}
\]
- Симметрическая разность:
\[
A \triangle B = \{1,4\}
\]
Основные законы (аналогия с логикой)
| Закон | Формула |
|---|---|
| Коммутативность | \(A \cup B = B \cup A,\quad A \cap B = B \cap A\) |
| Ассоциативность | \((A \cup B) \cup C = A \cup (B \cup C)\) |
| Дистрибутивность | \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) |
| Идемпотентность | \(A \cup A = A, \quad A \cap A = A\) |
| Поглощение | \(A \cup (A \cap B) = A,\quad A \cap (A \cup B) = A\) |
| Закон де Моргана | \(\overline{A \cup B} = \overline{A} \cap \overline{B}, \overline{A \cap B} = \overline{A} \cup \overline{B}\) |
Кардинальность (мощность множества)
- \(|A|\) — мощность множества \(A\), то есть количество элементов.
\[
|A| = n \text{ — если } A \text{ содержит } n \text{ элементов.}
\]
- Для бесконечных множеств:
\[
|\mathbb{N}| = \aleph_0, \quad |\mathbb{R}| = \mathfrak{c}
\]
Декартово произведение
\[
A \times B = \{(a, b) \mid a \in A,\, b \in B\}
\]
— множество упорядоченных пар, первая из \(A\), вторая из \(B\).
Семейства множеств
- Объединение семейства:
\[
\bigcup_{i \in I} A_i = \{x \mid \exists i \in I,\ x \in A_i\}
\]
- Пересечение семейства:
\[
\bigcap_{i \in I} A_i = \{x \mid \forall i \in I,\ x \in A_i\}
\]
Обозначение различных числовых множеств
| Обозначение | Описание |
|---|---|
| \(\mathbb{N}\) | множество натуральных чисел |
| \(\mathbb{Z}\) | целые числа |
| \(\mathbb{Q}\) | рациональные |
| \(\mathbb{R}\) | вещественные |
| \(\mathbb{C}\) | комплексные |
Круги Эйлера (диаграммы Эйлера)
Круги Эйлера — наглядный способ показать отношения между множествами: подмножества, пересечения, непересечения.
Основные идеи
- Множество изображается кругом или другой замкнутой фигурой.
- Если множество \(A\) является подмножеством \(B\) → круг \(A\) внутри круга \(B\).
- Если множества пересекаются → круги пересекаются, общая область \(= A \cap B\).
- Если множества не пересекаются → круги раздельны.
- Пустые пересечения обычно не рисуются (в отличие от диаграмм Венн, где показываются все \(2^n\) возможные комбинации).
Пример
- \(A\) = студенты
- \(B\) = спортсмены
- \(C\) = преподаватели
Диаграмма:
- Круг \(A\) внутри круга всех людей (если нужно)
- Пересечение \(A \cap B\) = студенты-спортсмены
- \(C\) может пересекаться или быть отдельным кругом, в зависимости от задачи.
Связь с формулой включения–исключения
Круги Эйлера помогают визуализировать, откуда берётся формула:
- \(A \cup B = \text{область } A + \text{область } B - \text{пересечение } (A \cap B)\)
- Для трёх множеств: добавляются пересечения по тройкам и т.д.
Круги Эйлера — удобный инструмент для понимания и визуализации множеств и их отношений, особенно при применении правил объединения, пересечения и формулы включения–исключения.
Символы и их значения
| Символ | Читается как | Значение |
|---|---|---|
| \(\in\) | принадлежит | элемент принадлежит множеству |
| \(\notin\) | не принадлежит | элемент не принадлежит множеству |
| \(\subseteq\) | подмножество | все элементы \(A\) содержатся в \(B\) |
| \(\subset\) | строгое подмножество | \(A\) содержится в \(B\), но не равно \(B\) |
| \(\supseteq\) | надмножество | \(B\) содержит \(A\) |
| \(\cup\) | объединение | все элементы из обоих множеств |
| \(\cap\) | пересечение | общие элементы |
| \(\setminus\) | разность | элементы одного без другого |
| \(\triangle\) | симметрическая разность | элементы, принадлежащие только одному множеству |
| \(\overline{A}\) или \(A'\) | дополнение | всё, что не входит в \(A\) |
| \(\forall\) | для всех | “для любого элемента” |
| \(\exists\) | существует | “существует хотя бы один элемент” |
| \(\Rightarrow\) | влечёт | если …, то … |
| \(\Leftrightarrow\) | эквивалентно | равносильно |
| \(\mid\) | такое, что | используется в описаниях множеств: \(\{x \mid условие\}\) |
| \(\emptyset\) или \(\varnothing\) | пустое множество | множество без элементов |
| \(\aleph_0\) | алеф-нуль | мощность множества натуральных чисел |
| \(\mathfrak{c}\) | континуум | мощность множества вещественных чисел |