Кратко
- Множество – это совокупность различных объектов, называемых элементами, выделенных по какому-то признаку.
Пример: множество натуральных чисел $\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}$ | континуум | мощность множества вещественных чисел |