Роджер Пенроуз - Новый ум короля: О компьютерах, мышлении и законах физики
Мы можем представить себе лексиграфический способ упорядочивания как обычный способ, используемый для натуральных чисел, только сделанный «по основанию k + 1», где для k + 1 чисел берутся различные символы формальной системы, вместе с новым «нулем», который никогда не используется. (Последняя сложность возникает в связи с тем, что числа, начинающиеся с нуля, и те, где он опущен — равны.) Простое лексикографическое упорядочивание в строчках из девяти символов осуществляется при помощи натуральных чисел, которые могут быть выписаны в стандартной десятичной системе без нуля: 1,2, 3,4…,8,9, 11, 12 19,21,22 99, 111, 112…
73
В действительности ход рассуждений в теореме Геделя может быть представлен таким образом, чтобы не зависеть от полностью привнесенного извне понятия «истины» для утверждений, подобных Pk(k). Однако, он по-прежнему будет зависеть от интерпретации фактического «значения» некоторых символов: в частности, «~ Eк.с.» должно означать «не существует (натурального числа)…такого, что…».
74
В нижеследующем прописные буквы будут представлять натуральные числа, а заглавные — конечные множества натуральных чисел. Пусть m → [n, k, r] представляет такое утверждение: «Если X = {0,1…., m}, каждое из подмножеств которого длиной в k элементов приписано к r ящикам, то существует „большое“ подмножество Y, принадлежащее X и имеющее по крайней мере n элементов, такое, что все подмножества Y из k элементов попадут в один ящик». Здесь «большое» означает, что число элементов, входящих в Y, больше самого маленького из натуральных чисел, принадлежащих Y. Рассмотрим теперь следующее утверждение: «При любых k, r, n существует m0 такое, что при m > m0 утверждение m → [n, k, r] всегда справедливо». Дж. Парисом и Л. Харрингтоном [1977] было доказано, что это положение эквивалентно геделевскому утверждению для стандартных (введенных Пеано) аксиом арифметики, которое не выводится из этих аксиом и которое позволяет делать утверждения о тех аксиомах, которые «очевидно верны» (в данном случае оно говорит, например, о том, что утверждения, выведенные из аксиом, сами будут справедливыми).
75
Статья называлась «Система логики, основанная на порядковых числах», и некоторые читатели будут уже знакомы со способом записи Канторовых порядковых чисел, который я применял для субиндексов. Иерархия логических систем, которые получаются с помощью приведенной мной процедуры, описывается с помощью вычислимых порядковых чисел.
Есть несколько довольно естественных и легко формулируемых математических теорем, которые, если их пытаться доказать путем использования стандартных (введенных Пеано) правил арифметики, привели бы к «гипертрофированной» геделевской процедуре (по числу шагов многократно превосходящей ту, что я описал ранее). Математические доказательства этих теорем по природе своей не зависят от туманных и сомнительных рассуждений, выходящих за рамки аппарата нормального математического доказательства (см. Сморински [1983]).
76
Делается различие между «множествами» и «Классами», где «множества» могут быть собраны вместе для образования других множеств или классов; а классы не могут образовывать сколько-нибудь более крупные объединения, будучи для этого «слишком большими». Однако не существует правила, согласно которому можно было бы решать, какие объединения могут рассматриваться как множества, а какие с необходимостью должны быть только классами — если не считать «порочно» замкнутое правило, гласящее, что множествами являются те объединения, которые можно составлять вместе, чтобы получать новые объединения!
77
Континуум-гипотеза, которая упоминалась в главе 3, (конец подглавы «Сколько же всего действительных чисел?», и из которой следует, что С = N1 ), является наиболее «экстремальным» математическим утверждением, которое здесь встречается (хотя часто рассматриваются и куда более «экстремальные» рассуждения). Континуум-гипотеза интересна еще и потому, что сам Гедель, совместно с Полом Дж. Коэном, показал, что эта гипотеза в действительности не зависит от стандартных аксиом и правил теории множеств. Таким образом, отношение любого математика к континуум-гипотезе позволяет причислить его к сторонникам либо формалистской, либо платонистской точки зрения. Для формалиста данная гипотеза будет «недоказуемой», поскольку ее справедливость не может быть установлена или опровергнута, если опираться на стандартную (построенную Цермело и Френкелем) формальную систему, и, значит, не «имеет смысла» называть ее ни «истинной», ни «ложной». Однако, для убежденного платониста эта гипотеза является либо истинной, либо ложной, хотя какой именно — это можно установить только путем рассуждений некоторого нового типа, идущих еще дальше, чем использование геделевских утверждений для формальной системы Цермело — Френкеля. (Коэн [1966] сам предложил принцип рефлексии, который позволяет показать, что континуум-гипотеза — «с очевидностью ложна»!)
78
Живое и не слишком насыщенное техническими деталями изложение этой темы можно найти у Ракера [1984].
79
Интуиционизм был назван так потому, что ему предназначалось служить отражением человеческой мысли.
80
Сам Брауэр начал размышлять в этом направлении, в частности, потому, что очень придирчиво и болезненно относился к «неконструктивности» доказательства своей теоремы из области топологии, «теоремы Брауэра о неподвижной точке». Эта теорема утверждает, что, если вы возьмете круг — то есть окружность вместе со всеми точками внутри нее — и будете непрерывно двигать его внутри области, где он находился изначально, то найдется по крайней мере одна точка круга, — называемая неподвижной точкой, — которая окажется точно там же, откуда она начала движение. Не ясно, где именно располагается эта точка, и может ли их быть несколько — теорема говорит только о существовании такой точки. (Среди математических теорем существования, эта, на самом деле, носит довольно «конструктивный» характер. Примеры теорем существования более высокой степени неконструктивности ― это теоремы, зависящие от так называемой «аксиомы выбора» или «леммы Цорна» (см. Коэн [1966], Ракер [1984]).) Трудность в случае Брауэра была аналогична той, что возникает в следующей задаче: найти точки, в которых f обращается в нуль, если известно, что f — действительная непрерывная функция действительной переменной, которая принимает как положительные, так и отрицательные значения. Стандартная процедура заключается в последовательном делении пополам отрезка, на котором функция меняет свой знак; но решение о том, какое именно промежуточное значение принимает функция (положительное, отрицательное или нулевое), может оказаться неконструктивным в том смысле, которого требует Брауэр.
81
Вообще говоря, для нас является существенным, чтобы такие неудачные варианты могли реализоваться, тем самым гарантируя нам потенциальную возможность описывать любую алгоритмическую операцию. Вспомните, что для описания машин Тьюринга в общем мы должны допустить существование, в частности, машин, которые никогда не останавливаются.
82
''Доказательство могло бы, в действительности, состоять из последовательности шагов, которые отражали бы действие машины, продолжающееся до ее остановки. Доказательство завершалось бы, как только машина остановится.
83
Мы нумеруем множества {v, ω, x….,z], где v представляет функцию f в согласии с некоторой лексикографической схемой. Мы (рекурсивно) проверяем на каждом этапе справедливость равенства f (ω, x…,z) = 0 и оставляем утверждение Eк.с. ω, х…., z[(ω, х…., z) = 0] только в том случае, если это равенство выполняется.
