Доведення неможливості

Доведення неможливості, відоме також як доведення від супротивного, доведення теореми неможливості, або негативний результат — це доведення, яке показує, що конкретна задача не може бути розв'язана, або розв'язання відсутнє взагалі. Часто доведення неможливості потребує багато роботи і часу для того, щоб знайти розв'язок. Щоб довести щось неможливе, необхідно розвинути теорію, і це, зазвичай, набагато складніше, аніж розв'язати протилежне завдання. Теореми неможливості у більшості випадків виражені як універсальні судження в логіці (див. квантор загальності).

Одним з найвідоміших є доведення Фердинанда фон Ліндеманна 1882 року, який показав, що стародавня задача про квадратуру круга не може бути розв'язана, тому що число π є трансцендентним (не алгебраїчним) і тільки підмножина алгебраїчних чисел може бути побудована за допомогою циркуля й лінійки. Для двох інших класичних задач — трисекції кута і подвоєння куба, неможливість побудови була доведена у дев'ятнадцятому столітті.

Задачею, що виникла в XVI столітті, було створення загальної формули за допомогою радикалів, що виражають розв'язок будь-яких поліноміальних рівнянь ступеня k, де k ≥ 5. У 1820-х роках, теорема Абеля-Руффіні показала, що це неможливо, з використанням таких понять, як розв'язні групи з теорії Галуа, нового розділу абстрактної алгебри.

Серед найважливіших доведень неможливості у 20-му столітті були задачі алгоритмічної нерозв'язності, які показали, що існують задачі, які неможливо розв'язати взагалі за допомогою будь-якого алгоритму. Найвідомішою є проблема зупинки.

У теорій складності обчислень такі методи, як релятивізація (див. Пророча машина), дають «слабкі» доведення неможливості, за винятком деяких технік доведень. Інші методи, такі як доведення повноти класу обчислювальної складності, свідчать про складність проблем. З цього видно, що їх так само важко розв'язати, як інші відомі проблеми, які виявилися незмінними.

Різновиди доведення неможливості

Доведення від супротивного

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

Доведення спуском

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

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

Види спростування неможливості припущень

Існує два альтернативні способи довести неправильну гіпотезу про те, що щось неможливо: контрприклад (конструктивне доведення) і логічна суперечність (неконструктивне доведення).

Очевидним способом спростувати гіпотезу неможливості є шлях надання єдиного контрприкладу. Наприклад, Ейлер запропонував, щоб принаймні n різних N-ї ступенів були необхідні для підрахування суми ще однієї n-й ступені. Ця гіпотеза була спростована в 1966 році контрприкладом, який включає в себе лише чотири різні числа у 5-му ступені у сумі дають інше число у 5-му ступені:

27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵.

Доведення контрприкладу є конструктивним доведенням.

І навпаки, неконструктивне доведення того, що щось не є неможливим, продовжується виявленням логічної суперечливості, оскільки всі можливі контрприклади є недійсними: принаймні один з елементів у списку можливих контрприкладів повинен бути дійсно чинним контрприкладом до неможливості гіпотези. Наприклад, гіпотеза про те, що ірраціональна ступінь, підвищена до ірраціонального ступеня, не може бути раціональною, була спростована, тим що один із двох можливих контрприкладів повинен бути дійсним контрприкладом без доведення того.

Про існування ірраціональних чисел: доведення Піфагорійців

Доведення Піфагора (або, швидше за все, його учня), який був зроблений близько 500 до н. е., справив дуже сильний ефект на математику. У ньому стверджується, що квадратний корінь з 2 не може бути виражений, як співвідношення двох цілих чисел (рахункових чисел). Доведення розбиває «числа» на дві непересічні множини — раціональні числа та ірраціональні числа. Таке розбиття було використовувано Кантором у його діагональному методі, який, у свою чергу, був використаний Тьюрингом у своєму доведенні того, що задачу розв'язності (проблема вибору Гільберта) неможливо розпізнати.

Невідомо, коли або ким, було відкрито "теорему Піфагора". Навряд чи це відкриття було зроблено самим Піфагором, але це, безумовно, відбулося у його школі. Піфагор жив приблизно 570-490 р. до н. е. Демокрит, що народився близько 470 р. до н. е., писав про ірраціональні лініях і твердих тілах ...

Доведення можна використовувати і для різних квадратних коренів числа до числа 17.

Є відомий уривок з газети «Теєт» Платона, у якому говориться, що Феодор (учень Платона) довів ірраціональність таких коренів:

${\sqrt {3}},{\sqrt {5}},...,$

