A.6: Інший приклад

Доказ. Припустимо, що$A \subseteq C$. Ми хочемо це показати$A \cup (C \setminus A) = C$.

Почнемо з того, що спостерігаємо, що це умовний оператор. Це мовчазно універсально кількісно: пропозиція тримається для всіх наборів$A$ і$C$. Так$A$ і$C$ є змінними для довільних множин. Щоб довести таке твердження, ми припускаємо попереднє і доведемо наслідок.

Продовжуємо, використовуючи припущення, що$A \subseteq C$. Розпакуємо визначення$\subseteq$: припущення означає, що всі елементи також$A$ є елементами$C$. Давайте запишемо це - це важливий факт, який ми будемо використовувати протягом усього доказу.

За визначенням$\subseteq$, так як$A \subseteq C$, для всіх$z$, якщо$z \in A$, то$z \in C$.

Ми розпакували всі визначення, які даються нам у припущенні. Тепер можна переходити до висновку. Ми хочемо показати$A \cup (C \setminus A) = C$, що, і тому ми створили доказ аналогічно останньому прикладі: ми показуємо, що кожен елемент також$A \cup (C \setminus A)$ є елементом$C$ і, навпаки, кожен елемент$C$ є елементом$A \cup (C \setminus A)$. Ми можемо скоротити це до:$A \cup (C \setminus A) \subseteq C$ і$C \subseteq A \cup (C \setminus A)$. (Тут ми робимо протилежне розпакування визначення, але це робить доказ трохи легше читати.) Оскільки це кон'юнкція, ми повинні довести обидві частини. Щоб показати першу частину, тобто, що кожен елемент також$A \cup (C \setminus A)$ є елементом$C$, ми припускаємо, що$z \in A \cup (C \setminus A)$ для довільного$z$ і показати, що$z \in C$. За визначенням$\cup$, можна зробити висновок, що$z \in A$ або$z \in C \setminus A$ з$z \in A \cup (C \setminus A)$. Тепер ви повинні отримати повісити це.

$A \cup (C \setminus A) = C$іфф$A \cup (C \setminus A) \subseteq C$ і$C \subseteq (A \cup (C \setminus A)$. Спочатку доведемо це$A \cup (C \setminus A) \subseteq C$. Нехай$z \in A \cup (C \setminus A)$. Отже, або$z \in A$ або$z \in (C \setminus A)$.

Ми дійшли до диз'юнкції, і з неї ми хочемо це довести$z \in C$. Робимо це, використовуючи докази випадками.

Випадок 1:$z \in A$. Оскільки для всіх$z$, якщо$z \in A$$z \in C$, ми маємо це$z \in C$.

Тут ми використали факт, записаний раніше, який випливав з гіпотези про те, що$A \subseteq C$. Перший випадок завершений, і переходимо до другого випадку,$z \in (C \setminus A)$. Нагадаємо, що$C \setminus A$ позначає різницю двох множин, тобто безліч всіх елементів$C$ яких не є елементами$A$. Але будь-який елемент$C$ не в$A$ є особливим елементом$C$.

Випадок 2:$z \in (C \setminus A)$. Це означає, що$z \in C$ і$z \notin A$. Так, зокрема,$z \in C$.

Чудово, ми довели перший напрямок. Тепер до другого напрямку. Тут ми це доведемо$C \subseteq A \cup (C \setminus A)$. Таким чином, ми припускаємо, що$z \in C$ і довести це$z \in A \cup (C \setminus A)$.

Тепер давайте$z \in C$. Ми хочемо показати, що$z \in A$ або$z \in C \setminus A$.

Оскільки всі елементи також$A$ є елементами$C$, і$C \setminus A$ є сукупністю всіх речей, які є елементами,$C$ але ні$A$, випливає, що$z$ є$A$ або в $C \setminus A$. Це може бути трохи незрозуміло, якщо ви ще не знаєте, чому результат вірний. Краще було б довести це поетапно. Це допоможе використовувати простий факт, який ми можемо заявити без доказів:$z \in A$ або$z \notin A$. Це називається «принципом виключеної середини:» для будь-якого твердження або$p$ істинно$p$, або його заперечення вірно. (Ось твердження,$p$ що$z \in A$.) Оскільки це диз'юнкція, ми можемо знову використовувати proof-by-cases.

Або$z \in A$ або$z \notin A$. У першому випадку,$z \in A \cup (C \setminus A)$. В останньому випадку$z \in C$ і$z \notin A$, так$z \in C \setminus A$. Але потім$z \in A \cup (C \setminus A)$.

Наш доказ повний: ми це показали$A \cup (C \setminus A) = C$.

◻