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)\). ◻