1.8: Скорочення та абсурд

Last updated
Save as PDF

Page ID: 51538

Craig DeLancey
SUNY Oswego via OpenSUNY

\( \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}}\)

8. Скорочення та абсурд

8.1 Історичний приклад

У своїй книзі «Дві нові науки» ^[10] Галілео Галілея (1564-1642) наводить кілька аргументів, покликаних продемонструвати, що не може бути такого поняття, як фактичні нескінченності чи фактичні нескінченності. Один з його аргументів можна перебудувати наступним чином. Галілей пропонує прийняти як передумову, що існує фактична нескінченність натуральних чисел (натуральні числа - це позитивні цілі числа з 1 на):

{1, 2, 3, 4, 5, 6, 7,...}

Він також пропонує прийняти як передумову, що існує фактична нескінченність квадратів натуральних чисел.

{1, 4, 9, 16, 25, 36, 49,...}

Тепер, Галілео причини, зауважте, що ці дві групи (сьогодні ми б назвали їх «набори») мають однаковий розмір. Ми бачимо це, тому що бачимо, що між двома групами існує відповідність один до одного.

{1,	2,	3,	4,	5,	6,	7,...}

{1,	4,	9,	16,	25,	36,	49,...}

Якщо ми можемо пов'язати кожне натуральне число з одним і тільки одним квадратним числом, і якщо ми можемо пов'язати кожне квадратне число з одним і тільки одним натуральним числом, то ці набори повинні бути однакового розміру.

Але зачекайте хвилинку, каже Галілей. Є, очевидно, дуже багато більше натуральних чисел, ніж квадратних чисел. Тобто кожне квадратне число знаходиться в списку натуральних чисел, але багатьох натуральних чисел немає в списку квадратних чисел. Наступні числа є у списку натуральних чисел, але не в списку квадратних чисел.

{2, 3, 5, 6, 7, 8, 10,...}

Отже, Галілей міркує, якщо в групі натуральних чисел багато чисел, які не входять в групу квадратних чисел, і якщо в групі квадратних чисел немає чисел, яких немає в натуральних числах, то натуральні числа більше квадратних. І якщо група натуральних чисел більше, ніж група квадратних чисел, то натуральні числа і квадратні числа не однакового розміру.

Ми дійшли двох висновків: множина натуральних чисел і набір квадратних чисел однакового розміру; і, набір натуральних чисел і набір квадратних чисел не однакового розміру. Це суперечливо.

Галілей стверджує, що причина, по якій ми досягли протиріччя, полягає в тому, що ми припускали, що існують фактичні нескінченності. Тому він робить висновок, що фактичних нескінченностей немає.

8.2 Непрямі докази

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

(Р → (qVr))

¬Q

¬R

_____

¬П

Цей аргумент виглядає коректним. За першою передумовою ми знаємо: якби P були істинними, то так би (Q v R) було правдою. Але тоді або Q або R, або обидва були б правдою. І за другим і третім умовам ми знаємо: Q є помилковим, а R помилковим. Тож не може бути, що (Q v R) є істинним, і тому не може бути, що P є істинним.

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

П	Q	R	(кВР)	(Р → (кВр))	¬Q	¬Р	¬П
				приміщення	приміщення	приміщення	висновок
Т	Т	Т	Т	Т	F	F	F
Т	Т	F	Т	Т	F	Т	F
Т	F	Т	Т	Т	Т	F	F
Т	F	F	F	F	Т	Т	F
F	Т	Т	Т	Т	F	F	Т
F	Т	F	Т	Т	F	Т	Т
F	F	Т	Т	Т	Т	F	Т
F	F	F	F	Т	Т	Т	Т

У будь-якій ситуації, в якій всі приміщення відповідають дійсності, висновок вірний. Тобто: приміщення все вірно тільки в останньому ряду. Для цього ряду висновок також вірний. Отже, це вагомий аргумент.

Але знайдіть хвилинку і спробуйте довести цей аргумент. починаємо з

