Теорема Гёделя о неполноте формальной арифметики. Геделя теоремы о неполноте

Идея доказательства заключается в том, чтобы построить такое выражение, которое свидетельствовало бы о своей

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

Первый этап - установление соответствия между формальной арифметикой и множеством целых чисел (гедели-зации);

Второй этап - построение некоторого специального свойства о котором неизвестно, является ли оно теоремой формальной арифметики или нет;

Третий этап - подстановка в вместо х определенного целого числа, связанного с самим т. е. замещение этими числами всех

Первый этап. Геделизация формальной арифметики

Формальная арифметика может быть арифметизирована (т. е. геделизирована) следующим образом: каждой ее теореме ставится в соответствие некоторое число. Однако так как всякое число также является теоремой, то всякая теорема может рассматриваться, с одной стороны, в качестве теоремы формальной арифметики, а с другой - как теорема над множеством теорем формальной арифметики, т. е. в качестве метатеоремы, соответствующей доказательству некой теоремы.

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

Теперь более конкретно и подробно изложим полученные результаты.

Во-первых, мы можем связать с каждым символом и формальной арифметики специальное кодовое обозначение, называемое в данном случае геделевым номером

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

В-третьих (и это существенно), каждому доказательству последовательности аксиом и правил подстановки (или правил замещения) ставится в соответствие число где обозначает последовательность теорем, используемых при доказательстве

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

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

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

Сформулируем следующее положение.

Формальная метаарифметика содержится в множестве натуральных чисел, а оно само содержится в интерпретации формальной арифметики.

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

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

Таблица 3.2

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

где простое число.

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

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

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

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

Это разложение означает, что доказательство теоремы содержит два этапа: один соответствует числу 1981027125 253, а другой - числу 1981027125 211. Разлагая снова на простые множители каждое из этих чисел, получим

Из таблицы кодирования алфавита формальной арифметики (табл. 3.2) находим, что нашим геделевым номерам для Этих двух чисел

будет соответствовать следующее доказательство:

Из формулы следует формула

Таким образом, в метаарифметике получено значение исходного числа из формальной арифметики.

Второй этап. Лемма Геделя

Всякому числу Т, связанному с доказательством, соответствует теорема доказуемая в формальной арифметике. “Геделизированную” формальную арифметику называют арифметизированной формальной арифметикой. Поскольку каждая аксиома и каждое правило арифметизированной формальной арифметики соответствуют какой-нибудь арифметической операции, то с помощью систенатизированной проверки можно определить, соответствует ли данное число Т доказательству какой-то теоремы Числа Т и образуют в этом случае пару сопряженных чисел. Выражение и являются сопряженными” Представимо внутри самой арифметизированной формальной арифметики. Это означает, что существует геделев номер который выражает в цифровой форме это утверждение.

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

Кантора и Ришара): оно одновременно является истинным выражением для подстановки и результирующим термом. Эту специальную подстановку будем обозначать как Так формула означает, что число есть геделев номер, получаемый при выполнении подстановки - к выражению А:

Затем Гедель строит выражение (о котором неизвестно, представляет ли оно собой теорему или не-теорему), в которое вводит эту подстановку. Выражение имеет следующий вид:

Третий этап. Завершающая подстановка

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

Это второе выражение обозначим через а его геделев номер через Е. Дадим интерпретации выражения е.

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

Вторая интерпретация. Не существует арифметизированного доказательства Т теоремы которое было бы -замещением Е. Итак, если не существует доказательства, то потому, что само по себе не является теоремой. Отсюда вытекает третья интерпретация.

Третья интерпретация. Выражение, для которого геделев номер есть -замещение Е, не является теоремой арифметизированной формальной арифметики. Но в этом и заключается противоречие, так как по построению именно само является -замещением Е и номер есть не что иное по построению, как сам номер Е. Отсюда вытекает последняя интерпретация е.

Успенский В.А.

Теорема Геделя о неполноте.1994.

Theoretical Computer Science 130,1994, pp.273-238.

Пожалуй, теорема Геделя о неполноте является воистину уникальной. Уникальной в том, что на нее ссылаются, когда хотят доказать "все на свете" - от наличия богов до отсутствия разума. Меня всегда интересовал более "первичный вопрос" - а кто из ссылающихся на теорему о неполноте смог-бы не только сформулировать ее, но и доказать? Я публикую данную статью по той причине, что в ней изложена вполне доступная формулировка теоремы Геделя. Рекомендую предварительно ознакомиться со статьей Туллио Редже Курт Гедель и его знаменитая теорема

Вывод о невозможности универсального критерия истины является

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

теоремы Геделя о неразрешимости с его собственной теорией истины, согласно

которому универсального критерия истины не может быть даже для относительно

узкой области теории чисел, а значит, и для любой науки, использующей

арифметику. Естественно, что этот результат применим a fortiori к понятию истины

в любой нематематической области знания, в которой широко

используется арифметика.

Карл Поппер

Успенский Влaдимиp Aндpеевич pодился 27 ноябpя 1930 г. в г. Москве. Окончил мехaнико-мaтемaтический фaкультет МГУ (1952). Доктоp физико-мaтемaтических нaук (1964). Пpофессоp, заведующий кaфедpой мaтемaтической логики и теоpии aлгоpитмов мехaнико-мaтемaтического фaкультетa (1966). Читает курсы лекций "Введение в математическую логику", "Вычислимые функции", "Теорема Геделя о полноте". Подготовил 25 кандидатов и 2 докторов наук

1. Постановка задачи

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

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

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

1.1.1. Алфавит

