К интерпретации теорем Гёделя о неполноте арифметики

Размещено на http://www.allbest.ru/

УДК 164.07

К интерпретации теорем Гёделя о неполноте арифметики

А.В. Бессонов

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

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

Почти общепризнано, что знаменитые теоремы К. Гёделя о неполноте арифметики [1, 2] свидетельствуют о принципиальной ограниченности метода формализации даже в области математического знания. Они рассматриваются как решающий аргумент о несостоятельности гильбертовскойфинитистской программы [3] обоснования математики (с такой оценкой в свое время был согласен и сам Д. Гильберт). Более того, на них основывается вывод о принципиальной неполноте любых более богатых по сравнению с арифметикой теорий и в других отраслях знания.

Убеждение в сверхзначимости теорем Гёделя о неполноте формальной арифметики давно вышло за пределы математики и ныне тотально распространено на философию, гносеологию [4], социологию [5], юриспуденцию и т.д. и является «почти неисчерпаемым источником интеллектуальных злоупотреблений» [6]. Между тем имеются свидетельства того, что А.Н. Колмогоров не верил в распространение этих теорем на все известные теории при любых их построениях [7]. Я. Хинтикка предложил «независимодружественнуюкванторную логику», в которой теоремы Гёделя не выполняются [8]. Да и сам Гёдель вовсе не был убеждён в величии и универсальности своих результатов и следующих из них выводов [9]. Не покушаясь на собственно математическую сторону доказательств, а сосредоточившись на критике общепринятого истолкования этих теорем, мы покажем, что их значимость чрезвычайно преувеличена даже в родной для них области логики и математики.

§1. Теоремы Гёделя о неполноте: комментарии

Приведём краткое изложение гёделевых доказательств теорем о неполноте формальной арифметики2.

Напомним, что теория называется щнепротиворечивой, если в ней ни для какой формулы Ц( )x с одной свободной переменной не могут одновременно быть доказуемыми формулы

Ц(1),Ц(2),…, ?Цx ( ).x

В первой теореме Гёделя о неполноте арифметики утверждается, что если формальная арифметика Пеано (PA) щнепротиворечива, то она неполна2. Более точно, в ней доказывается существование некоторой замкнутой формулы («говорящей» о своей собственной недоказуемости) такой, что ни она, ни ее отрицание не доказуемы в PA (такие формулы называются неразрешимыми). В соответствии со второй теоремой Гёделя, если PA непротиворечива, то в ней не доказуема формула, выражающая непротиворечивость PA [2.Theorems VI, XI].

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

Эта широко используемая метафорическая формулировка нуждается в пояснении. То, что никакая теория не в состоянии обосновать саму себя, известно с античных времен независимо от теорем Гёделя. Следует понимать, что во второй теореме речь идет лишь о недоказуемости некоторой формулы (тем или иным способом выражающей непротиворечивость PA). И даже если бы подобная формула была доказуемой, это никак не гарантировало бы непротиворечивость PA, поскольку в противоречивой теории доказуемы все формулы, в том числе и (имеющаяся в PA) формула, «выражающая» формулировку второй теоремы: «Если PA непротиворечива, то формула, выражающая непротиворечивость PA, в ней не доказуема». Рассмотрим вторую теорему более внимательно.

Доказательства Гёделя основаны на кодировании языка формальной арифметики и её логики (гёделева нумерация), а также на введённом им понятии «определимости» («выразимости»).

Определение. Предикат F x( 1,…,xk) , заданный на множестве натуральных чисел, называется «определимым» в PA, если в PA найдётся формула Ц(x1,…,xk), такая что для любого набора натуральных чисел (n1,…,nk) справедливы условия: если F n( 1,…,nk) выполняется, тоAЦ(n1,…,nk) ; если F n( 1,…,nk) не выполняется, то AЦ(n1,…,nk).

Здесь, как обычно, A означает доказуемость (в PA). Для сокращения записи условимся вместо нумералов в PA использовать обычные цифры, т.е., например, вместо 0??? писать 3, 7 9A будет обозначать гёделев номер формулы A .

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

