Теоремы Гёделя

Две теоремы, разные годы, разные предметы. И длинный список того, чего в них нет

Первая теорема Гёделя: в любой непротиворечивой формальной системе, содержащей арифметику, есть истинные, но недоказуемые в ней утверждения. Вторая говорит, что такая система не может доказать собственную непротиворечивость. Обе они о формальных системах с арифметикой, а не о человеке, сознании или пределах науки. Урок разбирает список популярных «следствий», которых в теоремах нет.

Гёдель, 1929/30 и 1931. Franzén, «Gödel's Theorem: An Incomplete Guide to Its Use and Abuse» (2005). Open Logic Project · 28 мин · обновлено 06.09.2026

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

Первое. Гёдель доказал две разные вещи, в разные годы и о разных предметах. Одна называется теоремой о полноте, другие называются теоремами о неполноте.

Второе. У теоремы о неполноте три условия, и без любого из них её нет. Слова «в любой системе» стирают все три разом.

Третье. Вывод про машину и человека из теорем не следует. Это отдельное рассуждение, и большинство логиков его отвергает.

Теоремы Гёделя остаются самым злоупотребляемым результатом в истории математики, и про злоупотребления написана отдельная книга Franzén, «Gödel's Theorem: An Incomplete Guide to Its Use and Abuse» (2005). Урок устроен так: сначала что доказано, потом чего не доказано. Второе займёт не меньше места, чем первое.

Две теоремы, которые смешивают

Начнём с развода. Смешение двух работ остаётся ошибкой номер один, и без неё половина мистики исчезает.

1929 год, диссертация, напечатана в 1930-м. Теорема о полноте. Предметом работы служит логика первого порядка: это язык с кванторами «все» и «некоторые» из модуля V. Что доказано: всякое утверждение, истинное во всех моделях, доказуемо в исчислении. Коротко: если Γ ⊨ φ, то Γ ⊢ φ. Читается: если следует, то выводимо. «Истинно во всех моделях» значит вот что: при любом наборе объектов и при любом смысле предикатов утверждение остаётся истинным. Это хорошая новость: аппарат вывода не упускает ничего, и за каждым следованием стоит вывод, который можно найти и предъявить.

1931 год. Теоремы о неполноте. Предмет другой: формальные системы, в которых записана арифметика. Что доказано: такая система не решает всех вопросов о числах, и в ней есть утверждение, которое она не доказывает и не опровергает.

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

Одно слово, два свойства

Полнота исчисления есть свойство набора правил вывода, и оно про переход: если из посылок следует, то из них и выводимо. Про истину саму по себе тут не сказано ничего. Урок 18 разбирал это подробно: полная система не докажет «идёт дождь», ведь из пустого набора посылок дождь не следует.

Полнота системы аксиом есть свойство совсем другое, и оно про решения. Система полна в этом смысле, если о каждом утверждении своего языка она выносит приговор: либо доказывает его, либо доказывает его отрицание. Неполна она тогда, когда нашлось утверждение, о котором система не говорит ни да, ни нет. Первое свойство у логики первого порядка есть, и это теорема 1929/30 года. Второго свойства у формальной арифметики нет, и это теорема 1931 года. Одно слово, два разных обещания, и вторая половина мистики вырастает прямо отсюда: услышали «неполна», подставили не то значение и получили загадку из ничего.

Первая теорема целиком

Теперь формулировка. Даю её целиком, со всеми условиями. Выбрасывать из неё нельзя ничего.

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

«Достаточно сильная» имеет точную меру: достаточно арифметики Робинсона. Разберём слова по одному, простыми словами.

Непротиворечивая означает, что система не доказывает утверждение вместе с его отрицанием.

Эффективно аксиоматизируемая означает, что список её аксиом можно перечислить машиной.

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

Неполна означает, что есть утверждение, которое система не доказывает и не опровергает. Три условия, и каждое работает по-настоящему: сейчас уберём их по очереди и посмотрим, что останется от теоремы.

Уберите любое условие, и теоремы нет

Убираем непротиворечивость. Урок 9 показал: из противоречия выводимо что угодно. Отсюда всё и получится. Разбор по шагам, ни один не пропускаю.

