Мы легко принимаем действительность, может быть, потому, что интуитивно чувствуем: ничто реально не существует.
Хорхе Луис Борхес, “Бессмертный”
Всё взаимосвязано.
Томас Пинчон, “Радуга тяготения”
Есть теория, согласно которой в том случае, если кто-то точно выяснит, для чего и зачем появилась Вселенная, она тут же исчезнет, и ее заменит нечто другое, еще более бессмысленное и необъяснимое.
Есть другая теория, согласно которой это уже произошло.
Дуглас Адамс, “Ресторан на краю Вселенной”
Мы легко принимаем действительность, может быть, потому, что интуитивно чувствуем: ничто реально не существует.
Хорхе Луис Борхес, “Бессмертный”
Всё взаимосвязано.
Томас Пинчон, “Радуга тяготения”
Есть теория, согласно которой в том случае, если кто-то точно выяснит, для чего и зачем появилась Вселенная, она тут же исчезнет, и ее заменит нечто другое, еще более бессмысленное и необъяснимое.
Есть другая теория, согласно которой это уже произошло.
Дуглас Адамс, “Ресторан на краю Вселенной”
занимательное пособие по экспериментальной философии
1
2
1
Нашего робота зовут Гёдель в честь величайшего логика после Аристотеля (как его часто называют) Курта Гёделя. В этой главе речь, конечно же, пойдёт о его знаменитой теореме о неполноте*. Вспомним, что мы уже упоминали эту теорему в комментарии 3 Главы 3.
Что нам с вами важно знать о Гёделе?
Для начала вспомним его онтологическое доказательство существования бога (см. комментарий 4 Главы 3). А теперь исторический анекдот.
В 1947 году у Гёделя состоялись слушания по поводу получения им американского гражданства. Гёдель - естественно - перед слушанием решил проштудировать американскую конституцию на предмет противоречий и юридических лазеек - и конечно же нашёл их. Судья, перед которым предстал Гёдель, заметил, что бывшая страна проживания Гёделя - Германия (и тут судья ошибся, потому что у Гёделя было австрийское гражданство) - находилась под властью диктатуры, что, к счастью, в Америке невозможно.
- Отнюдь, - ответил Гёдель. - Я сейчас вам покажу, каким образом американская конституция может обеспечить приход к власти диктатора.
Исследователи до сих пор спорят, что именно нашёл Гёдель в конституции, но, к сожалению, записи тех слушаний не сохранилось.
А теперь от конституции перейдём к теореме.
Курт Гёдель доказал теорему о неполноте в 25 лет и представил её на конгрессе в Кёнигсберге в 1930 году. Значение доклада Гёделя, как пишет Густаво Эрнесто Пинейро в книге о теореме, сравнимо только с "Метафизикой" Аристотеля.
Но почему для нас в этой книге важна какая-то там (пусть и очень важная) теорема о формальной системе арифметики?
На это есть несколько причин.
1) Как уже упоминалось, доказательство теоремы Гёделя замечательно тем, что оно: во-первых, говорит о системе изнутри самой системы. Да, конечно, арифметику нельзя сравнить по сложности с философией бытия, и тем не менее - Гёдель дал пример, некий образец для подражания. Хайдеггер предлагает Дазайну, погружённому в Бытие, говорить о его собственном Бытии изнутри этого самого Бытия. Это выглядит невозможным; ну что ж, пусть это будет возможным хотя бы на уровне математики. Мы очень подробно рассмотрим, как именно Гёдель получил свой результат.
Во-вторых, доказательство теоремы использует принцип самореференции, не скатываясь при этом в парадокс Рассела, Ришара** и тому подобные.
2) Теорема Гёделя поднимает крайне важные для наших целей вопросы взаимоотношений синтаксиса и семантики***. Откуда берётся смысл? Каким образом символы, поставленные в определённом порядке, рождают нечто большее, чем сами символы? Может ли мета-язык быть идентичен языку (см. причину 1)? Может ли синтаксис породить все возможные смыслы? И так далее.
3) Является ли теорема Гёделя доказательством того, что разум мощнее формальной манипуляции символами****? Некоторые философы считают, что да. Например, Джон Р. Лукас в нашумевшей статье "Разум, машины и Гёдель" на основе теоремы Гёделя пытается опровергнуть теорию сильного ИИ (см. комментарий 3 Главы 5):
Мне кажется, что теорема Гёделя доказывает, что механицизм неверен, то есть что разум не может быть объяснён как машина. [...] Теорема Гёделя должна быть применима к кибернетическим машинам, потому что в сущности машины заложено, что она должна быть конкретной реализацией формальной системы. Отсюда следует, что для любой машины, которая непротиворечива и способна выполнять простые арифметические расчёты, существует формула, которую она не сможет доказать – то есть, эта формула недоказуема в системе, – но которая, как мы видим, верна. Отсюда следует, что никакая машина не может быть полной или адекватной моделью разума, что разум существенно отличен от машин.[...]
Гёделева формула – Ахиллесова пята кибернетической машины. И следовательно, мы не можем надеяться когда-либо построить машину, которая будет способна делать всё, что может человек; у нас в принципе никогда не будет механической модели разума.
Дуглас Хофштадтер, будучи сторонником теории сильного ИИ, возражает Лукасу в книге "Гёдель, Эшер, Бах". Но оставим пока его возражения до лучших времён.
4) Доказательство теоремы Гёделя даст нам повод поговорить о семиотике - науке о знаках, знаковых системах, интерпретации знаков, взаимоотношении символов и объектов, а также коммуникации с помощью знаковых систем*****.
Здесь справедливо будет задать вопрос: а при чём здесь теорема Гёделя?
Дело в том, что, пытаясь понять доказательство теоремы о неполноте, автор сего произведения столкнулся с некоторой путаницей (у себя в голове), связанной с формулами, представляющими знаки, и знаками, представляющими формулы; с символьными значениями чисел и числовыми значениями символов... ну, вы уже поняли закономерность. Так вот, чтобы всю эту мешанину распутать, автору пришлось изрядно попотеть, а потом ещё и попробовать изложить доказательство так, чтобы не создавать этой путаницы в головах читателей. В дальнейшем вы увидите, насколько эти попытки увенчались успехом.
5) В начале 20-го века три "деструктивных" научных события во многом определили дальнейшее развитие философской мысли: Эйнштейн разрушил классический мир Ньютона с его бесконечной, равномерной и всеобъемлющей пустотой, в которой ровно тикают единые для всех космические часы; Гейзенберг уничтожил возможность абсолютного знания в микромире; Гёдель подорвал основы математики.
Ребекка Голдстин в книге "Incompleteness: The Proof and Paradox of Kurt Gödel" пишет об этом так:
Теорема Гёделя является третьей опорой, вместе с принципом неопределенности Гейзенберга****** и теорией относительности Эйнштейна, этого треножника теоретических катаклизмов, которые, как считалось, вызывают нарушения глубоко в основах "точных наук". Три этих открытия, кажется, переносят нас в незнакомый мир, который настолько расходится с нашими предыдущими предположениями и интуицией, что почти столетие спустя мы всё ещё пытаемся понять, где именно мы оказались. [...]
Работы Гёделя и Эйнштейна, признанные всеми революционными и получившие наводящие на размышления названия, вместе с принципом неопределенности Гейзенберга обычно группируются и приводятся в качестве одной из наиболее веских причин, по которым современная мысль отказывается от "мифа об объективности". Такая интерпретация этой триады сама по себе является частью современной - или, точнее, постмодернистской******* - мифологии.
6) Наконец, сам Гёдель утверждал, что его теорема доказывает справедливость платонистической точки зрения. Рассуждал он примерно так:
Наш разум содержит интуитивное представление о натуральных числах. Мы понимаем, что означает операция сложения (мысленно представляя как к одной кучке предметов прибавляется вторая кучка) и операция умножения (кучка предметов, взятая столько-то раз). При этом первая теорема о неполноте утверждает, что чисто синтаксических методов в нашей модели недостаточно, чтобы получить все недостижимые истины этой системы. Это, по мнению Гёделя, доказывает, что объекты, которые мы понимаем под натуральными числами, существуют в идеальной реальности Платона - математическая реальность превосходит все формальные попытки "усмирить" её.
Хочется надеяться, что всех перечисленных причин достаточно для оправдания существования этой главы. Да даже если бы и не было ни одной из этих причин, доказательство теоремы Гёделя настолько прекрасно само по себе, что в любом случае стоило бы его разобрать!
2
"Манипуляции с символами, лишёнными всякого смысла. Смыслы, возникающие из этих манипуляций". Эта фраза настолько важна для понимания данной главы, что мы просто обязаны задержаться на ней подольше.
Прежде всего, читатель должен твёрдо уяснить: математика - это не наука о числах. Слово Нагелю и Рою (книга "Теорема Гёделя"):
...математика есть попросту наука, изучающая получение логических следствий из некоторых заданных аксиом, или постулатов********. Фактически стало общепризнанным то обстоятельство, что математические выводы и заключения не имеют никакого другого смысла, помимо того в некотором роде специального смысла, который связан с терминами или выражениями, входящими в постулаты. Таким образом, математика оказалась даже еще значительно более абстрактной и формальной наукой, чем это было принято считать: более абстрактной — поскольку математические предложения в принципе могут быть истолкованы скорее как утверждения о чем угодно, а не как утверждения, относящиеся к некоторым фиксированным множествам предметов и неотъемлемым свойствам этих предметов; более формальной — поскольку правильность математических доказательств гарантируется чисто формальной структурой некоторых предложений, а отнюдь не содержанием этих предложений.
В 1920-1930 годах великий немецкий математик Давид Гильберт предложил программу полной формализации математики. В этой программе утверждалось, что любая математическая теория должна быть основана на аксиомах (утверждениях, не требующих доказательств), а любое утверждение (теорема) может быть доказано на основе этих аксиом с помощью заданных правил вывода. Таким образом, справедливость каждого утверждения можно будет проверить чисто механически - с помощью манипуляций над ничего не значащими значками, составляющими формулы. И только если математики в качестве аксиом смогут выбрать такие последовательности значков, которые, будучи прочитанными людьми, обретут некий смысл - такого рода "выдумки" получат своё семантическое обоснование и приведут к построению стройной и полностью формализованной математики*********.
* Наиболее проницательный из всех Пресловутых Проницательных Читателей сего произведения в этом месте, конечно, спросит: о какой именно теореме Гёделя идёт речь? Ведь их, как всем известно, две!
Успокоим этого читателя: теорем без всякого сомнения две (и мы будем об этом говорить), но для простоты станем называть этот комплекс теорем просто "Теоремой Гёделя о неполноте".
** См. комментарий 5 Главы 3.
*** Синтаксис это совокупность правил построения объектов языка - предложений или формул.
Синтаксис совершенно однозначно может быть определён как корректный или нет.
Семантика это совокупность соглашений, описывающих наше понимание фраз, предложений или формул.
Семантика позволяет
считать одни формулы верными, а другие нет. Однако, такой однозначности как с синтаксисом здесь уже нет.
**** См. Главу 5. Весь эксперимент с "китайской комнатой" представляет собой именно этот спор.
***** Уже неоднократно встреченный нами филолог и семиотик Ю.М.Лотман в своей книге "Семиосфера" пишет:
Предмет семиотики — науки о коммуникативных системах и знаках, которыми в процессе общения пользуются люди (и не только люди, но и животные или машины), — прост. Что может быть проще и знакомее ситуации «я сказал — ты понял»? А между тем именно эта ситуация дает обильные основания для научных размышлений. Каков механизм передачи информации? Что обеспечивает надежность ее передачи? В каких случаях можно в ней сомневаться? И что означает «понимать»?
(см. продолжение сноски)
****** Принцип неопределённости Гейзенберга гласит, что невозможно одновременно с точностью определить координаты и скорость квантовой частицы (заметьте, что речь идёт о микромире).
На самом деле этот принцип связывает и другие пары характеристик элементарных частиц. Например, также невозможно
точно измерить энергию квантовой системы и определить момент времени, в который она обладает этой энергией.
******* Философ и критик Терри Иглтон определяет постмодернизм так:
Постмодернизм - это стиль мышления, который с подозрением относится к классическим понятиям истины, разума, идентичности и объективности, к идее всеобщего прогресса или эмансипации, единых рамок, больших нарративов и окончательных объяснений ... [Он] видит мир как случайный, необоснованный, разнообразный, нестабильный, неопределенный; как набор разобщенных культур или интерпретаций, порождающих определенную степень скептицизма в отношении объективности истины, истории и норм, данности природы и согласованности идентичностей.
******** В комментарии 3 мы увидим, как именно это делается.
********* Вот, что о семантикосинтаксическом дуализме говорит
Г. Э. Пинейро в книге "Гёдель. Теоремы о неполноте":
Основная предпосылка программы Гильберта состояла в требовании того, чтобы справедливость семантических аспектов математики контролировалась синтаксическими методами. Синтаксис, ясный и не вызывающий сомнений, должен был ограничивать семантику, грозящую парадоксами.
***** (продолжение сноски)
И дальше:
Английский писатель Дж. Свифт в фантастическом путешествии Гулливера на остров Лапуту описал чудаков-ученых, которые решили заменить слова предметами. Нагруженные разнообразными вещами, тащились они по городу и, вместо того, чтобы произнести слово, протягивали друг другу предметы. Именно в таком положении находилось бы человечество, если бы оно не сделало некогда одного из величайших открытий в своей истории — не изобрело знаков. Знаки заменяют сущности, явления и вещи и позволяют людям обмениваться информацией.
Фердинанд де Соссюр - основатель семиотики, которую он называл семиологией, определял её так:
Семиология – это наука о знаках, которая изучает, что происходит, когда человек пытается передать свою мысль с помощью средств, которые неизбежно носят условный характер.
Другой знаменитый семиотик Умберто Эко в своей книге "Отсутствующая структура. Введение в семиологию" даёт следующее определение семиологии:
Семиология рассматривает все явления культуры как знаковые системы, предполагая, что они таковыми и являются, будучи, таким образом, также феноменами коммуникации. Тем самым она отвечает потребностям самых разнообразных современных научных дисциплин, как раз и пытающихся свести явления самого разного порядка к факту коммуникации. Психология изучает восприятие как факт коммуникации, генетика устанавливает коды наследственной информации, нейрофизиология описывает процесс передачи сигналов с периферии нервных окончаний к коре головного мозга, при этом все эти дисциплины неизбежно обращаются к математической теории информации, которая и была создана для того, чтобы объяснить процесс передачи сигнала на уровне машины на основе общих положений физико-математических дисциплин.
Термин "семиотика" принято связывать с американской традицией (основоположником которой был Чарльз Сандерс Пирс), а термин "семиология" - с европейской (начиная с Соссюра). Но на самом деле никакой особенной разницы между этими понятиями нет.
3
3
Шестерёночный механизм нашего Робота является метафорой, которая поможет нам разобраться в теореме Гёделя и её доказательстве. Оговоримся: она поможет нам разобраться не в самом доказательстве Гёделя (которое довольно технически сложно и доступно для понимания только математикам), а в схеме этого доказательства. Собственно, вся неспециальная литература по теореме о неполноте намечает только схему этого доказательства, и мы последуем этому примеру - дважды. Один раз схема доказательства будет приведена в рисунках основного действия, а второй раз - в комментариях. Эта вторая схема будет уже гораздо более подробной и близкой к настоящему доказательству*.
Метафорой чего же именно является шестерёночный механизм Робота Гёделя? Ответ может испугать неподготовленного читателя, но ни в коем случае не надо бояться! Поверьте, здесь всё достаточно просто: он является метафорой формальной (или аксиоматической) системы.
В этом месте можно пуститься в длинные рассуждения о том, что же такое формальные системы и с чем их едят, но вместо этого мы приведём крайне важный и совершенно необходимый для понимания этой главы словарь формальных систем, а после этого рассмотрим примеры. Этого должно быть достаточно для преодоления начального барьера для любого неподготовленного читателя.
Словарь формальных систем
Алфавит - набор абстрактных символов, используемых для формирования формул формальной системы.
Формула - любая конечная последовательность символов алфавита.
Грамматика - набор условий или критериев, с помощью которых допустимые в системе формулы отличаются от недопустимых.
Правила вывода - набор логических (синтаксических, типографских) операций, которые могут выполняться над формулами для преобразования одной допустимой формулы в другую.
Аксиома - формула, которая считается допустимой по определению, без доказательства.
Формальная система - абстрактная сущность, состоящая из алфавита,
формул, грамматики, аксиом и правил вывода.
Последовательность доказательств - конечная последовательность допустимых формул, такая, что каждая формула следует из своей предшественницы, с помощью применения одного из правил вывода.
Теорема - заключительная (завершающая) формула в некоторой последовательности доказательств.
Полная система - формальная система, в которой каждое истинное утверждение может быть доказано, т.е. каждая истинная формула является теоремой системы.
Непротиворечивая система - формальная система, в которой любое истинное утверждение и его отрицание не являются одновременно доказуемыми, т.е. обе эти формулы не могут быть теоремами.
Все эти понятия лучше всего объяснить на простых примерах**.
Рассмотрим элементарную формальную систему (назовём её Х в честь Хармса), алфавит которой состоит из двух символов:
наклоняли и самовар
Пусть вас не смущает, что наши "символы" на самом деле состоят из многих символов. Понятно, что это не имеет никакого значения, потому что мы с тем же успехом могли бы заменить алфавит нашей системы Х на нечто менее читабельное, например
N и S
и от этого ничего бы не изменилось***.
Итак, у нас есть алфавит. Как насчёт аксиом, то есть формул системы, которые не нуждаются в доказательствах? В системе Х есть только одна аксиома и выглядит она так:
самовар
- Что за чертовщина? - удивится читатель. Почему этот символ вдруг стал аксиомой? И что это за формула, состоящая из одного символа?
Отвечаем на первый вопрос: потому что нам так захотелось. Дело в том, что создатель формальной системы вправе определять, какие формулы являются её аксиомами. Мы - демиурги системы Х, и никто не вправе указывать нам, что является аксиомой, а что нет.
Ответ на второй вопрос прост: формулой системы может быть любая последовательность символов этой системы, в том числе и "последовательность", состоящая из одного символа.
Наконец, нам нужны правила вывода, чтобы из аксиомы получались теоремы. У нас будет только одно правило вывода:
Если F - формула Х,
то и
наклоняли F
тоже формула X.
Другими словами, к любой формуле системы можно слева присоединить символ наклоняли, и это в свою очередь тоже будет формулой системы.
Посмотрим на примеры некоторых теорем нашей системы. Начнём с аксиомы и применим к ней правило вывода:
самовар (аксиома) ⇒ (применяем правило вывода) ⇒
наклоняли самовар (F1)
Мы получили новую формулу F1 (можете считать её теоремой) нашей системы. А что, если мы снова применим к ней правило вывода?
наклоняли самовар (F1) ⇒ (применяем правило вывода) ⇒
наклоняли наклоняли самовар (F2)
Попробуем ещё раз:
наклоняли наклоняли самовар (F2) ⇒ (применяем правило вывода) ⇒
наклоняли наклоняли наклоняли самовар (F3)
Теперь уже понятно, что любая формула, в которой символ самовар предваряется любым числом символов наклоняли является формулой нашей системы X. При этом интуитивно понятно. что, например, формула
самовар наклоняли
не будет принадлежать грамматически верным формулам системы X, потому что она не может получена из аксиомы самовар с помощью нашего единственного правила вывода****.
* Если же читателя смущает большое количество формул, и вообще он пришёл сюда не за математикой, а за философией - такой читатель может смело пропустить комментарии и ограничиться картинками.
** А вот вам неожиданный пример ещё одной формальной системы - шахматы. Давайте очень кратко познакомимся с этой системой, тем более, что в этой главы шахматы нам ещё пригодятся.
(см. продолжение сноски)
*** В программировании - а в особенности в языке программирования Lisp -такого рода неделимые символы называются атомами по понятной причине.
**** Ну хорошо, с синтаксисом системы Х мы разобрались, а что же с семантикой? Какой именно смысл у формул (предложений) нашей системы?
(см. продолжение сноски)
** (продолжение сноски)
Алфавитом шахматной формальной системы являются символы фигур, которые можно обозначать любым способом - с помощью алгебраической нотации или на диаграмме - как вы уже знаете, сами обозначения символов роли не играют. Собственно то же и с формулами: одна диаграмма может представлять формулу системы. Эта же формула может быть представлена строкой в виде перечисления фигур вместе с их положением на доске.
Аксиомой "шахматной формальной системы" будет начальное положение фигур на доске - это формула, которая раз и навсегда задана создателем игры (кто бы он ни был) и не требует никаких "доказательств".
Вот наша единственная аксиома:
Правила вывода в системе - ходы фигур. Каждая законная позиция является грамматически верной формулой системы.
Например, вот эта абсолютно безумная позиция является грамматически верной формулой системы, потому что её можно получить с помощью правильных ходов (правильных с точки зрения правил игры, а не прагматики):
При этом следующая простейшая позиция не является грамматически верной. Обратите внимание, что на доске два белых слона на чёрных полях. Такая позиция недостижима никакими законными ходами фигур:
Немедленная оговорка для пуристов: на самом деле на доске возможны два чернопольных слона, если представить, что одна из пешек, дошедших до последней горизонтали, была превращена в слона именно на чёрном поле. Но на приведённой диаграмме все пешки стоят на своих местах. Кстати - это ещё одна причина, почему данная позиция невозможна - слон просто не может перепрыгнуть через ряды пешек.
**** (продолжение сноски)
Говоря о семантике, мы пытаемся выйти за пределы системы. Внутри Х символы самовар и наклоняли не имеют никакого смысла: мы могли бы обозначить их другими значками, и система бы не изменилась. В то же время мы понимаем, что арифметическая формула 1 + 1 = 2 имеет гораздо более глубокий смысл, чем просто значки 1, +, 1, = и 2, поставленные друг за другом. С другой стороны эта формула обретает свою семантическую окраску, потому что мы выбираем придать её символам определённый смысл: мы как бы решаем вдохнуть в них жизнь.
Нагель и Рой в "Теореме Гёделя" пишут:
единственный вопрос, встающий перед чистым математиком (в отличие от естествоиспытателя, применяющего математику для решения конкретных задач), состоит вовсе не в том, истинны ли принятые им постулаты и полученные из постулатов следствия, а в том, действительно ли являются полученные им заключения логически необходимыми следствиями из начальных допущений.
В принципе ничто не мешает нам "вдохнуть жизнь" в систему Х. Например, аксиома
самовар
может обозначать самовар, спокойно стоящий на столе - исходную позицию любого самовара. Формула
наклоняли самовар
может значить, что дядя Петя, тётя Катя и другие пытаются извлечь немного оставшегося кипятка для опоздавшего Серёжи. А формула
наклоняли наклоняли наклоняли самовар
может говорить о том, что все обитатели дома (включая Жучку и Мурку) уже довольно давно предпринимают безуспешные усилия по наливанию чая. И чем больше символов наклоняли входит в формулу, тем больше времени прошло с момента первого наклона самовара.
Это довольно жалкие попытки придать смысл нашим формулам, но согласитесь - система Х убога по определению.
Говоря о семантике, нельзя не упомянуть и прагматику. Эти два понятия немного сложно различить, но давайте попробуем.
Семантика относится к значению слов в предложении (символов в формуле), не принимая во внимание контекст происходящего. Прагматика же рассматривает значение тех же слов в зависимости от ситуации. Например, чисто семантически наш самовар в формуле наклоняли наклоняли наклоняли самовар наклоняется сильней, чем в формуле наклоняли наклоняли самовар и уж точно сильней, чем в формуле наклоняли самовар. Собственно, больше мы об этом событии не знаем ничего. Если же рассматривать эти формулы в прагматическом смысле, то получится примерно то, о чём говорилось выше: это не просто самовар, а Иван Иваныч Самовар; наклоняют его домочадцы Серёжи, чтобы выцедить последнюю каплю кипятка для неумытого и неряшливого опоздавшего. Возможно, есть смысл рассматривать и мета-прагматику, то есть тот факт, что действие происходит не на самом деле, а в стихотворении, а именно в четвёртой с конца строфе; что написал его Хармс в 1928 году; что Хармс - не более, чем "знак" или "символ" человека по имени Даниил Ювачёв, что и само по себе это имя является не более, чем другим "обозначением" поэта - и так далее. Но мы не станем этого делать, а скажем только, что подробный разговор о знаках и символах впереди.
4
4
Один поворот рычага в этом случае соответствует получению очередной формулы в цепочке формального доказательства. Рычаг символизирует правило вывода.
Осмысленная Фраза, которую произносит робот в конце доказательства - это, естественно, теорема нашей формальной системы.
5
5
Заглавие этой песни называется «Пуговки для сюртуков».
— Вы хотите сказать — песня так называется? — спросила Алиса, стараясь заинтересоваться песней.
— Нет, — ты не понимаешь, — ответил нетерпеливо Рыцарь. — Это заглавие так называется. А песня называется «Древний старичок».
— Мне надо было спросить: это у песни такое заглавие? — поправилась Алиса.
— Да нет! Заглавие совсем другое. «С горем пополам!» Но это она только так называется!
— А песня эта какая? — спросила Алиса в полной растерянности.
— Я как раз собирался тебе об этом сказать. «Сидящий на стене»! Вот какая это песня!
Льюис Кэрролл,
"Сквозь зеркало и что там увидела Алиса"
(перевод Н.Демуровой)
Да-да, у этого комментария есть эпиграф! Почему?
Дело в том, что этот великолепный диалог из "Алисы в Зазеркалье" необычайно важен для понимания того, что будет происходить в этой главе дальше.
Мартин Гарднер в своих комментариях пишет:
Для человека, искушенного в логике и семантике, все это вполне понятно. Песня эта есть «Сидящий на стене»; она называется «С горем пополам»; имя песни – «Древний старичок»; имя это называется «Пуговки для сюртуков». Кэрролл здесь различает предметы, имена предметов и имена имен предметов. «Пуговки для сюртуков», имя имени, принадлежит к той области, которую в современной логике именуют «метаязыком»*. Приняв соглашение о иерархии метаязыков, логикам удается избежать определенных парадоксов, которые мучили их со времен древних греков.
Этот диалог - нирвана для семиотика** (интересно, считается ли Льюис Кэрролл отцом семиотики?). Но в отличие от Мартина Гарднера мы с читателем не искушены в логике и семантике, а поэтому нам понадобится специальная диаграмма, чтобы разобраться в хитросплетениях Белого Рыцаря:
Ну что ж, вроде бы стало ясней***.
Зачем мы так подробно разбираем этот диалог? Как уже было сказано, каждое имя и мета-имя в нём понадобятся нам для того, чтобы лучше понять доказательство Гёделя (а поэтому вскоре будет ещё одна диаграмма, с ним связанная).
* Метаязык арифметики будет играть ключевую роль во всём, что касается нашей теоремы.
** Двигаться дальше без знакомства с Соссюром и Пирсом не имеет смысла. А потому мы этим сейчас и займёмся.
(см. продолжение сноски)
*** Некоторые комментаторы указывают на то, что сама песня Белого Рыцаря не есть "Сидящий на стене". В ответ на вопрос "А песня эта какая?" Белый Рыцарь должен был просто начать петь саму песню.
Существует история о том, как после исполнения Шубертом своего фортепианного произведения некая дама спросила его, что это произведение значит. В ответ Шуберт молча сел за рояль и снова сыграл то же самое. Значение музыки - это и есть сама музыка.
(см. продолжение сноски)
** (продолжение сноски)
С этими двумя мы уже кратко повстречались в комментарии 1. Давайте же посмотрим, в чём именно состоят их подходы к знакам, обозначениям, символам и прочему.
Фердинанд де Соссюр определил лингвистический знак (то есть, единицу потока знаков, составляющую коммуникацию) как диаду (то есть, единый объект, состоящий из двух частей), в которую входят "обозначаемое" (signified) и "обозначающее" (signifier). Эту диаду проще объяснить с помощью диаграммы:
Здесь: обозначаемое - это концепция курицы в голове говорящего (думающего), а обозначающее - само слово "курица". (Заметим в скобках, что само слово "курица" состоит из 1) знаков (signifiers) к, у, р, и, ц, а и
2) ментальных концепций этих букв (signifieds), вместе составляющих идею курицы).
Одной из центральных идей Соссюра является также случайный выбор знака (обозначающего) для обозначаемого.
Это и понятно: слово "курица", записанное шестью знаками, не имеет никакого отношения к ментальному образу курицы в голове говорящего, кроме общего договора, по которому данный символ привязан к этому образу. Единственное, что имеет значение для знака - это его уникальность, отличие от всех других знаков.
С ним согласен Шекспир:
Что в имени? То, что зовем мы розой, -
И под другим названьем сохраняло б
Свой сладкий запах! ☆
(пер. Щепкиной-Куперник)
А вот, что по этому поводу писал Мандельштам:
Живое слово не означает предмета, а свободно выбирает как бы для жилья, ту, иную предметную значимость, вещность, милое тело. И вокруг вещи слово блуждает свободно, как душа вокруг брошенного, но не забытого тела.
А уж что по этому поводу думает Шалтай-Болтай и упоминать не станем (но только потому, что встреча с этим удивительным лингвистом нам ещё предстоит).
Однако французский лингвист Эмиль Бенвенист спорит с Соссюром в том, что касается случайности выбора знака. Его идея состоит в том, что обозначающее настолько впитывается в нас с самого раннего возраста и настолько срастается с обозначаемым, что мы практически не разделяем эти два понятия в жизни. Эта идея крайне важна для понимания программы Гильберта и аксиом оснований математики. Дело в что, что любой человек, которому покажут уравнение 1+1=2, моментально и абсолютно рефлекторно поймёт, о чём идёт речь. Развидеть смысл этой формулы - всё равно что "пять минут не думать о розовом слоне". Мы срослись с этими знаками так прочно, что требуется немалое интеллектуальное усилие, чтобы перестать воспринимать эту формулу как высказывание мета-математики и начать думать о ней как о наборе лишённых всякого смысла типографских знаков (как требует от нас Гильберт).
В отличие от Соссюра Чарльз Пирс представил свою семиотическую модель как триаду, состоящую из следующих элементов:
1) Interpretant: это "расшифровка" знака, примерно соответствует обозначаемому Соссюра, то есть концепции представленной идеи.
2) Representamen: символ, представляющий концепцию. Соответствует обозначающему Соссюра.
3) Object: собственно объект - не ментальное представление в голове "расшифровщика", а именно объект, который и обозначается знаком Representamen. Пирс разделяет такого рода объект на категории: непосредственный объект и динамический объект (то есть объект, не зависящий от знака, но приводящий к созданию знака). Мы не будем углубляться во все эти хитросплетения.
Для примера посмотрим на "Фонтан" Марселя Дюшана:
В этой интерпретации, наблюдатель видит лишь писсуар - настоящий писсуар, без всякого отношения к Дюшану. Отсюда и знак этого объекта - слово "писсуар", и концепция в голове смотрящего такая же.
Приключения писсуара на этом, однако, не заканчиваются. Здесь происходит то, что Умберто Эко назвал "бесконечным семиозисом". Семиозис - процесс интерпретации знака, то есть создания Interpretant на основе Representamen. Взгляните на следующую диаграмму:
Концепция именно этого писсуара (Interpretant) в голове смотрящего сама становится знаком (Representamen), а именно символом объекта, представляющего собой уже не просто писсуар, а произведение искусства - потому что именно этот смысл придал ему Дюшан. А раз так, у этого объекта есть и свой собственный Interpretant - представление о данном произведении искусства в голове зрителя.
Но и на этом процесс не кончается: такое представление (Interpretant) должно - в качестве знака (Representamen) относиться к некоторому в высшей степени абстрактному объекту (Object) - а именно, не просто произведению искусства, а целой "вехе в искусстве", коей, по общему соглашению, является "Фонтан". Такая веха будет представлена своей собственной концепцией (Interpretant) в голове смотрящего - и так далее, вполне возможно, что до бесконечности (хотя мы и сомневаемся, что найдутся смельчаки, готовые продолжать эту диаграмму).
- Стоп-стоп, - скажет здесь неискушенный читатель. Всё это понятно - знаки, обозначения, курицы, писсуары... Но зачем всё это нужно? Какая от всего этого может быть польза?
Автор, однако, подготовился к этому вопросу. Польза от всего этого одна: все эти диады, триады и т. п. помогают нам структурировать мысли и идеи, которые мы в данный момент рассматриваем. Например, можно прямо сейчас объяснить, чем семиотические модели могут нам помочь в понимании доказательства Гёделя. Смотрите.
Возьмём нашу формулу:
1 + 1 = 2
и применим к ней диаду Соссюра:
Signified: один объект и другой объект, взятые вместе, представляют собой два объекта.
Signifier: 1 + 1 = 2
Итак, мы видим, что на уровне знаков, мы имеем дело с синтаксисом. Символы 1, +, 1, = и 2, поставленные в определённом порядке образуют некий единый знак - уравнение. Этот знак - подчеркнём это особо! - совершенно случаен. Сами по себе символы этого уравнения могут быть другими. Пойдём даже дальше и представим себе, что концепция "один объект и другой объект, взятые вместе, представляют собой два объекта" выражаются на языке неких инопланетян (а у них обязательно должна быть такая концепция!), например, одним единственным символом ֍. Для этих инопланетян не будет нужды использовать 5 символов, как это делаем мы. При одном беглом взгляде на ֍ в их инопланетных головах немедленно будет возникать образ двух объектов, взятых вместе.
Таким образом, диада Соссюра позволила нам разделить "знак, обозначающий уравнение" на два языка: чисто синтаксический язык математики и чисто семантический языке мета-математики. Напомним ещё раз, что доказательство теоремы Гёделя как раз и заключается в том, что высказывания математики говорят о высказываниях мета-математики на языке самой математики.
А теперь посмотрим, как будет выглядеть триада Пирса по отношению к нашей формуле:
Interpretant: один объект и другой объект, взятые вместе, представляют собой два объекта.
Representamen: 1 + 1 = 2
Object: ?
Интересно, а что же такое в данном случае "объект"? По всей видимости (если принять платонистическую точку зрения), объект этого уравнения существует в идеальном мире, откуда его и извлекают - в равной степени и мы, и инопланетяне.
Вообще же, вопрос "а зачем всё это нужно?" подходит и ко всей философии целиком. И ответ будет тем же: философия помогает структурировать мысли наблюдателя о наблюдаемой системе. А так как в данном случае наблюдатель является частью системы, то такого рода структурирование помогает упорядочивать саму систему.
*** (продолжение сноски)
То же самое пишет и Лев Толстой:
Если же бы я хотел сказать словами все то, что имел в виду выразить романом, то я должен бы был написать роман тот самый, который я написал, сначала. И если близорукие критики думают, что я хотел описывать только то, что мне нравится, как обедает Облонский и какие плечи у Карениной, то они ошибаются. Во всем, почти во всем, что я писал, мною руководила потребность собрания мыслей, сцепленных между собой для выражения себя, но каждая мысль, выраженная словами особо, теряет свой смысл, страшно понижается, когда берется одна из того сцепления, в котором она находится.
Как здесь не вспомнить удивительно глубокую философскую заметку нашего старинного друга Хармса:
1. Значение всякого предмета многообразно. Уничтожая все значения, кроме одного, мы тем самым делаем данный предмет невозможным. Уничтожая и это последнее значение, мы уничтожаем и само существование предмета.
2. Всякий предмет (неодушевленный и созданный человеком) обладает четырьмя рабочими значениями и пятым сущим значением.
Первые четыре суть: 1) Начертательное значение (геометрическое), 2) целевое значение (утилитарное), 3) значение эмоционального воздействия на человека, 4) значение эстетического воздействия на человека.
Пятое значение определяется самим фактом существования предмета. Оно вне связи предмета с человеком и служит самому предмету. Пятое значение — есть свободная воля предмета.
[…]
6. Пятое значение шкафа — есть шкаф.
Пятое значение бега — есть бег.
Очень интересно, если задуматься: уничтожая все значения предмета, мы делаем сам этот предмет невозможным. И в самом деле - может ли существовать предмет без всякого значения?
☆ Да и целиком весь отрывок слишком хорош, чтобы можно было им пренебречь. Встречайте прадедушку семиотики - Уильяма Шекспира:
Джульетта
Одно ведь имя лишь твое - мне враг,
А ты - ведь это ты, а не Монтекки.
Монтекки - что такое это значит?
Ведь это не рука, и не нога,
И не лицо твое, и не любая
Часть тела. О, возьми другое имя!
Что в имени? То, что зовем мы розой, -
И под другим названьем сохраняло б
Свой сладкий запах! Так, когда Ромео
Не звался бы Ромео, он хранил бы
Все милые достоинства свои
Без имени. Так сбрось же это имя!
Оно ведь даже и не часть тебя.
Взамен его меня возьми ты всю!
[...]
Ромео
Я не знаю,
Как мне себя по имени назвать.
Мне это имя стала ненавистно,
Моя святыня: ведь оно - твой враг.
Когда б его написанным я видел,
Я б это слово тотчас разорвал.
6
6
Прежде, чем что-либо объяснять, вернёмся на минуту к сноске * комментария 5 Главы 3. Речь там шла о парадоксе Ришара в упрощённой версии Берри. Для наших же целей здесь нужно привести оригинальную версию парадокса Ришара.
Возьмём множество самых разных утверждений о числах*, например "число, которое не делится ни на одно целое число, кроме самого себя и числа 1" (определение простого числа) или "целое число делится на другое целое число" и т. д.
Каждому такому высказыванию поставим в соответствие некоторое целое число, причём высказывание, описание которого содержит меньше букв будет иметь порядковый номер меньше, чем описание, содержащее больше букв. Если число букв совпадает, будет определять порядок лексикографически, то есть сортировкой по алфавиту соответствующих букв в двух предложениях**.
Мы получили пример кодирования или mapping, который широко применяется в математике.
И теперь мы полностью готовы к тому, чтобы познакомиться с первым гениальным шагом, предпринятым Гёделем на пути к доказательству своей теоремы.
Для начала Гёдель назначил каждому символу алфавита формальной системы арифметики (см. комментарий 2) некое целое число. Выбор числа может быть совершенно случаен, например:
A ➝ 1
B ➝ 2
...
T ➝ 20
...
Z ➝ 26
= ➝ 27
+ ➝ 28
- ➝ 29
* ➝ 30
/ ➝ 31
и так далее.
Составив такую таблицу, Гёдель смог под каждым символом каждой формулы записать их числовые соответствия, например:
A + B = C
1 28 2 27 3
Дальше, возьмём возрастающую последовательность простых чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...
и возведём каждое из чисел этой последовательности в степень, соответствующую числу, находящемуся под символами нашей формулы; а затем перемножим все получившиеся степени:
2^1 * 3^28 * 5^2 * 7^27 * 11^3
Получившееся число огромно, но это не имеет никакого значения. А вот что имеет значение, так это тот факт, что: во-первых, такое численное значение каждой формулы уникально, а во-вторых - благодаря основной теореме арифметики*** - из этого числа можно легко получить назад исходную формулу!
Такое число называется гёделевским номером формулы - здесь и далее ГН.
Прочувствуйте грандиозность полученного результата: арифметические формулы, сообщающие некие факты о числах, сами превратились в числа, с которыми имеет дело эта самая арифметика Но это ещё только начало восхитительного пути. Мы продолжим его в следующих комментариях.
Таким образом, наш Шестерёночный Шифр, описывающий Осмысленные Фразы - это метафора гёделевского номера (ГН) формул арифметики. Сама же "Осмысленная Фраза" - метафора грамматически верной формулы (см. комментарий 2).
Но и это ещё не конец! Гёдель пошёл ещё дальше и применил свою нумерацию не только к отдельным формулам, но и к целым доказательствам****.
* Воспользуемся примерами из книги Нагеля и Ньюмена "Теорема Гёделя".
** Здесь мы приведём сам парадокс Ришара, чтобы не отвлекать читателя от основной идеи комментария.
(см. продолжение сноски)
*** Основная теорема арифметики гласит:
Каждое натуральное число n > 1 можно представить в виде n=p1 * p2 * ... * pk где p1, p2..., pk — простые числа, причём такое представление единственно, если не учитывать порядок следования множителей.
А порядок следования множителей мы знаем: это возрастающая последовательность простых чисел. Именно это даст нам возможность правильно восстановить порядок символов в формуле.
**** Давайте разберём на конкретном примере, как именно это делается.
(см. продолжение сноски)
** (продолжение сноски)
Рассмотрим какое-нибудь утверждение, например вышеприведённое "не делится ни на одно целое число, кроме самого себя и числа 1". Пусть в нашей кодировке этому утверждению присвоен номер 17. А теперь посмотрим на само число 17: делится ли оно само на какое-то другое число, кроме 1 и 17? Очевидно, что нет. Таким образом, порядковый номер определения сам подпадает под это определение. А теперь предположим, что выражение "быть произведением некоторого натурального числа на то же самое число" (то есть, определение квадрата) имеет порядковый номер 15. Число 15 само квадратом не является, а следовательно в данном случае порядковый номер определения не подпадает под само это определение. Назовём такое число ришаровым. В нашем примере 15 - ришарово число, а 17 - не ришарово☆.
А как быть с самим утверждением "быть ришаровым числом"? Это ведь тоже некое утверждение о числах, не правда ли? А раз так, то у него должен быть свой порядковый номер в нашей последовательности - некое число Х.
Вопрос: является ли число Х ришаровым? Если вспомнить определение, это означает, что порядковый номер определения ришарова числа (то есть Х) сам не должен обладать свойством быть ришаровым. Но тогда утверждение, с которого мы начали, а именно "Х - ришарово число", должно быть ложным. В этом и заключается парадокс. Опровержение этого парадокса см. в Главе 3.
**** (продолжение сноски)
Воспользуемся примером из комментария 3. Алфавит нашей формальной системы состоит из двух символов, которым мы присвоим гёделевские номера:
наклоняли ➝ 1
самовар ➝ 2
У нас есть одна аксиома, ГН которой тоже легко вычислить:
самовар
2^2 = 4
Как вы помните, из этой аксиомы по правилу вывода можно получить формулу со своим ГН
наклоняли самовар
2^1 * 3^2 = 18
Попробуем ещё раз применить формулу вывода:
наклоняли наклоняли самовар
2^1 * 3^1 * 5^2 = 150
Назовём получившуюся формулу теоремой. А теперь получим гёделевский номер доказательства этой теоремы. Применим ту же систему, что и с отдельными формулами, но теперь степень каждого последующего простого числа будет ГН очередной формулы:
2^4 * 3^18 * 5^150 = 4.34313389×10^114
Даже для такой простой системы и крошечной теоремы её ГН - поистине гигантское число (больше, чем googol☆☆!). Но, как уже было сказано, это не имеет никакого значения; ведь нам удалось совершенно однозначно сопоставить доказательство теоремы с целым числом. Это даёт нам возможность рассуждать о природе чисел и одновременно в равной мере рассуждать на языке мета-математики о математических утверждениях, которые эти числа представляют (теоремах системы). Если это не потрясает ваше воображение, то, наверное, его уже ничто не может потрясти.
Чтобы не быть голословным, вот вам пример. Хотите узнать как сильно наклоняли самовар? Сколько именно усилий приложили дядя Петя, тётя Катя, Жучка, Мурка и другие? Пожалуйста: разложите число 4.34313389×10^114 на простые множители (2, 3, 5 - число всех формул в цепочке вывода) и вычтите из общего числа множителей единицу (одна из формул - аксиома самовар). Получилось число 2, то есть наклоняли наклоняли. Вот именно с такой силой его и наклоняли. Ещё раз: усилие семьи по наклонению самовара прямо пропорционально числу простых множителей гёделевского номера теоремы о наклоне самовара.
Усилия семьи - язык мета-математики (мы говорим о смысле формулы); число простых множителей - язык математики (мы говорим в терминах чисел).
☆ Некую аналогию определения ришаровых чисел можно увидеть и на комментируемом рисунке. Робот говорит: "Шестерёночные Шифры тоже могут быть Осмысленными Фразами". В терминах парадокса Ришара Шестерёночный Шифр Осмысленной Фразы, который сам не является Осмысленной Фразой - это "ришаров" Шестерёночный Шифр. А тот, который и сам представляет собой ОФ - не ришаров.
☆☆ Гугол (googol) - это единица со 100 нулями (10^100). Большие числа вообще очень интересная тема, но, к сожалению, она займёт на этой странице слишком много места.
7
8
9
7
В этом месте необходимо немедленно сделать замечание: мистер Цо говорит о достижениях Робота Гёделя, а вовсе не о реальном Гёделе. Никакого отношения к предложениям человеческого языка теорема Гёделя не имеет.
8
В сноске **** комментария 6 говорилось о той самой связи (вовсе не таинственной, конечно) между формулами системы и их гёделевскими номерами. Дуглас Хофштадтер называет множество гёделевских номеров доказуемых формул формальной системы арифметики* prim numbers. Как всегда у Хофштадтера, это игра слов: prime numbers + PRIncipia Mathematica. В нашем примере с самоваром из комментария 6 это множество чисел 4, 18, 150 и так далее.
В книге "I am a Strange Loop" Хофштадтер пишет:
Таким образом, казалось бы, prim numbers скрытым образом содержат в себе все математические знания, упакованные внутри них! Никакая другая последовательность чисел, когда-либо придуманная кем-либо до Гёделя, не обладала подобными магическими качествами оракула. Эти удивительные цифры кажутся на вес золота!
К сожалению, эти числа только кажутся таковыми, и на это есть две причины. Во-первых, невозможно сказать, является ли данное число prim или нет; а во-вторых, эти числа не заключают в себе все математические знания. Вспомним определение: prim numbers - это множество ГН доказуемых формул. Но Гёдель как раз и доказал, что существуют такие теоремы, которые невозможно доказать - проще говоря, недоказуемые истинные формулы. А это значит, что существуют такие числа, которые содержат в себе истинное математическое знание, но их ГН не принадлежит множеству prim numbers.
9
"Чем ворон похож на конторку?" ("Why is a raven like a writing desk?") - загадка Шляпника из "Алисы в стране чудес" по всей видимости не имеет однозначного решения**. Сам Кэрролл писал об этом:
Меня так часто спрашивали о том, можно ли найти ответ на загадку Шляпника, что мне следует, пожалуй, запечатлеть здесь вариант, который мог бы, как мне кажется, быть достаточно приемлемым, а именно: "С помощью того и другого можно давать ответы, хоть и плоские; их никогда не ставят не той стороной!" Впрочем, это мне пришло в голову уже позже; загадка поначалу не имела отгадки.
К сожалению, перевести эту игру слов невозможно. В оригинале: "Because it can produce a few notes, tho they are very flat", note - это и "заметка" и "нота", а flat в данном случае обозначает как "плоский", так и "ноту, пониженную бемолем".
* Эта система разработана Расселом и Уайтхедом в их фундаментальном труде Principia Mathematica
(см. комментарий 12)
** Одним из наиболее оригинальных вариантов является такой ответ: "Эдгар Аллан По писал на обоих (имеется в виду, что он писал на рукописи стихотворения "Ворон").
10
10
Читатель, конечно, в этом месте нашей главы уже и без подсказки понимает, почему это основной вопрос жизни Робота Гёделя.
"Можно ли с помощью разных манипуляций с шетерёнками получить все Осмысленные Фразы" на язык математики переводится так: "можно ли доказать все теоремы формальной системы арифметики с помощью синтаксических правил вывода, применённых к аксиомам" (то есть, с помощью чисто типографских манипуляций лишёнными всякого смысла значков*). Ответом на этот вопрос, конечно является громкое гёделевское "нет".
* Или лучше сказать "с помощью манипуляций лишённых всякого смысла значками"? О, великий и могучий!
11
12
11
С программой Гильберта мы уже познакомились в комментарии 2. В соответствии с ней мы должны уметь строить такую формальную систему математики (для начала - арифметики), в которой с помощью чисто механических правил вывода из строчек (формул) ничего не значащих символов, можно получить все истинные высказывания (теоремы) - такая система называется полной; и нельзя получить одновременно и высказывание, и его отрицание - такая система называется непротиворечивой.
12
Монументальный труд Бертрана Рассела и Альфреда Норта Уайтхеда Principia Mathematica (1910-1913) в трёх томах целиком посвящён основаниям математики.
Говоря исключительно кратко, задача Рассела и Уайтхеда состояла в том, чтобы вывести всю математику из формальной логики, приняв за основу минимальное количество аксиом. Естественно, такая система должна была быть непротиворечивой* , полной и не содержать парадоксов**.
К сожалению, Гёдель нанёс сокрушительный удар как по Principa Mathematica, так и по программе Гильберта. Программа оказалась абсолютно - никогда! - нереализуемой.
Хуже того: не только Principa Mathematica, но и любая другая аксиоматическая система подобного рода пала жертвой теоремы жестокого и беспощадного Курта Гёделя.
Хофштадтер в "Гёдель, Эшер, Бах" пишет:
«Основания математики» явились первой, но далеко не последней жертвой удара. Выражение «и родственные системы» в заглавии Гёделевой статьи говорит о многом. Если бы результат, полученный Гёделем, указывал бы только на дефект в работе Рассела и Уайтхеда, другие математики могли бы попытаться исправить ошибки в «Основаниях математики» и «перехитрить» теорему Гёделя. Однако это оказалось невозможным: теорема Гёделя была приложима ко всем аксиоматическим системам, ставившим своей целью то же, что и система Рассела и Уайтхеда. Для различных систем подходил один и тот же основной трюк. Короче, Гёдель показал, что понятие «доказуемости» уже, слабее понятия истинности вне зависимости от того, какую аксиоматическую систему мы выбираем.
Таким образом, теорема Гёделя произвела электризующий эффект на логиков, математиков и философов, заинтересованных в основах математики, поскольку она показала, что ни одна установленная система, какой бы сложной она не была, не может отразить всей сложности целых чисел: 0,1, 2, 3…
* Однажды на лекции Бертран Рассел показал как на основе ложной предпосылки (то есть, в противоречивой системе) можно доказать всё, что угодно.
Аудитория предложила доказать, что Смит (один из слушателей) является Папой Римским, исходя из ложной предпосылки о том, что 1 = 0. Рассел ответил: если 1 = 0, то при прибавлении 1 к обоим членам мы делаем вывод, что 2 = 1. Теперь подумаем о множестве, образованном Смитом и Папой. У этого множества два члена, но так как 2 = 1, то мы можем сказать, что у множества только один член. То есть Смит и Папа — это одно и то же лицо.
** Описание парадокса самого Рассела см. в комментарии 5 Главы 3.
13
13
Тот факт, что Робот сам произнёс теорему о Неполноте Шестерёночного механизма, как бы намекает на вторую теорему Гёделя. Эта теорема гласит:
ни одно непротиворечивое множество аксиом не содержит арифметики, достаточной для того, чтобы доказать свою собственную непротиворечивость.
Вернёмся к программе Гильберта (см. комментарий 2). Во-первых, эта программа требовала найти такое множество аксиом арифметики, чтобы каждая теорема в этой системе была доказуемой. А во-вторых, программа требовала, чтобы непротиворечивость этих аксиом проверялась алгоритмически. Вторая теорема Гёделя как раз и доказывает невозможность такой проверки.
Перефразируем вторую теорему Гёделя для того, чтобы лучше её понять:
допустим, что у нас есть система аксиом, которая непротиворечива и может доказать все истинные высказывания (то есть, она полна). В таком случае, само высказывание, в котором утверждается непротиворечивость множества аксиом (то есть, высказывание "Эта система непротиворечива"), недоказуемо на основе этих самых аксиом*.
* Иными словами, формальная система арифметики не может доказать свою собственную непротиворечивость изнутри самой себя!
И если мы захотим доказать эту непротиворечивость, нам придётся вводить в систему новые аксиомы, что создаст новую систему, которая тоже не сможет доказать собственную непротиворечивость. И так до бесконечности.
14
15
14
Собственно, это и есть главная идея доказательства первой теоремы Гёделя. Если нам удастся сконструировать теорему, которая утверждает
Я недоказуема
или более формально:
Теорема G недоказуема (G)
то это и явится свидетельством того, что в системе существуют недоказуемые истинные утверждения (заметьте, что G - теорема, а следовательно, она истинна)*.
15
Здесь мы вступаем на тонкий лёд как семиотики, так и самореференции (а как вы помните, мы немало времени посвятили самореференции и парадоксам, вызываемым ею).
Бертран Рассел считал, что в Principia Mathematica ему удалось полностью избавиться от самоуказующих понятий вроде "эта формула", "эта теорема" или "эта фраза". И тем не менее, Гёдель с помощью своей нумерации хитрым образом проник в систему, избегая при этом парадоксов самореференции.
Знаменитая картина великого сюрреалиста Рене Магритта "La Trahison des images" ("Вероломство образов") изображает курительную трубку под которой написано Ceci n’est pas une pipe ("Это не трубка"). Но к чему именно относится слово "это"?
Энтони Уайлден (автор множества книг, находящихся на стыке идей и областей из социальной теории, семиотики, кибернетики, антропологии и структурализма) предложил всевозможные интерпретации слова "это" в названии картины:
- это [трубка] не трубка.
- это [изображение трубки] не трубка.
- это [картина] не трубка.
- это [предложение] не трубка.
- [это] это не трубка.
- [это] не трубка.
Понятно, что сам Магритт имел в виду именно это: множество интерпретаций. Нам же важно как можно точней обозначить нашу Осмысленную Фразу - так, чтобы разночтения были невозможны.
* Доказательство теоремы Гёделя удивительно напоминает так называемый "парадокс лжеца", который можно сформулировать, например, так:
"Я всегда вру".
Если произносящий это всегда говорит неправду, значит и эта фраза - ложь. А это в свою очередь значит, что он говорит правду. Хммм, но тогда он и правда всегда врёт?
Фокус состоит в том, что Гёделю удалось избежать этого парадокса.
16
17
16
Мы приближаемся к месту нашего назначения. Вступая в удивительный мир доказательства теоремы Гёделя, нелишним будет убедиться, что мы с читателем не одни в мире удивлены происходящим. Вот, что пишет Ребекка Голдстин:
Говоря со мной о теореме Гёделя, логик Саймон Коушен заметил, что это доказательство удивительно напоминает работы Кафки (которыми Гёдель восхищался). И у Кафки, и у Гёделя есть определенное сходство с Алисой в Стране чудес; ощущение, что ты попал в странную вселенную, где одни вещи трансформируются в другие, включая сами значения вещей*.
Прежде, чем приступать к делу, нам понадобится навести порядок во всех этих значениях и значениях значений. И здесь снова на помощь придёт Кэролл, а точнее Белый Рыцарь и его диалог с Алисой из комментария 5.
На этот раз мы воспользуемся обозначениями Рыцаря для того, чтобы классифицировать понятия, которыми нам придётся оперировать, доказывая теорему. Прежде всего:
действие будет происходить на трёх уровнях: семантическом, синтаксическом и уровне гёделевских номеров (ГН).
Уровень 1 - это мета-математический, семантический уровень. На этом уровне мы можем обсуждать смысл формулы уровня 2.
Уровень 2 - это уровень формальной системы ("математики"), синтаксический уровень. На этом уровне действуют строгие правила манипуляции с лишёнными какого бы то ни было смысла символов.
Уровень 3 - это уровень целых чисел, являющихся гёделевскими номерами (ГН) символов и формул уровня 2. На этом уровне действуют законы арифметики: ГН можно раскладывать на простые множители, находить экспоненты и т.п.
Каждую формулу мы будем записывать сразу на всех трёх уровнях. Автору представляется, что таким образом легче разобраться в доказательстве Гёделя**.
А теперь для забавы сопоставим обозначения Белого Рыцаря с только что определёнными тремя уровнями:
Уровень 1 - значение формулы - "песня".
Уровень 3 - ГН этой формулы - "заглавие".
Уровень 2 - сама формула (все символы) - "название песни".
Уровень 2 - символы, обозначающие ГН в формуле - "название заглавия".
Диаграмма поможет это понять***:
Ещё немного приготовлений.
При чтении доказательства очень важно понимать, какой символ обозначает число (гёделевский номер - ГН), а какой - переменную, то есть символ, вместо которого можно подставить что-то другое (обычно ГН).
Поэтому мы введём следующие шрифтовые обозначения:
S, T, G, Q и так далее - символы переменных;
S, T, G, Q и так далее - символы, обозначающие ГН****.
Далее, напомним читателю, что целые предложения вида there-is-no-sequence-that-proves или theorem-with-GN - это символы нашей формальной системы, или - как упоминалось выше - атомы. Не имеет значения, сколько именно отдельных букв используется в предложении; это делается исключительно для удобства чтения. Каждое из этих "предложений" - это один единственный символ.
И последнее. В доказательстве Гёделя используется некий вариант системы, разработанной Расселом и Уайтхедом в Principia Mathematica. Однако, он с таким же успехом мог бы воспользоваться любой другой аксиоматической формальной системой, которая достаточно мощна, чтобы определить множество натуральных чисел с арифметическими операциями над ними.
В доказательстве ниже мы будем пользоваться неким неформальным приближением формул Principia Mathematica для простоты.
17
О значении "слона" см. комментарий 18.
* Не пройдём мимо крайне важной фразы в этом отрывке: "одни вещи трансформируются в другие, включая сами значения вещей".
Значения предметов перетекают в сами предметы; имена вещей становятся самими вещами, а вещи - своими именами.
Вот с чем нам приходится иметь здесь дело!
** Вся прочитанная литература по этому вопросу грешит одним и тем же: уровни в объяснении постоянно смешиваются, и читатель не всегда замечает, что действие переместилось с одного уровня на другой.
*** Несмотря на юмористический характер такой аналогии, она, тем не менее, довольно точно отражает суть:
- "сама песня" - это смысл формулы;
- "заглавие песни" - её гёделевский номер, то есть способ обозначить формулу, не прибегая к её названию;
- "название заглавия" - это само "заглавие", то есть ГН, изображённый с помощью символа.
- "название песни" - это сама формула, изображённая с помощью символов (как видите, смысл формулы - "сама песня" - выражается её названием).
**** Почему "символы, обозначающие ГН", а не просто ГН? Возвращаясь к семиотике, можно сказать, что ГН - это обозначаемое (signified) гёделевского номера, то есть концепция этого номера в голове - ну, или в идеальном мире чисел Платона.
Символ же, обозначающий ГН - это обозначающее (signifier) гёделевского номера, то есть конкретный символ.
18
18
Итак мы можем приступать к изложению доказательства первой теоремы Гёделя. Это доказательство уникально тем, что его можно понять без всякого математического образования. Говоря точнее, схему доказательства Гёделя (которую мы здесь и рассмотрим) можно понять без всякой подготовки, хотя детали доказательства, конечно же, представляют собой сложные математические выкладки*.
* Так как доказательство довольно громоздко, мы изложим его в продолжении этой сноски.
(см. продолжение сноски)
* (продолжение сноски)
Начнём с цели нашего предприятия. Задача - сконструировать теорему, которая бы говорила о своей собственной недоказуемости (см. комментарий 14). Ну что ж, попробуем:
Формула (1)
Уровень 1: Эта теорема недоказуема
Уровень 2: there-is-no sequence such-that sequence proves this very theorem
Уровень 3: формула уровня 2 ещё не достаточно формализована, чтобы иметь ГН.
Вспомним: уровень 1 - семантический, это смысл формулы уровня 2. Уровень 2 - синтаксический. На нём находится бессмысленный набор символов, которым мы придаём смысл на уровне 2.
Как вы, наверное, догадываетесь, в математике слова вроде "эта теорема" не работают, поэтому попробуем немного формализовать нашу теорему:
Формула (1)
Уровень 1: Теорема с ГН=G недоказуема
Уровень 2: there-is-no sequence such-that sequence proves theorem-with-GN G
Уровень 3: G (то есть, ГН теоремы уровня 2 = G)
Что здесь произошло? Благодаря нумерации Гёделя, у нас есть отличный способ сослаться не любую формулу (и на любой символ) с помощью гёделевского номера (ГН) этой формулы. Ровно это мы и сделали, обозначив ГН нашей теоремы G.
Сделаем ещё один шаг навстречу математическому сообществу: мы всё-таки имеем дело с формулой, поэтому будет логично записать её в "чистом" виде, то есть с переменной, обозначающей ГН теоремы вместо самого символа, обозначающего ГН (ещё и ещё раз: на втором уровне находятся не сами номера или переменные, а символы, обозначающие эти номера или переменные - то есть, их имена; когда сомневаетесь, вспоминайте Соссюра и Белого Рыцаря).
Итак:
Формула (2)
Уровень 1: Теорема с ГН=T недоказуема никакой последовательностью формул с ГН=S
Уровень 2: there-is-no sequence-with-GN S such-that sequence-with-GN S proves theorem-with-GN T
Уровень 3: Некий ГН
А теперь исключительно для простоты будем вместо
there-is-no sequence-with-GN S such-that sequence-with-GN S proves...
писать
there-is-no-sequence-that-proves...
то есть:
Формула (2)
1: Теорема с ГН=T недоказуема никакой последовательностью формул
2: there-is-no-sequence-that-proves theorem-with-GN T
3: Некий ГН
Ну и вместо слова "уровень" будем для краткости просто обозначать их цифрами.
Как уже было неоднократно сказано, длинная фраза there-is-no-sequence-that-proves - есть просто один символ нашей системы. Мы могли бы обозначить его любым уникальным символом (скажем, A), но такая фраза даёт нам намёк на то, какой смысл скрывается за этим символом. У него есть своей гёделевский номер, который может быть чем угодно: коль скоро это символ, мы можем назначить ему любой ГН.
Что вышло из всей этой формализации?
Попробуем подставить вместо символа числа T символ числа G (то есть, ГН самой теоремы уровня 2):
Формула (3)
1: Эта теорема с ГН=G недоказуема никакой последовательностью формул
2: there-is-no-sequence-that-proves theorem-with-GN G
3: X
Мы получили высказывание: "теорема с ГН=G недоказуема". К сожалению, как видите, у этой формулы уже совсем другой гёделевский номер - X. Кроме того, совершенно исключено, что гёделевский номер этой формулы равен G - он обязательно должен быть гораздо больше, раз уж само число G является частью этой формулы (достаточно вспомнить, каким именно образом рассчитывается гёделевский номер формулы - см. комментарий 6).
Что же делать? Как говорит Хофштадтер, здесь нам придётся запихнуть слона в спичечный коробок. Чтобы проделать подобный трюк, вместо самого слона нам нужно будет положить в формулу описание слона.
Подготовим это описание. Для этого нам понадобится функция замены. В самом общем смысле функция замены синтакстически подменяет некий символ в данной формуле другим символом и возвращает гёделевский номер полученной новой формулы. Здесь важно понять, что функции - это не утверждения, то есть они ничего не утверждают (в отличие от, скажем, формулы (3), которая очень даже что утверждает!), а просто выполняют какую-то работу и выдают результат. Наша функция будет выдавать некий ГН:
(in A replace-symbol B with C) -> GN
Например, возьмём утверждение
3 = next X. Пусть его гёделевский номер равен Z. Теперь применим к этому утверждению функцию
(in Z replace-symbol X with 2). Как нетрудно увидеть, такая подстановка даст истинное утверждение
3 = next 2, а результатом функции замены будет гёделевский номер этого утверждения - какой-нибудь W.
Теперь, когда мы разобрались с функцией замены, рассмотрим её очень частный случай:
(in A replace-symbol B with A) -> GN
а именно: заменить в формуле с ГН=A символ B на символ A. Пока совершенно непонятно, зачем нам может понадобиться такая штука, но совершенно понятно, что ничего незаконного в такой функции нет.
А теперь вернёмся к нашим привычным обозначениям: T в честь "теоремы". Обратите внимание, что вместо T мы пишем T, чтобы подчеркнуть, что это не какое-то конкретное число Гёделя, а переменная:
Формула (4)
1. Гёделевский номер результата применения функции замены в формуле с ГН=T символа T на T
2. in T replace-symbol B with T
3. Некий ГН
Ещё один необходимый шаг. Вместо некоего случайного символа B в функции замены, будем заменять сам символ T!
Формула (4)
1. Гёделевский номер результата применения функции замены в формуле с ГН=T символа T на T
2. in T replace-symbol T with T
3. Некий ГН
Это выглядит довольно странно и бессмысленно - заменить Т на Т? К счастью, как вы знаете, для каждой формулы и каждого символа у нас есть другое его обозначение - своеобразный указатель на этот символ (второго уровня), который мы можем взять "нырнув" за ним на третий уровень: это гёделевский номер символа, который однозначно определяет сам символ. В частности, символ T имеет ГН=20 (см. комментарий 6). Возьмём символ числа 20 (который на втором уровне будет выглядеть как 20) и подставим его в формулу замены:
Формула (4)
1. Гёделевский номер результата применения функции замены в формуле с ГН=T символа с ГН=20 на T
2. in T replace-symbol-with-GN 20 with T
3. Некий ГН
Гёдель показал, что функция замены (уровень 2) вычислима в нашей арифметической системе. В самом деле, ведь мы имеем дело исключительно с числами, будь то 20 или символ replace-symbol-with-GN (у которого свой ГН), символ T со своим ГН и так далее. Такую подстановку всегда можно выполнить путём арифметических вычислений.
(продолжение следует)
19
19
Снова воспользуемся нашим типографским трюком...*
* ...для того, чтобы иметь больше места для манёвра. Воспользуемся продолжением сноски.
(см продолжение сноски)
* (продолжение сноски)
Возвращаемся к нашему главному нарративу.
Воспользуемся только что придуманной функцией замены в формуле (2), то есть:
there-is-no-sequence-that-proves theorem-with-GN T
и вместо T подставим результат функции замены (который, как мы помним, является неким гёделевским номером):
Формула (5)
1: Теорема с ГН=(результат функции замены), которая получена путём замены всех символов с ГН=20 на символ T недоказуема
2: there-is-no-sequence-that-proves theorem-with-GN (in T replace-symbol-with-GN 20 with T)
3: F (опять какой-то свой ГН, так как мы заменили некоторые символы в формуле (2))
Почему на первом уровне написано "Теорема с ГН=(результат функции замены)" ?
Да потому что наш первый - семантический - уровень просто-напросто расшифровывает то, что написано на втором - синтаксическом - уровне. А там, как мы видим, написано "theorem-with-GN (in T replace-symbol-with-GN 20 with T)"
А это и переводится как "теорема с гёделевским номером, равным результату функции замены..." (Вспомним формулу (4)).
Нам остался только один - но очень важный - шаг. На сцену выходит наш давний знакомый Уроборос - дракон, кусающий самого себя за хвост. Что если, подумал Гёдель (и мы вместе с ним), что если подставить в формулу (5) вместо переменной T сам гёделевский номер формулы (5), то есть F?
F - такое же число, как и любое другое - никто не может помешать нам использовать его вместо переменной T:
Формула (6)
1: Теорема с ГН=(результат функции замены), которая получена путём замены всех символов с ГН=20 на символ F недоказуема
2: there-is-no-sequence-that-proves theorem-with-GN (in F replace-symbol-with-GN 20 with F)
3: Q - номер этой новой формулы нам пока неизвестен, назовём его Q в честь Куайна (см. сноску ** комментария 1 Главы 3).
Если сравнить первые уровни формул (5) и (6), то станет понятно, что в объяснении формулы (6) чего-то не хватает. Ведь на втором уровне не просто написано (результат функции замены), там написано
theorem-with-GN (in F replace-symbol-with-GN 20 with F)
то есть "результат функции замены в формуле с ГН=F всех символов с ГН=20 на F".
Перепишем это ещё раз, более точно:
Формула (6)
1: Теорема с ГН=(результат функции замены в формуле с ГН=F всех символов с ГН=20 на F), которая получена путём замены всех символов с ГН=20 на символ F недоказуема
2: there-is-no-sequence-that-proves theorem-with-GN (in F replace-symbol-with-GN 20 with F)
3: Q
Хорошо, а что такое формула с ГН=F? Это формула (5). Попробуем расшифровать эту загадочную надпись в скобках на первом уровне:
первый шаг расшифровки:
(результат функции замены в формуле с ГН=F всех символов с ГН=20 на F), то есть
второй шаг расшифровки:
(результат функции замены в формуле (5) всех символов с ГН=20 на F), то есть (подставляем формулу (5)):
третий шаг расшифровки:
(результат функции замены в формуле
"there-is-no-sequence-that-proves theorem-with-GN (in T replace-symbol-with-GN 20 with T)"
всех символов с ГН=20 на F), то есть (применяем функцию замены всех символов T на F, чтобы получить этот самый результат):
четвёртый шаг расшифровки:
"there-is-no-sequence-that-proves theorem-with-GN (in F replace-symbol-with-GN 20 with F)", то есть (изменим шрифт, чтобы подчеркнуть, что надпись в скобках - это конкретное число):
пятый шаг расшифровки:
"there-is-no-sequence-that-proves theorem-with-GN (in F replace-symbol-with-GN 20 with F)", то есть (внимательно смотрим на формулу (6)):
шестой шаг расшифровки:
формула (6), то есть (речь идёт всё-таки о результате функции, а именно о гёделевском номере нашей формулы (6)):
Q.
Что-что? Ну да, здесь нет никакой ошибки - результат нашей длинной расшифровки первого - семантического - уровня формулы (6), а вернее того, что написано в скобках - это число Q!
Давайте же скорее перепишем формулу (6) в новом виде:
Формула (6)
1: Теорема с ГН=Q, которая получена путём замены всех символов с ГН=20 на символ F недоказуема
2: there-is-no-sequence-that-proves theorem-with-GN (in F replace-symbol-with-GN 20 with F)
3: Q
Смотрим на первый уровень: теорема с ГН=Q - это и есть сама формула (6)! Но в формуле (6) нет никаких символов с ГН=20 (то есть, символа T). Поэтому не проще ли переписать уровень 1 нашей формулы (6) так:
1: Теорема с ГН=Q недоказуема
А теперь, вместо того, чтобы - как обычно - описать на уровне 1 формулу, находящуюся на уровне 2, сделаем ровно наоборот: семантический уровень у нас уже есть; запишем его же на синтаксическом уровне 2:
Формула (6)
1: Теорема с ГН=Q недоказуема
2: there-is-no-sequence-that-proves theorem-with-GN Q
3: Q
Вспомните формулу (3). Мы ведь только что её и записали, только на этот раз не как желаемый результат, а как совершенно законную конструкцию нашей формальной системы. Вернём гёделевскому номеру формулы (6) - или (3) - его первоначальное имя (которое, как мы теперь догадываемся, выбрано в честь Гёделя) - G и запишем:
Формула (7)
1: Теорема с ГН=G недоказуема
2: there-is-no-sequence-that-proves theorem-with-GN G
3: G
Таким образом, теорема (7) утверждает:
"Я недоказуема".
(окончание следует)
20
20
Хорошо, но откуда мы знаем, что теорема (7) истинна? Да ведь мы только что построили её по всем правилам нашей формальной арифметической системы! Мы не придумали, а вывели её. (Не мы, а Гёдель, конечно).
Осталось посмотреть, что это нам даёт. Это уже совсем просто.
Предположим, что теорема (7) ложна. Тогда её утверждение "я недоказуема" тоже ложно, то есть - теорема (7) доказуема Но если она доказуема, то это значит, что наша система противоречива, потому что в ней существуют ложные доказуемые утверждения!
Теперь предположим, что наша система непротиворечива, и теорема (7) истинна. Тогда - по её же собственному (истинному!) утверждению - она недоказуема. Система, в которой существуют истинные утверждения, которые невозможно доказать, называется неполной.
Таки образом, в нашей непротиворечивой системе существуют истинные утверждения, которые невозможно доказать. Это и есть первая теорема Гёделя о неполноте*.
* Если читателю всё-таки не удалось прорваться сквозь язык формул - не надо отчаиваться!
Объяснение Робота Гёделя даёт вполне приемлемое представление о схеме доказательства.