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

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

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

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

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

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

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

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

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

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

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

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

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

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

розглядаючи всі окремі випадки до кореня 17 квадратних футів ….Hardy and Wright, p. 42 Зараз існує більш узагальнене доведення того, що: М-й корінь цілого числа N ірраціональний, якщо N не є ступенем m цілого n".Hardy and Wright, p. 40 Тобто, неможливо виразити m-й корінь цілого числа N у вигляді відношення a / b двох цілих чисел a та b, таких, які не мають спільного коефіцієнту, крім випадків, коли b = 1.

Неможливі конструкції, які шукали стародавні греки Три відомі питання геометрії у Давньогрецькій геометрії були такими: … Як з компасом і прямим краєм, щоб трисектувати будь-який кут,   Як побудувати куб обсягом вдвічі більше обсягу даного куба  Як побудувати квадрат, рівний по площині, що відповідає певному колу. Понад 2000 років не вдавалося відповісти на ці питання; Нарешті, у XIX столітті було доведено, що дані конструкції логічно неможливі.Nagel and Newman p. 8

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

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

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

Квадратура круга не є евклідовим числом … і тому неможливо побудувати  довжину, яка дорівнює окружності кола з одиничним діаметром за допомогою евклідових методівHardy and Wright p. 176 Доведення існує для того, щоб показати, що будь-яке евклідове число є алгебраїчним числом (числом, яке є розв'язком деякого алгебраїчного рівняння). Тому, оскільки у 1882 р.  було доведено, що  — це трансцендентне число і воно за визначенням не алгебраїчне число. Із цього випливає, що це не евклідове число. Отже неможливо побудувати довжину за допомогою одиничного колаHardy and Wright p. 159 referenced by E. Hecke. (1923). Vorlesungen über die Theorie der algebraischen Zahlen. Leipzig: Akademische Verlagsgesellschaft, а квадратуру круга знайти неможливо.

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

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

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

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

Велика теорема Ферма була сформульована П'єром де Ферма в 1600-х роках. У цій теоремі йдеться про неможливість знайти розв'язок рівняння для у натурних числах. Ферма сам довів випадок з , використавши техніку нескінченного спуску, розроблену ним, а інші окремі випадки були доведені пізніше, але загальне твердження було доведено лише у 1994 році Ендрю Вайлсом.

Парадокс Річарда Цей глибокий парадокс, представлений Жулем Рішаром у 1905 році, сповістив про роботу Курта Геделя (див. Нагель і Ньюман, стор. 60фф) та Алана Тюринга. Коротке визначення знайдено в Principia MathematicaPrincipia Mathematica, 2nd edition 1927, p. 61, 64 in Principia Mathematica online, Vol.1 at University of Michigan Historical Math Collection:Курт Гедель вважав, що його доведення є «аналогією» парадокса Річарда, який він назвав «антиномією Річарда».Gödel in Undecidable, p. 9 Докладніше дивіться далі про доведення Геделя.

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

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

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