Шаг 1. Пусть система доказала какое-то P и вдобавок отрицание P.
Шаг 2. Из P выводимо «P или Q» при любом Q, и это введение дизъюнкции.
Шаг 3. Из «P или Q» и отрицания P выводимо Q, и это дизъюнктивный силлогизм.
Шаг 4. Значит, доказуемо любое Q. И любое отрицание тоже: отрицание есть такое же утверждение.
Шаг 5. Значит, о каждом утверждении система выносит приговор. По второму смыслу слова она полна.

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

Убираем эффективную аксиоматизируемость. Требование выглядит техническим. Оно не техническое: доказательство обязано проверяться, а проверить его нельзя, если неизвестно, что в системе аксиома, а что нет.

Возьмём теперь списком аксиом все истинные утверждения арифметики. Такая система полна задаром: для любого утверждения истинно оно само или его отрицание, значит одно из двух в списке уже лежит. И перечислить этот список машина не может, вот почему: иначе мы получили бы непротиворечивую, эффективно аксиоматизируемую и полную систему арифметики, а её теорема запрещает. Заметьте, чем мы сейчас воспользовались: невозможность перечислить список выведена из самой теоремы, а не откуда-то со стороны.

Убираем достаточную силу. Это условие снимается легче всего, и примеров два, оба настоящие. Арифметика Пресбургера есть арифметика со сложением, но без умножения. Она полна и разрешима. Элементарная геометрия по Тарскому тоже полна и разрешима.

Значит, бывают формальные системы, о которых теоремы Гёделя не говорят ничего. И это не «мы пока не проверяли»: условие не выполнено, и теорема к ним просто не относится. Отсюда рабочая проверка на каждый день: услышав «любая система неполна», спросите, а арифметика в ней выражается? Если нет, теорема ни при чём.

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

Вторая теорема 1931 года говорит о той же системе и об одном определённом утверждении.

Такая система не может доказать собственную непротиворечивость, если она непротиворечива.

Оговорка в конце не украшение: противоречивая система докажет что угодно, в том числе и собственную непротиворечивость, а толку от такого доказательства ноль. Смысл теоремы проще, чем кажется: систему нельзя удостоверить изнутри неё самой. Уверенность в том, что арифметика себе не противоречит, приходит не из доказательства внутри арифметики. Вопрос о том, откуда она приходит, остаётся отдельным, и этот курс на него не отвечает. На этом месте обычно делают печальное лицо. Печалиться не о чем. Ни одна доказанная теорема арифметики от 1931 года не пошатнулась.

Замысел доказательства на пальцах

Дальше идут три идеи, из которых сложено доказательство первой теоремы, и сразу оговорюсь: это не доказательство, а его замысел. Настоящее требует техники, которой в курсе нет и не будет, и притворяться, что вы сейчас увидите доказательство, я не стану.

Идея первая: нумерация. Каждому выражению языка сопоставляется число, и сопоставление устроено так, что по числу выражение восстанавливается однозначно. Теперь утверждения о выражениях превращаются в утверждения о числах: «Вот эта строчка есть доказательство вот этой формулы» становится свойством пары чисел. А про числа система говорить умеет, на то она и арифметика. Именно здесь работает третье условие теоремы.

Идея вторая: самоссылка. Раз система говорит о числах, а числа кодируют выражения, система заговорила о собственных выражениях, и дальше строится утверждение, которое говорит о себе самом.

Идея третья: то самое утверждение. Оно означает примерно следующее: «это утверждение недоказуемо в данной системе». Посмотрим на развилку. Пусть система его доказала, тогда она доказала утверждение, объявляющее себя недоказуемым, и для непротиворечивой системы исход плохой.

Значит, непротиворечивая система его не докажет, а раз не докажет, сказанное в нём и вправду верно. Заметьте оговорку: верно при условии непротиворечивости, и она нам скоро понадобится. Точная развилка устроена тоньше этого абзаца, и разбирают её курсы металогики. Здесь важен только замысел, и он именно таков. Аналогия. Похоже на фразу «это предложение ложно», на старый парадокс лжеца.