розглядаючи всі окремі випадки до кореня 17 квадратних футів ... .

Зараз існує більш узагальнене доведення того, що:

М-й корінь цілого числа N ірраціональний, якщо N не є ступенем m цілого n".

Тобто, неможливо виразити m-й корінь цілого числа N у вигляді відношення a / b двох цілих чисел a та b, таких, які не мають спільного коефіцієнту, крім випадків, коли b = 1.

Неможливі конструкції, які шукали стародавні греки

Три відомі питання геометрії у Давньогрецькій геометрії були такими:

1. ... Як з компасом і прямим краєм, щоб трисектувати будь-який кут,
2.   Як побудувати куб обсягом вдвічі більше обсягу даного куба
3.  Як побудувати квадрат, рівний по площині, що відповідає певному колу.

Понад 2000 років не вдавалося відповісти на ці питання; Нарешті, у XIX столітті було доведено, що дані конструкції логічно неможливі.

Четверте питання давніх греків полягало у побудові рівностороннього багатокутника з заданим числом n сторін, без основних випадків: n = 3, 4, 5, які вони вміли будувати.

Усе це є питаннями в евклідовій конструкції, а евклідові конструкції можна будувати, лише з евклідовими числами (за визначенням останнього) (Харді та Райт, стор. 159). Ірраціональні числа можуть бути евклідовими. Хороший приклад цього: ірраціональне число - квадратний корінь з 2-х. Це просто довжина гіпотенузи прямого трикутника з ногами, як одна одиниця довжини, і вона може бути побудована за допомогою лінійної стріли і компаса. Але століттями після Евкліда довелося довести, що евклідові числа не можуть включати жодних операцій, крім додавання, віднімання, множення, розподілу та вилучення квадратних коренів.

Трисекція кута і подвоєння куба

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

Квадратура круга

$\pi$ не є евклідовим числом ... і тому неможливо побудувати  довжину, яка дорівнює окружності кола з одиничним діаметром за допомогою евклідових методів