Мы, как и сам Гёдель [2.Theorem XI], будем использовать другое содержательное определение непротиворечивости: теория T непротиворечива, если в ней имеется хотя бы одна недоказуемая формула.

Как известно, эти два определения эквивалентны: если теория T непротиворечива в соответствии с первым определением, то она непротиворечива в соответствии со вторым, и наоборот. В самом деле, из (1) следует, что для любой формулы A либо она, либо её отрицание не доказуемо, т.е. существует хотя бы одна недоказуемая формула, т.е. следует (2). Пусть верно (2). Из этого следует (1), так как в противном случае в T была бы доказуемой какаято формула вместе с её отрицанием, и по правилу A&A AB доказуемой была бы любая формула.

При доказательстве теорем о неполноте синтаксис и логика PA нумеруются посредством гёделевой нумерации, после чего вводится предикат доказуемости Pr( , )x y , который выполняется тогда и только тогда, когда x является гёделевым номером некоторой формулы, а y - гёделевым номером её доказательства. Известно, что этот предикат эффективно разрешим. Гёдель установил, что всякий заданный на натуральных числах предикат «определим» в PA тогда и только тогда, когда он разрешим. Значит, Pr( , )x y «определим» в PA с помощью некоторой арифметической формулы Prov( , )x y , т.е. для любых натуральных чисел n , k верны условия: если Pr(,)n k выполняется, то A Prov( , )n k ; если Pr( , )n k не выполняется, то A Prov(, )n k .

В этих обозначениях определение непротиворечивости (2) выражается арифметической формулой

?x? y Prov( , )x y , (*)

а в силу эквивалентности определений непротиворечивости (1) и (2), формула(*) (которую С. Клини назвал «Consis») «выражает» непротиворечивость PA независимо от того, какое именно содержательное определение непротиворечивости имеется в виду.

Во второй теореме Гёделя доказывается, что если PA непротиворечива, то формула (*) не может быть доказана в PA. Отсюда Гёдель немедленно делает вывод, что «непротиворечивость P (PA в наших обозначениях. - А.Б.) недоказуема в P» [2.P. 193]. Отметим, что во второй теореме этот вывод доказывается исключительно по отношению к гёделевой формуле Consis. Однако Гёдель, видимо, предполагая, что других формул, «выражающих» непротиворечивость PA, нет, тут же максимально обобщает вывод второй теоремы: «Доказательство теоремы XI слово в слово переносится на систему аксиом теории множеств, M , и систему аксиом классической математики, A , из чего следует: не существует доказательства непротиворечивости для M или A , которое может быть формализовано соответственно в M или в A , в предположении, что M или A непротиворечивы» [2.P. 195].

Очевидно, что подобное обобщение второй теоремой никак не обосновано. Доказательства второй теоремы явно недостаточно для вывода, что в PA не может быть доказана никакая другая (не эквивалентная гёделевойConsis) формула, «выражающая» непротиворечивость PA. Ведь даже студенту первого курса мехмата известно, что из существования формулы, удовлетворяющей некоторому свойству («выражать» непротиворечивость PA и быть недоказуемой), логически не следует, что все формулы должны удовлетворять этому свойству. Из второй теоремы никак не следует несуществование «других, чем в теореме Гёделя, быть может не столь естественных (или естественных както подругому), но всё же разрешимых в P арифметических выражений непротиворечивости... Странным образом последнее обстоятельство не было замечено в 1931 году» [11.С. 112].

Вопрос о ином способе построения Consis вообще не поднимается ни самим Гёделем, ни многими его последователями. Приводим цитаты без купюр: «Если арифметическая формальная система гл. IV (просто) непротиворечива, то не AConsis; иначе говоря, если указанная система непротиворечива, то не существует (!? - А.Б.) доказательства её непротиворечивости, проведённого средствами, формализуемыми в этой системе (Вторая теорема Гёделя)» [12.С. 190].

«Если теория S непротиворечива, то в ней невыводима и формула ConS; иными словами, если теория непротиворечива, то в ней невыводима некоторая (! - А.Б.) формула, содержательно выражающая непротиворечивость теории S. Этот результат носит название второй теоремы Гёделя. Грубо говоря, эта теорема утверждает, что если теория S непротиворечива, то доказательство непротиворечивости теории не может быть проведено средствами самой теории S, т.е. всякое (!? - А.Б.) такое доказательство обязательно должно использовать невыразимые в теории S идеи или методы» [13.С. 165].