Под алфавитом мы понимаем конечный набор элементарных знаков (то есть - вещей, которые невозможно разбить на составные части). Эти знаки называются буквами алфавита. Под словом алфавита мы понимаем конечную последовательность букв. Например, обыкновенные слова в английском языке (включая имена собственные) являются словами 54-хбуквенного алфавита (26 маленьких букв, 26 прописных, тире и апостроф). Другой пример - натуральные числа в десятичной записи являются словами 10-тибуквенного алфавита, чьи буквы - знаки: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Для обозначения алфавитов мы будем использовать обыкновенные заглавные буквы. Если L - алфавит, то L? будет обозначать множество всех слов алфавита L, - слов, образованных из его букв. Мы предположим, что любой язык имеет свой алфавит, так что все выражения этого языка (т. е. - имена различных объектов, утверждения относительно этих объектов и т.д.) являются словами этого алфавита. Например, любое предложение английского языка, равно как и любой текст, написанный по-английски, может рассматриваться как слово расширенного алфавита из 54-х букв, включающего также знаки пунктуации, междусловный пробел, знак красной строки и, возможно, некоторые другие полезные знаки. Предполагая, что выражения языка являются словами некоторого алфавита, мы, таким образом, исключаем из рассмотрения "многослойные" выражения типа???f(x)dx. Однако, это ограничение не слишком существенно, так как любое подобное выражение, при использовании подходящих конвенций, может быть "растянуто" в линейную форму. Любое множество М, содержащееся в L? называется словным множеством алфавита L. Если мы просто говорим, что М - словное множество, то мы подразумеваем, что оно является словом некоторого алфавита. Теперь сформулированное выше предположение о языке может быть перефразировано следующим образом: в любом языке любое множество выражений является словным множеством.

1.1.2. Множество истинных утверждений

Мы предположим, что нам задано подмножество Т множества L? (где L алфавит некоторого рассматриваемого нами языка), которое называется множеством "истинных утверждений" (или просто "истин"). Переходя непосредственно к подмножеству Т, мы опускаем следующие промежуточные шаги рассуждения: во-первых, какие именно слова алфавита L являются корректно образованными выражениями языка, то есть - имеющими определенное значение в нашей интерпретации этого языка (например, 2+3, х+3, х=у, х=3, 2=3, 2=2 являются корректно образованными выражениями, в то время как выражения типа +=х таковыми не являются); во-вторых, какие именно выражения являются формулами, т.е. могут зависеть от параметра (например, х=3, х=у, 2=3, 2=2); в третьих, какие именно из формул являются закрытыми формулами, т.е. утверждениями, не зависящими параметров (например, 2=3, 2=2); и наконец, какие именно закрытые формулы являются истинными утверждениями (например, 2=2).

1.1.3. Фундаментальная пара языка

1.2. "Недоказуемые"

"Недоказуемые" значит не имеющие доказательства.

1.3. Доказательство

Несмотря на то что термин "доказательство" является, возможно, одним из важнейших в математике (Бурбаки начинают свою книгу "Основания математики" словами: "Со времени древних греков сказать "математика" значило то же, что сказать "доказательство""), он не имеет своей точной дефиниции. В целом, понятие доказательства со всеми его смысловыми ответвлениями относится, скорей, к области психологии, нежели к математике. Но как бы то ни было, доказательство - это просто аргумент, который мы сами находим вполне убедительным для того, чтобы убедить всех остальных.

Будучи записано, доказательство становится словом в некотором алфавите Р, так же как любой английский текст является словом алфавита L, пример которого был приведен выше. Множество всех доказательств образуют подмножество (и довольно-таки обширное подмножество) множества Р?. Мы не будем пытаться дать точное определение этой одновременно "наивной" и "абсолютной" концепции доказательства, или - что равносильно - дать определение соответствующему подмножеству Р?. Вместо этого мы рассмотрим формальный аналог этого смутного понятия, для обозначения которого в дальнейшем мы все же будем пользоваться термином "доказательство". Этот аналог имеет две весьма важные особенности, кои отличают его от интуитивного понятия (хотя интуитивная идея доказательства все же отражает в некоторой степени эти особенности). Прежде всего мы допустим, что существуют разные концепции доказательства, то есть - допустимы разные подмножества доказательств в Р?, и даже больше того: мы, на деле, будем допускать, что сам алфавит доказательств Р может изменяться. Далее мы потребуем, чтобы для каждой такой концепции доказательства существовал эффективный метод, другими словами, алгоритм, который бы с необходимостью определял, является ли данное слово алфавита Р доказательством или нет. Мы также предположим, что существует алгоритм, с помощью которого всегда можно определить, какое именно утверждение доказывает данное доказательство. (Во многих ситуациях доказываемым утверждением просто является последнее утверждение в последовательности шагов, образующих доказательство.)

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

(1) У нас имеются алфавит L (алфавит языка) и алфавит Р (алфавит доказательства).

(2) Нам дано множество Р, являющееся подмножеством Р?, и чьи элементы называются "доказательствами". В дальнейшем мы будем предполагать, что также у нас имеется алгоритм, который позволяет нам определить является ли произвольное слово алфавита Р элементом множества Р, то есть доказательством, или нет.

(3) Также у нас есть функция? (для нахождения того, что именно было доказано), чья область определения? удовлетворяет условию Р???Р?, и чья область значений находится в Р?. Мы предполагаем, что у нас есть алгоритм, который вычисляет эту функцию (точное значение слов "алгоритм вычисляет функцию" следующее: значения функции получаются при помощи этого алгоритма - набора специальных правил преобразования). Мы будем говорить, что элемент р? Р есть доказательство слова?(р) алфавита L.

Тройка, удовлетворяющая условиям (1)-(3) называется дедуктивной системой над алфавитом L.

Для читателя, знакомого с обычным способом определения "доказательства" в терминах "аксиома" и "правило вывода", мы сейчас поясним, как этот метод может рассматриваться в качестве специального случая определения, данного в параграфе 1.3.2. То есть - доказательство обычно определяется как последовательность таких выражений языка, каждое из которых является либо аксиомой, либо ранее полученным из уже существующих утверждений при помощи одного из правил вывода. Если мы добавим новое слово * к алфавиту нашего языка, то мы сможем записать такое доказательство в виде слова составленного при помощи полученного в результате такой модификации алфавита: последовательность выражений становится словом C1*C2*...*Cn. В таком случае, функция, определяющая, что именно было доказано, своим значением имеет часть этого слова, стоящую сразу за последней в последовательности буквой *. Алгоритм, существование которого требуется в части 1.3.2. определения, может легко быть сконструирован, как только мы точно определим какое-либо из принятых значений слов "аксиома" и "правила вывода".

1.4.Попытки точной формулировки теоремы о неполноте

1.4.1. Первая попытка

"При определенных условиях для фундаментальной пары языка алфавита L и дедуктивной системы над L - всегда существует слово в Т, не имеющее доказательства". Этот вариант все еще выглядит смутным. В частности, мы могли бы запросто придумать сколько угодно дедуктивных систем, имеющих очень немного доказуемых слов. Например, в пустой дедуктивной системе (где Р = ?) совсем нет слов, у которых были бы доказательства.

