Теорема Геделя про неповноту за 20 хвилин

Екологія життя. Наука і відкриття: Теоремі Геделя про неповноту, однією з найвідоміших теорем математичної логіки, пощастило і не пощастило одночасно. У цьому вона схожа на спеціальну теорію відносності Ейнштейна. З одного боку, майже всі про них щось чули. З іншого інтерпретації теорія Ейнштейна «говорить, що все в світі відносно».

Отже, що ж? Нижче я спробую «на пальцях» розповісти про це. Виклад моє буде, зрозуміло нестрогим і інтуїтивним, але я попрошу математиків не судити мене строго. Можливо, що для нематематика (до яких, взагалі-то, ставлюся і я), в розказаному нижче буде щось нове і корисне.

Математична логіка - наука дійсно досить складна, а головне - не дуже звична. Вона вимагає акуратних і строгих маневрів, при яких важливо не переплутати реально доведене з тим, що «і так зрозуміло». Проте, я сподіваюся, що для розуміння наступного нижче «начерку докази ТГН» читачеві знадобиться тільки знання шкільної математики / інформатики, навички логічного мислення і 15-20 хвилин часу.

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

Почнемо з того, що спробуємо розібратися, що таке доказ. Візьмемо якусь шкільну задачку з математики. Наприклад, нехай потрібно довести вірність наступної нехитрої формули: «∀x (x-1) (x-2) -2 = x (x-3)» (нагадаю, що символ ∀ читається «для будь-якого» і називається «квантор загальності» ). Довести її можна, тотожне перетворюючи, скажімо, так:

1. ∀x (x-1) (x-2) -2 = x (x-3)

2. ∀xx2-3x + 2-2 = x2-3x

3. ∀xx2-3x-x2 + 3x = 0

4. ∀x0 = 0

5. ІСТИНА

Перехід від однієї формули до іншої відбувається за деякими відомими правилами. Перехід від 4-й формули до 5-ї стався, скажімо, тому, що будь-яке число дорівнює самому собі - така аксіома арифметики. А вся процедура доведення, таким чином, переводить формулу в логічне значення ІСТИНА. Результатом могла бути і брехня - якби ми спростовували якусь формулу. В такому випадку ми б довели її заперечення. Можна собі уявити програму (і такі програми дійсно написані), які б доводили подібні (і більш складні) висловлювання без участі людини.

Викладемо те ж саме трохи більше формально. Нехай у нас є безліч, що складається з рядків символів якогось алфавіту, і існують правила, за якими з цих рядків можна виділити підмножина S так званих висловлювань - тобто граматично осмислених фраз, кожна з яких є істинною або помилкова. Можна сказати, що існує функція P, що зіставляє висловлювань з S одне з двох значень: ІСТИНА або БРЕХНЯ (тобто відображає їх в булево безліч B з двох елементів).

Назвемо таку пару - безліч висловлювань S і функція P з> S в B - «мовою висловлювань». Зауважимо, що в повсякденному сенсі поняття мови дещо ширше. Наприклад, фраза російської мови «А ну йди сюди! "Не істинна і не помилкова, тобто висловлюванням, з точки зору математичної логіки, не є.

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

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

Запитаємо себе: для будь-якої чи функції P існує «доводить алгоритм» (або, коротше, «дедуктіка»), еквівалентний цієї функції, тобто переводить кожне висловлювання саме в той логічне значення, що і вона? Лаконічніше той же питання можна сформулювати так: чи всяка функція над безліччю висловлювань обчислюваності?

Як ви вже здогадалися, з справедливості ТГН слід, що ні, не всяка - існують невичіслімие функції такого типу. Іншими словами, не всяке вірне висловлювання можна довести.

Дуже може бути, що це твердження викличе у вас внутрішній протест. Пов'язано це з кількома обставинами. По-перше, коли нас вчать шкільної математики, то іноді виникає хибне враження майже повної тотожності фраз «теорема X вірна» і «можна довести або перевірити теорему X».

Але, якщо вдуматися, це зовсім не очевидно. Деякі теореми доводяться досить просто (наприклад, перебором невеликого числа варіантів), а деякі - дуже складно. Згадаймо, наприклад, знамениту Велику теорему Ферма:

Не існує таких натуральних x, y, z і n> 2, що xn + yn = zn,

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

Другий інтуїтивний аргумент проти ТГН тонший. Припустимо, у нас є якесь недовідне (в рамках даної дедуктікі) висловлювання. Що заважає нам прийняти його в якості нової аксіоми? Тим самим ми трохи ускладнити нашу систему доказів, але це не страшно.

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

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

У таких випадках кажуть, що дедуктіка суперечлива. Таким чином, ще одна формулювання ТГН звучить так: «Існують мови висловлювань, для яких неможлива повна несуперечлива дедуктіка» - звідси і назва теореми.

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

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