<проміжок перекладати= \ [\ fitchprf {\ лінія [1] {(P\ lif (Q\ або R))} [приміщення]\\ pline [2.] {\ not Q} [приміщення]\\\ рядок [3]. {\ lnot R} [приміщення]} {}\]» клас = «ql-img-відображений-рівняння швидкого латексного автоматичного формату» висота = «99" title="Відображено QuickLatex.com» width="422" src=» https://human.libretexts.org/@api/de...9c061e0_l3.png "/>

І ось ми зупинилися. Ми не можемо застосовувати жодне з наших правил. Ось вагомий аргумент, що ми не зробили нашу систему міркувань достатньо сильною, щоб довести.

Є кілька способів виправити цю проблему і зробити нашу систему міркувань досить сильною. Одним з найдавніших рішень є впровадження нового методу доказів, традиційно званого «reductio ad absurdum», що означає зведення до абсурду. Цей метод також часто називають «непрямим доказом» або «непрямим виведенням».

Ідея полягає в тому, що ми припускаємо заперечення нашого висновку, а потім показуємо, що протиріччя призводить. Протиріччя проявляється, коли доведено деяке речення ψ, і його заперечення ¬ψ. Це може бути будь-яке речення. Справа в тому, що, враховуючи принцип бівалентності, ми, мабуть, довели щось помилкове. Бо якщо ψ істинно, то ¬ψ є хибним; а якщо ¬ψ істинно, то ψ є хибним. Нам не потрібно знати, що є помилковим (ψ або ¬ψ); достатньо знати, що один з них повинен бути.

Пам'ятайте, що ми побудували нашу логічну систему так, що вона не може спричинити неправду з істинних тверджень. Отже, джерелом неправди, яку ми виробляємо в непрямому виведенні, повинна бути певна неправда, яку ми додали до нашого аргументу. І те, що ми додали до нашого аргументу, - це заперечення висновку. Таким чином, висновок повинен бути вірним.

Форма аргументу така:

<проміжок перекладати= \ [\ fitchctx {\ підзахисний {\ pline {\ not\ phi}} {\ ellipsesline\\\ pline {\ psi}\\ рядок {\ not\ psi}}\ flline {\ phi}\]» клас = "ql-img-відображений-рівняння швидкого латекс-автоформату» висота = "161" назва ="Відображено QuickLA Tex.com» ширина = «69" src=» https://human.libretexts.org/@api/de...155748/Images/ швидкий латекс.-78 ад cfd 2484235103 афс 6дфб18д20кфа_л3.png» />

Традиційно припущення про непряму деривацію також прийнято називати «припущенням для скорочення».

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

<проміжок перекладати= \ [\ fitchprf {\ лінія [1] {(P\ lif (Q\ або R))} [приміщення]\\ pline [2.] {\ not Q} [приміщення]\\\ рядок [3]. {\ lnot R} [приміщення]} {\ незахищений {\ рядок [4] {\ not\ not P} [припущення для непрямої деривації]} {\ pline [5] {P} [подвійне заперечення, 4]\\\ pline [6.] {(Q\ або R)} [режим роботи, 1, 5]\\\ pline [7.] {R} [режим полендо, 6, 2]\\\ pline [8] {\ not R} [повторити, 3]\\}\ рядок [9]. {\ lnot P} [непряме похідне, 4-8]}\]» клас = «ql-img-відображений-рівняння швидкого латекс-автоформату» висота = «249" title="Відображено QuickLatex.com» width="626" src=» https://human.libretexts.org/@api/de...7321229_l3.png "/>

Ми припустили заперечення нашого висновку на рядку 4. Висновок, який ми вважали правильним, був ¬П, а заперечення цього — ¬¬П. У рядку 7 ми довели R. Технічно ми закінчили на цьому етапі, але ми хотіли б бути добрими до тих, хто намагається зрозуміти наш доказ, тому повторюємо рядок 3, щоб речення R і ¬R були поруч, і дуже легко побачити, що щось пішло не так. Тобто, якщо ми довели і R, і ¬R, то довели щось помилкове.

Наші міркування тепер йдуть так. Що пішло не так? Рядок 8 - це правильне використання повторення; лінія 7 походить від правильного використання modus tollendo ponens; лінія 6 від правильного використання modus ponens; лінія 5 від правильного використання подвійного заперечення. Отже, ми не помилилися в своїх міркуваннях. Ми використовували лінії 1, 2 і 3, але це приміщення, які ми погодилися вважати правильними. Це залишає рядок 4. Це повинно бути джерелом мого протиріччя. Воно повинно бути помилковим. Якщо рядок 4 є помилковим, то ¬P має значення true.

Деякі люди вважають непрямі докази менш сильними, ніж прямі докази. Для цього існує безліч, і складних, причин. Але, для нашої логіки пропозиції, жодна з цих причин не застосовується. Це тому, що можна довести, що наша логіка пропозиції послідовна. Це означає, що можна довести, що наша логіка пропозиції не може довести неправду, якщо хтось вперше не введе неправду в систему. (Як правило, неможливо довести, що більш потужні та вдосконалені логічні чи математичні системи є послідовними зсередини цих систем; наприклад, неможливо довести в арифметиці, що арифметика послідовна.) Враховуючи, що ми можемо бути впевнені в послідовності логіки пропозиції, ми можемо бути впевнені, що в нашій логіці пропозиції непряме доказ є хорошою формою міркування. Ми знаємо, що якщо ми доведемо неправду, ми повинні були вкласти неправду; і якщо ми впевнені у всіх інших припущеннях (тобто передумовах) нашого доказу, за винятком припущення про непряму деривацію, то ми можемо бути впевнені, що це припущення для непрямого виведення повинно бути джерелом брехня.

Тут обов'язкова замітка про термінологію. Слово «протиріччя» вживається неоднозначно в більшості логічних дискусій. Це може означати ситуацію, як ми бачимо вище, де стверджуються два речення, і ці речення не можуть бути істинними. Або це може означати одне речення, яке не може бути істинним. Прикладом такого речення є (P^¬P). Таблиця істинності для цього речення така:

П	¬П	(Р ^ ¬П)
Т	F	F
F	Т	F

Таким чином, подібного роду речення ніколи не може бути істинним, незалежно від значення П.

Щоб уникнути неоднозначності, у цьому тексті ми завжди називатимемо одне речення, яке не може бути істинним, «суперечливим реченням». Таким чином, (P^¬P) є суперечливим реченням. Ситуації, коли стверджуються два речення, які не можуть бути істинними, називатимуться «протиріччям».

8.3 Наш приклад та інші приклади

Тепер ми можемо реконструювати версію аргументу Галілея. Ми будемо використовувати наступний ключ.

П: Існують фактичні нескінченності (включаючи натуральні числа та квадратні числа).

Q: Існує відповідність один до одного між натуральними числами і квадратними числами.

R: Розмір множини натуральних чисел і розмір множини квадратних чисел однакові.

S: Всі квадратні числа є натуральними числами.

T: Деякі з натуральних чисел не є квадратними числами.

U: Є більше натуральних чисел, ніж квадратних чисел.

За допомогою цього ключа аргумент буде переведений:

(Р → Q)

(Q→R)

(Р → (S^T))

((S^T) → U)

(U→¬R)

______

¬П

І ми можемо довести, що це вагомий аргумент, використовуючи непряму деривацію:

<проміжок перекладати= \ [\ fitchprf {\ лінія [1] {(P\ lif Q)} [приміщення]\\ pline [2.] {(Q\ lif R)} [приміщення]\\ pline [3.] {(P\ lif (S\ земля T))} [приміщення]\\ pline [4.] {(S\ земля T)\ lif U)} [приміщення]\\ pline [5.] {(U\ lif\ lnot R)} [приміщення]} {\ незахищений {\ лінія [6] {\ not\ not P} [припущення для непрямої деривації]} {\ pline [7] {P} [подвійне заперечення, 6]\\\ pline [8.] {Q} [режим роботи, 1, 7]\\\ pline [9.] {R} [режим поненса, 2, 8]\\\ pline [10.] {(S\ земля T)} [модуль поненса, 3, 7]\\\ pline [11.] {U} [режим поненса, 4, 10]\\\ pline [12.] {\ lnot R} [режим поненса, 5, 11]\\\ рядок [13] {R} [повторити, 9]}\ рядок [14.] {\ lnot P} [непряме похідне, 6-13]}\]» клас = «ql-img-відображений-рівняння швидкого латекс-автоформату» висота = «337" title="Відображено QuickLatex.com» width="626" src=» https://human.libretexts.org/@api/de...2daeaf3_l3.png "/>