Следует сказать, что Мендельсон всетаки оговаривается, указывая на результат С. Фефермана [14.P. 35-92]: «... как показал Феферман [1960], существует некоторый приемлемый способ построения ConS, при котором AS ConS. Итак, следует уточнить формулировку теоремы». Уточнение сводится к тому, что в формулировке второй теоремы фраза «некоторая формула, выражающая...» заменяется на «некоторая REформула, выражающая...» (REформула - это формула вида ?y1…?y Ak, где k.0 и A - формула «выражающая» какуюлибо примитивно рекурсивную функцию) [13.С. 166- 167]. Значит, в PA всетаки существует «выражающая» непротиворечивость PA формула (пусть и не REформула), и она доказуема в PA, т.е. PA всетаки может «доказать свою непротиворечивость»!

Еще один контрпример ко второй теореме Гёделя построил К.Ф. Самохвалов [15]. Однако и он, и Феферман строят свои формулы, «выражающие» непротиворечивость PA, как производные от гёделевых предиката доказуемости и формулы Consis. А нельзя ли построить формулы, «выражающие» непротиворечивость PA и доказуемые в ней, используя принципиально иные выразительные средства?

§2. Вторая теорема Гёделя: контрпримеры

Для ответа на поставленный вопрос рассмотрим свойства гёделевых формулы Prov( , )x y и предиката Pr( , )x y .

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

?yProv(7 9A , ).y(* )A

Действительно, из A?yProv(7 9A , )y по закону экзистенциального обобщения [ F t( ) >?xF x( ) ] немедленно следовало бы A?x? y Prov( , )x y , т.е. A (*) . Но это означает, что в PA невозможно доказать недоказуемость никакой - ни доказуемой, ни недоказуемой, ни неразрешимой (если таковые есть) формулы. Этот обескураживающий факт весьма просто объясняется выбором базового в доказательствах теорем о неполноте предиката Pr( , )x y .

Его разрешающая процедура такова:

Выберем пару натуральных чисел (x, y) и проверим, является ли xгёделевым номером формулы, а y - гёделевым номером доказательства. По гёделевым номерам восстановим формулу с номером x и доказательство с номером y . Доказательство представляет собой последовательность формул. Рассмотрим заключительную формулу этой последовательности и сравним её с формулой, имеющей номер x . Если эти формулы совпадут, то Pr( , )x y истинно.

Как по этому алгоритму установить доказуемость формулы - понятно. А как установить недоказуемость? Восстановив по номеру x формулу A, мы должны последовательно перебрать номера всех доказательств, восстановить их и убедиться, что во всех случаях заключительная формула доказательства отличается от A. Ясно, что если PA непротиворечива и A доказуема, то установить недоказуемость A нельзя. Если же A недоказуема, то этот процесс никогда не остановится, даже если заключительной формулой какогото вывода окажется формула A: она также отличается от A. Требование щнепротиворечивости в доказательстве первой теоремы даёт дополнительную (как следует из результата Б. Россера, даже избыточную) гарантию того, что недоказуемость A не может быть установлена какимлибо иным образом.

Отсюда следует, что подлинной причиной недоказуемости неразрешимой гёделевой формулы является не какоето врождённое свойство PA, а то, что базовый предикат Pr( , ),x y более или менее пригодный для представления рассуждений о доказуемости, совершенно не подходит для представления рассуждений о недоказуемости. Этот предикат мажет одной краской все формулы, «выражающие» недоказуемость какой бы то ни было формулы, а не только те, которые «говорят» о своей собственной недоказуемости или о непротиворечивости PA в целом. А ведь при доказательствах непротиворечивости или неразрешимости требуется адекватность представления рассуждений именно о недоказуемости! Таким образом, попытки установить недоказуемость какойлибо формулы PA, используя исключительно гёделевы выразительные средства, подобны попыткам выкопать яму зубочисткой, для этого заведомо не приспособленной. А может, вместо зубочистки прибегнуть к лопате или экскаватору?

