Теорема Гёделя: почему в математике есть недоказуемые истины

В 1931 году 25-летний австрийский математик Курт Гёдель доказал две теоремы, изменившие представление о природе математики. Его теоремы неполноты показали: никакая достаточно сложная математическая система не может быть одновременно непротиворечивой и полной.

Первая теорема неполноты

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

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

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

Метод доказательства

Гёдель придумал "гёделевскую нумерацию" — способ кодировать математические утверждения числами. Это позволяло математике говорить о себе самой. Дальше он построил утверждение, эквивалентное "это утверждение недоказуемо". Если бы оно было доказуемо, возник бы парадокс. Если недоказуемо — значит, в системе есть истинные недоказуемые утверждения.

Гильбертовская программа

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

Философские следствия

Многие интерпретировали теоремы как "мышление больше формальной логики". Роджер Пенроуз использовал их в аргументе против того, что сознание — вычислимая функция.

Ограничения

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

Гёдель и компьютеры

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

Наследие

Гёдель навсегда изменил философию математики. Его теоремы обсуждаются в логике, информатике, теории знания.