Где аналогия ломается. Гёделевское утверждение говорит не об истине, а о доказуемости в определённой системе, и построено оно не в русском языке, а внутри арифметики, числами и по правилам. И главное: из «я лгу» не следует ничего, а отсюда следует теорема. Аналогия остаётся главным каналом, по которому Гёделя перевирают, поэтому в этом уроке она одна, и она помечена.

Чего теоремы не говорят

Теперь список. Он длинный, и каждый пункт стоит прочесть медленно.

Не говорят, что ничего нельзя доказать. Огромное большинство математических утверждений доказуемо. Неполнота говорит не про бессилие.

Не говорят, что математика противоречива. Неполнота и противоречивость противоположны друг другу: противоречивая система как раз полна.

Не относятся к логике высказываний. Она полна и разрешима.

Не относятся к логике первого порядка как таковой. Она полна по теореме самого же Гёделя 1929/30 года.

Не относятся к арифметике Пресбургера. В ней сложение без умножения, и она полна и разрешима. И к элементарной геометрии по Тарскому тоже не относятся.

Не доказывают, что человек умнее машины. Этому отведён следующий раздел.

Не относятся к этике, искусству, политике и «системам» вообще. Требуется формальная система, выражающая арифметику.

Последний пункт стоит развернуть. Государство, компания, мораль, язык, «истина вообще» не являются формальными системами: у них нет ни списка аксиом, ни правил вывода, ни языка с точным синтаксисом. Тут нечего проверять на непротиворечивость и нечего перечислять машиной. К ним теоремы Гёделя не относятся не потому, что кто-то поленился проверить: условие не выполнено, и говорить попросту не о чем.

Отрицания в этом списке не должны заслонить, что теоремы дают. Они дают точный ответ на вопрос, который две тысячи лет казался вопросом веры: можно ли свести всю математику к одному конечному списку аксиом. Ответ отрицательный, и он доказан, а не выбран. И вместе с ним получен способ говорить о самих системах строго: «эта система доказывает про себя вот это» стало проверяемым утверждением, а не оборотом речи.

Аргумент Лукаса и Пенроуза

Отдельного разбора заслуживает самый популярный вывод из теорем: человеческий ум сильнее любой машины. Ход рассуждения такой: машина есть формальная система, и для неё найдётся гёделевское утверждение, которого она не докажет. А человек это утверждение видит и понимает, что оно истинно, значит, человек может больше. Рассуждение известно как аргумент Лукаса и Пенроуза. Большинством логиков оно отвергнуто, и причина конкретная. Вспомните оговорку из разбора выше: гёделевское утверждение истинно при условии, что система непротиворечива, а без этого условия из него не выходит ничего.

Значит, чтобы человек «видел» истинность своего гёделевского утверждения, надо сначала знать: человеческое мышление непротиворечиво. Аргумент это молча предполагает, а непротиворечивость человеческого мышления и есть как раз то, что требовалось бы доказать. Довод, который берёт даром недоказанное допущение, доказательством не является. Заметьте форму возражения: никто не утверждает «человек не умнее машины». Говорят другое: из теорем Гёделя это не следует. Разница ровно та же, что в уроке 3: сломанный довод не делает заключение ложным, а делает его недоказанным, и вопрос остаётся открытым.

Где интуиция даёт другой ответ

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

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

Что дальше

Модуль почти закончен, остался один вопрос, и он практический. Урок 20 спрашивает: что можно поручить машине? Для логики высказываний можно всё: есть механический способ, дающий ответ за конечное число шагов. Для логики первого порядка такого способа не существует, и это доказано в 1936 году. Но кое-что машине поручить всё-таки можно, и последний урок модуля разбирает, что именно.

Вопросы для самопроверки

Что читать

• Franzén, «Gödel's Theorem: An Incomplete Guide to Its Use and Abuse» (2005): Книга специально про злоупотребления: точные формулировки в одной половине, каталог искажений в другой. Если после урока читать одну книгу, то эту.
• Open Logic Project, разделы о неполноте: Открытый учебник по металогике под лицензией CC BY 4.0. Здесь доказательство дано целиком, с нумерацией и построением самоссылочного утверждения. Читать трудно и не обязательно, но именно там видно, чего в нашем изложении на пальцах нет.