1.4.2. Вторая попытка

Есть другой, более естественный подход. Предположим, нам задан язык - в том смысле, что нам задана фундаментальная пара этого языка. Теперь мы будем искать такую дедуктивную систему над L (интуитивно, мы ищем технику доказательства), при помощи которой мы могли бы доказать как можно больше слов из Т, в пределе все слова из Т. Теорема Геделя описывает ситуацию, в которой такая дедуктивная система (посредством коей, каждое слово в Т было бы доказуемо) не существует. Таким образом, нам бы хотелось сформулировать следующее утверждение:

"При определенных условиях относительно фундаментальной пары не существует такой дедуктивной системы, в которой бы каждое слово из Т имело бы доказательство".

Однако такое утверждение, очевидно, ложно, так как необходимо лишь взять такую дедуктивную систему, в которой Р = L, Р = Р? и?(р) = р для всех р из Р?; тогда каждое слово из L? является тривиально доказуемым. Следовательно, нам нужно принять некоторое ограничение на то, какими дедуктивными системами мы пользуемся.

1.5. Непротиворечивость

Было бы вполне естественно потребовать, что только "истинные утверждения", то есть только слова из Т, могут быть доказаны. Мы будем говорить, что дедуктивная система является непротиворечивой относительно фундаментальной пары, если?(Р)?Т. Во всех последующих рассуждениях нас будут интересовать только такие непротиворечивые дедуктивные системы. Если же нам задан язык, то было бы чрезвычайно соблазнительно найти такую непротиворечивую дедуктивную систему, в которой каждое истинное утверждение имело бы доказательство. Интересующий нас вариант теоремы Геделя в точности утверждает, что при определенных условиях относительно фундаментальной пары, невозможно найти такую дедуктивную систему.

1.6. Полнота

Говорится, что дедуктивная система полна относительно фундаментальной пары, при условии если?(Р)?Т. Тогда наша формулировка теоремы о неполноте приобретает следующий вид:

При определенных условиях относительно фундаментальной пары, не существует такой дедуктивной системы над L, которая была бы одновременно полна и непротиворечива относительно.

1. Формальные аксиоматические теории и натуральные числа

2. Формальная арифметика и ее свойства

3. Теорема Гёделя о неполноте

4. Гёдель и его роль в математической логике XX в

Эта теорема, уже неоднократно встречавшаяся нам, утверждает, что любая непротиворечивая формальная аксиоматическая теория, формализующая арифметику натуральных чисел, не является (абсолютно) полной. В настоящем параграфе дается доказательство этой теоремы, опирающееся на идеи и методы теорий алгоритмов. Тем самым будет еще раз продемонстрирована на самом высоком уровне теснейшая связь математической логики и теории алгоритмов - двух математических дисциплин, образующих фундамент всей современной математики. Наше изложение будет основываться на доказательстве, разработанном М.Арбибом.

После доказательства теоремы 35.7 о том, что существует перечислимое, но неразрешимое множество натуральных чисел, было заявлено, что она фактически включает в себя в неявном виде теорему Гёделя о неполноте формальной арифметики. Цель настоящего параграфа состоит в том, чтобы обосновать это заявление. Таким образом, в рамках общей теории алгоритмов, кроме тех теорем, которые были доказаны в двух предыдущих параграфах, будет продемонстрировано продвижение теории алгоритмов в направлении решения чисто логических проблем. Для этого сначала предстоит увязать терминологию логической проблемы о неполноте формальной арифметики с методологической терминологией общей теории алгоритмов, методами которой эта проблема будет решена. При этом утверждение теоремы 35.7 о существовании перечислимого, но неразрешимого множества натуральных чисел будет основополагающей предпосылкой для доказательства теоремы Гёделя, которую мы докажем в следующей формулировке: "Каждая адекватная со-непротиворечивая формальная арифметика неполна". Далее, мы поясним, что будем понимать под формальной арифметикой, а также определим и разъясним те понятия, которые участвуют в приведенной формулировке теоремы Гёделя. Начнем с формальных аксиоматических теорий.

Формальные аксиоматические теории и натуральные числа

Ранее было определено понятие формальной аксиоматической теории. Чтобы задать такую теорию T , нужно задать алфавит (счетное множество символов); в множестве всех слов, составленных из букв данного алфавита, выделить подмножество, элементы которого будут называться формулами (или правильно построенными выражениями) данной теории; в множестве формул выделить те, которые будут называться аксиомами теории; наконец, должно быть задано конечное число отношений между формулами, называемых правилами вывода. При этом должны существовать эффективные процедуры (алгоритмы) для определения того, являются ли данные слова (выражения) формулами (т.е. правильно построенными выражениями), являются ли данные формулы аксиомами и, наконец, получается ли одна данная формула из ряда других Данных формул с помощью данного правила вывода. Это означает, что множество всех формул разрешимо и множество всех аксиом разрешимо. Следовательно, каждое из этих множеств перечислимо.

Понятия вывода и теоремы в формальной аксиоматической теории даны в определении 28.2.

Все теоремы, приводимые в настоящей лекции, в соответствии с нашей терминологией являются фактически метатеоремами, т.е. теоремами о свойствах (формальных) аксиоматически* теорий. Но поскольку здесь никакой конкретной аксиоматической теории мы не рассматриваем, никаких теорем такой теории не доказываем, т.е. никаких теорем, кроме метатеорем, здесь не будет, то мы метатеоремы будем называть просто теоремами.

Теорема 37.1. Множество всех теорем формальной аксиоматической теории Т перечислимо.

Доказательство. Мы уже отметили, что множество аксиом формальной теории перечислимо, т. е. мы можем их эффективно перенумеровать A_1,A_2,A_3,\ldots . Поскольку все формулы состоят из конечного числа букв (символов), все выводы содержат конечное число формул и каждый вывод использует лишь конечное число аксиом, то ясно, что для каждого натурального п существует лишь конечное число выводов, имеющих не более чем п формул (шагов) и использующих только аксиомы \{A_1,A_2,\ldots,A_n\} . Следовательно, двигаясь от n=1 к n=2,~ n=3 и т.д., можно эффективно перенумеровать все теоремы данной теории. Это и означает, что множество теорем перечислимо.

