Гёдель, Эшер, Бах. Эта бесконечная гирлянда

Теперь давайте на минуту остановимся и переведем дыхание — а заодно подумаем, что означало бы иметь такую формальную систему, которая могла бы отличить все истинные высказывания от ложных. Для такой системы все эти строчки были бы просто некими формальными конструкциями, лишенными содержания (в то время как мы видим в них высказывания). Эта система была бы словно решето, сквозь которое проходили бы только конструкции определенного стиля — «стиля истины». Если вы сами имели дело с шестью формулами выше и отделили истинные от ложных, размышляя об их значении, вы сможете оценить, насколько тонкой должна быть система, которая сможет проделать то же самое, но чисто типографским путем! Граница, отделяющая истинные высказывания от ложных (записанных нотацией ТТЧ) вовсе не пряма — это граница со множеством предательских извилин (вспомните рис. 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:    Ac:~Eb:(b+b)=c    ~Еc:Sc=d

ОТКРЫТЫЕ ФОРМУЛЫ содержат по крайней мере одну свободную переменную.

Примеры: ~c=c  b=b 

ЗАМКНУТАЯ ФОРМУЛА (суждение) не содержит свободных переменных.

Примеры: S0=0  ~Ad:d=0  Ec:

Это дает нам полную таблицу Правил Образования для правильно сформированных формул ТТЧ.

Еще несколько упражнений на перевод

Вот еще несколько упражнений для вас, чтобы проверить, насколько вы поняли нотацию ТТЧ. Попробуйте перевести первые четыре из приведенных ниже высказываний Ч в высказывания ТТЧ, а последнее — в открытую правильно сформированную формулу.

Все натуральные числа равны 4.

Ни одно натуральное число не равно собственному квадрату.

Различные натуральные числа имеют различные последующие элементы.

Если 1 равняется 0, то любое число нечетно.

b — это степень 2.

Последнее может показаться вам трудным. Однако это еще цветочки по сравнению со следующим:

b — это степень 10.

Как это ни странно, чтобы записать это выражение в нашей нотации, требуется большая ловкость. Приступайте к нему только в том случае, если вы готовы просидеть над ним несколько часов — и если при этом вы уже хорошо знакомы с теорией чисел.

Нетипографская система