5.S: Теорія множин (резюме)

Важливі визначення

• Рівні множини, сторінка 55
• Підмножина, сторінка 55
• Правильна підмножина, сторінка 218
• Комплекти живлення, сторінка 222
• Кардинальність скінченної множини, сторінка 223
• Перетин двох множин, сторінка 216
• Об'єднання двох комплектів, сторінка 216
• Набір різниці, сторінка 216
• Доповнення набору, сторінка 216
• Нероз'ємні набори, сторінка 236
• Декартовий добуток двох наборів, сторінки 256
• Замовлена пара, сторінка 256
• Союз над сім'єю наборів, сторінка 265
• Перетин над сімейством наборів, сторінка 265
• Набір індексації, сторінка 268
• Індексоване сімейство наборів, сторінка 268
• Союз над індексованим сімейством множин, сторінка 269
• Перетин над індексованим сімейством множин, сторінка 269
• Попарно нез'єднане сімейство наборів, сторінка 272

Важливі теореми та результати про множини

• Теорема 5.5. \(n\)Дозволяти невід'ємне ціле число і нехай\(A\) бути підмножиною якогось універсального множини. Якщо\(A\) є скінченною множиною з\(n\) елементами, то\(A\) має\(2^n\) підмножини. Тобто якщо\(|A| = n\), то\(|\mathcal{P}(A)| = 2^n\).
• Теорема 5.18. Дозволяти\(A\)\(B\), і\(C\) бути підмножини якогось універсального множини\(U\). Тоді всі наступні рівності дотримуються.
  
  Властивості порожньої множини\(A \cap \emptyset = \emptyset\)\(A \cap U = A\)
  та універсальної\(A \cup \emptyset = A\)\(A \cup U = U\)
  
  множини ідемпотентних законів \(A \cap A = A\)\(A \cup A = A\)
  
  Комутативні закони. \(A \cap B = B \cap A\)\(A \cup B = B \cup A\)
  
  Асоціативні закони\((A \cap B) \cap C = A \cap (B \cap C)\)
  \((A \cup B) \cup C = A \cup (B \cup C)\)
  
  розподільні закони\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
  \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
• Теорема 5.20. Дозволяти\(A\) і\(B\) бути підмножинами якогось універсального множини\(U\). Тоді вірно наступне:
  \[\begin{array} {ll} {\text{Basic Properties}} & & {(A^c)^c = A} \\ {} & & {A - B = A \cap B^c} \\ {\text{Empty Set, Universal Set}\ \ \ \ \ \ \ \ \ \ \ \ \ } & & {A - \emptyset = A \text{ and } A - U = \emptyset} \\ {} & & {\emptyset ^c = U \text{ and } U^c = \emptyset} \\ {\text{De Morgan's Laws}} & & {(A \cap B)^c = A^c \cup B^c} \\ {} & & {(A \cup B)^c = A^c \cap B^c} \\ {\text{Subsets and Complements}} & & {A \subseteq B \text{ if and only if } B^c \subseteq A^c.} \end{array}\]
• Теорема 5.25. Нехай\(A\)\(B\), і\(C\) бути набори. Потім
  
  1. \(A \times (B \cap C) = (A \times B) \cap (A \times C)\)
  2. \(A \times (B \cup C) = (A \times B) \cup (A \times C)\)
  3. \((A \cap B) \times C = (A \times C) \cap (B \times C)\)
  4. \((A \cup B) \times C = (A \times C) \cup (B \times C)\)
  5. \(A \times (B - C) = (A \times B) - (A \times C)\)
  6. \((A - B) \times C = (A \times C) - (B \times C)\)
  7. Якщо\(T \subseteq A\), то\(T \times B \subseteq A \times B\).
  8. Якщо\(T \subseteq B\), то\(A \times Y \subseteq A \times B\).
• Теорема 5.30. \(\Lambda\)Дозволяти бути непорожній набір індексації і нехай\(\mathcal{A} = \{A_{\alpha}\ |\ \alpha \in \Lambda\}\) бути індексованим сімейством множин. Потім
  
  1. Для кожного\(\beta \in \Lambda\),\(\bigcap_{\alpha \in \Lambda}^{} A_{\alpha} \subseteq A_{\beta}\).
  2. Для кожного\(\beta \in \Lambda\),\(A_{\beta} \subseteq \bigcap_{\alpha \in \Lambda}^{} A_{\alpha}\).
  3. \((\bigcap_{\alpha \in \Lambda}^{} A_{\alpha})^c = \bigcup_{\alpha \in \Lambda}^{} A_{\alpha} ^c\)
  4. \((\bigcup_{\alpha \in \Lambda}^{} A_{\alpha})^c = \bigcap_{\alpha \in \Lambda}^{} A_{\alpha} ^c\)
  
  Частини (3) і (4) відомі як закони Де Моргана.
• Теорема 5.31. \(\Lambda\)Дозволяти бути непорожній набір індексації, нехай\(\mathcal{A} = \{A_{\alpha}\ |\ \alpha \in \Lambda\}\) бути індексоване сімейство множин, і нехай\(B\) бути множиною. Потім
  
  1. \(B \cap (\bigcup_{\alpha \in \Lambda}^{} A_{\alpha}) = \bigcup_{\alpha \in \Lambda}^{} (B \cap A_{\alpha})\), і
  2. \(B \cup (\bigcap_{\alpha \in \Lambda}^{} A_{\alpha}) = \bigcap_{\alpha \in \Lambda}^{} (B \cup A_{\alpha})\),

Важливий метод доказування

Метод
Choose-an-element Метод choose-an-element часто використовується, коли ми стикаємося з універсальним квантором у твердженні в зворотному процесі доказу. Ця заява часто має вигляд

Для кожного елемента з заданою властивістю щось відбувається.

У прямому процесі доказу ми вибираємо довільний елемент із заданою властивістю.

Всякий раз, коли ми вибираємо довільний елемент із заданою властивістю, ми не вибираємо конкретний елемент. Швидше, єдине, що ми можемо припустити про елемент - це задане властивість.

Докладніші відомості див. на сторінці 232.