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

Вторая теорема Гёделя о неполноте звучит следующим образом:

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

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

Использовать эту теорему для доказательства того, что разумная деятельность не сводится к вычислениям, пытались многие. Например, еще в 1961 году известный логик Джон Лукас (John Lucas) выступал с подобной программой. Его рассуждения оказались довольно уязвимыми – однако он и задачу ставил более широко. Роджер Пенроуз использует несколько другой подход, который излагается в книге полностью, «с нуля».

Дискуссии

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

А вот такое перефразирование второй теоремы является ещё более тревожным для основ математики:

Если невозможно доказать непротиворечивость и полноту системы в рамках неё самой, то эта система противоречива.

Следовательно, для установления факта непротиворечивости некоторой системы S необходимо использовать более мощную систему T, но доказательство в рамках T не может быть полностью законченным, пока не доказана непротиворечивость самой T (причём без использования системы S).

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

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

Необходимо также отметить, что теоремы Гёделя применимы только к достаточно сильным системам аксиом. «Достаточно сильный» в данном контексте обозначает, что теория содержит достаточно средств для представления данных, необходимых для доказательства первой теоремы о неполноте. Существенно то, что для этого нужны базовые аксиомы, представляющие операции сложения и умножения, как, к примеру, в арифметике Робинсона Q. Существуют более слабые системы аксиом, которые полны и непротиворечивы, например, арифметика Пресбургера, которая доказывает истинность утверждений первого порядка только относительно сложения.

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

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

Сам Гёдель доказал технически более слабые версии теорем. Первое доказательство теорем в приведённых в статье формулировках впервые было приведено Д.Б. Россером в 1936 году.

По существу, доказательство первой теоремы содержит процесс конструирования утверждения p в рамках формальной системы, которое можно описать на метаязыке следующим образом:

p= «Это утверждение не может быть доказано в рассматриваемой формальной системе»

Как видно, это, всего лишь, современный вариант парадокса лжеца, который в отличие от классической формулировки, не совсем парадоксальный.

Если система аксиом непротиворечива, доказательство теоремы Гёделя показывает, что p (и его отрицание) не могут быть доказаны в рамках системы. Следовательно утверждение p истинно (это утверждение о том, что оно само недоказуемо, и оно действительно недоказуемо). Если система аксиом ω-непротиворечива, то отрицание p также не может быть доказано, и таким образом p невычислимо. В системах, которые ω-противоречивы (но непротиворечивы), либо имеется такая же ситуация, либо утверждение p может быть доказано.

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

Список литературы

гедель математический теорема неполнота

1. В.А. Успенский. Теорема Геделя о неполноте. – М.: Наука, 1982.

2. Теорема Геделя / Э. Нагель, Дж.Р. Ньюмен. – М.: Красанд, 2010. – 120 с.

3. Традиция. Русская энциклопедия: URL: http://traditio.ru/wiki/

[1] Цитата сборника статей «Основания математики» выпущенному в Нью-Йорке в честь 60-летия К. Гёделя.