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

Теорема Гёделя о неполноте — фундаментальное положение математической логики, установленное австрийским логиком и математиком Куртом Гёделем в 1931 году. Теорема утверждает, что для любой достаточно богатой формальной системы (например, содержащей арифметику натуральных чисел) существуют истинные утверждения, которые нельзя ни доказать, ни опровергнуть средствами этой системы. Результат кардинально ограничил возможности формальных методов в математике и оказал глубокое влияние на философию, теоретическую информатику и теорию познания.

История открытия

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

Курт Гёдель, работая над проблемой непротиворечивости арифметики, в 1931 году опубликовал статью «О формально неразрешимых предложениях Principia Mathematica и родственных систем». В ней он показал, что апория «Лжеца» («Данное утверждение ложно») может быть переведена на язык формальной арифметики таким образом, что ни доказательство, ни опровержение получающегося утверждения невозможно в рамках самой системы.

Содержание теоремы

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

Первая теорема

Формальная система достаточно богата, если она позволяет выражать утверждения о натуральных числах и содержит аксиомы арифметики. Непротиворечивость означает, что в этой системе нельзя одновременно доказать утверждение и его отрицание.

Формулировка: Если формальная система арифметики непротиворечива, то она неполна. Существует истинное арифметическое утверждение, которое нельзя доказать, и его отрицание также нельзя доказать.

Это утверждение называют гёделевым утверждением G. Оно построено так, чтобы быть истинным ровно тогда, когда в системе нет его доказательства. Иными словами, G говорит: «Не существует доказательства G». Если бы система могла доказать G, то оно было бы истинным, а значит, доказательства действительно нет, что противоречило бы самому факту доказательства. Если бы система доказала отрицание G, то G было бы ложным, а значит, доказательство существовало бы — опять противоречие. Остаётся единственное: истинное G недоказуемо в системе.

Вторая теорема

Формулировка: Если формальная система арифметики непротиворечива, то невозможно доказать её собственную непротиворечивость средствами этой системы.

То есть любое потенциальное доказательство непротиворечивости системы потребует выхода за её собственные рамки и использования более сильных логических средств. Это стало ударом по программе Гильберта, которая предполагала, что непротиворечивость можно установить без выхода за пределы системы.

Математические основы гёделевой нумерации

Гёдель разработал метод гёделевой нумерации, позволяющий присвоить каждому символу, формуле и доказательству системы уникальное целое число — гёделев номер. Например:

• переменным: 1, 3, 5, …
• символу «+»: 7
• символу «=»: 13
• логической связке «и»: 9

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

Это позволяет формулировать утверждения о свойствах чисел (например, «число x является номером доказательства формулы с номером y») в виде арифметических формул. Так, утверждение G становится чисто арифметическим: «Не существует натурального числа n, такого что n является номером доказательства формулы с номером g» (где g — гёделев номер самой G).

Следствия и интерпретации

Для математики

• Ограничение формальных систем: Любая попытка создать всеобъемлющую и непротиворечивую систему для всей математики обречена на неполноту. Всегда останутся истинные утверждения, недоказуемые в этой системе.
• Неразрешимость задачи полной аксиоматизации: Нельзя создать конечный набор аксиом, из которого выводились бы все истинные арифметические утверждения.
• Влияние на вычислимость и логику: Теорема оказала воздействие на работы Алана Тьюринга по проблеме остановки (неразрешимость). Обе теоремы можно считать логическими аналогами алгоритмической неразрешимости.

Для философии

• Критика позитивизма: Теорема показала принципиальные границы формализма и логического позитивизма. Истина не всегда сводится к доказуемости.
• Математический реализм: Многие философы (например, Роджер Пенроуз) интерпретируют результат как аргумент в пользу существования математической реальности, не сводимой к вашим собственным логическим конструкциям. Человеческое познание, по их мнению, выходит за пределы формальных систем.
• Ограничения искусственного интеллекта: Обсуждается гипотеза, что полностью формальные системы (например, логические программы) не могут постичь все истины, которые доступны интуиции человека.

Для компьютеров и вычислений

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

Критика и уточнения

• Ограничения на «достаточно богатые системы»: Теорема не применима к очень слабым системам (например, логика высказываний или примитивная арифметика сложения без умножения). Такие системы могут быть полными и непротиворечивыми.
• Неполнота не означает непосредственное противоречие: В системе может быть добавлено новое аксиоматическое утверждение, делающее недоказуемое ранее утверждение доказуемым. Но новое «гёделево» утверждение всё равно возникнет.
• Множественность интерпретаций: Не все философские и «парадоксальные» выводы из теоремы имеют математически строгое обоснование. Некоторые популяризации вводят в заблуждение, смешивая формальные системы с реальностью.

См. также

• Парадокс Рассела
• Проблема остановки
• Аксиома выбора
• Теория множеств
• Логические парадоксы

Литература

• Гёдель, К. «О формально неразрешимых предложениях Principia Mathematica и родственных систем».
• Успенский, В. А. «Апология математики».
• Нагель, Э., Ньюман, Дж. Р. «Теорема Гёделя о неполноте».
• Судзуки, М. «Логика, теория множеств и неполнота».