Відкрити головне меню

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

(Перенаправлено з Доказ неможливості)

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

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

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

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

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

Різновиди доказу неможливостіРедагувати

Доказ від супротивногоРедагувати

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

Доказ спускомРедагувати

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

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

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

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

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

275 + 845 + 1105 + 1335 = 1445.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кут трисекції і подвоєння кубаРедагувати

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

Квадратура кругаРедагувати

не є евклідовим числом ... і тому неможливо побудувати  довжину, яка дорівнює окружності кола діаметра одиниці за допомогою евклідових методів[4]

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

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

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

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

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

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

Остання теорема ФермаРедагувати

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

Парадокс РічардаРедагувати

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

Парадокс Річарда ... полягає в наступному. Розглянемо всі десяткові числа, які можна визначити за допомогою кінцевого числа слів ["слова" означають символи;]; Нехай E - клас таких десятих знаків. Тоді Є має параграф Річарда ... виглядає наступним чином. Розглянемо всі десяткові числа, які можна визначити за допомогою кінцевого числа слів ["слова" означають символи; Bold emphasis added for emphasis]; Нехай E - клас таких десятих знаків. Тоді є    [нескінченне число] повторів;

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

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

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

За словами Нагеля та Ньюмана (стор. 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: Проблема поштової корреспонденції (див. Хопкрофт та Улманн[7], стор 193фф, стор 407 для довідки)
  3. Квітень 1947: доказ Еміля Пост (рекурсивна нерозв'язність проблеми Ту) (невирішеність стор 293). З тих пір вона стала відома як "Проблема Слову Ту" або "Проблема Тусу Слово" (Аксель Туа запропонував цю проблему в роботі 1914 р. (Див. Посилання на статтю "Погашення неможливо", стор 303)).
  4. Теорема Райса: узагальнена формулювання другої теореми Тьюринга (див. Хопкрофт і Улманн[9], с. 185фф)[8]
  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)

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

Чи має це діофантівське рівняння ціле рішення? Десята проблема ГільбертРедагувати

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

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

В соціальних наукахРедагувати

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

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

У природничих наукахРедагувати

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

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

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

Також дивітсяРедагувати

ПриміткиРедагувати

  1. Pudlák, pp. 255–256.
  2. Hardy and Wright, p. 42
  3. Nagel and Newman p. 8
  4. Hardy and Wright p. 176
  5. Principia Mathematica, 2nd edition 1927, p. 61, 64 in Principia Mathematica online, Vol.1 at University of Michigan Historical Math Collection
  6. Gödel in Undecidable, p. 9
  7. John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. 
  8. "...there can be no machine E which ... will determine whether M [an arbitrary machine] ever prints a given symbol (0 say)" (Undecidable p. 134).

ПосиланняРедагувати