A.5: Приклад

Доказ. Ми хочемо показати, що для будь-яких наборів$A$$B$, і$C$,$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Спочатку ми розпаковуємо визначення «$=$» в висловлюванні пропозиції. Нагадаємо, що доводити множини ідентичні означає показувати, що множини мають однакові елементи. Тобто всі елементи також$A \cup (B \cap C)$ є елементами$(A \cup B) \cap (A \cup C)$, і навпаки. «Навпаки» означає, що також кожен елемент$(A \cup B) \cap (A \cup C)$ повинен бути елементом$A \cup (B \cap C)$. Таким чином, в розпакування визначення, ми бачимо, що ми повинні довести кон'юнкцію. Запишемо це:

За визначенням$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$, якщо кожен елемент також$A \cup (B \cap C)$ є елементом$(A \cup B) \cap (A \cup C)$, і кожен елемент$(A \cup B) \cap (A \cup C)$ є елементом$A \cup (B \cap C)$.

Оскільки це сполучник, ми повинні довести кожен кон'юнкт окремо. Почнемо з першого: доведемо, що кожен елемент також$A \cup (B \cap C)$ є елементом$(A \cup B) \cap (A \cup C)$.

Це універсальна претензія, і тому ми розглядаємо довільний елемент$A \cup (B \cap C)$ і покажемо, що він також повинен бути елементом$(A \cup B) \cap (A \cup C)$. Ми виберемо змінну для виклику цього довільного елемента, скажімо,$z$. Наше доказ триває:

По-перше, ми доведемо, що кожен елемент також$A \cup (B \cap C)$ є елементом$(A \cup B) \cap (A \cup C)$. Нехай$z \in A \cup (B \cap C)$. Ми маємо це показати$z \in (A \cup B) \cap (A \cup C)$.

Тепер настав час розпакувати визначення$\cup$ і$\cap$. Наприклад, визначення$\cup$ є:$A \cup B = \Setabs{z}{z \in A \text{ or } z \in B}$. Коли ми застосовуємо визначення до «»$A \cup (B \cap C)$, роль «$B$» у визначенні тепер грає «$B \cap C$,» так$A \cup (B \cap C) = \Setabs{z}{z \in A \text{ or } z \in B \cap C}$. Отже, наше припущення, що$z \in A \cup (B \cap C)$ становить:$z \in \Setabs{z}{z \in A \text{ or } z \in B \cap C}$. І якщо$z \in \Setabs{z}{\dots z\dots}$...$z$..., тобто в даному випадку,$z \in A$ або$z \in B \cap C$.

За визначенням$\cup$, або$z \in A$ або$z \in B \cap C$.

Так як це диз'юнкція, корисно буде застосовувати докази за випадками. Ми беремо два випадки і показуємо, що в кожному з них виходить висновок, до якого ми прагнемо (а саме «$z \in (A \cup B) \cap (A \cup C)$»).

Випадок 1: Припустимо, що$z \in A$.

На основі наших припущень працювати не набагато більше. Отже, давайте розглянемо, з чим нам доведеться працювати в висновку. Ми хочемо це показати$z \in (A \cup B) \cap (A \cup C)$. Виходячи з визначення$\cap$, якщо ми хочемо показати$z \in (A \cup B) \cap (A \cup C)$, що, ми повинні показати, що це в обох$(A \cup B)$ і$(A \cup C)$. Але$z \in A \cup B$ якщо$z \in A$ або$z \in B$, і у нас вже є (як припущення випадку 1) що$z \in A$. З тієї ж міркування—перемикання$C$ на$B$ -$z \in A \cup C$. Цей аргумент пішов у зворотному напрямку, тому давайте запишемо наші міркування в напрямку, необхідному в нашому доказі.

Так як$z \in A$,$z \in A$ або$z \in B$, а значить, за визначенням$\cup$,$z \in A \cup B$. Аналогічно,$z \in A \cup C$. Але це означає$z \in (A \cup B) \cap (A \cup C)$, що, за визначенням$\cap$.

На цьому закінчується перший випадок доказу по справах. Тепер ми хочемо вивести висновок у другому випадку, де$z \in B \cap C$.

Випадок 2: Припустимо, що$z \in B \cap C$.

