Вначале была аксиома. Гильберт. Основания математики

Для начала Тьюринг сформулировал, что означает думать как машина, механически. Его первая победа заключалась в определении понятия вычислимой функции: это функция, которую способна вычислить машина Тьюринга — вид компьютера без ограничений в пространстве или времени. Одновременно, по другую сторону Атлантического океана, Чёрч пришел к аналогичным выводам, разработав формальную систему, которую назвал лямбда-исчислением. С тех пор под названием тезиса Чёрча — Тьюринга известен постулат, утверждающий, что любое альтернативное определение вычислимости равносильно определению, данному Тьюрингом в терминах его машин. Прибегнув к изобретательному варианту диагонального аргумента Кантора, Тьюринг доказал, что существует намного больше функций, чем машин Тьюринга. Другими словами, существуют невычислимые функции.

Исчислимые функции, как и машины Тьюринга, имеются в счетном количестве, то есть они как иголки в стоге сена всех функций.

Наконец, рассмотрев проблему остановки, он предложил отрицательный ответ на вопрос Гильберта — Entscheidungsproblem: если бы существовала эта процедура, она также была бы способна определить за конечное время, останавливается любая машина Тьюринга через конечное число шагов или входит в бесконечную петлю, когда на входе вводятся некоторые данные. Но последнее, как он доказал, невозможно. Не существует алгоритма, способного получить на входе логическое или математическое высказывание и выдать на выходе: «теорема» или «не теорема» (хотя свойство выводимости действительно разрешимо в ограниченной логике пропозиций).

Сланцевая статуя и портрет Алана Тьюринга в музее Блетчли-Парка.

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

Вскоре Гёдель предположил, что континуум-гипотеза Кантора, которую в 1925 году Гильберт считал почти доказанной на основе выведенной из его теории доказательства изящной техники, была примером неразрешимого высказывания в привычной теории множеств. В 1938 году, ограничиваясь подмножеством конструктивных множеств, Гёдель доказал: невозможно доказать, что она ложная в ZFC. И обратно, в 1963 году Пол Коэн (1934-2007), использовав метод форсинга, доказал: также невозможно доказать, что она истина в ZFC. Гёдель и Коэн построили модели, в которых гипотеза истинна и ложна соответственно. Так что ни утверждение, ни отрицание континуум-гипотезы недоказуемо. То же самое происходит с аксиомой выбора, непротиворечивость и независимость которой относительно остальных аксиом также доказали оба математика. Следовательно, статус аксиомы выбора и континуум-гипотезы в теории множеств аналогичен статусу аксиомы параллельных прямых в геометрии. Рай Кантора — не единственный доступный рай теории множеств.