На рядку 6 ми припустили ¬¬П, тому що Галілей вважав, що ¬П і мав на меті довести, що ¬П. Тобто він вважав, що фактичних нескінченностей немає, і тому припускав, що помилково вважати, що це не так, що фактичних нескінченностей немає. Ця брехня призведе до інших брехні, викриваючи себе.

Для тих, хто зацікавлений: Галілей дійшов висновку, що фактичних нескінченностей немає, але є потенційні нескінченності. Таким чином, міркував він, це не так, що всі натуральні числа існують (в деякому сенсі «існувати»), але це правда, що ви могли б рахувати натуральні числа назавжди. Багато філософів до і після Галілея дотримувалися цієї точки зору; це схоже на точку зору Аристотеля, який був важливим логіком і філософом, який писав майже дві тисячі років до Галілея.

Зауважте, що в такому аргументі ви могли б міркувати, що не припущення про непряме виведення, а скоріше одне з передумов було джерелом протиріччя. Сьогодні більшість математиків вважають це з приводу аргументу Галілея. Логік і математик на ім'я Георг Кантор (1845-1918), винахідник теорії множин, стверджував, що нескінченні множини можуть мати належні підмножини однакового розміру. Тобто Кантор заперечував передумову 4 вище: хоча всі квадратні числа є натуральними числами, а не всі натуральні числа є квадратними числами, це не так, що ці два набори мають різний розмір. Кантор прийняв, однак, передумова 2 вище, і, отже, вважав, що розмір безлічі натуральних чисел і розмір безлічі квадратних чисел однакові. Сьогодні, використовуючи міркування Кантора, математики і логіки вивчають нескінченність, і виробили великий масив знань про природу нескінченності. Якщо це вас цікавить, див. Розділ 17.5.

Розглянемо ще один приклад, щоб проілюструвати непряму деривацію. Дуже корисний набір теорем сьогодні називається «Теореми Де Моргана», на честь логіка Августа Де Моргана (1806—1871). Ми не можемо викласти їх повністю до 9 глави, але ми можемо констатувати їх еквівалент англійською мовою: DeMorgan зауважив, що ¬ (PvQ) і (¬P^¬Q) еквівалентні, а також що ¬ (P^Q) і (¬Pv¬q) еквівалентні. Враховуючи це, має бути теорема нашої мови, яка (¬ (PvQ) → (¬P^¬Q)). Доведемо це.

Вся формула є умовною, тому будемо використовувати умовну деривацію. Таким чином, наше доказ має починатися:

<проміжок перекладати= \ [\ fitchprf {} {\ підзахисний {\ лінія [1.] {\ lnot (P\ or Q)} [припущення для умовного похідного]} {}}\]» клас = «ql-img-відображений-рівняння швидкого латекс-автоформату» висота = «117" title="Відображено QuickLatex.com» width="652" src=» https://human.libretexts.org/@api/de...425c1da_l3.png "/>

Щоб завершити умовну деривацію, треба довести (¬P^¬Q). Це кон'юнкція, і наше правило для показу сполучників - примикання. Оскільки використання цього правила може бути нашим найкращим способом показати (¬P^¬Q), ми можемо прагнути показати ¬P, а потім показати ¬Q, а потім виконати прив'язку. Але, очевидно, нам дуже мало працювати з - просто рядок 1, який є запереченням. У такому випадку, як правило, розумно спробувати непрямий доказ. Почніть з непрямого доказу ¬П.