Знову працюємо з перетином двох наборів. Давайте застосуємо визначення$\cap$:

Так як$z \in B \cap C$,$z$ повинен бути елементом обох$B$ і$C$, за визначенням$\cap$.

Настав час знову подивитися на наш висновок. Ми повинні показати, що$z$ є в обох$(A \cup B)$ і$(A \cup C)$. І знову ж таки, рішення негайне.

З тих пір$z \in B$,$z \in (A \cup B)$. Так як$z \in C$, також$z \in (A \cup C)$. Отже,$z \in (A \cup B) \cap (A \cup C)$.

Тут ми застосували визначення$\cup$ і$\cap$ знову, але оскільки ми вже згадували ці визначення, і вже показали, що якщо$z$ в одному з двох наборів це в їхньому союзі, ми не повинні бути настільки явними в тому, що ми зробили.

Ми завершили другий випадок доказу за випадками, тому тепер можемо стверджувати наш перший висновок.

Отже, якщо$z \in A \cup (B \cap C)$ тоді$z \in (A \cup B) \cap (A \cup C)$.

Тепер ми просто хочемо, щоб показати інший напрямок, що кожен елемент$(A \cup B) \cap (A \cup C)$ є елементом$A \cup (B \cap C)$. Як і раніше, ми доводимо це універсальне твердження, припускаючи, що ми маємо довільний елемент першого множини і показуємо, що він повинен бути у другому наборі. Давайте заявимо, що ми збираємося зробити.

Тепер припустимо, що$z \in (A \cup B) \cap (A \cup C)$. Ми хочемо це показати$z \in A \cup (B \cap C)$.

Зараз ми працюємо з гіпотезою про те, що$z \in (A \cup B) \cap (A \cup C)$. Сподіваюся, не надто заплутано, що ми використовуємо те ж саме$z$ тут, як і в першій частині доказу. Коли ми закінчили цю частину, всі припущення, які ми зробили, більше не діють, тому тепер ми можемо робити нові припущення про те, що$z$ є. Якщо це збиває$z$ з пантелику, просто замініть на іншу змінну в наступному.

Ми знаємо, що$z$ є в обох$A \cup B$ і$A \cup C$, за визначенням$\cap$. І за визначенням$\cup$, ми можемо додатково розпакувати це до: або$z \in A$ або$z \in B$, а також або$z \in A$ або$z \in C$. Це виглядає як доказ випадків знову - за винятком «і» робить це заплутаним. Ви можете подумати, що це становить три можливості:$z$ є або в$A$,$B$ або$C$. Але це було б помилкою. Ми повинні бути обережними, тому розглянемо кожну диз'юнкцію по черзі.

За визначенням$\cap$,$z \in A \cup B$ і$z \in A \cup C$. За визначенням$\cup$,$z \in A$ або$z \in B$. Розрізняємо випадки.

Оскільки ми зосереджуємося на першій диз'юнкції, ми ще не отримали нашу другу диз'юнкцію (від розпакування$A \cup C$). Насправді, нам це ще не потрібно. Перший випадок$z \in A$, і елемент множини також є елементом об'єднання цієї множини з будь-яким іншим. Отже, випадок 1 простий:

Випадок 1: Припустимо, що$z \in A$. З цього випливає$z \in A \cup (B \cap C)$.

Тепер для другого випадку,$z \in B$. Тут ми розпакуємо другий$\cup$ і зробимо ще одне підтвердження за випадками:

Випадок 2: Припустимо, що$z \in B$. З тих пір$z \in A \cup C$, або$z \in A$ або$z \in C$. Розрізняємо випадки далі:

Випадок 2а:$z \in A$. Потім, знову ж таки,$z \in A \cup (B \cap C)$.

Гаразд, це було трохи дивно. Ми насправді не потрібно припущення, що$z \in B$ для цього випадку, але це нормально.

Випадок 2b:$z \in C$. Потім$z \in B$ і$z \in C$, так$z \in B \cap C$, а отже,$z \in A \cup (B \cap C)$.

На цьому завершуються обидва докази за випадками, і тому ми закінчили з другою половиною.

Отже, якщо$z \in (A \cup B) \cap (A \cup C)$ тоді$z \in A \cup (B \cap C)$. ◻