Теперь от произвольных формальных теорий будем переходить к таким, которые так или иначе имеют дело с натуральными числами. Если мы хотим в нашей теории говорить о подмножестве Q множества натуральных чисел, то мы должны иметь эффективный способ выписывания для каждого натурального п формулы W_n , означающей, что n\in Q . Более того, если мы сможем доказать, что формула W_n является теоремой теории T тогда и только тогда, когда n\in Q , то будем говорить, что теория T полуполна для Q (или что в T имеется полуполное описание Q ). Точнее, это определение сформулируем так.

Определение 37.2. Теория T называется полуполной для множества натуральных чисел Q\subseteq \mathbb{N} , если существует перечислимое множество формул W_0,W_1,\ldots,W_n,\ldots , такое, что .

Определение 37.3. Теория T называется полной для Q , если она полуполна для Q и мы также имеем формулу \lnot W_n , которая интерпретируется как n\notin Q , и мы можем доказать, что \lnot W_n является теоремой теории T тогда и только тогда, когда n\notin Q . Другими словами, теория T полна для Q , если в T для каждого п мы можем установить, принадлежит оно Q или нет. Точнее, это означает, что теория T называется полной для множества натуральных чисел T , если она полуполна для Q и полуполна для его дополнения \overline{Q} .

Теорема 37.4. Если теория T полуполна для множества Q , то Q перечислимо.

Доказательство. По определению полуполноты T для Q множество Q есть множество номеров тех формул из некоторого перечислимого множества \{W_0,W_1,\ldots,W_n,\ldots\} формул, которые являются теоремами теории T , т.е. принадлежит и множеству \operatorname{Th}(T) . Таким образом, Q есть множество номеров всех формул из множества \operatorname{Th}(T)\cap \{W_0,W_1,\ldots,W_n,\ldots\} . Каждое из этих пересекаемых множеств перечислимо: первое - по предыдущей теореме 37.1, второе - по сказанному в начале доказательства. Следовательно, и их пересечение, по теореме 35.5, перечислимо. Но тогда пере-цислимо и множество номеров тех формул, которые входят в это пересечение.

Следствие 37.5. Если Q перечислимое, но неразрешимое множество натуральных чисел, то никакая формальная теория не может быть полной для Q .

Доказательство. Если множество Q перечислимо, но неразрешимо, то в силу теоремы 35.6 его дополнение \overline{Q} неперечис-лимо. Тогда по теореме 37.4 никакая теория T не является полуполной для \overline{Q} . Следовательно, никакая теория T неполна для Q .

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

Формальная арифметика и ее свойства

Формальная арифметика как формальная аксиоматическая теория строится на базе формализованного исчисления предикатов, рассмотренного ранее. Предметные переменные здесь будем называть числовыми, потому что вместо них будем подставлять натуральные числа.

Предметная переменная называется свободной в формуле, если она не стоит под знаком квантора (общности или существования), и связанной - в противном случае. Формула называется замкнутой, если все ее предметные переменные связаны, и открытой, если в ней имеются свободные переменные. Замыканием формулы F называется формула C(F) , получающаяся из F дописыванием спереди кванторов общности по всем переменным, свободным в F . Ясно, что для любой F формула C(F) замкнута. Если F замкнута, то C(F)=F .

Функция C(F) вычислима. Отсюда следует, что класс замкнутых формул разрешим, поскольку.Рему принадлежит тогда и только тогда, когда C(F)=F , и для распознавания этого равенства существует вычислительная процедура.

С понятием подстановки в формулу мы уже знакомы. Если в формулу F вместо символа (слова) X везде, где он входит в F , вставить слово (формулу) H , то получим новое слово (формулу), обозначаемое S_X^HF и называемое результатом подста-новки в F слова H вместо слова X . Тогда ясно, что

\begin{gathered}S_X^H(\lnot F)\equiv \lnot S_X^HF;\qquad S_X^H(F\to G)\equiv S_X^HF\to S_X^HG;\\ \text{esli}~ i\ne j,~ \text{to}~ S_{x_i}^N(\forall x_j)(F)\equiv (\forall x_j)S_{x_i}^NF,~ S_{x_i}^N(\exists x_j)(F)\equiv (\exists x_j)S_{x_i}^NF. \end{gathered}

Имея дело с натуральными числами, мы хотели бы иметь возможность подставлять их в формулы формальной теории (арифметики), т.е. иметь возможность говорить о числах на языке нашей формальной теории. Для этой цели в формальной теории необходимо иметь слова, которые служили бы названиями натуральных чисел. Такие слова называются нумералами. Нумерал числа п обозначается n^{\ast} . Требование к этим названиям (именам) вполне естественное: различные числа должны называться различными именами, т.е. если m\ne n , то m^{\ast}\ne n^{\ast} . (Идея введения нумералов состоит в том, чтобы разделить вещи и имена этих вещей.)

Таким образом, в формулы арифметики мы будем подставлять вместо числовых переменных x_1,x_2,x_3,\ldots не сами натуральные числа m,n,k,\ldots , а их нумералы (имена) m^{\ast},n^{\ast},k^{\ast},\ldots соответственно.

Наконец, мы можем сформулировать последнее требование (аксиому), которое мы предъявляем к формальной арифметике. Назовем его аксиомой арифметики: если предметная переменная jc, не связана в F , то

\text{(AA)}\colon~ S_{x_i}^{n^{\ast}}F\to (\exists x_i)(F).

Если ввести для S_{x_i}^{n^{\ast}}F обозначение F(n^{\ast}) , то эта аксиома принимает вид:

\text{(AA)}\colon~ F(n^{\ast})\to (\exists x_i)(F).

Это исключительно естественное требование: если формула F превращается в истинное высказывание при подстановке в нее вместо переменной x_i какого-нибудь натурального числа n^{\ast} , то истинно и высказывание (\exists x_i)(F) .

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

Итак, определившись с понятием формальной арифметики, посвятим оставшуюся часть этого пункта понятиям ю-непротиво-речивости, адекватности и полноты этой формальной теории, участвующим в точной формулировке теоремы Гёделя.

Начнем с понятия непротиворечивости. Как и всякая аксиоматическая теория, формальная арифметика называется непротиворечивой, если в ней нельзя доказать какое-либо утверждение и его отрицание, т.е. если не существует такой формулы F , что одновременно \vdash F и \vdash\lnot F .

