е, теорія неповна). Важливе концептуальне зауваження полягає в тому, що необхідно припустити, що теорія несуперечлива, для того щоб оголосити вислів Геделя істинним.
Друга теорема Геделя про неповноту
Друга теорема Геделя про неповноту звучить наступним чином:
Для будь формально рекурсивно перечислимого (тобто ефективно генерується) теорії T, включаючи базові арифметичні істиннісні висловлювання та певні висловлювання про формальну доказовою, дана теорія T включає в себе твердження про свою несуперечності тоді і тільки тоді, коли теорія T суперечлива.
Іншими словами, несуперечність досить багатою теорії не може бути доведена засобами цієї теорії. Однак цілком може виявитися, що несуперечність однієї конкретної теорії може бути встановлена засобами іншої, більш потужної формальної теорії. Але тоді постає питання про несуперечності цієї другої теорії, і т.д.
Використовувати цю теорему для доказу того, що розумна діяльність не зводиться до обчислень, намагалися багато. Наприклад, ще в 1961 році відомий логік Джон Лукас (John Lucas) виступав з подібною програмою. Його міркування виявилися досить уразливими - однак він і завдання ставив більш широко. Роджер Пенроуз використовує дещо інший підхід, який викладається в книзі повністю, В«з нуляВ».
Дискусії
Наслідки теорем зачіпають філософію математики, особливо такі формалізму, які використовують формальну логіку для визначення своїх принципів. Можна перефразувати першу теорію про неповноту таким чином: В« неможливо знайти всеохоплюючу систему аксіом, яка була б здатна довести всі математичні істини, і жодної брехні В». З іншого боку, з точки зору суворої формальності, ця переформулировка НЕ має особливого сенсу, оскільки вона передбачає поняття В«істинаВ» і В«брехняВ» визначеними в абсолютному значенні, ніж у відносному для кожної конкретної системи.
А ось таке перефразування Друга теорема є ще більш тривожним для основ математики:
Якщо неможливо довести несуперечність і повноту системи в рамках неї самої, то ця система суперечлива.
Отже, для встановлення факту несуперечності деякої системи S необхідно використовувати більш потужну систему T , але доказ в рамках T не може бути повністю закінченим, поки не доведена несуперечність самої T (причому без використання системи S ).
Спочатку здавалося, що все-таки теореми Геделя залишають трохи надії, оскільки можна створити загальний алгоритм, який вирішує, чи є задане твердження вирішуваним чи ні. Цей алгоритм дозволить математикам обійти всі нерозв'язні проблеми відразу разом. Однак, негативна відповідь на проблеми вибору, отриманий в 1936 році, показав, що такого алгоритму не існує.
Деякі дослідники припускають, що твердження, яке недоказово в рамках дедуктивної системи, може бути абсолютно доказово на деякому метамови. А те, що не може бути доведено на цьому метамови, може, в свою чергу, бути доведено на мета- метамови , і так до нескінченності. Застосовуючи такі системи типізованих метамова спільно з аксіомою редуціруеми, яка з індуктивного припущенням застосовується до всього набору мов, можна для будь-яких галузей знань обходити проблему неповноти.
Необхідно також відзначити, що теореми Геделя застосовні тільки до досить сильним системам аксіом. В«Досить сильнийВ» в даному контексті позначає, що теорія містить достатньо коштів для представлення даних, необхідних для доказу Перша теорема про неповноту. Суттєво те, що для цього потрібні базові аксіоми, що представляють операції додавання і множення, як, наприклад, в арифметиці Робінсона Q. Існують більш слабкі системи аксіом, які повні і несуперечливі, наприклад, арифметика Пресбургера, яка доводить істинність тверджень першого порядку тільки щодо додавання.
Система аксіом може містити нескінченну кількість аксіом (як, наприклад, арифметика Пеано першого порядку), але для застосовності до такої системи теореми Геделя. повинен бути ефективний алгоритм, який дозволяє перевіряти коректність. Наприклад, можна розглянути безліч всіх висловлювань першого порядку, який істинні в стандартній моделі натуральних чисел. Ця система повна, але теорема Геделя незастосовна в даному випадку, оскільки не існує ефективної процедури, яка визначає, чи є задана послідовність аксіомою. Фактично, це так по слідству з Перша теорема Геделя про неповноту.
Інший приклад теорії, до якої непридатна Перша теорема Геделя про неповноту, може бути побудований таким чином: необхідно відсортувати всі можливі істинні твердження щодо натуральних чисел спочатку по довжині рядка, а потім лексикографічно. Далі система аксіом будується так - спочатку береться система аксіом Пеано, після чого необхідно в списку тверджень вибирати перше по порядку твердження, яке не може бути доведено. Далі це твердження вноситься в список аксіом нової системи. І так до кінця. В остаточному підсумку цей процес створить повну, несуперечливу і досить потужну формальну систему, яка, проте, не буде перечислимого.
Сам Гедель довів технічно більш слабкі версії теорем. Перший доказ теорем в наведених у статті формулюваннях вперше було приведено Д.Б. Россером в 1936 році.
За суті, доказ Перша теорема містить процес конструювання затвердження p в рамках формальної системи, яка можна описати на метамові наступним чином:
p = В«Це твердження не може бути доведено в розглянутій формальної системі В»
Як видно, це, всього лише, сучасний варіант парадокса брехуна, який на відміну від класичної формулювання, не зовсім парадоксальний.
Якщо система аксіом несуперечлива, доказ теореми Геделя показує, що p (і його заперечення) не можуть бути доведені в рамках системи. Отже твердження p істинно (це твердження про те, що воно само недоказово, і воно дійсно недоказово). Якщо система аксіом П‰ -несуперечлива, то заперечення p також не може бути доведено, і таким чином p невичіслімо. У системах, які П‰ -суперечливі (Але несуперечливі), або є така ж ситуація, або твердження В¬ p може бути доведено.
Додавання затвердження p в якості аксіоми не вирішує проблеми, оскільки для такої розширеної системи буде існувати інше твердження Геделя. Такі теорії, як арифметика Пеано, для яких не може бути побудовано перечислимого розширення, називаються істотно неповними .
Список літератури
Гедель математичний теорема неповнота
1. В.А. Успенський. Теорема Геделя про неповноту. - М.: Наука, 1982.
2. Теорема Геделя/Е. Нагель, Дж.Р. Ньюмен. - М.: Красанд, 2010. - 120 с.
3. Традиція. Російська енциклопедія: URL: traditio.ru/wiki/
[1] Цитата збірника статей В«Підстави математикиВ» випущеному в Нью-Йорку на честь 60-річчя К. Геделя.
