4.5: Деякі докази про набори

Щоб знайти докази, ви можете використовувати всі стратегії, які були корисними: робота назад, робота вперед, зміна того, що ви дивитеся, розбиваючи докази на випадки, і доказ протиріччя - все це важливо. Правила введення та усунення для квантіфікаторів просто додають деякі нові параметри, коли ви працюєте вперед або працюєте назад. Зокрема:

• Якщо у вас є\(\exists x, \mathcal{A}(x)\), ви, ймовірно, будете використовувати\(\exists\)\(\mathcal{A}(c)\) -elimination: припустимо для якоїсь літери,\(c\) яка ще не використовується, а потім виведіть висновок, який не містить\(c\).
• Якщо бажаний висновок є\(\forall x \in X,\mathcal{A}(x)\), то ваш доказ майже напевно базуватиметься на\(\forall\) -вступ, тому перші слова вашого доказу зазвичай будуть «Дано\(x \in X\),...»
• Якщо у вас є\(\forall x,\mathcal{A}(x)\), і це може бути корисно знати\(\mathcal{A}(c)\) (для деякої константи\(c\)), то ви можете використовувати\(\forall\) -elimination.

Наприклад, тепер, коли у нас є всі правила логіки першого порядку, ми можемо довести наступний важливий факт, який був заявлений далі.

Приклад\(4.5.1\).

Припустімо\(A\) і\(B\) є множинами. У нас є\(A = B\) якщо і тільки якщо\(A \subset B\) і\(B \subset A\).

Рішення

Доказ.

(\(\Rightarrow\)) Припустимо\(A = B\). Кожен набір є підмножиною себе (див. Зауваження\(3.2.20\)), тому ми маємо за\[A=B \subset B \quad \text { and } \quad B=A \subset A ,\] бажанням.

(\(\Leftarrow\)) Припустимо\(A \subset B\) і\(B \subset A\). Бажаємо показати\(A = B\); іншими словами, ми хочемо показати\[\forall x, (x \in A \eiff x \in B) .\]

\(x\)Дозволяти бути довільним.

(\(\Rightarrow\)) Припустимо\(x \in A\). Так як\(A \subset B\), це має на увазі\(x \in B\).

(\(\Leftarrow\)) Припустимо\(x \in B\). Так як\(B \subset A\), це має на увазі\(x \in A\).

Тому,\(x \in A \eiff x \in B\). Оскільки\(x\) є довільним, це має на увазі\(\forall x, (x \in A \eiff x \in B)\), за бажанням.

Приклад\(4.5.2\).

Припустимо\(A\)\(B\), і\(C\) є набори (і\(\univ\) є універсальним набором, як зазвичай). Потім:

1. \(A \cap B \subset A\).
2. \(A \subset A \cup B\).
3. \(A \cap \mathcal{U} =A\).
4. \(\text { If } A \subset B \text { and } B \subset C, \text { then } A \subset C \text {. }\)
5. \(A \cap B \subset A \cup B\).
6. \(\text { If } A \subset B \text { and } A \subset C, \text { then } A \subset B \cap C \text {. }\)

Рішення

Доказ.

1. Ми хочемо показати, що кожен елемент\(A \cap B\) є елементом\(A\). З огляду на\(x \in A \cap B\), ми знаємо, з визначення того\(A \cap B\), що\(x \in A\) і\(x \in B\). Зокрема\(x \in A\), за бажанням.
2. Ми хочемо показати, що кожен елемент\(A\) є елементом\(A \cup B\). Враховуючи\(x \in A\), очевидно, вірно, що\(x \in A\) або або\(x \in B\) (оскільки, насправді, ми знаємо\(x \in A\)). \(x \in A \cup B\)Тому за бажанням.
3. З 1., ми це знаємо\(A \cap \mathcal{U} \subset A\), тому достатньо, щоб показати це\(A \subset A \cap \mathcal{U}\). Враховуючи\(a \in A\), у нас, очевидно, є\(a \in A\). Крім того, оскільки універсальний набір\(\mathcal{U}\) містить кожен елемент, який знаходиться на розгляді, ми також маємо\(a \in \mathcal{U}\). Значить\(a \in A \cap \mathcal{U}\), за бажанням.
4. \(a\)Дозволяти бути довільним елементом\(A\). Так як\(A \subset B\), ми знаємо\(a \in B\). Тоді, тому що\(B \subset C\), ми знаємо\(a \in C\). Оскільки\(a\) є довільним елементом\(A\), це має на увазі\(A \subset C\).
5. Враховуючи\(x \in A \cap B\), ми знаємо\(x \in A\) і\(x \in B\). Зокрема, у нас є\(x \in A\), тому, безумовно, вірно, що\(x \in A\) або\(x \in B\). Тому\(x \in A \cup B\). Так як\(x\) є довільним елементом\(A \cap B\), це має на увазі\(A \cap B \subset A \cup B\), за бажанням.
   Альтернативний доказ 5.. З частин і, знаємо\(A \cap B \subset A\) і\(A \subset A \cup B\). Отже 4. має на увазі\(A \cap B \subset A \cup B\), що, за бажанням.