Чрезвычайно важно понимать, что выбор предиката Pr( , )x y и соответствующей ему формулы Prov( , )x y (или производных от них) в качестве исключительных средств для представления рассуждений о (не)доказуемости в PA, несмотря на кажущуюся его естественность, Гёделем и его последователями никак не обосновывается. Эти средства выбраны абсолютно произвольно, при этом вопрос о возможности использования принципиально иных выразительных средств даже не поднимается. Мы же далее рассмотрим именно этот вопрос.

По алгоритму разрешения предиката Pr( , )x y для установления недоказуемости формулы требуется осуществить бесконечный перебор номеров всех выводов. Но для построения формулы, «выражающей» факт непротиворечивости PA, достаточно указать всего на одну недоказуемую в PA формулу, которая, конечно же, имеется в предположении, что PA непротиворечива. Отсюда просто напрашивается мысль о введении предиката недоказуемости.

Рассмотрим предикат BessNPr( )x , который выполняется тогда и только тогда, когда x является гёделевым номером первой пришедшей в голову автору этой статьи недоказуемой в PA формулы. Заверяю, что это была формула (0 = 0) , очевидно недоказуемая в PA, если последняя непротиворечива.

Этот предикат «определим» в PA формулой BessNProv( )x , эквивалентной формуле x =7(0 = 0)9 . В самом деле, предикат BessNPr( )x выполняется только для значения x , совпадающего с 7(0 = 0)9 , и в этом случае в PA A7(0 = 0) =9 7(0 = 0)9 , т.е. A BessNProv(7(0 = 0) )9 . При любом другом значении x , скажем, l , не равном 7(0 = 0)9 , BessNPr( )l не выполняется, и в этом случае, очевидно, A BessNProv( )l , так как для любого l ? 7 (0 = 0)9 в PA доказуемо ( =l 7(0 = 0) )9 . Поскольку в PA A BessNProv(7(0 = 0) )9 , по закону экзистенциального обобщения получаем

A ?xBessNProv( ).x

Иными словами, в PA доказуема формула, «выражающая» существование в PA первой пришедшей в голову автору недоказуемой в PA формулы. Но из этого следует существование в PA недоказуемой формулы, т.е. следует непротиворечивость PA! Таким образом, PA вполне может «доказать свою непротиворечивость» ровно в том смысле, в каком, как полагается, она не может этого сделать, если вторая теорема о неполноте верна.

Для тех, кто посчитает приведённый контрпример ко второй теореме незначимым на том основании, что в PA нет никакого «автора», следует сказать, что в PA нет также ни гёделевой, ни какойлибо иной нумерации: из каких аксиом PA следует существование нумераций? Нумерирование (арифметизация) синтаксиса и логики PA является таким же фактическим (произвольным, случайным, внешним, посторонним и т.п.) обстоятельством для PA как формальной системы, что и факт пришествия в голову А.В. Бессонова некоей недоказуемой в PA формулы. Последний факт связан с аксиомами PA в столь же малой степени, что и, например, факт использования Гёделем для нумерации левой скобки - числа 11, правой - числа 13, а не наоборот. Можно привести и более математичные примеры.

Рассмотрим предикат MinNPr( )x , который выполняется тогда и только тогда, когда x является наименьшим гёделевым номером недоказуемой в PA формулы. Очевидно, что такой номер n существует, поскольку минимум ищется в конечном множестве 0,7(0 = 0)9 . Проводя те же рассуждения, что и в случае предиката BessNPr( )x , получаем, что предикат MinNPr( )x «определим» в PA формулой MinNProv( )x , эквивалентной формуле x=n , и что в PA доказуема формула

?xMinNProv( ),x

«выражающая» существование в PA недоказуемой формулы c наименьшим гёделевым номером. Но из этого также следует существование в PA недоказуемой формулы, т.е. непротиворечивость PA.

