Текст книги "ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда"
Автор книги: Даглас Хофштадтер
Жанры:
Философия
,сообщить о нарушении
Текущая страница: 20 (всего у книги 64 страниц)
ГЛАВА VIII: Типографская теория чисел
«Крабий Канон» и косвенная автореференция
В «КРАБЬЕМ КАНОНЕ» есть три примера косвенной автореференции. Ахилл и Черепаха описывают известные им произведения искусства – и по случайному совпадению оказывается, что эти произведения построены по той же схеме, как и диалог, в котором они упоминаются. Вообразите мое удивление, когда я, автор, сам это заметил! Более того, краб описывает биологическую структуру, которая тоже имеет подобные свойства. Разумеется, можно прочитать и понять диалог, не заметив при этом, что он сделан в форме ракохода – но это было бы пониманием диалога только на одном уровне. Чтобы увидеть автореференцию, надо обратить внимание как на содержание, так и на форму диалога.
Построение Гёделя состоит из описания как формы, так и содержания строчек формальной системы, которую мы опишем в этой главе – Типографской Теории Чисел. Неожиданный поворот состоит в том, что при помощи хитроумного отображения, открытого Гёделем, форма строчек может быть описана в самой формальной системе. Давайте же познакомимся с этой странной системой, способной взглянуть сама на себя.
Что мы хотим выразить в ТТЧ
Для начала приведем некоторые высказывания, типичные для теории чисел; затем постараемся найти основные понятия, в терминах которых эти высказывания могут быть перефразированы. Далее эти понятия будут заменены индивидуальными символами. Необходимо заметить, что, говоря о теории чисел, мы имеем в виду только свойства положительных целых чисел и нуля (и множеств подобных чисел). Эти числа называются натуральными числами. Отрицательные числа не играют в этой теории никакой роли. Таким образом, слово «число» будет относиться исключительно к натуральным числам. Очень важно для вас, читатель, помнить о разнице между формальной системой (ТТЧ) и удобной, хотя и не очень строго определенной, старой ветвью математики – самой теорией чисел; я буду называть последнюю «Ч».
Вот некоторые типичные высказывания Ч – теории чисел:
(1) 5 – простое число.
(2) 2 не является квадратом другого числа.
(3) 1729 – сумма двух кубов.
(4) Сумма двух положительных кубов сама не является кубом.
(5) Существует бесконечное множество простых чисел.
(6) 6 – четное число.
Кажется, что нам понадобится символ для каждого из таких понятий, как «простое число», «куб» или «положительное число» – однако эти понятия, на самом деле, не примитивны. Например, «простота» числа зависит от его множителей, которые, в свою очередь, зависят от умножения. Кубы также определяются в терминах умножения. Давайте постараемся перефразировать те же высказывания в более элементарных терминах.
(1) Не существует чисел а и b больших единицы, таких, что 5 равнялось бы а×b
(2) Не существует такого числа b, что b×b равнялось бы 2.
(3) Существуют такие числа b и с, что b×b×b + с×с×с равняется 1729.
(4) Для любых чисел b и с больше нуля не существует такого числа а, что а×а×а = b×b×b + с×с×с.
(5) Для каждого а существует b, большее, чем а, такое, что не существует чисел c и d, больших 1 и таких, что b равнялось бы c×d.
(6) Существует число e такое, что 2×e равняется 6.
Этот анализ продвинул нас на пути к основным элементам языка теории чисел. Очевидно, что некоторые фразы повторяются снова и снова:
для всех чисел b существует число b, такое, что больше чем равняется умноженное на О, 1, 2,…
Большинство таких фраз получат индивидуальные символы. Исключением является «больше чем», которое может быть упрощено еще. Действительно, высказывание «а больше b» становится:
существует число с отличное от 0, такое, что а = b + с.
Символы чисел
Мы не будем вводить отдельного символа для каждого из натуральных чисел. Вместо этого у нас будет очень простой способ приписать каждому натуральному числу составной символ, так, как мы делали это в системе pr. Вот наше обозначение натуральных чисел.
нуль 0
один S0
два SS0
три SSS0
и т. д.
Символ S интерпретируется как «следующий за.» Таким образом, строчка SS0 интерпретируется буквально как «следующий за следующим за нулем.» Подобные строчки называются символами чисел.
Переменные и термины
Ясно, что нам нужен способ говорить о неопределенных, или переменных числах. Для этого мы будем использовать буквы а, b, с, d, e. Однако пяти букв будет недостаточно Так же, как для атомов в исчислении высказывании, нам требуется их неограниченное количество Мы используем похожий метод для получения большего количества переменных – добавление любого количества штрихов. Например:
e
d'
с"
b'''
a''''
все являются переменными.
В каком-то смысле, использовать целых пять букв алфавита – это слишком большая роскошь, так как мы могли бы легко обойтись просто буквой а и штрихами. Впоследствии я действительно опущу буквы b,c,d, и e – результатом будет более строгая версия ТТЧ, сложные формулы которой будет немного труднее расшифровать. Но пока давайте позволим себе некоторую роскошь! Как насчет сложения и умножения? Очень просто: мы будем использовать обычные символы «+» и «*». Однако мы также введем требование скобок (мы мало помалу углубляемся в правила, определяющие правильно построенные строчки ТТЧ). Например, чтобы записать «b плюс с» и «b, умноженное на с», мы будем использовать строчки:
(b + с)
(b*с)
В отношении скобок послабления быть не может; опустить их – значит произвести неправильно сформированную формулу. («Формула?» Я использую этот термин вместо слова «строчка» лишь для удобства. Формула – это просто строчка ТТЧ.)
Кстати, сложение и умножение всегда будут рассматриваться как бинарные операции, то есть операции, объединяющие не более, чем два числа. Таким образом, если вы хотите записать «1+2+3», вы должны решить, какое из двух выражений использовать:
(S0+(SS0+SSS0))
((S0+SS0)+SSS0)
Теперь давайте символизируем понятие равенства. Для этого мы просто используем «=». Преимущество этого символа, принадлежащего Ч – неформальной теории чисел – очевидно: его весьма легко прочесть. Неудобство же при его использовании напоминает проблему, возникавшую при использовании слов «точка» и «линия» в формальном описании геометрии: если ослабить внимание, то легко спутать обыденное значение этих слов с поведением символов, подчиняющихся строгим правилам. Обсуждая проблемы геометрии, я различал между обыденными словами и терминами – последние печатались заглавными буквами. Так, в эллиптической геометрии ТОЧКОЙ было объединение двух точек. Здесь такого различия не будет, поэтому читатель должен постараться не спутать символ с многочисленными ассоциациями, которые он вызывает. Как я сказал ранее о системе pr, строчка – не является числом 3; вместо этого она действует изоморфно с числом 3, по крайней мере, при сложении. То же самое можно сказать и о строчке SSS0.
Атомы и символы высказываний
Все символы исчисления высказываний, кроме букв, с помощью которых мы получали атомы (P, Q, R), будут использованы в ТТЧ; при этом они сохранят ту же интерпретацию. Роль атомов будут играть строчки, которые, будучи интерпретированы, дадут равенства, такие как S0=SS0 или (S0×S0) = S0. Теперь у нас есть достаточно данных, чтобы перевести несколько простых суждений в запись ТТЧ:
2+3 равняется 4: (SS0+SSS0)=SSSS0
2+2 не равняется 3: ~(SS0+SS0)=SSS0
Если 1 равняется 0, то 0 равняется 1:
Первая из этих строчек – атом; остальные – составные формулы. (Внимание: «и» во фразе «1 и 1 будет 2» – всего лишь еще одно обозначение «плюса» и должно быть представлено «+» (и необходимыми скобками).
Свободные переменные и кванторы
Все правильно сформированные строчки, приведенные выше, обладают следующим свойством: их интерпретация – либо истинное, либо ложное высказывание. Однако существуют правильно сформированные формулы, не обладающие этим свойством, такие, например, как:
(b+S0)=SS0
Ее интерпретация – «b плюс 1 равняется 2». Поскольку b не определено, то невозможно сказать, истинно ли данное высказывание. Это напоминает высказывание с местоимением, взятое отдельно от контекста, такое, как «Она неуклюжа.» Это высказывание не истинно и не ложно – оно просто ждет, чтобы его поставили в контекст. Поскольку она не истинна и не ложна, подобная формула зовется открытой, а переменная b называется свободной переменной.
Одним из способов превратить открытую формулу в замкнутую формулу или высказывание является добавление квантора – фразы «существует число b такое, что…» или фразы «для всех b». В первом случае, у вас получается высказывание:
Существует число b такое, что b плюс 1 равняется 2.
Ясно, что это истинно. Во втором случае, вы получите:
Для всех чисел b, b плюс 1 равняется 2.
Ясно, что это ложно. Теперь мы введем символы для обоих кванторов. Два высказывания, приведенные выше, в ТТЧ будут выглядеть как:
Eb:(b+S0)=SS0 ( E означает «существует»)
Ab:(b+S0)=SS0 ( A означает «все»)
Важно отметить, что речь идет уже не о неопределенных числах; первое высказывание – это утверждение существования, второе – утверждение общности. Их значение не изменится, даже если мы заменим b на c:
Ec:(c+S0)=SS0
Ac:(c+S0)=SS0
Переменная, управляемая квантором, называется квантифицированной переменной. Две следующие формулы иллюстрируют разницу между свободной и квантифицированной переменной.
(b*b)=SS0 (открытая)
~Eb:(b*b)=SS0 (замкнутая – высказывание ТТЧ)
Первая формула выражает свойство, которое может быть присуще какому-либо натуральному числу. Разумеется, такого числа не существует. Этот факт выражен второй формулой. Очень важно понять разницу между строчкой со свободной переменной и строчкой, в которой переменная квантифицирована. Последняя строчка – либо истинна, либо ложна. В переводе на русский язык, строчка, где есть по крайней мере одна свободная переменная, называется предикатом. Предикат – это высказывание без подлежащего (или с подлежащим, выраженным местоимением, лишенным контекста). Например, высказывания:
«является предложением без подлежащего»
«было бы аномалией»
«читается вперед и назад одновременно»
«сымпровизировал по требованию шестиголосную фугу»
являются неарифметическими предикатами. Они выражают свойства, которыми обладают или не обладают определенные предметы или существа. С тем же успехом мы могли бы добавить «подлежащее-пустышку», например, «такой-то». Строчка со свободными переменными подобна такому предикату с подлежащим-пустышкой. Например:
(S0+S0)=b
означает «1 плюс 1 равняется чему-то». Это предикат с переменной b. Он выражает свойство, которым может обладать число b. Заменяя b на различные числа, мы получили бы последовательность формул, большинство которых выражало бы ошибочные суждения. Вот еще один пример разницы между открытыми формулами и высказываниями:
Ab:Ac:(b+c)=(c+b)
Эта формула, разумеется, выражает коммутативность сложения. С другой стороны:
Ac:(b+c)=(c+b)
– это открытая формула, поскольку b здесь свободно. Она выражает свойство, которым может обладать или не обладать число b, а именно – коммутативность по отношению ко всем числам с.
Примеры перевода высказываний
Теперь наш словарь, с помощью которого мы сможем выразить все высказывания теории чисел, полон. Чтобы научиться выражать сложные утверждения Ч и, наоборот, понимать значение правильно сформированных формул, необходимо много практиковаться. Поэтому мы обратимся к шести простым высказываниям, данным в начале, и попробуем перевести их на язык ТТЧ. Кстати, не думайте, что переводы, которые вы найдете далее, единственно возможные. На самом деле, существует бесконечное множество способов выразить каждое высказывание в ТТЧ.
Начнем с последнего высказывания: «6 – четное число». Переведем его в
более примитивные понятия: «Существует число e, такое, что 2, умноженное на e, равняется 6.» Это легко перевести в нотацию ТТЧ:
Ee:(SS0*e)=SSSSSS0
Обратите внимание на необходимость квантора; недостаточно было бы написать просто:
(SS0*e)=SSSSSS0
Интерпретация последней строчки не была бы ни истинной, ни ложной; она выражает только свойство, которое может иметь число e.
Интересно, что, поскольку мы знаем, что умножение коммутативно, то вместо нашей строчки мы могли бы написать:
Ee:(e*SS0)=SSSSSS0
Таким же образом, зная, что равенство симметрично, мы могли бы поменять местами стороны этого равенства:
Ee:SSSSSS0=(SS0*e)
Эти три перевода высказывания «6 – четное число» дают три различные строчки; при этом совершенно не очевидно, что теоремность каждой из них связана с теоремностью остальных. (Совершенно так же тот факт, что строчка -p–r– была теоремой, почти не соотносился с фактом, что ее «эквивалентная» строчка –p-r– также была теоремой. Эквивалентность – у нас в голове, так как мы, люди, автоматически думаем об интерпретациях формул, а не об их структурных особенностях.)
С высказыванием 2: «2 не является квадратом» мы расправимся быстро:
~Eb:(b*b)=SS0
Однако здесь мы снова сталкиваемся с двусмысленностью. А что, если бы мы записали эту формулу по-другому?
Ab:~(b*b)=SS0
Интерпретация первой строчки – «Не существует такого числа b, квадрат которого равнялся бы 2»; вторая строчка читается как «Для всех чисел b неверно, что квадрат b равняется 2». Для нас эти строчки представляют одно и то же понятие – однако для ТТЧ это совершенно разные строчки.
Посмотрим теперь на высказывание 3: «1729 – сумма двух кубов». Тут нам понадобятся два квантора один за другим, вот так:
Eb:Ec:SSSSSS.....SSSSS0=(((b*b)*b)+((c*c)*c))
. |–1729 раза–|
Есть несколько альтернатив этой записи: можно переменить порядок кванторов – сменить переменные на d и e; переменить порядок слагаемых; записать умножение по-иному и т. д., и т. п. Однако я предпочитаю следующие два варианта перевода:
Eb:Ec:(((SSSSSSSSSS0*SSSSSSSSSS0)*SSSSSSSSSS0)+((SSSSSSSSS0*SSSSSSSSS0)*SSSSSSSSS0))=(((b*b)*b)+((c*с)*с))
и
Eb:Ec:(((SSSSSSSSSSSS0*SSSSSSSSSSSS0)*SSSSSSSSSSSS0)+((S0*S0)*S0))=(((b*b)*b)+((c*c)*c))
Понимаете, почему?
Трюки ремесла
Давайте попробуем перевести теперь высказывание 4: «Сумма двух положительных кубов сама не является кубом». Предположим, что мы хотим сказать, что 7 не является суммой двух положительных кубов. Легче всего сделать это, отрицая формулу, утверждающую обратное. Эта формула будет почти как предыдущая, касавшаяся 1729, только теперь нам надо добавить, что кубы должны быть положительными. Мы можем сделать это при помощи следующего трюка: добавим к каждой переменной префикс S:
Eb:Ec:SSSSSSS0=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))
Как видите, мы возводим в куб не сами b и c, а следующие за ними числа, которые должны быть положительными, поскольку минимальная величина b и c – 0. Таким образом, правая сторона представляет сумму двух положительных кубов. Кстати, обратите внимание, что перевод высказывания «существуют числа b и c, такие, что…» не включает символа «Λ», заменяющего «и». Этот символ используется для соединения целых правильно сформированных строчек, а не для соединения двух кванторов.
Итак, мы перевели высказывание «7 – сумма двух положительных кубов»; теперь нам нужно записать его отрицание. Для этого мы должны только поставить тильду слева от него. (Заметьте, что не требуется отрицать каждый квантор в отдельности, хотя нам и надо получить высказывание «Не существует чисел b и c, таких, что…») Таким образом, мы получим:
~Eb:Ec:SSSSSSS0=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))
Однако нашей первоначальной целью было выразить свойства всех чисел, а не только 7. Для этого давайте заменим символ числа SSSSSSSO строчкой ((а*а)*а), являющейся переводом «а в кубе».
~Eb:Ec:((a*a)*a)=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))
Ha этом этапе у нас имеется открытая формула, так как а все еще свободно. Эта формула выражает свойство, которым может обладать или не обладать а – однако мы хотим сказать, что все числа обладают этим свойством. Это просто – надо только добавить к имеющейся у нас формуле квантор общности:
Aa:~Eb:Ec:((a*a)*a)=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))
Таким же правильным переводом было бы:
~Eа:Eb:Eс:((а*a)*a)=(((Sb*Sb)*Sb)+((Sc*Sc)*Sc))
В строгом ТТЧ мы могли бы использовать a' вместо b и a'' вместо c; таким образом, формула приобрела бы вид:
~Ea:Ea':Ea'':((a*a)*a)=(((Sa'*Sa')*Sa')+((Sa''*Sa'')*Sa''))
Как насчет высказывания 1: «5 – простое число»? Мы перефразировали его следующим образом: «Не существует чисел a и b больших 1, таких, что 5 равнялось бы a умноженному на b.» Теперь мы можем это немного изменить: «Не существует чисел а и b таких, что 5 равнялось бы а плюс 2 умноженному на b плюс 2.» Это еще один трюк– поскольку а и b здесь – натуральные числа, эта формулировка кажется более адекватной. Далее, «b+2» может быть переведено как (b+SS0), но есть и более короткий способ записать то же самое: SSb. Точно так же, «c плюс 2» может быть записано как SSc. Теперь наш перевод становится совсем коротким:
~Eb:Ec:SSSSS0=(SSb*SSc)
Без тильды в начале это было бы утверждением того, что существуют два натуральных числа, которые, если их увеличить на два, дают при умножении 5. Тильда в начале это отрицает; таким образом, мы получаем утверждение того, что 5 – простое число.
Если бы вместо 5 мы хотели бы сказать то же самое про d плюс e плюс 1, самым экономным способом было бы заменить символ числа 5 на строчку (d+Se):
~Eb:Ec:(d+Se)=(SSb*SSc)
Мы снова получили открытую формулу; ее интерпретация – не истина и не ложь, а лишь некое утверждение о каких-то двух числах d и e. Обратите внимание, что число, выраженное строчкой (d+Se), больше d, так как мы добавили к d хотя и неопределенную, но положительную величину. Таким образом, если мы добавим к переменной e квантор существования, мы получим формулу, утверждающую, что
Существует некое простое число, большее d.
Ee:~Eb:Ec:(d+Se)=(SSb*SSc)
Осталось только добавить, что это свойство верно всегда, вне зависимости от d. Для этого мы должны добавить квантор общности для d:
Ad:Ee:~Eb:Ec:(d+Se)=(SSb*SSc)
Перед нами – перевод высказывания 5!
Несколько задачек на перевод
Мы завершили упражнение на перевод шести типичных высказываний теории чисел. Однако это еще не гарантирует, что вы стали экспертом в нотации ТТЧ. Остается усвоить несколько тонкостей. Следующие шесть правильно сформированных формул послужат проверкой того, насколько вы овладели нотацией ТТЧ. Что эти формулы означают? Является ли их интерпретация истинными или ложными высказываниями? (Подсказка читателю: при работе с этим упражнением лучше всего двигаться справа налево. Сначала переведите атомы; затем подумайте, что получится, если добавить квантор или тильду; затем, двигаясь налево, добавьте еще один квантор или тильду; снова продвиньтесь налево и опять повторите этот процесс.)
~Ac:Eb:(SS0*b)=c
Ac:~Eb:(SS0*b)=c
Ac:Eb:~(SS0*b)=c
~Eb:Ac:(SS0*b)=c
Eb:~Ac:(SS0*b)=c
Eb:Ac:~(SS0*b)=c
(Еще одна подсказка, либо четыре из них истинны и два ложны, либо, наоборот, два истинны и четыре ложны.)
Как отличить истинное от ложного?
Теперь давайте на минуту остановимся и переведем дыхание – а заодно подумаем, что означало бы иметь такую формальную систему, которая могла бы отличить все истинные высказывания от ложных. Для такой системы все эти строчки были бы просто некими формальными конструкциями, лишенными содержания (в то время как мы видим в них высказывания). Эта система была бы словно решето, сквозь которое проходили бы только конструкции определенного стиля – «стиля истины». Если вы сами имели дело с шестью формулами выше и отделили истинные от ложных, размышляя об их значении, вы сможете оценить, насколько тонкой должна быть система, которая сможет проделать то же самое, но чисто типографским путем! Граница, отделяющая истинные высказывания от ложных (записанных нотацией ТТЧ) вовсе не пряма – это граница со множеством предательских извилин (вспомните рис. 18). Математики смогли установить некоторые отрезки этой границы, работая над этим сотни лет. Представьте себе, как было бы здорово иметь типографский метод, который с гарантией мог бы поставить любую формулу по правильную сторону границы!
Правила для правильно-сформированности
Полезно иметь таблицу Правил Образования для правильно сформированных формул Такая таблица приведена ниже. На подготовительных этапах определяются символы чисел, переменные и термы. Эти три класса строчек являются ингредиентами правильно сформированных формул, но сами они не являются правильно сформированными. Минимальные правильно сформированные формулы – это атомы; существуют способы для соединения атомов. Многие из этих правил – рекурсивные и удлиняющие: в качестве вводных данных они берут элемент определенного класса и производят более длинный элемент того же класса. В этой таблице я использую «x» и «у» как символы для правильно сформированных формул и «s», «t» и «u» – как символы для всех остальных строчек ТТЧ. Нет нужды говорить, что никакой из этих пяти символов сам по себе не является символом ТТЧ.
СИМВОЛЫ ЧИСЕЛ
0 – это символ числа.
Символ числа, слева от которого стоит S – также символ числа.
Примеры: 0 S0 SS0 SSS0 SSSS0 SSSSS0
ПЕРЕМЕННЫЕ
a – это переменная Если забыть об аскетизме, то b, c, d, и e – тоже переменные. Переменная со штрихом справа – также переменная.
Примеры: а b' c" d''' e''''
ТЕРМЫ
Термами являются символы чисел и переменные. Терм, слева от которого стоит S – это также терм.
Если s и t – термы, то (s+t) и (s*t) – также термы.
Примеры: 0 b SSa' (S0*(SS0)+c)) S(Sa*(SbSc))
ТЕРМЫ могут быть подразделены на две категории:
(1) ОПРЕДЕЛЕННЫЕ термы. В них нет переменных.
Примеры: 0 (S0+S0) SS((S0*SS0)+(S0*S0))
(2) НЕОПРЕДЕЛЕННЫЕ термы. В них есть переменные.
Примеры: b Sa(b+S0) (((S0+S0)+S0)+e)
Приведенные выше правила объясняют нам, как получить части правильно сформированных формул; остальные правила говорят нам, как получить полные правильно сформированные формулы.
АТОМЫ
Если s и t – термы, то s+t – атом.
Примеры: S0=0 (SS0+SS0)=SSSS0 S(b+c)=((c*d)*e)
Если атом содержит переменную u, то u в нем свободна.
Таким образом, в последнем примере есть четыре свободных переменных.
ОТРИЦАНИЯ.
Правильно сформированная формула перед которой стоит тильда также правильно сформирована.
Примеры: ~S0=0 ~Eb:(b+b)=S0 ~<0=0эS0=0> ~b=S0
Кванторный статус переменной (говорящий нам, свободна или квантифицирована эта переменная) не меняется при отрицании.
СОСТАВНЫЕ.
Если x и у – правильно сформированные формулы и при этом ни одна переменная, свободная в одной из них, не квантифицирована в другой, тогда все следующие формулы правильно сформированы: <x Λ y>, <x V y>,<x э y>
Примеры: <0=0э~0=0>
Кванторный статус переменной здесь не меняется.
КВАНТИФИКАЦИЯ.
Если u – переменная и x – правильно сформированная формула, в которой и свободна, то следующие строчки – также правильно сформированные формулы:Eu:x и Au:x
Примеры: Ab:
ОТКРЫТЫЕ ФОРМУЛЫ содержат по крайней мере одну свободную переменную.
Примеры: ~c=c b=b
ЗАМКНУТАЯ ФОРМУЛА (суждение) не содержит свободных переменных.
Примеры: S0=0 ~Ad:d=0 Ec:
Это дает нам полную таблицу Правил Образования для правильно сформированных формул ТТЧ.
Еще несколько упражнений на перевод
Вот еще несколько упражнений для вас, чтобы проверить, насколько вы поняли нотацию ТТЧ. Попробуйте перевести первые четыре из приведенных ниже высказываний Ч в высказывания ТТЧ, а последнее – в открытую правильно сформированную формулу.
Все натуральные числа равны 4.
Ни одно натуральное число не равно собственному квадрату.
Различные натуральные числа имеют различные последующие элементы.
Если 1 равняется 0, то любое число нечетно.
b – это степень 2.
Последнее может показаться вам трудным. Однако это еще цветочки по сравнению со следующим:
b – это степень 10.
Как это ни странно, чтобы записать это выражение в нашей нотации, требуется большая ловкость. Приступайте к нему только в том случае, если вы готовы просидеть над ним несколько часов – и если при этом вы уже хорошо знакомы с теорией чисел.
Нетипографская система
Мы изложили нотацию ТТЧ; остается только превратить ТТЧ в ту амбициозную систему, которую мы только что описали. Если нам это удастся, это будет значить, что интерпретация, которую мы дали символам, была правильна. До тех пор, однако, наши интерпретации не более оправданы, чем интерпретация «лошадь – яблоко – счастливая» для символов системы pr.
Можно было бы предложить следующий способ для построения ТТЧ: (1) Не использовать никаких правил вывода – они не нужны, так как (2) мы будем считать за аксиомы все истинные суждения теории чисел (записанные нотацией ТТЧ). Какой простой рецепт! К несчастью, он начисто лишен смысла, как нам и подсказывает наша первая реакция. Часть (2), разумеется, не является типографским описанием строчек, в то время как целью ТТЧ является именно типографское описание истинных высказываний.
Пять аксиом и первое правило ТТЧ
Таким образом, нам придется отказаться от простого рецепта, предложенного выше, и пойти по более сложному пути: у нас будут аксиомы и правила вывода. Прежде всего, как было обещано, все правила исчисления высказываний будут использованы в ТТЧ. Итак, первой теоремой ТТЧ будет следующая:
Она может быть выведена так же, как <P V ~ P >. Прежде чем приводить правила, давайте запишем пять аксиом. ТТЧ:
АКСИОМА 1: Aa:~Sa=0
АКСИОМА 2: Aa:(a+0)=a
АКСИОМА 3: Aa:Ab:(a+Sb)=S(a+b)
АКСИОМА 4: Aa:(a*0)=0
АКСИОМА 5: Aa:Ab:(a*Sb)=((a*b)+a)
(В строгой версии вместо b используйте a'.) Все они очень просты. Аксиома 1 сообщает что-то о числе 0; аксиомы 2 и 3 говорят о свойствах сложения; аксиомы 4 и 5 говорят о свойствах умножения и о его отношении к сложению.
Пять постулатов Пеано
Интерпретация первой аксиомы – «Нуль не следует ни за каким натуральным числом» – это одно из пяти знаменитых свойств натуральных чисел, впервые выраженных математиком и логиком Джузеппе Пеано в 1889 году. Излагая свои постулаты, Пеано следовал за Эвклидом в том смысле, что он не пытался формализовать принципы логических рассуждений. Вместо этого он хотел дать небольшой набор свойств натуральных чисел, из которого можно было бы вывести все остальные путем логических рассуждений. Таким образом, попытка Пеано может быть названа «полуформальной.» Работа Пеано оказала на математиков большое влияние, поэтому я приведу здесь его постулаты. Поскольку Пеано пытался определить именно «натуральное число», мы не будем использовать знакомый и вызывающий ассоциации термин «натуральное число» – вместо него мы будем пользоваться неопределенным термином гений – словом свежим и свободным от математических ассоциаций. Итак, пять постулатов Пеано устанавливают пять ограничений для гениев. Другие неопределенные термины, которыми мы будем пользоваться – джинн и мета. Читатель может догадаться сам, какие знакомые понятия скрываются за этими двумя терминами. Далее следуют пять постулатов Пеано:
(1) Джинн – это Гений.
(2) Каждый Гений имеет мету (которая тоже является Гением).
(3) Джинн не является метой никакого Гения.
(4) Различные Гении имеют различные меты.
(5) Если джинн имеет X и каждый Гений передает X своей мете, тогда все Гении получают X.
В свете ламп «Маленького гармонического лабиринта» мы должны наименовать множество всех Гениев «БОГом». Это напоминает нам о знаменитом высказывании немецкого математика и логика Леопольда Кроникера, архиврага Георга Кантора: «Бог сотворил натуральные числа; все остальное – работа человека.»
Вы можете узнать в пятом постулате Пеано принцип математической индукции – другой термин для «наследственного» доказательства. Пеано надеялся, что его ограничения понятий «джинна», «Гения» и «меты» были так сильны, что эти понятия были бы идентичны для всех людей и формировали бы у них в сознании совершенно изоморфные структуры. Например, для любого человека существовало бы бесконечное число различных Гениев. И, предположительно, каждый согласился бы с тем, что ни один Гений не совпадает со своей метой или мета-метой… и т. д.
В своих пяти постулатах Пеано хотел выразить сущность натуральных чисел. Математики обычно считают, что ему это удалось; однако это не уменьшает важности вопроса «каким образом можно отличить истинное высказывание о натуральных числах от ложного?» Ответа на этот вопрос математики ищут в формальных системах, подобных ТТЧ. Вы найдете в ТТЧ влияние Пеано, поскольку все его постулаты так или иначе вошли в эту систему.
Новые правила ТТЧ: спецификация и обобщение
Мы подошли к новым правилам ТТЧ. Многие из них позволят нам забраться внутрь этой системы и поменять внутреннюю структуру ее атомов. В этом смысле эти правила имеют дело с «микроскопическими» особенностями строчек в большей степени, чем правила исчисления высказываний, обращающиеся с атомами как с неделимыми. Например, было бы хорошо, если бы мы могли выделить строчку ~S0=0 из первой аксиомы. Для этого нам понадобилось бы правило, позволяющее опустить общий квантор и при необходимости одновременно поменять внутреннюю структуру остающейся строчки. Вот это правило:
ПРАВИЛО СПЕЦИФИКАЦИИ. Предположим, что u – переменная, встречающаяся внутри строчки x. Если строчка Au:x – теорема, то x – тоже теорема, как и все строчки, получающиеся из x путем замены и на любой (один и тот же) терм.
(Ограничение: Терм, заменяющий и, не должен содержать никакой переменной, квалифицированной в x.)
Правило спецификации позволяет нам выделить нужную строчку из Аксиомы
1. Это одноступенчатая деривация:
Aa:~Sa=0 аксиома 1
~S0=0 спецификация
Обратите внимание, что правило спецификации позволяет некоторым формулам, содержащим свободные переменные (то есть, открытым формулам), стать теоремами. Например, следующие строчки также могут быть выведены из аксиомы 1 при помощи спецификации:
~Sa=0
~S(c+SS0)=0
Существует еще одно правило, правило обобщения, которое позволяет нам снова ввести квантор общности в теоремы с переменными, ставшими свободными в результате спецификации. Например, действуя на строчку низшего порядка, обобщение дало бы:
Ac:~S(c+SS0)=0
Обобщение уничтожает сделанное спецификацией, и наоборот. Обычно обобщение применяется после того, как были сделаны несколько промежуточных шагов, трансформировавших открытую формулу разными способами. Далее следует точная формулировка этого правила:
ПРАВИЛО ОБОБЩЕНИЯ: Предположим, что x – теорема, в которой встречается свободная переменная u. Тогда Au:x – тоже теорема.
(Ограничение: к переменным, которые встречаются в свободном виде в посылках фантазий, обобщение неприложимо.)
Вскоре я ясно покажу, почему эти два правила нуждаются в ограничениях. Кстати, это обобщение – то же самое, о котором я упомянул в главе II в Эвклидовом доказательстве бесконечного количества простых чисел. Уже отсюда видно, как правила, манипулирующие символами, начинают приближаться к типу рассуждений, используемых математиками.