6. \(a\)Дозволяти бути довільним елементом\(A\). З тих пір\(A \subset B\), у нас є\(a \in B\). Аналогічно, з тих пір\(A \subset C\), у нас теж є\(a \in C\). Встановивши, що\(a \in B\) і\(a \in C\), робимо висновок, що\(a \in B \cap C\). Оскільки\(a\) є довільним елементом\(A\), це має на увазі\(A \subset B \cap C\).

Вправа\(4.5.3\).

Припустимо\(A\),\(B\), і\(C\) є множинами.

1. Покажіть, що якщо\(A \subset B\), то\(A \cap B = A\).
2. Покажіть\(A \subset B\), якщо, то\(A \cup B = B\).
3. Покажіть, що якщо\(B \subset C\), то\(A \cap B \subset A \cap C\).
4. Покажіть, що якщо\(A \subset C\) і\(B \subset C\), то\(A \cup B \subset C\).
5. Показати\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\).
6. Показати\(A \backslash B = A \backslash (A \cap B)\).
7. Нехай\(X = A \cap B\), і покаже\(A \cup B = (A \backslash X) \cup (B \backslash X) \cup X\).
8. Покажіть, що якщо\(\mathcal{P}(A \cup B) = \mathcal{P}(A) \cup \mathcal{P}(B)\), то або\(A \subset B\) або\(B \subset A\).

Вправа\(4.5.4\).

Припустимо\(A\) і\(B\) є множинами.

1. Показати\(A \backslash B = A \cap \bar{B}\).
2. Показати\(A = (A \backslash B) \cup (A \cap B)\).
3. Доведіть закони Де Моргана:
   1. \(\overline{\bar{A}}=A\).
   2. \(\overline{A \cap B}=\bar{A} \cup \bar{B}\).
   3. \(\overline{A \cup B}=\bar{A} \cap \bar{B}\).
4. Покажіть, що якщо\(\bar{A}=\bar{B}\), то\(A = B\).
   [Підказка: Відразу випливає з одного із законів ДеМорган.]

Вправа\(4.5.5\).

Припустимо\(A\),\(B\), і\(C\) є множинами.

1. Показати, що не\(A\) є відмінним від\(B\) якщо і тільки якщо\(A \subset \bar{B}\).
2. Шоу\(A \backslash B\) не зчленоване від\(B\).
3. Показати, що якщо не\(A\) з'єднаний з\(B\), і\(C\) є підмножиною\(B\), то\(A\) є нез'єднаним з\(C\).
4. Покажіть, що не\(A \backslash B\) є відмінним від\(A \cap B\).
5. Показати, що\(A\) є\(B \cup C\) нероз'єднаним від iff\(A\) є відмінним від обох\(B\) і\(C\).

Вправа\(4.5.6\).

1. Показати\(A \cup B = (A \backslash B) \cup (B \backslash A) \cup (A \cap B)\).
2. Покажіть три набори\(A \backslash B\)\(B \backslash A\), і всі\(A \cap B\) вони не з'єднані один від одного.

Нагадаємо, що\(A_{1},A_{2},\ldots,A_{n}\) множини є попарно-роз'єднаними, якщо\(A_{i}\) є нероз'єднаним від\(A_{j}\) кожного разу\(i \neq j\).

Вправа\(4.5.7\).

Припустимо\(A_{1},A_{2},\ldots,A_{n}\), множини попарно-нероз'єднані. Показати:

1. Набори\(A_{1},A_{2},\ldots,A_{n-1}\) попарно-нез'єднані, якщо\(n > 1\).
2. \(A_{n}\)від'єднується від\(A_{1} \cup A_{2} \cup \cdots \cup A_{n-1}\), якщо\(n > 1\).