Теорема Гёделя о неполноте и вторая теорема Гёделя — две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой формальной системы , в которой можно определить основные арифметические понятия: натуральные числа , 0 , 1 , сложение и умножение .

Первая теорема утверждает, что если формальная арифметика непротиворечива, то в ней существует невыводимая и неопровержимая формула.

Вторая теорема утверждает, что если формальная арифметика непротиворечива, то в ней невыводима формула, содержательно утверждающая непротиворечивость этой арифметики.

Обе эти теоремы были доказаны Куртом Гёделем в 1930 году (опубликованы в 1931) и имеют непосредственное отношение ко второй проблеме из знаменитого списка Гильберта .

История

Ещё в начале XX века Давид Гильберт провозгласил цель аксиоматизировать всю математику, и для завершения этой задачи оставалось доказать непротиворечивость и логическую полноту арифметики натуральных чисел . 7 сентября 1930 года в Кёнигсберге проходил научный конгресс по основаниям математики, и на этом конгрессе 24-летний Курт Гёдель впервые обнародовал две фундаментальные теоремы о неполноте, показавшие, что программа Гильберта не может быть реализована: при любом выборе аксиом арифметики существуют теоремы, которые невозможно ни доказать, ни опровергнуть простыми ( финитными ) средствами, предусмотренными Гильбертом, а финитное доказательство непротиворечивости арифметики невозможно .

Это выступление не было заявлено заранее и произвело ошеломляющий эффект, Гёдель сразу стал всемирной знаменитостью, а программа Гильберта по формализации основ математики потребовала срочного пересмотра. 23 октября 1930 года результаты Гёделя были представлены Венской академии наук Хансом Ханом . Статья с обеими теоремами (« О принципиально неразрешимых положениях в системе Principia Mathematica и родственных ей системах ») была опубликована в научном ежемесячнике Monatshefte für Mathematik und Physik в 1931 году. Хотя доказательство второй теоремы Гёдель дал только в виде идеи, его результат был настолько ясен и неоспорим, что не вызвал сомнений ни у кого. Гильберт сразу признал ценность открытий Гёделя. Первые полные доказательства обеих теорем были опубликованы в книге Гильберта и Бернайса «Основания математики» в 1938 году. В предисловии ко второму тому авторы признали, что для достижения поставленной цели финитных методов недостаточно, и добавили в число логических средств трансфинитную индукцию . В 1936 году Герхард Генцен сумел непротиворечивость аксиом арифметики первого порядка , однако логическая полнота так и осталась недостижимой .

Теорема Гёделя о неполноте

В первоначальной форме

В своей формулировке теоремы о неполноте Гёдель использовал понятие ω-непротиворечивой формальной системы — более сильное условие, чем просто непротиворечивость. Формальная система называется ω-непротиворечивой , если для всякой формулы A ( x ) этой системы невозможно одновременно вывести формулы А ( 0 ), А ( 1 ), А ( 2 ), … и ∃ x ¬ A ( x ) (другими словами, из того, что для каждого натурального числа n выводима формула A ( n ), следует невыводимость формулы ∃ x ¬ A ( x )). Легко показать, что ω-непротиворечивость влечёт простую непротиворечивость (то есть любая ω-непротиворечивая формальная система непротиворечива) .

В процессе доказательства теоремы строится такая формула A арифметической формальной системы S, что :

Если формальная система S непротиворечива, то формула A невыводима в S ; если система S ω-непротиворечива, то формула ¬A невыводима в S . Таким образом, если система S ω-непротиворечива, то она неполна и A служит примером неразрешимой формулы.

Формулу A иногда называют гёделевой неразрешимой формулой .

Интерпретация неразрешимой формулы

В стандартной интерпретации формула A означает «не существует вывода формулы A », то есть утверждает свою собственную невыводимость в S. Следовательно, по теореме Гёделя, если только система S непротиворечива, то эта формула и в самом деле невыводима в S и потому истинна в стандартной интерпретации. Таким образом, для натуральных чисел формула A верна, но в S невыводима .

В форме Россера