Чем приведённые выше формулы, «выражающие» непротиворечивость PA, хуже гёделевой формулы Consis? А.А. Френкель и И. БарХилел формулируют следствие второй теоремы Гёделя так: «никакое предложение, которое можно точным образом (курсив наш. - А.Б.) интерпретировать как выражающее непротиворечивость какойлибо логистической системы, содержащей арифметику, не может быть доказано в этой системе» [16]. Очевидно, что наши формулы можно интерпретировать как выражающие непротиворечивость PA ничуть не менее точным образом, чем гёделевConsis. Эти формулы вполне погёделевски «выражают» факт существования в PA хотя бы одной недоказуемой формулы, что и означает непротиворечивость PA.

Г. Крайзель уточняет формулировку второй теоремы следующим образом: «Если система S непротиворечива, а относительно формулы A в S может быть доказано, что A выражает непротиворечивость S, то A не может быть доказана в S» [17]. Но как доказать в PA, что сам гёделевConsis выражает непротиворечивость PA? Если Крайзель имеет в виду требование, чтобы любая формула, выражающая непротиворечивость PA, должна быть доказуемо эквивалентной в PA гёделевой формуле Consis или её производным (в духе Фефермана), то это напоминает ситуацию, когда требуется доказать, что лопатой или ковшом экскаватора тоже можно чистить зубы.

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

Очевидно, что этот предикат разрешим. Его разрешающая процедура отличается от таковой для гёделева предиката Pr( , )x y только тем, что заключительная формула вывода с номером y сравнивается не с самой формулой, имеющей номер x , а с её отрицанием. Следовательно, предикат NPr( , )x y «определим» в PA некоторой формулой NProv( , )x y , а факт существования в PA заведомо недоказуемой формулы «выражается» формулой

?x?yNProv( , )x y . (**)

В PA выводима формула (0 = 0) , значит, выводима и формула (0 = 0) , поскольку в PA A ((0 = 0) ? (0 = 0)). Пусть n - гёделев номер вывода формулы (0 = 0) . Из определения предиката NPr( , )x y следует, что NPr(7(0 = 0) , )9 n истинно. Тогда по условиям «определимости» в PA доказуема формула NProv(7(0 = 0) , )9 n . Дважды применяя к последней формуле закон экзистенциального обобщения, получаем вывод формулы (**) . Таким образом, в PA доказуема формула, «выражающая» существование заведомо недоказуемой, а значит, и просто недоказуемой формулы. Поэтому арифметика вполне может «доказать свою собственную непротиворечивость».

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

Теперь понятно, что такая формулировка неверна. Формулы в приведённыхконтрпримерах доказуемы в PA и прекрасно выражают непротиворечивость PA. Однако из этого противоречивость PA никак не следует.

Заметим, что в приведённых примерах использованы вполне REформулы. Поэтому и в переформулировке Мендельсона-Фефермана вторая теорема о неполноте не имеет универсального значения. От этой теоремы остаётся только нечто вроде «если PA непротиворечива, то в ней имеется некоторая формула, одним из возможных способов «выражающая» непротиворечивость PA и недоказуемая в PA. При этом существуют другие, ничуть не хуже “выражающие” непротиворечивость PA и доказуемые в PA формулы». Вторая теорема, таким образом, лишается ошибочно приписываемого ей пафосного значения и должна рассматриваться просто как одно из рядовых следствий первой теоремы о неполноте. В то же время это следствие, как мы покажем ниже, заставляет пересмотреть общепринятое универсальное истолкование первой теоремы.

§3. Неадекватность гёделева представления

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

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

Вернёмся к поставленному в начале статьи вопросу о значимости теорем Гёделя. Очевидно, что правомерность переноса на содержательную математику и тем более на иные отрасли знания выводов о принципиальной неполноте теорий основывается на молчаливом предположении об адекватности способа представления знания, используемом при доказательстве теорем Гёделя. Но насколько верно это предположение?

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

Нумерирование (арфметизация синтаксиса).

Введение определённого понятия «выразимости», с помощью которого содержательные утверждения транслируются в PA.

Выбор определённых выразительных средств (базовый предикат Pr( , )x y и соответствующая ему формула Prov( , )x y ).

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

