3.3: Непрямі докази - протиріччя та протиставлення
- Page ID
- 64828
Припустимо, ми намагаємося довести, що всі тремтіння поліциклічні 1. Прямим доказом цього може бути пошук визначення того, що означає бути тріскою, і того, що це означає бути поліциклічним, і якимось чином розпізнавання способу перетворення будь-якого логічного еквівалента трекла в логічний еквівалент поліциклічного. Як це трапляється досить часто, очевидного способу виконання цього завдання може не бути. Непрямий доказ приймає зовсім іншу прихватку. Припустимо, у вас була тріска, яка не була поліциклічною, і, крім того, показати, що це припущення призводить до чогось справді неможливого. Ну а якщо не можна, щоб трекіл не був поліциклічним, то повинно бути так, що всі вони є. Такий аргумент відомий як доказ протиріччям.
Цілком можливо, найсолодшим непрямим доказом, відомим є доказ Евкліда, що існує нескінченна кількість простих чисел.
(Евклід) Безліч усіх простих чисел нескінченна.
- Доказ
-
Припустимо, навпаки, що існує лише кінцева кількість простих чисел. Цей скінченний набір простих чисел може, в принципі, перераховуватися в порядку зростання.
\ (\ {p_1, p_2, p_3,., p_n\})
Розглянемо число,\(N\) утворене шляхом додавання\(1\) до добутку всіх цих простих чисел.
\(N = 1 + \prod_{k=1}^{n} p_k \)
Зрозуміло,\(N\) що набагато більше, ніж найбільший\(p_n\) простий, тому\(N\) не може бути самим простим числом. Таким чином,\(N\) повинен бути добуток деяких простих чисел у списку. Припустимо, що\(p_j\) це один з простих чисел, який ділить\(N\). Тепер зверніть увагу, що, по будівництву, залишив\(N\) би залишок\(1\) при поділі на\(p_j\). Це протиріччя, оскільки ми не можемо мати обох\(p_j |N\) і\(p_j ∤ N\).
Оскільки припущення, що простих чисел існує лише скінченно багато, призводить до протиріччя, дійсно має бути нескінченна кількість простих чисел.
Q.E.D.
Якщо ви працюєте над доведенням UCS і прямий підхід, здається, не вдається, ви можете виявити, що інший непрямий підхід, доказ протиставлення, зробить трюк. В одному сенсі ця техніка доказів насправді не є такою непрямою; те, що робиться, - це визначити контрапозитив оригінального умовного, а потім довести це безпосередньо. В іншому сенсі цей метод є непрямим, оскільки доказ протиставлення зазвичай може бути перероблений як доказ протиріччя досить легко.
Найпростіший доказ, який я знаю про використання методу контрапозиції (і, можливо, найприємніший приклад цієї техніки) є доказом леми, яку ми заявили в розділі 1.6 в ході доведення, що це не\(\sqrt{2}\) було раціональним. Якщо ви забули, нам потрібен був той факт,\(x^2\) що коли - парне число, так і є\(x\).
Давайте спочатку фразовуємо це як UCS.
\(∀x ∈ \mathbb{Z}, x^2 \text{ even } \implies x \text{ even}\)
Можливо, ви намагалися довести цей результат раніше. Якщо так, ви, напевно, зіткнулися з концептуальною проблемою, з якою все, що вам потрібно працювати, - це рівність\(x^2\) якої не дає вам багато боєприпасів, намагаючись показати,\(x\) що навіть. Контрапозитивом цього твердження є:
\(∀x ∈ \mathbb{Z}, x \text{ not even } \implies x^2 \text{ not even }\)
Тепер, оскільки\(x\) і\(x^2\) є цілими числами, існує лише одна альтернатива бути парним - тому ми можемо повторно висловити контрапозитивне як
\(∀x ∈ \mathbb{Z}, x \text{ odd } \implies x^2 \text{ odd }.\)
Без зайвих прихильностей, ось доказ:
\[∀x ∈ \mathbb{Z}, x^2 \text{ even } \implies x \text{ even }\]
- Доказ
-
Це твердження логічно еквівалентно
\(∀x ∈ \mathbb{Z}, x \text{ odd } \implies x^2 \text{ odd }\)
тому ми доведемо, що замість цього.
Припустимо, що\(x\) це конкретне, але довільно вибране ціле число таке, що\(x\) є непарним. Оскільки\(x\) непарна, існує ціле число\(k\) таке, що\(x = 2k + 1\). Звідси випливає, що\(x^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\). Нарешті, ми бачимо, що\(x^2\) має бути непарним, тому що він має форму\(2m + 1\), де\(m = 2k^2 + 2k\) явно ціле число.
Q.E.D.
Основна проблема при застосуванні методу доказування протиріччям полягає в тому, що він зазвичай передбачає «кмітливість». Ви повинні придумати якусь причину, чому презумпція про те, що теорема є помилковою, призводить до протиріччя - і це може бути очевидним, а може і не бути. Більше, ніж будь-яка інша техніка доказу, доказ протиріччям вимагає, щоб ми використовували чернетки та рерайтинг. Після того, як мавпи навколо достатньо, щоб ми знайшли спосіб досягти протиріччя, нам потрібно повернутися до початку доказу і виділити особливість, яку ми врешті-решт суперечимо! Зрештою, ми хочемо, щоб це виглядало так, ніби наші докази абсолютно чіткі, лаконічні та розумні, навіть якщо їх формулювання викликало у нас якусь душевну муку на рівні Гордіана.
Ми закінчимо цей розділ прикладом з Geometry.
Серед всіх трикутників, вписаних в нерухоме коло, рівносторонній є той, що має максимальну площу.
- Доказ
-
Будемо діяти протиріччям. Припустимо навпаки, що існує трикутник, вписаний в коло\(\triangle ABC\), що має максимальну площу, яка не є рівносторонньою. Так як\(\triangle ABC\) не рівносторонній, є дві його сторони, які не рівні. Без втрати спільності припустимо, що сторони\(\overline{AB}\) і\(\overline{BC}\) мають різну довжину. Залишилася сторона (\(\overline{AC}\)) вважаємо основою цього трикутника. Ми можемо побудувати інший трикутник\(\triangle AB'C\), також вписаний у наше коло, а також має\(\overline{AC}\) як його основу, що має більшу висоту, ніж\(\triangle ABC\) - оскільки площа трикутника\(b\) задається формулою\(\dfrac{bh}{2}\) (де основа, і\(h\) висота), цей трикутник площа, очевидно, більше, ніж у\(\triangle ABC\). Це протиріччя, оскільки\(\triangle ABC\) передбачалося, що має максимальну площу.
Ми залишаємо власне будівництво\(\triangle AB'C\) на наступну вправу.
Q.E.D.
Де ми повинні розмістити точку,\(B'\) щоб створити трикутник,\(\triangle AB'C \) що має більшу площу, ніж будь-який трикутник, наприклад\(\triangle ABC \), який не є рівнобедреним?
Вправи:
Доведіть, що якщо куб ціле непарне число, то це ціле непарне.
Доведіть, що всякий раз, коли простий\(p\) не ділить квадрат цілого числа, він також не ділить вихідне ціле число. \((p ∤ x^2 \implies p ∤ x)\)
Доведіть (протиріччям), що немає найбільшого цілого числа.
Доведіть (протиріччям), що не існує найменшого позитивного дійсного числа.
Довести (протиріччям), що сума раціонального і ірраціонального числа є ірраціональною.
Довести (шляхом контрапозиції), що для всіх цілих чисел\(x\) і\(y\), якщо\(x + y\) непарно, то\(x \neq y\).
Доведіть (шляхом протиставлення), що для всіх дійсних чисел\(a\) і\(b\), якщо\(ab\) є ірраціональним, то\(a\) є ірраціональним або\(b\) ірраціональним.
Піфагорійська трійка - це набір з трьох натуральних чисел\(a\),\(b\) і\(c\), такі, що\(a^2 + b^2 = c^2\). Доведіть, що в піфагорійській трійці, принаймні один з\(a\) і\(b\) є парним. Використовуйте або доказ протиріччя, або доказ протиставлення.
Припустимо, у вас є\(2\) пари позитивних дійсних чисел, чиї продукти є\(1\). Тобто у вас є\((a, b)\) і\((c, d)\) в\(\mathbb{R}^2\) задоволенні\(ab = cd = 1\). Доведіть, що a < c означає, що\(b > d\).