В процессе доказательства теоремы строится такая формула B арифметической формальной системы S, что :

Если формальная система S непротиворечива, то в ней невыводимы обе формулы B и ¬B; иначе говоря, если система S непротиворечива, то она неполна , и B служит примером неразрешимой формулы.

Формулу B иногда называют россеровой неразрешимой формулой . Эта формула немного сложнее гёделевой.

Интерпретация неразрешимой формулы

В стандартной интерпретации формула B означает «если существует вывод формулы B , то существует вывод формулы ¬ B ». Согласно же теореме Гёделя в форме Россера, если формальная система S непротиворечива, то формула B в ней невыводима; поэтому, если система S непротиворечива, то формула B верна в стандартной интерпретации .

Обобщённые формулировки

Доказательство теоремы Гёделя обычно проводят для конкретной формальной системы (не обязательно одной и той же), соответственно утверждение теоремы оказывается доказанным только для одной этой системы. Исследование достаточных условий, которым должна удовлетворять формальная система для того, чтобы можно было провести доказательство её неполноты, приводит к обобщениям теоремы на широкий класс формальных систем. Пример обобщённой формулировки :

Всякая достаточно сильная рекурсивно аксиоматизируемая непротиворечивая теория первого порядка неполна.

В частности, теорема Гёделя справедлива для каждого непротиворечивого конечно аксиоматизируемого расширения арифметической формальной системы S.

Полиномиальная форма

После того как Юрий Матиясевич доказал диофантовость любого эффективно перечислимого множества и были найдены примеры универсальных диофантовых уравнений , появилась возможность сформулировать теорему о неполноте в полиномиальной (или диофантовой) форме :

Для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение

${\displaystyle {\begin{aligned}&(elg^{2}+\alpha -(b-xy)q^{2})^{2}+(q-b^{5^{60}})^{2}+(\lambda +q^{4}-1-\lambda b^{5})^{2}+\\&(\theta +2z-b^{5})^{2}+(u+t\theta -l)^{2}+(y+m\theta -e)^{2}+(n-q^{16})^{2}+\\&((g+eq^{3}+lq^{5}+(2(e-z\lambda )(1+xb^{5}+g)^{4}+\lambda b^{5}+\lambda b^{5}q^{4})q^{4})(n^{2}-n)+\\&(q^{3}-bl+l+\theta \lambda q^{3}+(b^{5}-2)q^{5})(n^{2}-1)-r)^{2}+\\&(p-2ws^{2}r^{2}n^{2})^{2}+(p^{2}k^{2}-k^{2}+1-\tau ^{2})^{2}+\\&(4(c-ksn^{2})^{2}+\eta -k^{2})^{2}+(r+1+hp-h-k)^{2}+\\&(a-(wn^{2}+1)rsn^{2})^{2}+(2r+1+\phi -c)^{2}+\\&(bw+ca-2c+4\alpha \gamma -5\gamma -d)^{2}+\\&((a^{2}-1)c^{2}+1-d^{2})^{2}+((a^{2}-1)i^{2}c^{4}+1-f^{2})^{2}+\\&(((a+f^{2}(d^{2}-a))^{2}-1)(2r+1+jc)^{2}+1-(d+of)^{2})^{2}+\\&(((z+u+y)^{2}+u)^{2}+y-K)^{2}=0\end{aligned}}}$

не имеет решений в неотрицательных целых числах, но этот факт не может быть доказан в теории T . Более того, для каждой непротиворечивой теории множество значений параметра K, обладающих таким свойством, бесконечно и алгоритмически неперечислимо .

Степень данного уравнения может быть понижена до 4 ценой увеличения количества переменных.

Набросок доказательства

В своей статье Гёдель даёт набросок основных идей доказательства , который приведён ниже с незначительными изменениями.

