A.7: Доказ протиріччям

Last updated

Oct 27, 2022
Save as PDF
- A.6: Інший приклад
- A.8: Читання доказів

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

У першому випадку доказ протиріччям - це шаблон висновку, який використовується для доведення негативних претензій. Припустимо, ви хочете показати, що якась претензія $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$ . ◻