Борис Бирюков - Жар холодных числ и пафос бесстрастной логики

• Название: Жар холодных числ и пафос бесстрастной логики
• Автор: Борис Бирюков
• Издательство: Издательство "Знание"
• Жанр: Математика
• Год: 1977

Цель книги доктора философских наук Б. В. Бирюкова и кандидата философских наук В. Н. Тростникова - создать общую картину подготовки и развития логико-математических аспектов кибернетики. Авторы рассказывают о длительном развитии науки логики, возникшей еще в Древней Греции, прослеживают непрерывающуюся нить преемственности, тянущуюся от Аристотеля к "чуду XX века" - быстродействующим кибернетическим устройствам.

---

Это делается так: вводится символ для числа «нуль» (0), а также символ «следования за» f, который трактуется так, что f0 есть единица, ff0 — два и т. д.

Но для целей, которые преследует Гёдель, недостаточно иметь лишь символы для логических операций и чисел. Нужно выразить также основные арифметические предикаты, такие, как «простое число», «делится нацело» и т. п. В этом месте Гёдель, используя понятия системы РМ и известную в математике процедуру рекурсивного задания функции, то есть задания новых значений функции через предыдущие (рекурсивно, например, определяется функция «факториал» — произведение всех натуральных чисел от единицы до данного числа: (1)0! = 1; (2) (n+ 1)! = (n!) (n + 1)), вводит понятие рекурсивной функции, которое заведомо выразимо средствами формальной арифметики. Делается это так: задаются исходные рекурсивные функции — константа 0 и функция «следования за» — а затем устанавливается способ, с помощью которого из них можно получать более сложные рекурсивные функции. В самом начале этой части работы Гёдель показывает, что такие важные функции, как сложение, умножение и возведение в степень, рекурсивны. Он определяет также понятие рекурсивного арифметического предиката; n-местным арифметическим рекурсивным предикатом (отношением между n числами) называется такой предикат, который определяется уравнением φ (х1, х2,..., хn) = 0, где φ—рекурсивная функция, а х1, х2, ..., >Хn — переменные для чисел. Примером рекурсивного предиката является двуместный предикат «меньше». Рассмотрим этот случай подробнее, так как в дальнейшем нам понадобится представление о рекурсивных функциях и предикатах.

1. Функция δ, определяемая условиями

а) δ(0)=0, б) δ(у+1)= y,

рекурсивна, как выраженная стандартной схемой рекурсии через исходные рекурсивные функции (здесь прибавление единицы к числу следует понимать как взятие следующего числа в натуральном ряду).

2. Функция х ∸ у, определяемая условиями

а) х ∸ О = х, б) х ∸ (у+1)=δ(х ∸ у),

рекурсивна, как выраженная стандартной схемой рекурсии через рекурсивную функцию δ. Как нетрудно убедиться, смысл функции х ∸ у (она называется усеченным вычитанием) таков: функция эта равна х — у, если х >= у и равна нулю, если х < у.

В самом деле, посмотрим, каково значение функции х ∸ у для х, у = 0, 1, 2, 3 (над знаками равенств помечаем какой пункт определений 1, 2 применяется или какое из ранее полученных значений функции х — у используется):

Подобным же образом вычисляется 0∸3=0,0∸4=0 (вообще, легко усматривается, что при дальнейшем возрастании значения у выражение 0 ∸ у будет оставаться равным нулю).

При дальнейшем возрастании значения y выражение 2 ∸ у становится равным нулю. Аналогично вычисляется, что 3 ∸ 0 = 3, 3 ∸ 1 = 2, 3 ∸ 2 = 1, но при y > 2 выражение 3 ∸ y равно нулю.

3. Предикат, опередляемый уравнением х ∸ у = 0, рекурсивен; это очевидно, поскольку функция х ∸ у, как мы показали, рекурсивна. Но смысл этого предиката выражается в обычном языке утверждением x <= у.

Далее, можно показать рекурсивность предиката строгого неравенства, так как для его выражения в формальной системе арифметики нужно использовать теперь только функцию взятия следующего числа («прибавление единицы»).

Несколько раньше введения рекурсивных функций Гёдель осуществляет важную процедуру, которая впоследствии была названа гёделевской нумерацией, или гёделизацией. Это — процедура нумерации всех символов, встречающихся в формальном арифметическом исчислении.

Сначала нумеруются знаки логических операций, вспомогательные символы и другие исходные знаки: символ 0 получает номер 1; символ f — номер 3; символ ~ — номер 5; символ V — номер 7; символ Ɐ — номер 9; символ ), то есть левая скобка, — номер 11; символ ), то есть правая скобка, — номер 13. Таким образом, для нумерации исходных знаков используются нечетные числа от 1 до 13. Символы импликации, конъюнкции и эквиваленции и квантор существования в исчислении Гёделя не фигурируют; эти логические операции могут быть выражены через отрицание, дизъюнкцию и квантор общности.

Далее нумеруются переменные x1, у1, z1,..., вместо которых в арифметические формулы подставляются числа. Для этого используются простые числа, начиная с 17. Аналогичным способом нумеруются предикатные переменные x2, y2, z2,... (переменные, на места которых в формулах подставляются знаки свойств и отношений), только для нумерации используются квадраты простых чисел, начиная с 17 (символ х2 получает номер 172, символа y2— номер 192 и т. д.).