Каждому примитивному символу, выражению и последовательности выражений некоторой формальной системы S поставим в соответствие определённое натуральное число . Математические понятия и утверждения таким образом становятся понятиями и утверждениями о натуральных числах, и, следовательно, сами могут быть выражены в символизме системы S. Можно показать, в частности, что понятия «формула», «вывод», «выводимая формула» определимы внутри системы S, то есть можно восстановить, например, формулу F ( v ) в S с одной свободной натурально-числовой переменной v такую, что F ( v ), в интуитивной интерпретации, означает: v — выводимая формула. Теперь построим неразрешимое предложение системы S, то есть предложение A , для которого ни A , ни не-A невыводимы, следующим образом:

Формулу в S с точно одной свободной натурально-числовой переменной назовём класс-выражением . Упорядочим класс-выражения в последовательность каким-либо образом, обозначим n -е через R ( n ), и заметим, что понятие «класс-выражение», также как и отношение упорядочения R можно определить в системе S. Пусть α — произвольное класс-выражение; через [α; n ] обозначим формулу, которая образуется из класс-выражения α заменой свободной переменной на символ натурального числа n . Тернарное отношение x = [ y ; z ] тоже оказывается определимым в S. Теперь определим класс K натуральных чисел следующим образом:

n ∈ K ≡ ¬Bew[ R ( n ); n ]    (*)

(где Bew x означает: x — выводимая формула ). Так как все определяющие понятия из этого определения можно выразить в S, то это же верно и для понятия K , которое из них построено, то есть имеется такое класс-выражение C , что формула [ C ; n ], интуитивно интерпретируемая, обозначает, что натуральное число n принадлежит K . Как класс-выражение, C идентично некоторому определённому R ( q ) в нашей нумерации, то есть

C = R ( q )

выполняется для некоторого определённого натурального числа q . Теперь покажем, что предложение [ R ( q ); q ] неразрешимо в S. Так, если предложение [ R ( q ); q ] предполагается выводимым, тогда оно оказывается истинным, то есть, в соответствии со сказанным выше, q будет принадлежать K , то есть, в соответствии с (*), будет выполнено ¬Bew[ R ( q ); q ], что противоречит нашему предположению. С другой стороны, если предположить выводимым отрицание [ R ( q ); q ], то будет иметь место ¬ q ∈ K , то есть Bew[ R ( q ); q ] будет истинным. Следовательно, [ R ( q ); q ] вместе со своим отрицанием будет выводимо, что снова невозможно.

Связь с парадоксами

В стандартной интерпретации гёделева неразрешимая формула A означает «не существует вывода формулы A », то есть утверждает свою собственную невыводимость в системе S. Таким образом, A является аналогом парадокса лжеца . Рассуждения Гёделя в целом очень похожи на парадокс Ришара . Более того, для доказательства существования невыводимых утверждений может быть использован любой .

Выражаемое формулой A утверждение не содержит порочного круга, поскольку изначально утверждается только, что некоторая конкретная формула, явную запись которой получить несложно (хоть и громоздко), недоказуема. «Только впоследствии (и, так сказать, по воле случая) оказывается, что эта формула в точности та, которой выражено само это утверждение» .

Вторая теорема Гёделя

В формальной арифметике S можно построить такую формулу, которая в стандартной интерпретации является истинной в том и только в том случае, когда теория S непротиворечива. Для этой формулы справедливо утверждение второй теоремы Гёделя:

Если формальная арифметика S непротиворечива, то в ней невыводима формула, содержательно утверждающая непротиворечивость S .

Иными словами, непротиворечивость формальной арифметики не может быть доказана средствами этой теории. Однако, могут существовать доказательства непротиворечивости формальной арифметики, использующие средства, невыразимые в ней.

Набросок доказательства

Сначала строится формула Con , содержательно выражающая невозможность вывода в теории S какой-либо формулы вместе с её отрицанием. Тогда утверждение первой теоремы Гёделя выражается формулой Con ⊃ G , где G — Гёделева неразрешимая формула. Все рассуждения для доказательства первой теоремы могут быть выражены и проведены средствами S, то есть в S выводима формула Con ⊃ G . Отсюда, если в S выводима Con , то в ней выводима и G . Однако, согласно первой теореме Гёделя, если S непротиворечива, то G в ней невыводима. Следовательно, если S непротиворечива, то в ней невыводима и формула Con .

