Эрнест Нагель, Джеймс Рой Ньюмен. Теорема Гёделя

Рубрика: 11. О разном

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

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

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

Эрнест Нагель, Джеймс Рой Ньюмен. Теорема Гёделя. Обложка

Скачать конспект (краткое содержание) в формате Word или pdf

Введение

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

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

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

Проблема непротиворечивости

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

В середине XIX столетия в работах Гаусса, Бойаи, Лобачевского, Римана и других математиков была доказана невозможность вывода аксиомы параллельности из остальных аксиом евклидовой геометрии. Этот результат имел громадное значение для понимания природы нашего мышления. В первую очередь он привлек внимание к тому поразительному факту, что можно доказать в качестве теоремы невозможность доказательства некоторых утверждений средствами данной системы.

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

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

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

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

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

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

Следующий важный шаг в решении обсуждаемой здесь проблемы непротиворечивости евклидовой геометрии предпринял Гильберт. Основная идея его метода подсказана аналитической геометрией, восходящей еще к Декарту. В предложенной Гильбертом «декартовской» интерпретации евклидовских аксиом они очевидным образом становятся истинными алгебраическими утверждениями. Например, фигурирующее в аксиомах плоской геометрии слово «точка» должно означать теперь пару действительных чисел, «прямая» — числовое соотношение, выражаемое уравнением первой степени с двумя неизвестными, «окружность» — числовое соотношение, выражаемое квадратным уравнением некоторого специального вида, и т.д. Геометрическое предложение, гласящее, что две различные точки однозначным образом определяют некоторую прямую, переходит теперь в истинное утверждение алгебры, согласно которому две различных пары действительных чисел однозначно определяют некоторое линейное уравнение; геометрическая теорема, согласно которой прямая и окружность пересекаются не более чем в двух точках, переходит в алгебраическую теорему о том, что система, состоящая из линейного и квадратного уравнений с двумя неизвестными, имеет самое большее две пары действительных корней, и т.д. Короче говоря, непротиворечивость евклидовских постулатов обосновывается тем обстоятельством, что они выполняются на некоторой алгебраической модели.

В некоторых областях математики, для которых существенную роль играют различные допущения о бесконечных совокупностях, были обнаружены весьма серьезные противоречия (именуемые обычно «антиномиями»). В частности, они были обнаружены в построенной Георгом Кантором в конце XIX в. теории бесконечных множеств (подробнее см. Чарльз Петцольд. Читаем Тьюринга, глава 2. Иррациональные и трансцендентные числа).

Бертран Рассел построил противоречие, оставаясь исключительно в рамках элементарной логики, — противоречие, в точности подобное тому, что было обнаружено первоначально в канторовской теории бесконечных классов (множеств). Антиномию Рассела можно описать следующим образом. Будем различать классы в зависимости от того, являются ли они своими собственными элементами или нет. Назовем класс «нормальным» в том и только в том случае, когда он не содержит самого себя в качестве элемента; в противном же случае будем называть класс «ненормальным». Примером нормального класса может служить класс всех математиков — ведь сам такой класс не является, очевидно, математиком и не является потому своим собственным элементом. Примером ненормального класса является класс всех мыслимых вещей; сам этот класс является, очевидно, «мыслимой вещью», а тем самым — и своим собственным элементом.

Определим теперь класс N — класс всех нормальных классов. Является ли N нормальным классом? Если N нормален, то он является своим собственным элементом (ведь, по определению, N содержит все нормальные классы). Но в таком случае N ненормален, так как в силу данного выше определения класс, содержащий самого себя в качестве элемента, является ненормальным. С другой стороны, если N — ненормальный класс, то он (в силу определения понятия ненормальности) является своим собственным элементом; но в таком случае N нормален, так как выше определено, что элементами N являются лишь нормальные классы. Короче говоря, N нормален тогда и только тогда, когда N ненормален. Отсюда следует, что утверждение «N — нормальный класс» является в одно и то же время истинным и ложным.

Абсолютные доказательства непротиворечивости

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

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

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

Все эти метаматематические высказывания не содержат никаких математических знаков и формул, а содержат лишь их имена. Точно так же, если мы хотим сказать что-нибудь о каком-либо слове, то мы должны использовать в качестве члена предложения не само слово/выражение, а его имя. Обычно это делается при помощи кавычек. Фраза «Чикаго состоит из трех слогов» безграмотна. Мы должны написать: «„Чикаго" состоит из трех слогов». Точно так же неверно было бы написать: «х = 5 есть уравнение». Правильная запись такова: «„х = 5" есть уравнение».

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

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

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

Другое направление исследований преследовало целью представить всю чистую математику как часть формальной логики. Классическое выражение эта линия развития логики и математики получила в Principia Mathematica (Р.М.) Уайтхеда и Рассела (1910–1913). Рассел же (а еще ранее немецкий математик Готтлоб Фреге) поставил своей целью показать, что все арифметические понятия можно определить в чисто логических терминах, а все аксиомы арифметики вывести из небольшого числа предложений, которые можно было бы квалифицировать как чисто логические истины.

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

Один пример абсолютного доказательства непротиворечивости

В качестве переменных мы будем использовать буквы «р», «q», «r», …, «p1», «p2» …, «<q1», «q2», … Постоянные символы (константы) — это «пропозициональные» связки и знаки препинания. Мы будем употреблять следующие пропозициональные связки: «~» читается как «не»; «∨» — «или»; «⊃» — «если…, то…»; «•» — «и»; знаки препинания: «(» — «левая скобка», «)» — «правая скобка».