Предположим теперь, что для некоторой формулы G(x) , содержащей свободно единственную предметную переменную х, установ-дено, что для всех натуральных чисел n=0,1,2,3,\ldots . Даже если в формальной арифметике невозможно доказать \vdash (\forall x)(G(x)) , мы конечно же можем считать это утверждение следствием приведенного списка теорем. Следовательно, если в теории удастся доказать теорему , то такую формальную арифметику следует считать противоречивой.

Определение 37.6. Формальная арифметика называется ω-непротиворечивой, если в ней нет такой формулы G(x) с единственной свободной предметной переменной x , что для всех натуральных чисел n справедливы теоремы \vdash G(n^{\ast}) и \vdash\lnot (\forall x)(G(x)) .

Теорема 37.7. Если формальная арифметика ^-непротиворечива, то она непротиворечива.

Доказательство. В самом деле, если бы она была противоречива, то, как доказано в §27, после определения 27.1, все ее формулы были бы теоремами, в том числе и те, которые создают ω-противоречивость формальной арифметики, и последняя была бы ω-противоречива.

Определение 37.8. Назовем n-местный предикат P(x_1,\ldots,x_n) над множеством натуральных чисел N вполне представимым в формальной арифметике, если существует такая формула F(x_1,\ldots,x_n) , свободными предметными переменными которой являются п переменных x_1,\ldots,x_n (и только они), что:

а) для каждого набора n натуральных чисел (a_1,\ldots,a_n) , для которого предикат P превращается в истинное высказывание P(a_1,\ldots,a_n) , имеет место теорема: \vdash F(a_1^{\ast},\ldots,a_n^{\ast}) ;

б) для каждого набора n натуральных чисел (a_1,\ldots,a_n) , для которого предикат P превращается в ложное высказывание P(a_1,\ldots,a_n) , имеет место теорема: \vdash\lnot F(a_1^{\ast},\ldots,a_n^{\ast}) .

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

Разъясним теперь понятие адекватности формальной арифметики, участвующее в формулировке теоремы Гёделя. Мы хотели бы иметь возможность отвечать на вопросы о перечислимых множествах в такой арифметике. В теореме 37.4 мы показали, что лишь перечислимые множества чисел могут иметь полуполное описание в формальной теории, т.е. существует перечислимое множество формул W_0,W_1,W_2,\ldots , такое, что Q=\{n\colon \vdash W_n\} . Адекватность нашей формальной теории (арифметики) могла бы означать, что она является полуполной для каждого перечислимого Множества натуральных чисел, т.е. что в ней имеет полуполное описание всякое множество, которое вообще может иметь такое описание хотя бы в какой-нибудь теории.

В теореме 37.1 мы установили, что множество всех теорем фор. мальной теории перечислимо, т.е. все теоремы и, значит, приво-дящие к ним выводы (доказательства) могут быть эффективно перенумерованы. Возьмем наше множество Q и соответствующее ему множество теорем \{W_0,W_1,W_2,\ldots\} . Рассмотрим следующий предикат P(x,y)\colon " y - номер доказательства теоремы W_x ". Если высказывание P(m,n) истинно, то это означает, что n есть номер вывода теоремы W_m , что, в свою очередь, означает, что m\in Q , т.е. n есть номер вывода о том, что m\in Q . Обратно, взяв конкретные числа m и n , мы можем эффективно построить теорему (формулу) W_m и эффективно построить n-й вывод, после чего эффективно определить, является ли построенный вывод выводом теоремы W_m , т.е. эффективно узнать, истинно ли высказывание P(m,n) . Следовательно, P(x,y) - такой вычислимый предикат, что .

Сформулируем теперь определение.

Определение 37.9. Формальная арифметика называется адекватной, если для каждого перечислимого множества Q натуральных чисел существует вполне представимый в этой арифметике предикат P(x,y) такой, что Q=\bigl\{x\colon (\exists y)(\lambda =1)\bigr\} .

Под полнотой формальной арифметики будем понимать абсолютную полноту, т.е. если для каждой замкнутой формулы F этой теории либо она сама, либо ее отрицание является теоремой этой теории: \vdash F или \vdash\lnot F .

Теперь мы можем перейти непосредственно к формулировке и доказательству теоремы Гёделя.

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

Теорема утверждает следующее. Всякая ω-непротиворечивая и адекватная формальная арифметика не является полной.

▼ Доказательство

Согласно теореме 35.7, выберем такое множество Q натуральных чисел, которое перечислимо, но неразрешимо. Так как наша формальная арифметика адекватна, то существует вполне представимый в ней перидикат P(x,y) такой, что

Q= \bigl\{x\colon\, (\exists y)\bigl(\lambda =1\bigr)\bigr\}.

Вполне представимость предиката P(x,y) в формальной арифметике означает, что найдется такая формула F(x,y) этой теории, содержащая лишь две свободных предметных переменных, что для каждой пары натуральных чисел (a,b) , для которой , имеет место теорема: \vdash F(a^{\ast},b^{\ast}) , а для каждой пары натуральных чисел (a,b) , для которой \lambda =1 , имеет место теорема: \vdash\lnot F(a^{ast},b^{\ast}) .

Применим к формуле F(x,y) квантор общности по переменной y . Получим формулу с единственной свободной предметной переменной x\colon\, G(x)\equiv (\exists y)(F(x,y)) . Покажем, что

Q= \bigl\{x\colon\, \vdash G(x^{\ast})\bigr\}.

Предположим, что m\in Q . Тогда (согласно (*)) найдется такое натуральное n , что высказывание P(m,n) истинно. Следовательно, имеет место теорема: \vdash F(m^{\ast},n^{\ast}) В силу аксиомы арифметики \text{AA} имеем теорему:

\vdash F(m^{\ast},n^{\ast})\to (\exists y)\bigl(F(m^{\ast},y)\bigr).

Из двух последних теорем по правилу МР заключаем:

\vdash (\exists y)\bigl(F(m^{\ast},y)\bigr) , то есть .

Это означает, что m\in \bigl\{x\colon \vdash G(x^{\ast})\bigr\} . Таким образом, Q \subseteq \bigl\{x\colon\vdash G(x^{\ast})\bigr\} .

Обратно, предположим, что m\in \bigl\{x\colon\vdash G(x^{\ast})\bigr\} , то есть \vdash G(m^{\ast}) , то есть \vdash (\exists y)(F(m^{\ast},y)) . Отсюда, в силу известного выражения (по закону де Моргана) квантора существования через квантор общности, заключаем, что

\vdash\lnot (\forall y)\bigl(\lnot F(m^{\ast},y)\bigr).