Как мы убедились, избранные Гёделем выразительные средства далеко не уникальны: формула NProv( , )x y ничуть не хуже «выражает» определённые рассуждения о (не)доказуемости, чем гёделева формула Prov()x y . При этом утверждение второй теоремы оказывается предикатно зависимым: основанная на Prov( , )x y формула, «выражающая» непротиворечивость PA, недоказуема, а основанная на NProv( , )x y - элементарно доказуема. Но это прямо опровергает общепринятую универсальную трактовку второй теоремы о неполноте: «В любой теории, содержащей арифметику, недоказуема любая формула, выражающая её непротиворечивость, если арифметика непротиворечива».

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

(* )A:

?yProv(7 9A , )y .

Этот факт известен, но, повидимому, не известно, что следствием его при использовании для «выражения» рассуждений о доказуемости исключительно формулы Prov( , )x y (т.е. в тех рамках, в которых Гёделем и проводятся доказательства теорем о неполноте PA) является следующая

ТЕОРЕМА (третья теорема о неполноте). Если PA непротиворечива, то для любой формулы A формула, «выражающая» недоказуемость A , недоказуема в PA.

Если PA щнепротиворечива, то для любой недоказуемой в PA формулы Aформула, «выражающая» недоказуемость A, неразрешима в PA.

ДОКАЗАТЕЛЬСТВО. Пусть A - некоторая недоказуемая в PA формула.

Её недоказуемость «выражается» формулой (* )A , которая, как следует из второй теоремы, недоказуема в PA. Рассмотрим отрицание формулы (* )A, т.е. формулу

? y Prov(7 9A , ).y

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

Prov(7 9A ,1),Prov(7 9A ,2),…,? y Prov(7 9A , )y

должна быть недоказуемой. По гипотезе последняя формула в перечне доказуема. Значит, найдётся номер k такой, что формула Prov(7 9A , )k будет недоказуемой. В таком случае по условиям определимости формула Pr(7 9A)k не может быть истинной, следовательно, она ложна, откуда вытекает, что формула Pr(7 9A , )k истинна. По определению предиката Pr последнее означает, что формула A доказуема. Приходим к противоречию, поскольку мы предположили, что A - недоказуемая формула.

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

?yProv(7(0 = 0) , )9 y ,

«выражающая» недоказуемость формулы (0 = 0) , неразрешима в PA.

Математики могут смириться с тем, что некая загадочная, существующая «в принципе» и интуитивно необозримая формула, «выражающая» свою собственную недоказуемость, неразрешима в PA. Так же, основываясь на смутных воспоминаниях из университетского курса философии, они могут согласиться с тем, что «арифметика не может доказать свою непротиворечивость». Но укажите на нормального математика, который согласится считать неразрешимым суждение о недоказуемости формулы (0 = 0) ! Ведь на самом деле недоказуемость этой формулы доказывается совершенно элементарно методом от противного: если бы формула (0 = 0) была доказуемой, то, учитывая доказуемость в PA формулы (0 = 0) , по правилам пропозициональной логики доказуемой была бы и формула (0 = 0)& (0 = 0), т.е. арифметика была бы противоречивой.

Подчеркнем, что правомерность подобного рассуждения в содержательной математике никем не оспаривается. В нём не используется ни аксиома индукции, ни тем более трансфинитная индукция. С применением закона исключённого третьего в данном рассуждении согласятся даже интуиционисты, поскольку в нём рассматривается лишь конечное множество формул (две формулы) и применяется никем не оспариваемое правило вывода пропозициональной логики A,B A A B&.

Но грош цена представлению содержательного математического знания (а следовательно, и полученным в данном представлении результатам), в котором теоремно устанавливается невозможность доказать формулу, «выражающую» недоказуемость (0 = 0) в предположении о непротиворечивости арифметики! А во сколько мы оценили бы представление содержательного математического знания посредством некоей «формальной арифметики», в которой было бы доказуемо 2Ч2 = 5 или оказывалась бы неразрешимой формула 1+1= 2 ? Поскольку недоказуемость формулы (0 = 0) элементарно и бесспорно устанавливается в содержательной арифметике, в гёделевом представлении оказываются доказуемыми заведомо ложные утверждения, прямо противоречащие самой обыденной математической практике. Но представление, в котором доказываются ложные в представляемом знании суждения, не отвечает требованию логической адекватности и безусловно должно быть отвергнуто.