Затем следует нумерация последовательностей символов (частным случаем которых являются формулы). Здесь правило присвоения номеров таково: если имеется последовательность из k символов, имеющих номера соответственно n1, n2, ... nk, то номер этой последовательности имеет вид: 2n1 * Зn2 * 5n3- ... pknk, где pk — k-тое простое число, начиная с двух. Покажем наглядно, как «работает» в этом случае гёделизация. Пусть дана формула Vх1(х2(х1)) (она читается: «Для всякого натурального числа x1 выполняется свойство х2). Найдем ее гёделев номер. Выпишем по порядку гёделевы номера входящих в формулу символов: 9, 17,11,289,11,17,13,13. Номер N рассматриваемой формулы таков:

N=29 • З17 • 511 • 7289• 1111• 1317 • 1718 • 1913.

Наконец, нумеруются последовательности формул. Если дана последовательность из 5 формул с номерами m1, m2, m3..., ms, то номер последовательности определяется как 2m1 • 3m2 • 5m3 • ... • psms, где ps — 5-тое простое число.

Используя рекурсивные функции, Гёдель показывает, что с помощью проведенной нумерации все «метаарифметические» высказывания, то есть высказывания об арифметических объектах, можно представить как соотношения между числами (гёделевыми номерами). Скажем, утверждение «Данная комбинация символов есть формула» выражается некоторым арифметическим предикатом от гёделева номера этой комбинации n, то есть записывается в виде некоторой арифметической формулы q2n.

Аналогично, утверждение «Данная последовательность формул является доказательством» предстает в виде арифметического предиката от номера этой последовательности. Показывается, что арифметизируются и высказывания вида: «Данная формула есть результат подстановки в такую-то формулу вместо такой-то переменной такой-то формулы», «Данная формула доказуема» (то есть существует последовательность формул, являющаяся доказательством, которая кончается на данной формуле) и т. д. Проведя такую работу, Гёдель показал фактически, что исчисление можно значительно «ужать», эаменив символы, формулы и доказательства некими представляющими их числами, а утверждения о формулах можно превратить в арифметические формулы.

Решающий момент в построении Гёделя наступает тогда, когда он предъявляет формулу, которая представляет в его системе кодировки метавыоказывание о собственной недосказуемости. В этом случае возникает следующая ситуация. Предположим, что формула, говорящая «Я недоказуема», доказуема. Тогда, если логико-арифметическая система непротиворечива — и, значит, все доказуемые в ней формулы (тождественно)истинны[3], данная формула не может быть доказуемой; в самом деле, если бы она была доказуемо и, то заключенное в ней утверждение «Я недоказуема» следует считать истинным, то есть признать формулу недоказуемой[4]. Но данная формула не только недоказуема, но и неопровержима, то есть недоказуемо ее отрицание. Таким образом, формулу, имеющую смысл «Я недоказуема», в системе «типа РМ» нельзя ни доказать, ни опровергнуть —это неразрешимая формула.

Существование же в формальной системе неразрешимой формулы — и к тому же содержательно истинной, так как ее смысл «Я недоказуема» соответствует ситуации в данной системе, означает неполноту системы. Заметим, наконец, что формула с таким смыслом на деле является схемой формул вида «Я формула Ф;, недоказуема», — так что в системе оказывается бесконечное множество неразрешимых высказываний, получаемых различным выбором значений Ф5.

Итак, если формальная арифметика («типа РМ») непротиворечива, то она неполна. А что если она противоречива? Тогда ее теоремы теряют всякую ценность, поскольку в этом случае доказывается, что можно доказать любую наперед заданную теорему —для этого достаточно даже одного-единственного противоречия между доказанной формулой и доказанным ее отрицанием. В этом случае, конечно, гёделева формула, говорящая «Я недоказуема», будет доказуема, но будет доказуемо и ее отрицание. Математики всей душой надеются, что арифметика непротиворечива. Но нельзя ли эту надежду превратить в твердую уверенность и доказать непротиворечивость формальной арифметики?

Исследование Гёделя привело к следующему результату. С помощью своего метода кодировки Геделю удалось доказать в логико-арифметическом исчислении формулу, метаматематический смысл которой таков: «Если формальная арифметика непротиворечива, то формула, говорящая «Я недоказуема», доказуема» (обозначим эту формулу через (*)). Предположим теперь, что мы сумели в рассматриваемом исчислении доказать формулу, утверждающую непротиворечивость формальной арифметики. Тогда, в силу доказанной Гёделем формулы (»), по модесу поненсу следует заключение, что формула, говорящая «Я недоказуема», доказуема. Но это противоречит предыдущей теореме (называемой теоремой о неполноте, или первой теоремой Гёделя). Поэтому получается, что формулу, говорящую о непротиворечивости формальной арифметики, доказать в этой последней нельзя, если только сама формальная арифметика не противоречива. Если же она противоречива, то в ней, как мы отметили выше, доказуема любая формула, в том числе и формула, которую можно считать выражающей наличие у данной формальной системы свойства «быть непротиворечивой».