Новый ум короля: О компьютерах, мышлении и законах физики
Шрифт:
А как насчет ~ P k ( k )? Из предыдущих рассуждений видно, что доказательство этому утверждению внутри системы мы найти не сможем. Мы только что установили, что ~ P k ( k ) должно быть ложным (ибо P k ( k ) является истинным), а мы, по определению, не имеем возможности доказывать ложные утверждения в рамках системы! Таким образом, ни P k ( k ), ни ~ P k ( k ) недоказуемы в нашей формальной системе, что и составляет теорему Геделя.
Математическая интуиция
Обратите внимание, что мы здесь сталкиваемся с одной примечательной особенностью. Часто думают, что теорема Геделя имеет, в некотором роде, отрицательный смысл, поскольку она указывает на принципиальные ограничения в применении формальных математических рассуждений. Независимо от нашего мнения об универсальности применяемого подхода, всегда найдутся утверждения, которые не попадают в сферу его действия. Но насколько, в действительности, нас могут затрагивать частные случаи типа P k ( k )? В ходе предыдущих рассуждений мы установили, что P k ( k ) — истинноеутверждение! Мы смогли это сделать несмотря на то, что это утверждение формально недоказуемо
73
В действительности ход рассуждений в теореме Геделя может быть представлен таким образом, чтобы не зависеть от полностью привнесенного извне понятия «истины» для утверждений, подобных P k ( k ). Однако, он по-прежнему будет зависеть от интерпретации фактического «значения» некоторыхсимволов: в частности, « ~ E к.с.» должно означать«не существует (натурального числа)…такого, что…».
«Да, есть странные утверждения, вроде P k ( k ), для которых мое понятие доказуемости или ИСТИНЫрасходится с вашим интуитивным понятием истинности, но подобные выражения едва ли встречаются в серьезной математике (по крайней мере не в такой, которая меня интересует), поскольку они абсурдно усложнены и неестественны для математики».
Несомненно, что утверждения вида P k ( k ), будучи полностью выписанными, были бы чрезвычайно громоздки и выглядели бы странно для числовых математических выражений. Однако за последнее время были выдвинуты сравнительно простые выражения приемлемого с точки зрения математики характера, которые эквивалентны утверждениям Геделя [74] . Они недоказуемы на основании обычных аксиом арифметики, однако же следуют из некоего свойства «самоочевидности», которым обладает сама система аксиом.
74
В нижеследующем прописные буквы будут представлять натуральные числа, а заглавные — конечные множества натуральных чисел. Пусть m – > [ n , k , r ] представляет такое утверждение: «Если X = { 0 , 1 …., m }, каждое из подмножеств которого длиной в k элементов приписано к r ящикам, то существует „большое“ подмножество Y , принадлежащее X и имеющее по крайней мере n элементов, такое, что все подмножества Y из k элементов попадут в один ящик». Здесь «большое» означает, что число элементов, входящих в Y , больше самого маленького из натуральных чисел, принадлежащих Y . Рассмотрим теперь следующее утверждение: «При любых k , r , n существует m 0 такое, что при m > m 0 утверждение m – > [ n , k , r ] всегда справедливо». Дж. Парисом и Л. Харрингтоном [1977] было доказано, что это положение эквивалентно геделевскому утверждению для стандартных (введенных Пеано) аксиом арифметики, которое не выводится из этих аксиом и которое позволяет делать утверждения о тех аксиомах, которые «очевидно верны» (в данном случае оно говорит, например, о том, что утверждения, выведенные из аксиом, сами будут справедливыми).
Отсутствие интереса к «математической истине», исповедуемое формалистами, кажется мне очень странной позицией в приложении к философии математики. Более того: она совсем не так прагматична, как представляется. Когда математики проводят свои выкладки, они не намерены постоянно проверять, могут ли они быть сформулированы посредством аксиом и правил вывода некоторой сложной формальной системы. Единственно, что необходимо — быть уверенным в правомерности использования этих рассуждений для установления истины. Доказательство Геделя удовлетворяет этому требованию, так что P k ( k ) является математической истиной с таким же правом, как и любое другое утверждение, полученное более стандартным путем с использованием изначально заданных аксиом и правил вывода.
Процедура, которая напрашивается сама собой, заключается в следующем. Давайте положим, что P k ( k ) — совершенно верное утверждение (переобозначим его здесь как G 0 ). Тогда мы можем присоединить его к нашей системе в качестве дополнительной аксиомы. Естественно, что наша новая система будет, в свою очередь, содержать новоеутверждение Геделя, скажем, G 1 , которое также будет истинным числовым выражением. Соответственно, мы можем и G 1 добавить в нашу систему. Это даст нам новую улучшенную систему, которая также содержит новое утверждение Геделя G 2 (опять же совершенно справедливое); и мы сможем снова добавить его к системе, получая следующее утверждение Геделя G 3 , которое мы тоже присоединяем — и так далее, повторяя этот процесс неограниченно. Что мы можем сказать о получившейся в результате системе, где мы используем весь набор G 0, G 1, G 2, G 3…. как дополнительные аксиомы? Может ли эта система быть полной? Поскольку мы теперь имеем неограниченную (бесконечную) систему аксиом, то возможность применения процедуры Геделя совсем не очевидна. Однако, это последовательное включение утверждений Геделя является в высшей степени систематичной схемой, результат применения которой может быть истолкован как обычная конечная система аксиом и правил вывода. Эта система будет иметь свое собственное утверждение Геделя G которое мы также сможем к ней присоединить, получая новую систему и с ней — еще одно утверждение Геделя G +1 . Продолжая, как и ранее, мы получаем набор утверждений G , G +1 , G +2 , G +3 ,
Есть ли логическое завершение у этого процесса? В определенном смысле — нет; но это приводит нас к ряду трудных математических рассуждений, которые здесь не могут быть нами рассмотрены во всех деталях. Вышеуказанная процедура обсуждалась Аланом Тьюрингом в статье [75] , опубликованной в 1939 году. Примечательно, что на самом деле любое истинное(в общепринятом смысле) утверждение в арифметике может быть получено путем повторения процедуры «геделизации» такого рода (см. Феферман [1988]). Однако это может вызвать вопрос о том, как мы в действительности решаем, является ли утверждение истинным или ложным. Исключительно важным будет также понять, как на каждом этапе нужно выполнять присоединение бесконечного семейства утверждений Геделя, чтобы они порождали единственную дополнительную аксиому (или конечное число аксиом). Для выполнения такого присоединения требуется определенная алгоритмическая систематизация нашего бесконечного семейства. Чтобы быть уверенным в том, что подобная систематизация корректнаи приводит к желаемому результату, нам придется опереться на интуитивные представления, выходящие за рамки системы — точь-в-точь, как мы это сделали для установления истинности P k ( k ). Именно эти «прозрения» и не могут быть систематизированы, не говоря о том, что они должны лежать вне сферы действия любойалгоритмической процедуры!
75
Статья называлась «Система логики, основанная на порядковых числах», и некоторые читатели будут уже знакомы со способом записи Канторовых порядковых чисел, который я применял для субиндексов. Иерархия логических систем, которые получаются с помощью приведенной мной процедуры, описывается с помощью вычислимых порядковых чисел.
Есть несколько довольно естественных и легко формулируемых математических теорем, которые, если их пытаться доказать путем использования стандартных (введенных Пеано) правил арифметики, привели бы к «гипертрофированной» геделевской процедуре (по числу шагов многократно превосходящей ту, что я описал ранее). Математические доказательства этих теорем по природе своей не зависят от туманных и сомнительных рассуждений, выходящих за рамки аппарата нормального математического доказательства (см. Сморински [1983]).
Интуитивная догадка, которая позволила нам установить, что утверждение Геделя P k ( k ) является на самом деле истинным, представляет собой разновидность общей процедуры, известной логикам как принцип рефлексии: посредством нее, размышляя над смыслом системыаксиом и правил вывода и убеждаясь в их способности приводить к математическим истинам, можно преобразовывать интуитивные представления в новые математические выражения, невыводимые из тех самых аксиом и правил вывода. То, как нами была выше установлена истинность P k ( k ), как раз базировалось на применении этого принципа. Другой принцип рефлексии, имеющий отношение к доказательству Геделя (хотя и не упомянутый выше), опирается на вывод новых математических истин исходя из представления о том, что система аксиом, которую мы полагаем априори адекватной для получения математических истин, является непротиворечивой. Применение принципов рефлексии часто подразумевает размышления о бесконечных множествах, и при этом нужно быть всегда внимательным и остерегаться рассуждений, которые могут привести к парадоксам наподобие расселовского. Принципы рефлексии полностью противопоставляются рассуждениям формалистов. Если использовать их аккуратно, то они позволяют вырваться за жесткие рамки любой формальной системы и получить новые, основанные на интуитивных догадках, представления, которые ранее казались недостижимыми. В математической литературе могло бы быть множество приемлемых результатов, чье доказательство требует «прозрений», далеко выходящих за рамки исходных правил и аксиом стандартной формальной системы арифметики. Все это свидетельствует о том, что деятельность ума, приводящая математиков к суждениям об истине, не опирается непосредственно на некоторую определенную формальную систему. Мы убедились в истинности утверждения Геделя P k ( k ), хотя мы и не можем вывести ее из аксиом системы. Этот тип «вйдения», используемый в принципе рефлексии, требует математической интуиции, которая не является результатом чисто алгоритмических операций, представимых в виде некоторой формальной математической системы. Мы вернемся к этому вопросу в главе 10.
Читатель может заметить определенное сходство между рассуждениями, устанавливающими, вопреки «недоказуемости», истинность P k ( k ), и парадоксом Рассела. Помимо этого, наблюдается сходство и с доказательством Тьюринга о невозможности существования «машины Тьюринга», которая могла бы решить проблему остановки. Эти сходства не случайны. Между этими тремя событиями имеется прочная историческая нить. Тьюринг пришел к своему доказательству после изучения работ Геделя. Сам Гедель был очень близко знаком с парадоксом Рассела и смог преобразовать те парадоксальные рассуждения, которые уводили слишком далеко в область логических абстракций, в состоятельное математическое доказательство. (Все эти утверждения уходят корнями к диагональному процессу Кантора, описанному в предыдущей главе)
Почему мы должны принимать доказательства Геделя и Тьюринга и в то же время сбрасывать со счетов рассуждения, ведущие к парадоксу Рассела? Первые являются более ясными и безупречными с точки зрения математики, тогда как парадокс Рассела строится на более туманных рассуждениях об «огромных» множествах. Но нужно признать, что различия здесь не настолько очевидны, как нам хотелось бы. Попытка придать этим различиям ясность была лейтмотивом всей идеи формализма. Доказательство Геделя, с одной стороны, показывает, что строгий формальный подход не выдерживает критики, но с другой стороны, оно не приводит нас к абсолютно надежной альтернативе. По-моему, этот вопрос до сих пор не разрешен. Процедура, используемая в современной математике с целью избежать рассуждений, вовлекающих в рассмотрение «огромные» множества и приводящих к парадоксу Рассела, не является полностью удовлетворительной [76] . Более того, она, как правило, формулируется в чисто формалистских терминах — или же в терминах, которые не дают нам полной уверенности, что в результате их использования не возникнет противоречий.
76
Делается различие между «множествами» и «Классами», где «множества» могут быть собраны вместе для образования других множеств или классов; а классы не могут образовывать сколько-нибудь более крупные объединения, будучи для этого «слишком большими». Однако не существует правила, согласно которому можно было бы решать, какие объединения могут рассматриваться как множества, а какие с необходимостью должны быть только классами — если не считать «порочно» замкнутое правило, гласящее, что множествами являются те объединения, которые можно составлять вместе, чтобы получать новые объединения!
Как бы там ни было, мне кажется, что из доказательства Геделя следует с очевидностью, что понятие математической истины не может быть заключено ни в. одну из формальных систем. Математическая истина выходит за рамки любого формализма. Возможно, это ясно даже без теоремы Геделя. Иначе как бы мы решали, какие аксиомы и правила вывода брать в расчет при построении формальной системы? Нашим руководством в принятии такого решения должно всегда служить интуитивное понимание о том, что является «самоочевидно верным» с учетом «смысловых значений» символов системы. Как нам решить, какие формальные системы стоит использовать (в соответствии с нашим интуитивным ощущением «самоочевидности» и «смысла»), а какие — нет? Понятие «внутренней непротиворечивости» явно не подходит для этой цели. Можно иметь много внутренне непротиворечивых систем, которые «бессмысленны» с точки зрения их практического использования, в которых аксиомы и правила вывода имеют ложные в нашем понимании значения или же не имеют никаких. «Самоочевидность» и «смысл» — это понятия, которые потребовались бы даже без теоремы Геделя.