Историческое влияние

Специалисты дают самые разные, иногда даже полярные оценки исторической значимости теорем Гёделя. Часть учёных считает, что эти теоремы «перевернули» основания математики или даже всю теорию познания , и значение гениального открытия Гёделя будет постепенно открываться ещё долгое время . Другие же (например, Бертран Рассел ) призывают не преувеличивать, поскольку теоремы опираются на финитный формализм Гильберта .

Вопреки распространённому заблуждению, теоремы о неполноте Гёделя не предполагают, что некоторые истины так и останутся навеки непознанными. Кроме того, из этих теорем не следует, что человеческие способности к познанию так или иначе ограничены. Нет, теоремы всего лишь показывают слабости и недостатки формальных систем .

Рассмотрим, например, следующее доказательство непротиворечивости арифметики .

Допустим, что аксиоматика Пеано для арифметики противоречива. Тогда из неё можно вывести любое утверждение, в том числе ложное. Однако все аксиомы Пеано очевидным образом истинны, а из истинных утверждений не может следовать ложный вывод — получаем противоречие. Следовательно, арифметика непротиворечива.

С точки зрения повседневной человеческой логики, это доказательство приемлемо и убедительно. Но оно не может быть записано по правилам теории доказательств Гильберта, поскольку в этих правилах семантика заменена на синтаксис, а истинность — на «выводимость» . В любом случае теоремы Гёделя подняли философию математики на новый уровень.

См. также

Примечания

Комментарии

Источники

Литература

• Бирюков Б. В. , Тростников В. Н. Жар холодных чисел и пафос бесстрастной логики. Формализация мышления от античных времен до эпохи кибернетики. — М. : Едиториал УРСС, 2004. — 232 с. — ISBN 5-354-00310-5 .
• Ершов Ю. Л. , программа А. Гордона от 16 июня 2003 года.
• Ершов Ю. Л. , Палютин Е.А. Математическая логика. — М. : Наука, 1987. — 336 с.
• Клини Стефен Коул. . — М. : ИЛ, 1957. — 526 с.
• Клини Стефен Коул. . — М. : «Мир», 1973. — 480 с.
• Кордонский М. . — ISBN 5-946448-001 -04.
• Коэн П. Дж. // Успехи математических наук . — 1974. — Т. 29 , № 5(179) . — С. 169–176 .
• Мендельсон Эллиот. . — М. : «Наука», 1971. — 320 с.
• Паршин А. Н. Размышления над теоремой Гёделя // Историко-математические исследования . — М. : Янус-К, 2000. — № 40 (5) . — С. 26—55 .
• Пиньейро Г. Э. У интуиции есть своя логика. Гёдель. Теоремы о неполноте // Наука. Величайшие теории. — М. : Де Агостини, 2015. — Вып. 17 . — ISSN .
• Сосинский А. Б. // Летняя школа . — Дубна, 2006.
• Успенский В. А. . — М. : Наука, 1982. — 110 с. — ( Популярные лекции по математике ).
• Успенский В. А. // Летняя школа . — Дубна, 2007.
• Davis, Martin (ed.). . — New York: Raven Press, 1965. — 440 p.
• Heijenoort, Jean van (ed.). . — Cambridge, Massachusetts: Harvard University Press, 1967. — 660 p.

Ссылки

• Музыкантский А. (неопр.) . Дата обращения: 10 сентября 2017.

Библиография — статьи Гёделя

• 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38 : 173—198.
• 1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. and On formally undecidable propositions of Principia Mathematica and related systems I in Solomon Feferman , ed., 1986. Kurt Gödel Collected works, Vol. I . Oxford University Press: 144—195. - Оригинальный немецкий текст с параллельным английским переводом, с элементарным введением, написанным Стивеном Клини .
• Hirzel, Martin, 2000, . - Современный перевод Марина Херцеля.
• 1951, Some basic theorems on the foundations of mathematics and their implications in Solomon Feferman , ed., 1995. Kurt Gödel Collected works, Vol. III . Oxford University Press: 304—323.