Новый ум короля: О компьютерах, мышлении и законах физики
Шрифт:
Однако эта уверенность пошатнулась, когда в 1902 году английский логик и философ Бертран Рассел придумал свой знаменитый парадокс (который предвидел и сам Кантор и который выводился непосредственно из его диагонального процесса). Чтобы понять доводы Рассела, мы сначала должны хотя бы немного почувствовать, как можно представить множество в виде единого целого. Давайте представим себе множество, характеризуемое некоторым (общим) свойством. Например, набор красныхпредметов может быть охарактеризован словом «краснота» как его определяющим свойством: нечто принадлежит этому множеству тогда и только тогда, когда это обладает «краснотой» (имеет красный цвет). Это позволит нам «перевернуть» точку зрения и трактовать свойство как единичный объект, который будет состоять из всего множества вещей, обладающих данным свойством. При таком рассмотрении «краснота» эквивалентнамножеству всех красных предметов. (При этом мы можем предполагать существование «там вовне» и других множеств, члены которых не могут быть охарактеризованы подобным простым свойством.)
Идея формулировки понятий в терминах множеств послужила основой для процедуры, предложенной в 1884 году влиятельным немецким логиком Готтлибом Фреге, которая позволяла определять числачерез множества. К примеру, что мы понимаем под числом 3 ? Мы знаем, в
69
Рассматривая множества, члены которых, в свою очередь, также являются множествами, мы должны тщательно проводить отличия между членами такого множества и членами его членов. Например, допустим, что S — это множество непустыхподмножеств некоторого другого множества Т , членами которого являются один апельсин и одно яблоко. Т в таком случае имеет свойство «двойственности», тогда как S обладает свойством «тройственности»: членами S будут множества а) из одного яблока; б) из одного апельсина и в) из одного апельсина и одного яблока — представляющие тричлена S . Аналогично, множество, чьим единственным членом является пустое множество, будет иметь свойство «единичности», а не «нулевости» — в него входит один член, а именно пустое множество! При этом самопустое множество не будет иметь, конечно, ни одного члена.
Может показаться, что мы попадаем в замкнутый круг, но в действительности это совсем не так. Мы можем определить числа в общем случае как совокупности всевозможных эквивалентных множеств, где говоря «эквивалентные», мы понимаем «состоящие из элементов, которые могут быть попарно сопоставлены друг другу» (или, в более привычной терминологии, «имеющих одинаковое число элементов»). Тогда число 3 будет одной из этих совокупностей множеств, которая содержит в себе в качестве члена множество, состоящее, скажем, из яблока, апельсина и груши. Обратите внимание, что это принципиально отличается от определения « 3 », данного Черчем (см. гл.2 «Лямбда-исчисление Черча»). Существуют также и другие определения, причем более популярные в наши дни.
Вернемся теперь к парадоксу Рассела. В чем он заключается? В нем рассматривается множество R , определенное следующим образом:
R есть множество множеств, которые не являются членами самих себя.
Таким образом, R есть набор множеств X , отвечающих следующему условию: среди членов множества X не должно быть самого X .
Не является ли абсурдным предполагать, что множество в действительности может быть членом самого себя? Ничуть. Рассмотрим, к примеру, множество I , состоящее из бесконечныхмножеств (множеств с бесконечным числом членов). С очевидностью, существует бесконечное число различныхбесконечных множеств, и само множество I , таким образом, является бесконечным. И, таким образом, оно, действительно, принадлежит самому себе! Но как же, в таком случае, рассуждения Рассела дают нам парадоксальное утверждение? Давайте спросим: является ли множество Рассела R членом самого себя или нет? Если нет, то оно должно принадлежать себе, ибо R состоит как раз из таких множеств, которые не являются членами самих себя. То есть, в конечном счете, R принадлежит R — противоречие! С другой стороны, если R есть членсамого себя, то, поскольку «самое себя» — это R , оно в то же время принадлежит множеству, члены которого, по определению, не могут быть составляющими самих себя, т. е. все-таки не принадлежит самому себе — и вновь противоречие! [70]
70
Можно дать занятную трактовку парадокса Рассела в более привычных терминах. Представьте себе библиотеку с двумя каталогами, один из которых перечисляет только те книги в библиотеке, которые хотя бы раз ссылаются на себя самих, а другой — остальные книги, т. е. те, которые не упоминают себя. В каком из этих каталогов, в таком случае, должен фигурировать второй каталог?
Этот парадоксальный вывод не был праздной игрой ума: Рассел использовал — хотя и в крайней форме — тот же тип весьма общих теоретико-множественных методов, которые математики начинали использовать в то время для своих доказательств. Становилось очевидным, что казавшаяся незыблемой почва ускользает из-под ног, и поэтому необходимо было как можно точнее определить, какие рассуждения считать допустимыми. Ясно было, что такие рассуждения должны быть свободны от внутренних противоречий, и что утверждения, которые будут выводиться с их помощью как следствия из априори верных посылок, должны быть также
Однако надежды Гильберта и его последователей были перечеркнуты, когда в 1931 году блестящий австрийский логик математики Курт Гедель выдвинул поразительную теорему, которая до основания разрушала программу Гильберта. Гедель показал, что любаяподобная точная («формальная») система аксиом и правил вывода, если только она достаточна широка, чтобы содержать в себе описания простых арифметических теорем (как, например, «последняя теорема Ферма», рассмотренная в главе 2), и если она свободна от противоречий — то такая система должна включать утверждения, которые не являются ни доказуемыми, ни недоказуемыми в рамках формализма данной системы. Истинность таких «неразрешимых» утверждений, следовательно, не может быть выяснена с помощью методов, допускаемых самой системой. Более того, Гедель смог показать, что даже утверждение о непротиворечивости системы аксиом, будучи переведенным в форму соответствующей теоремы, само по себе является «неразрешимым». Для нас будет очень важным понять природу этой неразрешимости. Тогда мы увидим, почему выводы Геделя опровергали самое основание программы Гильберта. Мы также увидим, каким образом они дают нам возможность, воспользовавшись интуицией, выходить за пределы любой рассматриваемой формализованной математической системы. Это понимание будет решающим для того, чтобы, в свою очередь, лучше понять обсуждаемое далее.
Формальные математические системы
Необходимо будет несколько уточнить, что мы понимаем под «формальными математическими системами аксиом и правил вывода». Мы должны предположить наличие некоторого алфавита символов, через которые будут записываться математические выражения. Эти символы в обязательном порядке должны быть адекватны для записи натуральных чисел с тем, чтобы в нашу систему могла быть включена «арифметика». По желанию, мы можем использовать общепринятую арабскую запись 0, 1, 2, 3…, 9, 10, 11, 12… хотя при этом конкретные выражения для правил вывода становятся несколько более сложными, чем требуется. Гораздо более простые выражения получаются, скажем, при использовании записи вида 0, 01, 011, 0111, 01111… для обозначения последовательности натуральных чисел (или, в качестве компромисса, мы могли бы использовать двоичную запись). Однако, поскольку это могло бы стать источником разночтений в дальнейших рассуждениях, я буду для простоты придерживаться обычной арабской записи независимо от способа обозначения, которая может на самом делеиспользоваться в данной системе. Нам мог бы понадобиться символ «пробел» для разделения различных «слов» или «чисел» в нашей системе, но, так как это тоже может вызвать путаницу, то мы будем по мере необходимости использовать для этих целей просто запятую (,). Произвольные («переменные») натуральные числа (равно как и целые, рациональные и т. д.; но давайте здесь ограничимся натуральными) мы станем обозначать буквами, например, t , u , v , , х , у , z , t' , t'' , t''' и т. п. Штрихованные буквы t' , t'', … вводятся нами в употребление, дабы не ограничивать число переменных, которые могут встретиться в произвольном выражении. Мы будем считать штрих( ' ) отдельным символом формальной системы, так что действительное количество символов в системе остается конечным. Помимо этого нам также потребуются символы для базовых арифметических операций =, +, х(«умножить») и т. д.; для различных видов скобок (, ), [, ], и для обозначения логических операций, таких как & (« и»), => (« следует»), V (« или»), <=> (« тогда и только тогда»), ~ (« не»). Дополнительно нам будут нужны еще и логические« кванторы»: квантор существования E к.с. (« существует… такое, что») и квантор общности A к.о. (« для любого… выполняется»). Тогда мы сможем такие утверждения, как, например, «последняя теорема Ферма», привести к виду:
— E к.с. , х , у , z [( x + 1 ) +3 +
+ ( у + 1 ) +3 = ( z + 1 ) +3 ]
(см. главу 2, «Неразрешимость проблемы Гильберта»). (Я мог бы написать « 0111 » для « 3 », и, возможно, использовать для «возведения в степень» обозначение, более подходящее к рассматриваемому формализму; но, как уже говорилось, я буду придерживаться стандартной системы записи во избежании ненужной путаницы.) Это утверждение (если читать его до левой квадратной скобки) звучит как:
« Не существует таких натуральных чисел , х, у, z, что… ».