Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Однако эти конструкции мешают друг другу. Пополняя множество е, для которого алфавит был достаточен, мы можем получить множество с недостаточным алфавитом, а добавляя новые константы, мы увеличиваем общий запас формул в языке и тем нарушаем полноту старых множеств.
Поэтому конструкции 1.5 и 1.6 придется по очереди провести счетное число раз, чтобы в конце концов доказать последнюю лемму
5-1
65
? 1
6.8. Лемма. j
Если езАхЬ непротиворечиво, то существует: |
а) язык L(00), алфавит которого получается добавлениемJt?
алфавиту L множества новых констант мощности ^card (алфа 1 вит Ь>+х„;
б) множество формул е(ос) в языке L(00), полное, непротиворечивое, содержащее s и AxL(00) и такое, что алфавит Llco) до статочен для него.
После того как лемма 6.8 будет доказана, теорема 6.2 получит, ся из основной леммы, если применить ее ks(00), а затем ограничить получившуюся модель на L и е.
Приступим теперь к доказательству лемм. Основная лемма бу-дет доказана в п. 6.9, леммы 6.5—6.7 — в п. 6.10—6.12.
6.9. Доказательство оснонной леммы. Начнем с явного построе-1 ния интерпретации ф языка L, которая окажется моделью для е.
а) Назовем постоянным термом такой терм в L, который не содержит символов переменных. Положим далее М = «второй экземпляр» множества постоянных термов языка = (F|?—постоянные термы} и определим первичные отображения интерпретации ф языка L в М условиями:
ф(с)=с для любой константы е;
?(/)(<"..., ?)=/(*, tr)
для любого символа операции ранга г и любых постоянных термов;
(Ти tr )е=ф(р),
если и только если p(ti (для любого отношения р ранга г и постоянных термов tu . . ., tr) ?
Докажем теперь следующее.
б) Утверждение. Пусть Р— замкнутая формула. Имеем |Р]ф = 1 в tomJh только том случае, когда Р?г. (Отсюда уже будет следовать, что у-модель е. В самом деле, если незамкнута, то ее замыкание уХ1 ...ухпР выводимо из е с помощью Оеп и в силу полноты и непротиворечивости е должно содержаться в е. В силу утверждения, | ух^... ухлР= 1, ; откуда |/Дф = 1).
Доказательство утверждения б). Проведем индукцию по общему числу кванторов и связок в формуле Р. Будем писать |Р| вместо \Р Ц.
б,) Р— атомарная формула p(tu •••, *п). Утверждение следует из определения \Р\ н списка первичных отображений, потому что из замкнутости Р вытекает, что термы ti постоянны.
б,) P=~\Q.
Если | Р] = 1, то j Q | = 0 и Q^e по индуктивному предположению для Q в силу полноты IQGe, т. е. Рег'
Если же | Р | = 0, то [Q |=1 и Qe«, откуда "IQ^e в силу непротиворечи
B0CTHJ?.
бз) Р= (Qi—
Сначала покажем, что если |Р|=0, то][Р^Ёе. 'Действительно, в этом слу чае | Q, |= 1, [Q2|=0; по индукции QiSe, 0.гф.*', в силу полноты Дф2€=« тавтология Qb- (Д Q2>- Д (Q, -> Q,)) и два МР дают ? [— Д (Q, -* Q*). В силу
66
полноты выводимые из е замкнутые формулы содержатся в в; значит, П (О, -*? -> <3г) = ""1 -Рб=е> так что Рф.е.
Теперь покажем, что если Рф.*, то |.Р|=0. Действительно, тогда в силу полноты Д “| (<?, -» (2г)^е. Тавтологии ~1 ((?1-><Э2)-*(21 а 1№->(2г)-* Д (32 и МР дают в]—С?!, е |— (?2, откуда в силу полноты «1^«, п<г,&.
По индуктивному предположению, | & ] = 1, | <321 = 0, откуда ] Р [ = | -> ф21 =
б*) (° = <31 V Сг ИЛИ С?! /\Чг.
С помощью тавтологий, выражающих V. Л через этот случай сво-
дится к ^предыдущим, и мы опускаем его разбор.
Если х не входит в <2 свободно, то |Р|=1 равносильно |(2|=1, т. е., по индуктивному предположению, фее. Это включение, в свою очередь, равносильно включению ухфее в одну сторону по Деп, в другую — по аксиоме специализации с t=x и МР.
Дальше мы предполагаем поэтому, что х входит в (3 свободно.
Сначала предположим, что |Р| = 1, но 8, н придем к противоречию.
Если Рф.е, то т- е- "1-4x0 (х) е е. Так как алфавит И достато-
чен для е, в е содержится формула Д ух<3 (х) -*• 1 Я (с^). Применяя МР, получим в]—"^(Сд), откуда в силу непротиворечивости е, (} (Сд) ф. е. По индуктивному предположению |(2(Сд)[=0 (<3 (Сд) замкнута!). Это означает, что |Я|(|)= = 0 для б?М, если х?’ = Сц, что противоречит предложению ] Р1 = 1.
Теперь предположим, что |Р|=0, но Рее, и придем к противоречию.
Так как |Р|=0, для некоторого |<=М имеем |<3|(|)=0. Найдем постоянный терм / из условия х^=Л Очевидно, х не связывает ^ в Q, так что 0= = |<3 (х) | (|) = |<9(0 |, откуда (?(0 Ф-в по индуктивному предположению, н Д (3(0 ее в силу полноты.
С другой стороны, если Рее, т. е. уэс(2(зс)ее, то по аксиоме специализации ух<3 (х) -» <3 (/) получаем е [—<3 ((). Эго несовместимо с непротиворечивостью г по результату предыдущего абзаца.
б.) Р = а*3-
Этот случай сводится к предыдущему с помощью аксиомы, выражающей д через у и отрицание, и мы опускаем его разбор.
6.10. Доказательство леммы 6.6. Чтобы вложить множество е в полное непротиворечивое множество е', мы должны будем воспользоваться трансфинитной индукцией или эквивалентной ей леммой Цорна и леммой о дедукции для языка Ё, доказанной в п. 4, 5 гл. II.
Лемма Цорна будет применяться к множеству Се = {множество множеств формул е' языка Ь, содержащих е и непротиворечивых, которое упорядочено включением.