Доведення існує для того, щоб показати, що будь-яке евклідове число є алгебраїчним числом (числом, яке є розв'язком деякого алгебраїчного рівняння). Тому, оскільки у 1882 р.  було доведено, що $\pi$ - це трансцендентне число і воно за визначенням не алгебраїчне число. Із цього випливає, що це не евклідове число. Отже неможливо побудувати довжину $\pi$ за допомогою одиничного кола, а квадратуру круга знайти неможливо.

Побудова рівностороннього n-гона

Теорема Гаусса-Вейззеля в 1837 році показала, що побудова рівностороннього n-гону неможлива для більшості значень n.

Аксіома паралельності Евкліда

Нагель і Ньюмен розглядають питання, поставлене паралельним постулатом, як "... можливо, найзначніший розвиток у його довгострокових ефектах на подальшу математичну історію" (стор. 9).

Питання звучить так: чи може аксіома, яка стверджує, що дві паралельні лінії "... не зустрінуться навіть на нескінченності" (виноска, там же) буде вираженою з інших аксіом геометрії Евкліда? Це так і не було доведено поки у дев'ятнадцятому столітті не вийшла праця: "... Гаус, Боляй, Лобачевський та Ріман про те, що неможливість виведення аксіоми паралельності з інших аксіом була показана. Це результат найвищої інтелектуальної важливості ... Можна довести неможливість доведення певних пропозицій [у даному випадку паралельний постулат] у межах певної системи [в даному випадку, перші чотири постулати Евкліда]". (стор 10)

Велика теорема Ферма

Велика теорема Ферма була сформульована П'єром де Ферма в 1600-х роках. У цій теоремі йдеться про неможливість знайти розв'язок рівняння $x^{n}+y^{n}=z^{n}$ для $n>2$ у натурних числах. Ферма сам довів випадок з $n=4$, використавши техніку нескінченного спуску, розроблену ним, а інші окремі випадки були доведені пізніше, але загальне твердження було доведено лише у 1994 році Ендрю Вайлсом.

Парадокс Річарда

Цей глибокий парадокс, представлений Жулем Рішаром у 1905 році, сповістив про роботу Курта Геделя (див. Нагель і Ньюман, стор. 60фф) та Алана Тюринга. Коротке визначення знайдено в Principia Mathematica:

Парадокс Річарда ... полягає в наступному. Розглянемо всі десяткові числа, які можна визначити за допомогою скінченного числа слів ["слова" означають символи; жирний текст додано для підкреслення]; нехай E - клас таких десятих знаків. Тоді E має $\aleph _{0}$ [нескінченне число] повторів; hence its members can be ordered as the 1st, 2nd, 3rd, ... Let X be a number defined as follows [Whitehead & Russell now employ the Cantor diagonal method].
If the n-th figure in the n-th decimal is p, let the n-th figure in X be p + 1 (or 0, if p = 9). Then X is different from all the members of E, since, whatever finite value n may have, the n-th figure in X is different from the n-th figure in the n-th of the decimals composing E, and therefore X is different from the n-th decimal. Nevertheless we have defined X in a finite number of words [i.e. this very definition of “word” above.] and therefore X ought to be a member of E. Thus X both is and is not a member of E.

Курт Гедель вважав, що його доведення є «аналогією» парадокса Річарда, який він назвав «антиномією Річарда». Докладніше дивіться далі про доведення Геделя.

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

Чи можна довести цю теорему за допомоги цих аксіом? Доведення Геделя

За словами Нагеля та Ньюмана (стор. 68), «документ Геделя складний, щоб досягнути основні результати потрібно освоїти 46 попередніх визначень разом з кількома важливими попередніми теоремами» (стор. 68). Насправді, Нагелю і Ньюману було потрібне 67-сторінкове введення в свою експозицію доведень. Але якщо читач відчуває себе досить сильним, щоб розглянути цей документ, Мартін Девіс зауважує, що «Цей чудовий документ є не тільки інтелектуальним орієнтиром, але написаний він з чіткістю та силою, що читач отримує задоволення від читання» (Davis in Undecidable, p. 4). Більшості читачів рекомендується^[ким?] спочатку почитати Нагеля і Ньюмена.

Так що ж Гедель довів? З його слів:

"Доцільно … зробити гіпотезу, що … аксіоми [від Principia Mathematica і Peano] є … достатніми для розв'язку всіх математичних питань, які можуть бути формально виражені в даних системах. Надалі видно, що це не той випадок, а скоріше, що … існують відносно прості задачі теорії звичайних цілих чисел, які неможливо розв'язати на основі аксіом "(Гедель в невиправданому, ст.4).

Гедель порівнював своє доведення з «антиномією Річарда» («антиномія» — це суперечність або парадокс; для більшого розуміння парадокс Річарда):

"Аналогія цього результату з антиномією Річарда відразу ж очевидна, існує також тісний зв'язок [14] з Парадоксом брехуна (виноска 14 Геделя: кожна епістемологічна антиномія може бути використана для аналогічного доведення нерозв'язності) … Таким чином перед нами, пропозиція, яка стверджує свою нездійсненність [15]. (Його виноска 15: на відміну від виступів, така пропозиція не є круговою, бо, по-перше, вона стверджує нездійсненність цілком певної формули) "(Гедел в нерозв'язному вигляді, С.9).

Чи буде ця обчислювальна машина зафіксована в «колі»? Перше підтвердження Тьюринга

• Задачі розв'язності, проблема вибору, вперше була відкликана церквою у квітні 1935 р., і переслідувала за це Тюрінга протягом року, оскільки документ Тюринга був отриманий для публікації в травні 1936 р. (Також отриманий для публікації в 1936 р. — у жовтні, пізніше, ніж Тюринг зміг його опублікувати, був короткий документ Еміля Поста, який обговорив скорочення алгоритму до простого машиноподібного «методу», дуже схожого на модель обчислювальної машини Тюринга (див. Машину Пост-Тьюринга для деталей).
• Доведення Тюрінга ускладнюється числом необхідних визначень і його витонченим характером. Дивіться довідку про машину Тюрінга і доведення Тюрінга.
• Перше підтвердження Тюрінга (з трьох) слідує схемі Парадокс Річарда: обчислювальна машина Тюрінга є алгоритмом, представленим рядком із семи букв на «обчислювальній машині». Його «обчислення» полягає в перевірці всіх обчислювальних машин (включаючи саме) для «кругів» і формують діагональний номер з обчислень некруглих або «успішних» обчислювальних машин. Він робить це, починаючи з послідовності з 1, шляхом перетворення цифр (база 8) на рядки із семи букв для тестування. Коли він потрапляє на власний номер, він створює власну літеру. Він вирішує, що це буква-рядок успішної машини, але коли вона намагається зробити свої (власні) обчислення, він блокує коло та не може продовжувати. Таким чином, ми прийшли до парадоксу Річарда. (Якщо ви здивовані, див. Доведення Тюринга, щоб отримати більше).

Ряд подібних доведень невидимості з'явився незабаром до і після доведень Тьюринга:

1. Квітень 1935: Доведення Алонзо Черча (нерозв'язна проблема теорії елементарних чисел). Його доведення полягало у тому, «… запропонувати визначення ефективної обчислення … і показати, на прикладі, що не кожну проблему цього класу можна розв'язати» (невиріканість стор 90))
2. 1946: Проблема збіжності Поста (див. Хопкрофт та Улманн, стор 193фф, стор 407 для довідки)
3. Квітень 1947: доведення Еміля Поста (рекурсивна нерозв'язність проблеми Ту) (невирішеність стор 293). З тих пір вона стала відома як «Проблема Слову Ту» або «Проблема Тусу Слово» (Аксель Туа запропонував цю проблему в роботі 1914 р. (Див. Посилання на статтю «Погашення неможливо», стор 303)).
4. Теорема Райса: узагальнена формулювання другої теореми Тьюринга (див. Хопкрофт і Улманн[9], с. 185фф)
5. Теорема Грейбах: нерозв'язність в теорії мовлення (див. Хопкрофт і Улманн, с. 205, і посилання на стор 401 Там же: Греібах [1963] «Нерозв'язність проблеми неоднозначності для мінімальних лінійних граматик», Information and Control, 6: 2, 117—125., Також посилання на стор 402 Там же: Греібах [1968] «Запис про нерозв'язні властивості формальних мов», Math Systems Theory 2: 1, 1-6.)
6. Питання мозаїки Пенроуза
7. Питання про розв'язок для диофантовых рівнянь і відповідна відповідь в теоремі МРПД; Див. Запис нижче.

Чи можна стиснути цей рядок? Доведення Чайтіна

Для експозиції, придатної для неспеціалістів, дивіться Beltrami p. 108фф Також див. Franzen Chapter 8, pp. 137–148, and Davis pp. 263–266. Обговорення Францана значно складніше, ніж Бельтрамі, і впадає в так звану «ймовірність припинення» Ω-Грегорі Хайтіна. Старше лікування Девіса підходить до питання з точки зору машини Тьюринга. Чайтин написав ряд книг про свої зусилля та подальші філософські та математичні випади з них.

Рядок називається (алгоритмічно) випадковий, якщо він не може бути зроблений з будь-якої коротшої комп'ютерної програми. Хоча більшість рядків є випадковими, жоден конкретний не може бути доведено так, за винятком кінцевого числа коротких:

«Перефразуванням результату Чайтіна є те, що не може бути формальних доведень того, що досить довгий рядок є випадковим …» (Beltrami стор 109)

Бельтрамі зауважує, що «Доведення Чайтіна пов'язані з парадоксом, поставленим бібліотекарем Оксфорду Дж. Беррі в початку XX століття, який вимагає» найменшого натурального числа, яке не може бути визначено англійським реченням з менш ніж 1000 символів ". Очевидно, найкоротше визначення цього номера повинно містити принаймні 1000 символів. Проте пропозиція в лапках, яка сама є визначенням передбачуваної кількості, становить менше 1000 символів! " (Бельтрами, с. 108)

Чи має це діофантівське рівняння цілий розв'язок? Десята проблема Гільберт

Питання: «Чи є яке-небудь довільне» діофантінське рівняння «цілим числом розв'язку?» Це неможливо розкрити. Тобто неможливо відповісти на запитання у всіх справах.

Францен представляє десяту проблему Гільберта та теорему МРДП (теорема Матіясевича-Робінсона-Девіса-Патнема), в якій сказано, що «немає алгоритму, який би розв'яза, чи є у діофантівського рівняння взагалі якийсь розв'язок». MRDP використовує доведення невразливості Тьюринга: «… набір розв'язних діофантових рівнянь є прикладом розрахунково перерахованого, але нерозв'язної множини, а безліч нерозв'язних діофантових рівнянь не підлягає обчисленню» (стор. 71).

В соціальних науках

У політичній науці теорема неможливості Ерроу стверджує, що неможливо спроектувати систему голосування, яка задовольняє набір з п'яти конкретних аксіом. Ця теорема доведена, показуючи, що чотири з аксіом разом означають протилежність п'ятому.

У економіці теорема Холмстрома є теоремою неможливості, яка доводить, що система стимулювання для групи агентів не може задовольнити всі три бажані критерії.

У природничих науках

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

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

При неможливість затвердження в науці ніколи не може бути абсолютно доведена, вона може бути спростована одним контрприкладом. Такий контрприклад потребує припущень, що лежать в основі теорії того, що є неможливість перегляду.

Також дивіться

• Список не розв'язаних проблем в математиці – розв'язок цих проблем шукають досі. В свою чергу вище вказані проблеми, не мають розв'язку.
• No-go теореми, відповідні фізичні поняття.