Поскольку наша формальная арифметика, кроме того, со-непро-тиворечива, то, ввиду наличия в ней последней теоремы, должно существовать такое натуральное число n_0 , что формула - \lnot F(m^{\ast},n^{\ast}_0) не является теоремой этой арифметики. А раз так, то высказывание P(m,n_0) истинно (если бы оно было ложно, то мы имели бы теорему \vdash\lnot F(m^{\ast},n^{\ast}_0) , что не так). По определению (*) множества Q , это означает, что m\in Q . Таким образом, \{x\colon\vdash G(x^{\ast})\}\subseteq Q . Итак, равенство (**) доказано.

Теперь выясним, в каком отношении находятся между собой множества \overline{Q} (дополнение Q ) и \{x\colon\vdash G(x^{\ast})\} . Пусть me m\in \{x\colon\vdash\lnot G(x^{\ast})\} , то есть \vdash\lnot G(x^{\ast}) . Тогда m\in \overline{Q} , ибо если бы m\in Q , то в силу (**) мы имели бы \vdash G(m^{\ast}) и наша формальная арифметика была бы противоречивой, но это не так в силу ее ©-непротиворечивости (по условию) и теоремы 37.7. Таким образом, \{x\colon\vdash G(x^{\ast})\}\subseteq \overline{Q} .

Покажем, что последнее включение является строгим. Напомним, что мы выбрали множество Q перечислимым, но не являющимся разрешимым. Тогда согласно следствию 37.5 из теоремы 37.4, никакая формальная теория не может быть полной для Q . Равенство (**) говорит, что наша формальная арифметика полуполна для Q . Если бы имело место равенство \overline{Q}= \{x\colon\vdash G(x^{\ast})\} , то это означало бы, что наша формальная арифметика полуполна и для \overline{Q} и, значит, она была бы полной для Q . Последнее невозможно в силу следствия 37.5 из теоремы_37.4. Следовательно, \{x\colon\vdash G(x^{\ast})\}\ne \overline{Q} .

Итак, \{x\colon\vdash\lnot G(x^{\ast})\}\subset \overline{Q} . Следовательно, существует такое число m_0\in \overline{Q} , что m_0\notin \{x\colon\vdash\lnot G(x^{\ast})\} , т. е. неверно, что \vdash\lnot G(m_0^{\ast}) . В тоже время неверно также, что \vdash G(m_0^{\ast}) , поскольку это, в силу (**), означало бы, что m_0\in Q , а это не так. Следовательно, мы нашли формулу G(m_0^{\ast}) , такую, что ни она сама, ни ее отрицание не являются теоремами нашей формальной арифметики. Это и означает, что данная формальная арифметика не является полной.

Теорема Гёделя полностью доказана.

Обратимся еще раз к высказыванию \lnot G(m_0^{\ast}) . Согласно равенству (**), его можно интерпретировать как m_0\on \overline{Q} и, следовательно, оно обязательно является "истинным" высказыванием. Но тем не менее оно не является теоремой нашей формальной арифметики. Если добавить формулу G(m_0^{\ast}) к списку аксиом и рассмотреть новую формальную арифметику, то положение не изменится: для вновь полученной формальной арифметики верны все те предпосылки, которые привели нас к теореме Гёделя. Значит, мы снова найдем такое число m_1 , что высказывание \lnot G(m_1^{\ast}) истинно, но не является теоремой новой формальной арифметики и т.д.

Гёдель и его роль в математической логике XX в

Курт Гёдель родился 28 апреля 1906 г. в г. Брюнне (ныне г. Брно в Чехии). Окончил Венский университет, где защитил докторскую диссертацию и был доцентом в период 1933- 1938 гг. После оккупации Австрии фашистской Германией эмигрировал в США. С 1940 по 1963 г. Гёдель работает в Принстонском институте высших исследований (с 1953 г. он профессор этого института). Гёдель - почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества. В 1951 г. Гёдель удостоен высшей научной награды США - Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал: "Вклад Курта Гёделя в современную логику поистине монументален. Это - больше, чем просто монумент, это веха, разделяющая две эпохи... Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки". Гёдель заложил основы целых разделов математической логики: теории моделей (1930), конструктивной логики (1932-1933), формальной арифметики (1932-1933), теории алгоритмов и рекурсивных функций (1934), аксиоматической теории множеств (1938). Гёдель умер в Принстоне (США) 14 января 1978 г.

В вашем браузере отключен Javascript.
Чтобы произвести расчеты, необходимо разрешить элементы ActiveX!

Всякая система математических аксиом начиная с определенного уровня сложности либо внутренне противоречива, либо неполна.

В 1900 году в Париже прошла Всемирная конференция математиков, на которой Давид Гильберт (David Hilbert, 1862–1943) изложил в виде тезисов сформулированные им 23 наиважнейшие, по его мнению, задачи, которые предстояло решить ученым-теоретикам наступающего ХХ века. Под вторым номером в его списке значилась одна из тех простых задач, ответ на которые кажется очевидным, пока не копнешь немножечко глубже. Говоря современным языком, это был вопрос: самодостаточна ли математика? Вторая задача Гильберта сводилась к необходимости строго доказать, что система аксиом - базовых утверждений, принимаемых в математике за основу без доказательств, - совершенна и полна, то есть позволяет математически описать всё сущее. Надо было доказать, что можно задать такую систему аксиом, что они будут, во-первых, взаимно непротиворечивы, а во-вторых, из них можно вывести заключение относительно истинности или ложности любого утверждения.

Возьмем пример из школьной геометрии. В стандартной Евклидовой планиметрии (геометрии на плоскости) можно безоговорочно доказать, что утверждение «сумма углов треугольника равна 180°» истинно, а утверждение «сумма углов треугольника равна 137°» ложно. Если говорить по существу, то в Евклидовой геометрии любое утверждение либо ложно, либо истинно, и третьего не дано. И в начале ХХ века математики наивно полагали, что такая же ситуация должна наблюдаться в любой логически непротиворечивой системе.

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

«Если можно доказать утверждение A, то можно доказать и утверждение не-A».

Иными словами, если можно доказать справедливость утверждения «предположение 247 недоказуемо», то можно доказать и справедливость утверждения «предположение 247 доказуемо». То есть, возвращаясь к формулировке второй задачи Гильберта, если система аксиом полна (то есть любое утверждение в ней может быть доказано), то она противоречива.

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

