Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Символы алфавита (их девять) занумеруем целыми числами от 1 до 9 в любом порядке, но так, чтобы 1 имела номер 9. После этого положим (а*е (алфавит SAr), v(a*)—номера a*):
k
номер {av ..., ak) — n(av a*) = 2 v (at)-\Qk~l I.
i=i
Иными словами, номер выражения получится, если заменить все входящие в него символы соответствующими арабскими цифрами (а 1 заменить на 9!), затем прочесть полученную десятичную запись и увеличить это число на единицу. Ясно, что по номеру выражение восстанавливается однозначно.
Ярлыком выражения Р назовем имя номера Р в SAr, т. е.
1...1 (п (Р) раз). Будем обозначать ярлык Р через как
в SELF (но теперь это — сокращенная запись).
Экспонатом Р назовем выражение Р >j< Р >jc.
11.2. Определение.
Пусть Р(х)—формула SAr с одной свободной переменной х.
а) Выражение Q удовлетворяет Р, если номер Q лежит во множестве {k\P(k)} истинна];
б) выражение Q выставлено в Р, если экспонат Q удовлетворяет Р.
11.3. Лемма. Пусть Р(х), как в п. 11.2. Обозначим через РЕ(х) формулу Р((х) -((Ю) \ (х))) Терм ,x10хи подставлен вместо всех свободных вхождений х). Тогда множество выражений, удовлетворяющих Ре, совпадает с множеством выражений, выставленных в Р.
Доказательство. Если Q имеет номер k, то экспонат Q имеет номер k- 10fe (вот зачем 1 имеет номер девять):
(Q)-1)10"(Q) +
n(Q) раз
+ 9...9+l=/z(Q)-10n(Q).
л(Q) раз
Значит, номер Q удовлетворяет Ре в том и только в том случае, когда номер экспоната Q удовлетворяет Р.
84
11.4. Теорема.
Для любой формулы Р(х), как в п. 11.2, имеем
{Множество формул, удовлетворяющих Р} ф
Множество истин-пых формул,
Множество ложных формул.
Доказательство. Рассмотрим формулу Тарского — Шмулья-яа 5: хРЕ %хРй >|<. Согласно определениям, имеем (учесть, что хРЕ — классовый терм, а >|<л-Ряфс— имя числа):
3 истинна ф=г$хРЕ удовлетворяет РЕ хРЕ выставлена в Р{лем-ма 10.3) фгф экспонат хРЕ удовлетворяет Р 5 удовлетворяет Р.
Значит, либо 5 не ложна и удовлетворяет Р, либо ложна и не удовлетворяет Р; поэтому множество удовлетворяющих Р формул не может совпадать с множеством ложных формул.
Как в § 9, формула 3 говорит: «Я удовлетворяю Р». Аналогично, формула
*№ I (Р))в*х((Р) 1 (Р))в
говорит: «Я не удовлетворяю Р» и потому либо удовлетворяет Р, либо не истинна. Теорема доказана.
11.5. Лемма 11.3 — это, конечно, чистое волшебство. Десятичная • система тут ни при чем, и 1 не обязательно было нумеровать девяткой, но так все гораздо красивее.
Более общо, пусть ?Аг — любой язык арифметики с конечным алфавитом, содержащим алфавит SAr. Пусть правила образования и стандартной интерпретации формул в ?Аг расширены как угодно по сравнению с SAr. Требуется лишь, чтобы термы и формулы SAr сохранили прежний смысл и для любой формулы Р(х) в ?Аг со свободной переменной х выражение x{P{x))k было формулой в ?Аг и интерпретировалось бы по тому лее рецепту, что и в SAr. (Например, можно добавить к SAr знак «+», связки и кванторы и разрешить строить формулы также по правилам так мы вложим ЦАг в ?Аг.)
Тогда для ?Аг справедлива теорема о невыразимости п. 11.4.
Нумерацию нужно выбрать так: если m — число элементов алфавита ?Ar, v — нумерация символов, при которой v(l)=m, то
n(a1...ak) = ^i v(а;)(™+!)*"' +1-
г=1
85
Тогда в прежних соглашениях
П (Q * Q >к) == я (Q1 • • • 1) = (Я (Q) — I) (т +1)',<<3) +
п(Q) раз
я (Q)—1
4-т 2 (^+1)/+l=«(Q)(w+l)',(<3)
/=о
и, определив Рц(х) как Р((х)- ((m-j-1) f(*))), мы без дальнейших изменений получим лемму 11.3 и теорему Тарского для ?Аг.
11.6. Комментарии, а) Если бы теорема Тарского была не верна и для какой-то формулы Р(х) оказалось, что {Q|Q — формула и P(n(Q)) истинна} совпадает с множеством всех истинных формул арифметики, это означало бы, что все теоретико-числовые вопро-сы сводятся к серии однотипных задач. Вместо того, чтобы спра-шивать, верна ли проблема номер п, можно было бы спрашивать, истинно ли утверждение Р(п).
Хотя такая массовая проблема может иметь значительную сложность (и в определенном смысле быть «бесконечно сложной»), теорема Тарского утверждает, что вся арифметика является еще гораздо более разнообразной.
б) Пока у нас остается повод для подозрения, что все дело в «слишком удачной» нумерации формул. Это не так. Можно по-* казать, что теорема Тарского остается верной для любой нумера« ции, при которой формула и ее номер эффективно восстанавлива-ются друг по другу.
в) Естественно задаться вопросом, выразимо ли множество но« меров доказуемых или выводимых формул (при каком-нибудь определении аксиом и правил вывода, скажем, в SAr). Ответ: да, выразимо.
Приведем интуитивные соображения в пользу этого.
Как бы мы ни определили понятие доказуемости, можно естественно считать, что оно обладает следующим свойством: существует алгоритм (скажем, программа на ЭВМ), который по любому тексту данного языка распознает, является ли этот текст доказательством и какой именно формулы.
Напишем теперь программу, которая будет подряд в словарном порядке строить тексты на языке, проверять, являются ли они доказательствами, и вычислять номер доказанной формулы в случае положительного ответа. График функции (номер доказательства) ->- (номер доказанной формулы) выразим в LiAr, грубо говоря, потому, что машинная логика и арифметика заложены в LiAr. Поэтому множество номеров доказуемых формул выразимо в LiAr, в SAr или в любом языке ?Аг, как в 11.5.
