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

Мечта Гильберта

Математика держится на доказательствах. Берут несколько исходных утверждений, аксиом, и по строгим правилам выводят из них теоремы. Гильберт предлагал построить такую систему аксиом для всей математики и доказать две вещи. Первое: она полна, то есть любое верное утверждение в ней можно доказать. Второе: она непротиворечива, то есть в ней нельзя доказать одновременно утверждение и его отрицание.

В 1930 году Гильберт закончил речь в Кёнигсберге словами «Мы должны знать, мы будем знать». Позже их выбили на его надгробии. Как раз на той же конференции, днём раньше, Гёдель коротко объявил о своём результате.

Парадокс лжеца

Начнём со старого парадокса. Рассмотрим фразу: «Это предложение ложно». Если оно истинно, то, как оно и говорит, оно ложно. Если ложно, то утверждение «оно ложно» неверно, значит, оно истинно. Ни то, ни другое не подходит.

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

Получилась формула, которая по смыслу говорит: «Меня нельзя доказать в этой системе». Слово «ложно» заменено на «недоказуемо», и парадокс превращается в теорему.

Две теоремы

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

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

Вторая теорема о неполноте

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

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

При чём тут компьютеры

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

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

Жизнь Гёделя и дружба с Эйнштейном

Курт Гёдель родился 28 апреля 1906 года в Брюнне, нынешнем Брно в Чехии, тогда это была Австро-Венгрия. В детстве родные звали его «господин Почему». Учился в Вене, там и сделал главные открытия. В 1940 году, спасаясь от войны, через Сибирь и Японию добрался до США и до конца жизни работал в Институте перспективных исследований в Принстоне.

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

Ещё одна история: готовясь к экзамену на американское гражданство в 1947 году, Гёдель так тщательно изучил конституцию США, что нашёл в ней, по его мнению, логическую лазейку, через которую страна могла бы превратиться в диктатуру. Эйнштейн и другой друг, экономист Оскар Моргенштерн, сопровождали его на экзамен и с трудом уговорили не спорить с судьёй.

Частые вопросы