<проміжок перекладати= \ [\ fitchprf {} {\ підзахисний {\ лінія [1.] {\ not (P\ or Q)} [припущення для умовного похідного]} {\ subproof {\ pline [2] {\ not\ not P} [припущення для непрямої деривації]} {\ pline [3] {P} [подвійне заперечення, 2]\\}}}\]» клас = "ql-img-відображений-рівняння швидкого латекс-автоформату» висота = «201" title="Відображено QuickLatex.com» width="652" src=» https://human.libretexts.org/@api/de...c23c123_l3.png "/>

Нам зараз треба знайти протиріччя — яке - те протиріччя. Але очевидне вже є. Рядок 1 говорить про те, що ні P, ні Q не вірні. Але рядок 3 говорить про те, що P вірно. Ми повинні зробити це протиріччя явним, знайшовши формулу та її заперечення. Ми можемо зробити це за допомогою додавання.

Щоб завершити доказ, ми знову використаємо цю стратегію.

<проміжок перекладати= \ [\ fitchprf {} {\ підзахисний {\ лінія [1.] {\ not (P\ or Q)} [припущення для умовного похідного]} {\ subproof {\ pline [2] {\ not\ not P} [припущення для непрямої деривації]} {\ pline [3] {P} [подвійне заперечення, 2]\\\ pline [4.] {(P\ або Q)} [додавання, 3]\\\ рядок [5.] {\ not (P\ або Q)} [повторити, 1]}\ рядок [6] {\ not P} [непряме похідне 2-5]\\\ підзахисний {\ лінія [7] {\ not\ not Q} [припущення для непрямого похідного]} {\ лінія [8]. {Q} [подвійне заперечення, 7]\\\ pline [9.] {(P\ або Q)} [додавання, 8]\\\ рядок [10.] {\ not (P\ або Q)} [повторити, 1]}\ рядок [1] {\ not Q} [непряме похідне 7-10]\\ рядок [12] {(\ не P\ земля\ not Q)} [примикання, 6, 1]}\ рядок [13] {(\ lnot (P\ або Q)\ lif (\ lnot P\ land\ not Q))} [умовне похідне 1-12]}\]» клас = «ql-img-відображений-рівняння швидколатексного автоматичного формату» висота ="373" title="Відображено QuickLatex.com» width="653" src =» https://human.libretexts.org/@api/de...209b6356ac7e4_ l3.png "/>

Теореми Де Моргана ми доведемо як задачі для глави 9.

Ось загальне правило для виконання доказів: Доводячи умовне, завжди робіть умовну деривацію; інакше спробуйте пряму деривацію; якщо це не вдається, то спробуйте непряму деривацію.

8.4 Проблеми

Заповніть наступні докази. Кожен зажадає непрямого виведення. Останні два є складними.
1. Приміщення: (П → Р), (Q → R), (PvQ). Висновок: Р.
2. Приміщення: ((PvQ) → R), ¬R. Висновок: ¬П.
3. Передумова: (¬P^¬Q). Висновок: ¬ (PvQ).
4. Передумова: (Р → Р), (Q → S), ¬ (R ^ S). Висновок: ¬ (Р ^ Q).
5. Передумова: ¬R, ((Р → R) v (Q → R)). Висновок: (¬P v ¬Q).
6. Передумова: ¬ (R v S), (Р → R), (Q → S). Висновок: ¬ (P v Q).
Доведіть наступні теореми.
1. ¬ (Р^¬П).
2. ¬ (Р → ¬П) ^ (¬П → П)).
3. (¬П → ¬ (Р^Q)).
4. ((P^¬Q) → ¬ (Р → Q)).
У звичайній розмовній англійській мові напишіть свій власний вагомий аргумент принаймні з двома передумовами. Ваш аргумент повинен бути просто абзацом (а не впорядкованим списком речень або чимось іншим, що виглядає як формальна логіка). Переведіть його в логіку пропозиції і доведіть, що він дійсний, використовуючи непряму деривацію.

[10] Цей переклад назви книги Галілея став найпоширенішим, хоча більш буквальним було б математичні дискурси та демонстрації. Переклади книги включають Дрейка (1974).