Формулой является каждая пропозициональная переменная. Если «S» обозначает некоторую формулу (именно обозначает, но не является формулой (является именем формулы); S, не принадлежащая алфавиту описываемого исчисления, относится к его метаязыку), то ее «формальное отрицание» «~(S)» также есть формула. Аналогично, если «S1» и «S2» суть обозначения некоторых формул, то выражения «(S1) ∨ (S2)», «(S1) ⊃ (S2)» и «(S1) • (S2)» также суть формулы.

Примеры формул: «р», «~р», «(р)⊃(q)», «((q)∨(r))⊃(р)». Однако выражения «(р)(~q)» или «((р)⊃(q))∨» формулами не являются, так как они не удовлетворяют приведенному здесь определению формулы.

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

Второе правило преобразования — это так называемое правило отделения (или modus ponens). Согласно этому правилу из любых двух формул, имеющих соответственно вид «S1» и «S1⊃S2», можно вывести и формулу «S2». Например, из формул «p∨~р» и «(р∨~р)⊃(р⊃р)» мы можем вывести «р⊃р».

Наконец, аксиомами нашего исчисления (по существу теми же, что в Principia Mathematica являются следующие четыре формулы:

  1. (p∨p)⊃р [если р или р, то р];
  2. p⊃(р∨q) [если р, то р или q];
  3. (р∨q)⊃(q∨p) [если р или q, то q или р];
  4. (p⊃q)⊃((r∨p)⊃(r∨q) [если р влечет q, то (r или р) влечет (r или q)].

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

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

Оказалось, что для столь простой системы свойство «быть тавтологией» наследственно относительно применений правила modus ponens. С другой стороны, можно привести пример формулы нашего исчисления, не являющейся тавтологией. Т.е., можно найти формулу, не являющуюся теоремой нашей системы. Но в случае противоречивости выбранной нами системы аксиом такой формулы в нашем исчислении не нашлось бы. Таким образом, из аксиом исчисления высказываний нельзя вывести никакой формулы одновременно с ее отрицанием. Этим и завершается абсолютное доказательство непротиворечивости исчисления высказываний.

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

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

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

Идея кодирования и ее использование в математике

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

Чтобы читателю было легче понять идею доказательства Гёделя, мы (следуя Гёделю) приведем вначале схему рассуждения, посредством которого получается логическая антиномия (противоречие), известная под названием парадокса Ришара (по имени описавшего ее в 1905 г. французского математика).

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

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

Исходя из такого упорядочения можно теперь расположить все определения рассматриваемого вида в последовательность, сопоставив каждому из них единственное натуральное число — номер в этой же последовательности. Тогда самое короткое (и стоящее ранее других в алфавитном порядке) определение получит номер 1, следующее за ним в этом «словаре определений» — номер 2 и т.д.

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

Пусть, например, определяющее выражение «не делиться ни на одно натуральное число, кроме самого себя и числа 1» оказалось в нашей последовательности на 17-м месте; ясно, что сопоставленное ему число 17 само подпадает под это определение. Пусть, с другой стороны, определяющее выражение «быть произведением некоторого натурального числа на то же самое число» получило номер 15; само число 15, очевидно, не является точным квадратом и потому данным свойством не обладает. Назовем числа, не обладающие свойствами, определяемыми предложениями, которым они соответствуют в описанной нами нумерации, ришаровыми. Таким образом, «ж — ришарово число» — это просто сокращение выражения «ж не обладает свойством, определяемым предложением, имеющим номер ж в данной словарной последовательности определяющих предложений». (Скажем, число 17 из нашего первого примера не является ришаровым, а число 15 из второго примера — ришарово.)

Теперь мы уже можем сформулировать парадокс Ришара. Определяющее выражение для свойства быть ришаровым числом описывает, очевидно, некоторое арифметическое свойство натуральных чисел. Значит, само определяющее выражение входит в описанную выше последовательность определяющих выражений. Но тогда оно имеет в этой последовательности некоторый номер, который мы обозначим через N. Зададим теперь вполне естественный вопрос (немедленно приводящий к антиномии Ришара): является ли число N ришаровым? Читатель, конечно, сразу увидит, что противоречие теперь неизбежно. В самом деле, число N является ришаровым в том и только в том случае, если оно не обладает свойством, описываемым предложением, имеющим номер N, т.е. не обладает свойством быть ришаровым! Короче говоря, N ришарово тогда и только тогда, когда оно не ришарово, т. е. утверждение «N — ришарово число» является одновременно истинным и ложным.

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

Теоремы Гёделя  [1]

Заключительные замечания

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

Платонизм (реализм) — доктрина, согласно которой математика не творит и не придумывает рассматриваемые в ней «объекты», а открывает их, подобно тому как, например, Колумб открыл Америку. Таким образом, согласно этой точке зрения, объекты должны в некотором смысле «существовать» до их «открытия».

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

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

По этой теме я ранее читал:

Даглас Хофштадтер. Гедель, Эшер, Бах. Эта бесконечная гирлянда

Грегори Хайтин. Пределы доказуемости

Чарльз Петцольд. Читаем Тьюринга

 

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


Прокомментировать