Курт Гедель

Будь-якому школяреві відомо, що, скажімо, в разі функції sin⁡x вам повинно сильно повезти з аргументом, щоб процес обчислення точного десяткового подання значення цієї функції закінчився за кінцеве число кроків.

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

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

Зрозуміло, що не всі такі рядки осмислені (наприклад, «12 = + ∀x>» - це нісенітниця). Підмножина осмислених висловлювань з цього класу (тобто рядків, які істинні або помилкові з точки зору звичайної арифметики) і буде нашим безліччю висловлювань.

Приклади висловлювань формальної арифметики:

• 1 = 1

• 2 × 2 = 5

• ∃xx> 3

• ∀y∀zy × z> y + z

і т.д. Тепер назвемо «формулою з вільним параметром» (ФСП) рядок, яка стає висловлюванням, якщо в якості цього параметра підставити в неї натуральне число. Приклади ФСП (з параметром x):

і т.д. Іншими словами, ФСП еквівалентні функціям натурального аргументу з булевими значенням.
Позначимо множину всіх ФСП буквою F. Зрозуміло, що його можна впорядкувати (наприклад, спочатку випишемо впорядковані за алфавітом однобуквені формули, за ними - дволітерні і т.д .; за яким саме алфавітом відбуватиметься упорядкування, нам не принципово). Таким чином, будь-який ФСП відповідає її номер k в упорядкованому списку, і ми будемо позначати її Fk.

Перейдемо тепер до начерку докази ТГН в такому формулюванні:

Для мови висловлювань формальної арифметики не існує повної несуперечливої дедуктікі.

Доводити будемо від противного.

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

1. Знаходимо k-ю формулу в списку F.

2. Підставляємо в неї число k як аргумент.

3. Застосовуємо до отриманого висловом наш доводить алгоритм (за нашим припущенням, він існує), який переводить його в істину або БРЕХНЯ.

4. Застосовуємо логічне заперечення до отриманого результату.

Простіше кажучи, алгоритм призводить до значення ІСТИНА тоді і тільки тоді, коли результат підстановки в ФСП її власного номера в нашому списку дає хибне висловлювання.

Тут ми підходимо до єдиного місця, в якому я попрошу читача повірити мені на слово.

Очевидно, що, при зробленому вище припущенні, будь ФСП з F можна зіставити алгоритм, який містить на вході натуральне число, а на виході - логічне значення.

Менш очевидно зворотне твердження:

Лемма: Будь-якому алгоритму, що переводить натуральне число в логічне значення, відповідає якась ФСП з безлічі F.

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

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

Пройшовши це слизьке місце, ми швидко добираємося до кінця.

Отже, вище ми описали алгоритм A. Згідно лемі, в яку я попросив вас повірити, існує еквівалентна йому ФСП. Вона має якийсь номер в списку F - скажімо, n. Запитаємо себе, чому дорівнює Fn (n)? Нехай це ІСТИНА. Тоді, з побудови алгоритму A (а значить, і еквівалентної йому функції Fn), це означає, що результат підстановки числа n в функцію Fn - БРЕХНЯ.

Аналогічно перевіряється і зворотне: з Fn (n) = БРЕХНЯ слід Fn (n) = ІСТИНА. Ми прийшли до протиріччя, а значить, вихідне припущення невірно. Таким чином, для формальної арифметики не існує повної несуперечливої ​​дедуктікі. Що й потрібно було довести.

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

На закінчення я хочу зауважити, що нічого особливого дивного ТГН не затверджує. Зрештою, все давно звикли, що не всі числа представимо у вигляді відносини двох цілих (пам'ятаєте, у цього твердження є дуже витончене доказ, яким більше двох тисяч років?). І корінням полиномов з раціональними коефіцієнтами є т оже не всі числа. А тепер ось з'ясувалося, що не всі функції натурального аргументу обчислюваності.

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

«Будь-яка фраза китайської мови є вірним висловом, якщо вона міститься в Цитатник товариша Мао Дзе Дуна, і невірна, якщо не міститься».

Тоді відповідний повний і несуперечливий доводить алгоритм (його можна назвати «догматичної дедуктікой») виглядає приблизно так:

«Гортає цитатника товариша Мао Дзе Дуна, поки не знайдеш шукане висловлювання. Якщо воно знайдено, то воно вірно, а якщо цитатника закінчився, а висловлювання, не знайдено, то воно невірно ».

Тут нас рятує те, що будь-який цитатник, очевидно, кінцевий, тому процес «доведення» неминуче закінчиться. Таким чином, до мови догматичних висловлювань ТГН непридатна. Але ж ми говорили про складні мовами, правда? опубліковано econet.ru