Итак, формулировка первой,или слабой теоремы Гёделя о неполноте: «Любая формальная система аксиом содержит неразрешенные предположения». Но на этом Гёдель не остановился, сформулировав и доказав вторую, или сильную теорему Гёделя о неполноте: «Логическая полнота (или неполнота) любой системы аксиом не может быть доказана в рамках этой системы. Для ее доказательства или опровержения требуются дополнительные аксиомы (усиление системы)».

Спокойнее было бы думать, что теоремы Гёделя носят отвлеченный характер и касаются не нас, а лишь областей возвышенной математической логики, однако фактически оказалось, что они напрямую связаны с устройством человеческого мозга. Английский математик и физик Роджер Пенроуз (Roger Penrose, р. 1931) показал, что теоремы Гёделя можно использовать для доказательства наличия принципиальных различий между человеческим мозгом и компьютером. Смысл его рассуждения прост. Компьютер действует строго логически и не способен определить, истинно или ложно утверждение А, если оно выходит за рамки аксиоматики, а такие утверждения, согласно теореме Гёделя, неизбежно имеются. Человек же, столкнувшись с таким логически недоказуемым и неопровержимым утверждением А, всегда способен определить его истинность или ложность - исходя из повседневного опыта. По крайней мере, в этом человеческий мозг превосходит компьютер, скованный чистыми логическими схемами. Человеческий мозг способен понять всю глубину истины, заключенной в теоремах Гёделя, а компьютерный - никогда. Следовательно, человеческий мозг представляет собой что угодно, но не просто компьютер. Он способен принимать решения, и тест Тьюринга пройдет успешно.

Интересно, догадывался ли Гильберт, как далеко заведут нас его вопросы?

Курт ГЁДЕЛЬ
Kurt Gödel, 1906–78

Австрийский, затем американский математик. Родился в г. Брюнн (Brünn, ныне Брно, Чехия). Окончил Венский университет, где и остался преподавателем кафедры математики (с 1930 года - профессором). В 1931 году опубликовал теорему, получившую впоследствии его имя. Будучи человеком сугубо аполитичным, крайне тяжело пережил убийство своего друга и сотрудника по кафедре студентом-нацистом и впал в глубокую депрессию, рецидивы которой преследовали его до конца жизни. В 1930-е годы эмигрировал было в США, но вернулся в родную Австрию и женился. В 1940 году, в разгар войны, вынужденно бежал в Америку транзитом через СССР и Японию. Некоторое время проработал в Принстонском институте перспективных исследований. К сожалению, психика ученого не выдержала, и он умер в психиатрической клинике от голода, отказываясь принимать пищу, поскольку был убежден, что его намереваются отравить.

Комментарии: 0

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

Анатолий Вассерман

В 1930 году Курт Гедель доказал две теоремы, которые в переводе с математического языка на человеческий означают примерно следующее: Любая система аксиом, достаточно богатая, чтобы с ее помощью можно было определить арифметику, будет либо не полна, либо противоречива. Не полная система – это значит, что в системе можно сформулировать утверждение, которое средствами этой системы нельзя ни доказать, ни опровергнуть. Но Бог, по определению, есть конечная причина всех причин. С точки зрения математики это означает, что введение аксиомы о Боге делает всю нашу аксиоматику полной. Если есть Бог, значит любое утверждение можно либо доказать, либо опровергнуть, ссылаясь, так или иначе, на Бога. Но по Геделю полная система аксиом неизбежно противоречива. То есть, если мы считаем, что Бог существует, то мы вынуждены прийти к выводу, что в природе возможны противоречия. А поскольку противоречий нет, иначе бы весь наш мир рассыпался от этих противоречий, приходиться прийти к выводу, что существование Бога не совместимо с существованием природы.

Сосинский А. Б.

Теорема Гёделя, наряду с открытием теории относительности, квантовой механики и ДНК, обычно рассматривается как крупнейшее научное достижение ХХ века. Почему? В чем ее суть? Каково ее значение? Эти вопросы в своей лекции в рамках проекта «Публичные лекции "Полит.ру"» раскрывает Алексей Брониславович Сосинский, математик, профессор Независимого московского университета, офицер Ордена академических пальм Французской Республики, лауреат премии Правительства РФ в области образования 2012 года. В частности, были даны несколько разных ее формулировок, описаны три подхода к ее доказательству (Колмогорова, Чейтина и самого Гёделя), и объяснено ее значение для математики, физики, компьютерной науки и философии.

Успенский В. А.

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

Успенский В. А.

Лекции летней школы «Современная математика», г. Дубна.

Одной из самых известных теорем математической логики, повезло и не повезло одновременно. В этом она похожа на специальную теорию относительности Эйнштейна. С одной стороны, почти все о них что-то слышали. С другой - в народной интерпретации теория Эйнштейна, как известно, «говорит, что всё в мире относительно» . А теорема Гёделя о неполноте (далее просто ТГН), в примерно столь же вольной фолк-формулировке, «доказывает, что есть вещи, непостижимые для человеческого разума» . И вот одни пытаются приспособить её в качестве аргумента против материализма , а другие, напротив, доказывают с её помощью, что бога нет . Забавно не только то, что обе стороны не могут оказаться правыми одновременно, но и то, что ни те, ни другие не удосуживаются разобраться, что же, собственно, эта теорема утверждает.

Итак, что же? Ниже я попытаюсь «на пальцах» рассказать об этом. Изложение моё будет, разумеется нестрогим и интуитивным, но я попрошу математиков не судить меня строго. Возможно, что для нематематиков (к которым, вообще-то, отношусь и я), в рассказанном ниже будет что-то новое и полезное.

Математическая логика - наука действительно довольно сложная, а главное - не очень привычная. Она требует аккуратных и строгих манёвров, при которых важно не перепутать реально доказанное с тем, что «и так понятно». Тем не менее, я надеюсь, что для понимания следующего ниже «наброска доказательства ТГН» читателю понадобится только знание школьной математики/информатики, навыки логического мышления и 15-20 минут времени.

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

Начнём с того, что попытаемся разобраться, что такое доказательство. Возьмём какую-нибудь школьную задачку по арифметике. Например, пусть требуется доказать верность следующей незамысловатой формулы: « » (напомню, что символ читается «для любого» и называется «квантор всеобщности»). Доказать её можно, тождественно преобразуя, скажем, так:

Переход от одной формулы к другой происходит по некоторым известным правилам. Переход от 4-й формулы к 5-й произошёл, скажем, потому, что всякое число равно самому себе - такова аксиома арифметики. А вся процедура доказывания, таким образом, переводит формулу в булево значение ИСТИНА. Результатом могла быть и ЛОЖЬ - если бы мы опровергали какую-то формулу. В таком случае мы бы доказали её отрицание. Можно себе представить программу (и такие программы действительно написаны), которые бы доказывали подобные (и более сложные) высказывания без участия человека.

Изложим то же самое чуть более формально. Пусть у нас есть множество, состоящее из строк символов какого-то алфавита, и существуют правила, по которым из этих строк можно выделить подмножество так называемых высказываний - то есть грамматически осмысленных фраз, каждая из которых истинна или ложна. Можно сказать, что существует функция , сопоставляющая высказываниям из одно из двух значений: ИСТИНА или ЛОЖЬ (то есть отображающая их в булево множество из двух элементов).

Назовём такую пару - множество высказываний и функция из в - «языком высказываний» . Заметим, что в повседневном смысле понятие языка несколько шире. Например, фраза русского языка «А ну иди сюда!» не истинна и не ложна, то есть высказыванием, с точки зрения математической логики, не является.

Для дальнейшего нам понадобится понятие алгоритма. Приводить здесь формальное его определение я не буду - это завело бы нас довольно далеко в сторону. Ограничусь неформальным: «алгоритм» - эта последовательность однозначных инструкций («программа»), которая за конечное число шагов переводит исходные данные в результат. Выделенное курсивом принципиально важно - если на каких-то начальных данных программа зацикливается, то алгоритма она не описывает. Для простоты и в применении к нашему случаю читатель может считать, что алгоритм - это программа, написанная на любом известном ему языке программирования, которая для любых входных данных из заданного класса гарантированно завершает свою работу с выдачей булевого результата.

Спросим себя: для всякой ли функции существует «доказывающий алгоритм» (или, короче, «дедуктика» ), эквивалентный этой функции, то есть переводящий каждое высказывание именно в то булево значение, что и она? Лаконичнее тот же вопрос можно сформулировать так: всякая ли функция над множеством высказываний вычислима ? Как вы уже догадываетесь, из справедливости ТГН следует, что нет, не всякая - существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.

Очень может быть, что это утверждение вызовет у вас внутренний протест. Связано это с несколькими обстоятельствами. Во-первых, когда нас учат школьной математике, то иногда возникает ложное впечатление почти полной тождественности фраз «теорема верна» и «можно доказать или проверить теорему ». Но, если вдуматься, это совершенно не очевидно. Некоторые теоремы доказываются довольно просто (например, перебором небольшого числа вариантов), а некоторые - очень сложно. Вспомним, например, знаменитую Великую теорему Ферма :

доказательство которой нашли только через три с половиной века после первой формулировки (и оно далеко не элементарно). Следует различать истинность высказывания и его доказуемость. Ниоткуда не следует, что не существует истинных, но недоказуемых (и не проверяемых в полной мере) высказываний.

Второй интуитивный довод против ТГН более тонок. Допустим, у нас есть какое-то недоказуемое (в рамках данной дедуктики) высказывание. Что мешает нам принять его в качестве новой аксиомы? Тем самым мы чуть усложним нашу систему доказательств, но это не страшно. Этот довод был бы совершенно верен, если бы недоказуемых высказываний было конечное число. На практике же может произойти следующее - после постулирования новой аксиомы вы наткнётесь на новое недоказуемое высказывание. Примете его в качестве ещё аксиомы - наткнётесь на третье. И так до бесконечности. Говорят, что дедуктика останется неполной . Мы можем также принять силовые меры, чтобы доказывающий алгоритм заканчивался через конечное число шагов с каким-то результатом для любого высказывания языка. Но при этом он начнёт врать - приводить к истине для неверных высказываний, или ко лжи - для верных. В таких случаях говорят, что дедуктика противоречива . Таким образом, ещё одна формулировка ТГН звучит так: «Существуют языки высказываний, для которых невозможна полная непротиворечивая дедуктика» - отсюда и название теоремы.

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

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

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

Примеры высказываний формальной арифметики:

и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром ):

и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.

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

Перейдём теперь к наброску доказательства ТГН в такой формулировке:

• Для языка высказываний формальной арифметики не существует полной непротиворечивой дедуктики.

Доказывать будем от противного.

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

Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.

Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.

Очевидно, что, при сделанном выше предположении, любой ФСП из можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение. Менее очевидно обратное утверждение:

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

Пройдя это скользкое место, мы быстро добираемся до конца.

Итак, выше мы описали алгоритм . Согласно лемме, в которую я попросил вас поверить, существует эквивалентная ему ФСП. Она имеет какой-то номер в списке - скажем, . Спросим себя, чему равно ? Пусть это ИСТИНА. Тогда, по построению алгоритма (а значит, и эквивалентной ему функции ), это означает, что результат подстановки числа в функцию - ЛОЖЬ. Аналогично проверяется и обратное: из ЛОЖЬ следует ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.

Здесь уместно вспомнить Эпименида (см. портрет в заголовке), который, как известно, заявил, что все критяне - лжецы, сам являясь критянином. В более лаконичной формулировке его высказывание (известное как «парадокс лжеца») можно сформулировать так: «Я лгу». Именно такое высказывание, само превозглашающее свою ложность, мы и использовали для доказательства.

В заключение я хочу заметить, что ничего особенного удивительного ТГН не утверждает. В конце концов, все давно привыкли, что не все числа представимы в виде отношения двух целых (помните, у этого утверждения есть очень изящное доказательство , которому больше двух тысяч лет?). И корнями полиномов с рациональными коэффициентами являются тоже не все числа . А теперь вот выяснилось, что не все функции натурального аргумента вычислимы.

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

• «Любая фраза китайского языка является верным высказыванием, если она содержится в цитатнике товарища Мао Дзе Дуна, и неверна, если не содержится».

Тогда соответствующий полный и непротиворечивый доказывающий алгоритм (его можно назвать «догматической дедуктикой») выглядит примерно так:

• «Листай цитатник товарища Мао Дзе Дуна, пока не найдёшь искомое высказывание. Если оно найдено, то оно верно, а если цитатник закончился, а высказывание не найдено, то оно неверно».

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