Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Определим очередные множества следующими соглашениями, а-;) Тм2г — классовые термы ранга ^2г:
Тм21-_аи{-^)1^1. РЕФл,,-.,}
(при г=1 не нужно включать Тм0).
Интерпретация:
(хк (Р))5== {х^ | пробегает те изменения Е по хк, для которых
|Р|(Е')=1}.
Все вхождения переменной хк в хк(Р) считаются связанными, вхождения остальных переменных — такие же, как в Р.
б{) Фл2а+1 — логическое замыкание множества выражений
Фл.{-»и {Х'ЛР) = Ч{0)\^
р, ^еФл2г_1}и{Т’%1. тетм2,}.
6—1 81
Функция истинности: положим хь(Р)=Ти хк(^)=Т2; тогда
На логическое замыкание функция ( | продолжается тем же спо-
собом, что в п. 10.3 б0).
Все вхождения переменных в Хк(Р)=хк(^) и ТЕ те же, как в соответствующий классовый терм. Композиция с помощью связки | не меняет качества вхождения.
Как в п. 2.10, доказывается-, что |/’|(§) зависит только от | — значений переменных, имеющих свободные вхождения в фор-
мулу Ре и Фл„+,.
/=0
На этом описание синтаксиса и семантики БАг закончено.
В заключение покажем, что классы множеств в иНг, выразимых формулами
Ь,Аг и 5Аг, совпадают. Этот результат ие используется в доказательстве теоремы Тарского в следующем параграфе. Однако он сам и метод его доказательства поучительны.
Пусть 1лАг имеют счетное множество переменных. Обозначив их Хи хг, ... . . ., Хп, ... И отождествив Х{ с х'—' 0—1 штрих), мы очевидным способом отождествим также интерпретационные классы для Ь,Аг и БАг. Утверждение о рав-новыразимости немедленно получится тогда из следующего более сильного факта:
10.4. Предложение.
Можно эффективно определить два отображения перевода {формулы ЩАг} {формулы БАг} со следующими свойствами:
а) в каждой точке | значения истинности любой формулы и ее перевода совпадают;
б) множества свободных переменных любой формулы и ее перевода сов-падают.
Заметим, что отображения, которые мы определим, не будут взаимно-обратными!
Доказательство.
а) Перевод 1лАг—БАг. Перевод формулы Р будем обозначать «Р». Сначала переведем атомарные формулы, затем проведем рекурсию по длине. В алфавите БАг нет сложения, зато есть умножение и возведение в степень, это позволяет вместо л=х+у писать 2г = 2х-2у.
I' а,) Атомарные формулы. Они имеют вид „Выполнив действия“, за-
меним каждый ненулевой терм в Ь,Аг „нормализованным термом*—многочленом
вида Зх^1 где одночлены записаны в виде (... ((х^-х,)- ...)-хг) ..•)> распо-
ложены в словарном порядке и отделены [скобками (... ((от,+тг)+т») + •?•)• Ясно, как такому терму поставить в соответствие терм »2 { в $Аг: скажем,
1, если как подмножества IV;
0 иначе;
1, если ? 0 иначе.
СО
82
»2 t ((*iM*i)_+*!)e есть (2 f (*iK*i))- (2 t (хг)). Перевод „2 t 0“ по определению есть 1. После этого перевод формулы <i = *2 по определению будет »2 t *i“ = »2 * *2“. Ясно, что они имеют одни и те же переменные и истинны в одних и тех же точках
а2) Если „Q“, „Q,“, »Q2“ уже определены, то „~1 Q“ определяется как „Q“ J, „Q". Аналогично строится „Q, Q,“ для остальных связок (ср. отступление о син-
таксисе в гл. 1).
а3) Если „Q“ определена, то „ухй*2“ определяется как
Xfe(«Q»)=xft
Обе формулы ИСТИННЫ В точке ё, если и только если Q (и «Q») истинны во всех изменениях I' ТОЧКИ I ПО Xk.
Свободные переменные у них общие, ибо по индукции можно предположить» что это так для Q и „Q
а4) »gXftQ“ по определению совпадает с „~1 ух,<, 1Q“.
б) Перевод SAr—LiAr.
Перевод Р по-прежнему будем обозначать «Р», хотя иа этот раз Р будет формулой SAr, а «Р»— формулой LiAr.
Тонким местом является перевод формулы х1=х2\хз. Известно, хотя и не слишком легко доказать [12], что он существует и даже может быть взят в виде ЗА ... 3 хпр(х 1, х2, ..., хп), где р — атомарная формула LtAr. Здесь мы примем этот факт иа веру н выберем некоторый перевод «Xi=xsfx3» раз навсегда.
61) Перевод формул из Фло- Следующие правила дают рекурсивное определение:
,,<!==/2“ имеет тот же вид, если S{переменные} U {Т, Т, 1,...} ( в том 'смысле, конечно, что х заменяется на хй, а 1 ... 1 —на (... (1 + 1) + + 0 + •••)•
„хй= *,-*2“ имеет вид ЭХ&Х/ {„Xi = *,“ Д „X/ = *2« ДХА = Xi-Xj)
„хй=*, t *2“ имеет вид 3Xi3X/ (»Xj = *,“ Д »X/ = *2“ А „ха — хЦ t X/“), где Xi, Xj — первые две переменные, не входящие в *ь *2.
Аналогично переводятся формулы с переставленными правыми и левыми частями, а также с 1 ... 1 вместо хк- Далее, положим
»*i = *2“ имеет вид зх,- (“Х?=*]“ Д »X/ — *2"),
где Xi — первая переменная, не входящая в *(, *2, если только нн один из термов *1, *2 не является переменной или I . . .1.
Ясно, что функция истинности и множество свободных переменных при таком переводе сохраняются.
62) Пусть формулы из Флг<-1 уже переведены. Положим
I>xk{Pl) = xk(Pa)a есть ухй („Р,* <->• „А,“);
„хк{Р)Иа есть „Р“ (п),
где справа п=(... (1+1)+ ...) подставлен вместо всех свободных вхождений Xk в «Р». Это завершает доказательство.
11. НЕВЫРАЗИМОСТЬ ИСТИННОСТИ: ТЕОРЕМА ТАРСКОГО
11.1. Язык SAr интерпретируется в N, не во множестве своих формул, как SELF. Чтобы иметь возможность определить вырази-
6* 83
мое множество формул, мы занумеруем их (некоторыми) целыми числами следующим способом.
