Теория множеств

Содержание

• Обозначение

• Принадлежность множеству

• Пустое множество

• Мощность множества

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

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

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

• Разбиение множества

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

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

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

Обозначение

$$\large A=\{ x~\vert~ P(x) \}$$

$A$ — множество таких $x$, для которых верно утверждение $P(x)$.

---

Принадлежность множеству

Если $x$ является элементом множества $A$, то

$$\large x \in A$$

Если $x$ не является элементом множества $A$, то

$$\large x \notin A$$

---

Пустое множество

Обозначение

$\varnothing$ — пустое множество.

Определение

$\varnothing$ — множество, не содержащее ни одного элемента.

---

Мощность множества

Обозначение

$|A|$ — мощность множества $A$.

Неформальное определение

$|A|$ — количество элементов множества $A$.

---

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

Определение

$A\subset B$ — означает, что любой элемент множества $A$ принадлежит множеству $B$.

Множество всех подмножеств

Обозначение

$2^A$ — множество всех подмножеств множества $A$.

Свойство

$$\large \left|2^A\right|=2^{|A|}$$

---

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

Обозначение

$A\cap B$ — пересечение множеств $A$ и $B$.

Определение

$A \cap B$ — множество $\{ x~\vert~x \in A \land x \in B \}$.

Пересекаемых множеств может быть любое количество.

Свойства

1. $A\cap A=A$;

2. $A\cap \varnothing =\varnothing$;

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

---

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

Обозначение

$A\cup B$ — объединение множеств $A$ и $B$.

Определение

$A\cup B$ — множество $\{x~\vert~ x \in A \vee x\in B\}$.

Объединяемых множеств может быть любое количество.

Свойства

1. $A\cup A=A$;

2. $A\cup \varnothing=A$;

3. $A\cup B\cup C=(A\cup B)\cup C = A\cup (B\cup C)$;

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

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

Для двух множеств

$$\large |A\cup B|=|A|+|B|-|A\cap B|$$

Для трёх множеств

$$\large |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+ |A\cap B\cap C|$$

---

Разбиение множества

$\{A_1,A_2,\ldots,A_n\}$ — разбиение множества $A$, если $A=A_1\cup A_2\cup \ldots\cup A_n$ и $A_i \cap A_j=\varnothing$ для всех $i\ne j$.

---

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

Обозначение

$A \backslash B$ — разность множеств $A$ и $B$.

Определение

$A \backslash B$ — множество $\{x~\vert~ x \in A \land x \notin B\}$.

---

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

Обозначение

$\overline{A}$ — дополнение множества $A$.

Определение

$\overline{A}$ — множество $X\backslash A$, где $X$ — множество всех элементов рассматриваемого пространства.

Свойства

1. $A\cup \overline{A}=X$;

2. $A\cap \overline{A}=\varnothing$;

3. $\overline{X}=\varnothing;$

4. $\overline{\overline{A}}=A$;

5. $\overline{A\cap B}=\overline{A} \cup \overline{B}$;

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

Свойства 5 и 6 называются законы де Моргана. В них может быть произвольное количество множеств.

---

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

Обозначение

$A\times B$ — прямое произведение множеств $A$ и $B$.

Определение

$A\times B$ — множество $\{ (x,y)~\vert~ x\in A \land y\in B \}$.

Множеств в прямом произведении может быть произвольное количество.

Свойство

$$\large |A\times B|=|A|\cdot |B|$$