Сказанное косвенно опровергает и первую теорему о неполноте. Из первой теоремы следует вторая, из неё - третья, следствия которой (например, неразрешимость формулы, «выражающей» недоказуемость формулы (0 = 0) ) совершенно неприемлемы. Но признав гёделево доказательство существования в PA неразрешимой замкнутой формулы, мы обязаны признать и неразрешимость формулы, «выражающей» недоказуемость (0 = 0) !

Значит, предположив, что первая теорема верна, мы получим абсурдные по отношению к представляемому знанию выводы. Таким образом, первая теорема опровергается буквальным reductioadabsurdum.

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

Исключительно в рамках некоторой фиксированной нумерации, исключительно в рамках введённого Гёделем понятия «выразимости», при использовании в качестве базовых для представления рассуждений о (не)доказуемости исключительно предиката Pr( , )x y и «определяющей» его формулы Prov( , )x y , можно доказать, что PA содержит неразрешимую формулу и в ней недоказуема формула, «выражающая» непротиворечивость PA.

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

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

Мы не утверждаем, что наши результаты доказывают полноту PA. Но из них следует, что в теоремах Гёделя о неполноте арифметики не доказано обратное.

В заключение автор выражает искреннюю благодарность участникам совместного философскоматематического семинара Отдела математической логики Института математики СО РАН и Отдела философии Института философии и права СО РАН за заинтересованное обсуждение работы и полезные замечания. Отдельная благодарность - д.филос.н. К.Ф. Самохвалову, чья критика и стимулирующее влияние во многом способствовали осуществлению данного исследования.

Литература

1. Gцdel K.Ьber formal unentscheidbareSдtze der Principia Mathematica und verwandterSysteme // MonatsheftefьrMathematik und Physik. 1931. Bd. 38. S. 173-198.

2. Gцdel K. On formally undecidable propositions of Principia mathematica and related systems I // S. Feferman, J.R. Dawson, S.C. Kleene, G.H. Moore, R.M. Solovay, and J. van Heijenoort (eds.).

3. Kurt Gцdel. Collected Works, Vol. 1.NewYork, 1986. P. 145-195.

4. Гильберт Д. Основания геометрии. М., 1948. С. 322-399.

5. Пенроуз Р. Тени разума: в поисках науки о сознании. М., 2005.

6. Debray R. Critique de la raison politique. Paris, 1981.

7. Сокал А., Брикмон Ж. Интеллектуальные уловки. Критика философии постмодерна. М., 2002.

8. Кузичев А.С. Новые колмогоровские теоретикомножественные основания современной математики [Электроннный ресурс]. Режим доступа: http://kuzichev.exponenta.ru/

9. HintikkaJa. The principles of mathematics revisited. London, 1996.

10. Крайзель Г. Биография Курта Гёделя // Успехи математических наук. 1988. Т. 43, вып. 2(260). С. 175-216.

11. Rosser B. Extensions of some theorems of Gцdel and Church // Journal of Symbolic Logic. 1936. Vol. 1, № 3. P. 87-91.

12. Ершов Ю.Л., Самохвалов К.Ф. Современная философия математики: недомогания и лечение. Новосибирск, 2007.

13. Клини С. Введение в метаматематику. 1957.

14. Мендельсон Э. Введение в математическую логику. М., 1976.

15. Feferman S.Arithmetization of metamathematics in a general setting // Fundam. Math. 1960. Vol. 49. P. 35-92.

16. Самохвалов К.Ф. Уточнения обычной интерпретации теорем Геделя о неполноте и понятия рекурсивной перечислимости // Проблемы логики и методологии науки. Новосибирск, 1982. С. 42-57.

17. Френкель А.А., БарХилел И. Основания теории множеств. М., 1966.

18. Kreisel G.Rewiew of Feferman's «Arithmetizationetc» // Mathematical Reviews. 1963.Vol. 25, № 5. P. 938-939.

Размещено на Allbest.ru