A.7: Доказ протиріччям
- Page ID
- 52850
У першому випадку доказ протиріччям - це шаблон висновку, який використовується для доведення негативних претензій. Припустимо, ви хочете показати, що якась претензія\(p\) є помилковою, тобто ви хочете показати\(\lnot p\). Найбільш перспективною стратегією є (а) припустити, що\(p\) це правда, і (б) показати, що це припущення призводить до того, що ви знаєте, є помилковим. «Щось, як відомо, є помилковим» може бути результатом, який конфліктує з\(p\) самим собою або якоюсь іншою гіпотезою загальної заяви, яку ви розглядаєте. Наприклад, доказ «якщо\(q\) тоді\(\lnot p\)» передбачає припущення, що\(q\) це правда і доказ\(\lnot p\) з цього. Якщо ви\(\lnot p\) доведете протиріччя, це означає припущення на\(p\) додаток до\(q\). Якщо ви можете довести\(\lnot q\)\(p\), ви показали, що припущення\(p\) призводить до чогось, що суперечить іншому вашому припущенню\(q\), оскільки\(q\) і\(\lnot q\) не може бути правдою. Звичайно, ви повинні використовувати інші шаблони висновків у вашому доказі протиріччя, а також розпакування визначень. Розглянемо приклад.
Пропозиція\(\PageIndex{1}\)
Якщо\(A \subseteq B\) і\(B = \emptyset\), то не\(A\) має елементів.
Доказ. Припустимо\(A \subseteq B\), і\(B = \emptyset\). Ми хочемо показати, що не\(A\) має елементів.
Оскільки це умовна претензія, ми припускаємо попереднє і хочемо довести наслідок. Наслідком є: не\(A\) має елементів. Ми можемо зробити це трохи більш виразним: це не так, що існує\(x \in A\).
\(A\)не має елементів, якщо це не так, що є\(x\) таке\(x \in A\).
Отже, ми визначили, що те, що ми хочемо довести\(\lnot p\), насправді є негативним твердженням, а саме: це не так, що існує\(x \in A\). Щоб використовувати доказ протиріччям, ми повинні прийняти відповідне позитивне твердження\(p\), тобто є\(x \in A\), і довести протиріччя з нього. Ми вказуємо, що ми робимо доказ протиріччям, пишемо «шляхом протиріччя, припускаємо» або навіть просто «не припускаємо», а потім висловлюємо припущення\(p\).
Припустимо, що ні: є\(x \in A\).
Це тепер нове припущення, яке ми будемо використовувати для отримання протиріччя. У нас є ще два припущення: те\(A \subseteq B\) і те\(B = \emptyset\). Перший дає нам, що\(x \in B\):
З тих пір\(A \subseteq B\),\(x \in B\).
Але оскільки\(B = \emptyset\), кожен елемент\(B\) (наприклад,\(x\)) також повинен бути елементом\(\emptyset\).
З тих пір\(B = \emptyset\),\(x \in \emptyset\). Це протиріччя, так як за визначенням не\(\emptyset\) має елементів.
Це вже завершує доказ: ми прийшли до того, що нам потрібно (протиріччя) з припущень, які ми створили, і це означає, що припущення не можуть бути правдивими. Оскільки перші два припущення (\(A \subseteq B\)і\(B = \emptyset\)) не оскаржуються, це повинно бути останнє введене припущення (є\(x \in A\)), яке повинно бути помилковим. Але якщо ми хочемо бути ретельними, ми можемо це викласти.
Таким чином, наше припущення про те, що\(x \in A\) має бути помилковим, отже, не\(A\) має елементів шляхом доказу протиріччям. ◻
Кожна позитивна претензія тривіально еквівалентна негативній претензії:\(p\) iff\(\lnot\lnot p\). Тож докази протиріччя також можуть бути використані для встановлення позитивних претензій «побічно», а саме: Щоб довести\(p\), читайте це як негативну претензію\(\lnot\lnot p\). Якщо ми можемо довести протиріччя від\(\lnot p\), ми встановили\(\lnot\lnot p\) доказом протиріччя, а отже\(p\).
В останньому прикладі ми мали на меті довести негативну претензію, а саме те, що не\(A\) має елементів, і тому припущення, яке ми зробили з метою доказу протиріччям (тобто, що є\(x \in A\)), було позитивним претензією. Це дало нам щось працювати, а саме гіпотетичне,\(x \in A\) про яке ми продовжували міркувати, поки не дісталися\(x \in \emptyset\).
При доведенні позитивної заяви опосередковано, припущення, яке ви зробите з метою доказу протиріччя, буде негативним. Але дуже часто можна легко переформулювати позитивну претензію як негативну претензію, а негативну - як позитивну. Наші попередні докази були б по суті такими ж, якби ми довели «\(A = \emptyset\)» замість негативного наслідку «не\(A\) має елементів». (За визначенням\(=\), «\(A = \emptyset\)» є загальним твердженням, оскільки воно розпаковується до «кожен елемент\(A\) є елементом\(\emptyset\) і навпаки».) Але це легко помітити, щоб бути еквівалентним негативному твердженню «ні: є»\(x \in A\).
Тому іноді простіше працювати\(\lnot p\) як з припущенням, ніж доводити\(p\) безпосередньо. Навіть коли прямий доказ настільки ж простий або навіть простіший (як у наступному прикладі), деякі люди вважають за краще діяти побічно. Якщо подвійне заперечення вас бентежить, подумайте про доказ протиріччя якоїсь претензії як доказ протиріччя з протилежного позову. Отже, доказ протиріччям\(\lnot p\) є доказом протиріччя з припущення\(p\); а доказ протиріччям\(p\) - доказ протиріччя з\(\lnot p\).
Пропозиція\(\PageIndex{2}\)
\(A \subseteq A \cup B\).
Доказ. Ми хочемо це показати\(A \subseteq A \cup B\).
На перший погляд, це позитивне твердження: кожен\(x \in A\) теж в\(A \cup B\). Заперечення того, що таке: деякі\(x \in A\) є\(\notin A \cup B\). Таким чином, ми можемо довести претензію побічно, припускаючи це заперечене твердження, і показуючи, що це призводить до протиріччя.
Припустимо, ні, т\(A \nsubseteq A \cup B\).
У нас є визначення\(A \subseteq A \cup B\): кожен теж\(x \in A\) є\(\in A \cup B\). Щоб зрозуміти, що\(A \nsubseteq A \cup B\) означає, ми повинні використовувати деякі елементарні логічні маніпуляції з розпакованим визначенням: помилково, що кожен також\(x \in A\)\(\in A \cup B\) є, якщо є таке\(x \in A\), що є\(\notin C\). (Це місце, де ви хочете бути дуже обережними: багато студентів спроби доказів протиріччя зазнають невдачі, оскільки вони неправильно аналізують заперечення претензії на кшталт «всі\(A\)\(B\) s є s».) Іншими словами,\(A \nsubseteq A \cup B\) якщо є\(x\) таке, що\(x \in A\) і\(x \notin A \cup B\). З цього моменту це легко.
Отже, є\(x \in A\) таке, що\(x \notin A \cup B\). За визначенням\(\cup\),\(x \in A \cup B\) якщо\(x \in A\) або\(x \in B\). З тих пір\(x \in A\), у нас є\(x \in A \cup B\). Це суперечить припущенню, що\(x \notin A \cup B\). ◻
Проблема\(\PageIndex{1}\)
Доведіть побічно, що\(A \cap B \subseteq A\).
Пропозиція\(\PageIndex{3}\)
Якщо\(A \subseteq B\) і\(B \subseteq C\) тоді\(A \subseteq C\).
Доказ. Припустимо\(A \subseteq B\), і\(B \subseteq C\). Ми хочемо показати\(A \subseteq C\).
Давайте приступимо побічно: припускаємо заперечення того, що ми хочемо встановити.
Припустимо, ні, т\(A \nsubseteq C\).
Як і раніше, ми\(A \nsubseteq C\) міркуємо, що якщо не кожен\(x \in A\) є також\(\in C\), тобто деякі\(x \in A\) є\(\notin C\). Не хвилюйтеся, з практикою вам не доведеться більше думати, щоб розпакувати такі заперечення.
Іншими словами, є\(x\) таке, що\(x \in A\) і\(x \notin C\).
Тепер ми можемо використати це, щоб дійти до нашого протиріччя. Звичайно, нам доведеться використовувати два інших припущення, щоб зробити це.
З тих пір\(A \subseteq B\),\(x \in B\). З тих пір\(B \subseteq C\),\(x \in C\). Але це суперечить\(x \notin C\). ◻
Пропозиція\(\PageIndex{4}\)
Якщо\(A \cup B = A \cap B\) тоді\(A = B\).
Доказ. Припустимо\(A \cup B = A \cap B\). Ми хочемо це показати\(A = B\).
Початок зараз рутинний:
Припустимо, шляхом протиріччя, що\(A \neq B\).
Наше припущення для доказу протиріччям полягає в тому, що\(A \neq B\). Так як\(A = B\) якщо\(A \subseteq B\) може\(B \subseteq A\), ми отримуємо, що\(A \neq B\) iff\(A \nsubseteq B\) або\(B \nsubseteq A\). (Зверніть увагу, наскільки важливо бути обережним при маніпулюванні запереченнями!) Щоб довести протиріччя від цієї диз'юнкції, ми використовуємо доказ за випадками і показуємо, що в кожному конкретному випадку випливає протиріччя.
\(A \neq B\)Вимкніть\(A \nsubseteq B\) або\(B \nsubseteq A\). Розрізняємо випадки.
У першому випадку припускаємо\(A \nsubseteq B\), тобто для деяких\(x\),\(x \in A\) але\(\notin B\). \(A \cap B\)визначається як ті елементи, які\(A\) і\(B\) мають спільне, так що якщо щось не в одному з них, це не в перетині. \(A \cup B\)є\(A\) разом з\(B\), так що все в будь-якому також є в союзі. Це говорить нам про те\(x \notin A \cap B\),\(x \in A \cup B\) але, і, отже, що\(A \cap B \neq B \cap A\).
Випадок 1:\(A \nsubseteq B\). Тоді для деяких\(x\),\(x \in A\) але\(x \notin B\). З тих пір\(x \notin B\)\(x \notin A \cap B\). З тих пір\(x \in A\),\(x \in A \cup B\). Отже\(A \cap B \neq B \cap A\), суперечить припущенню, що\(A \cap B = A \cup B\).
Випадок 2:\(B \nsubseteq A\). Тоді для деяких\(y\),\(y \in B\) але\(y \notin A\). Як і раніше, у нас є\(y \in A \cup B\) але\(y \notin A \cap B\), і так\(A \cap B \neq A \cup B\), знову суперечить\(A \cap B = A \cup B\). ◻