Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Проверка условий леммы Цорна. Пусть {е'а}а^/’—линейно упорядоченное подмножество В Се ДЛЯ 'любых а, Ре / либо г'аСе'9> либо е'3 С г'д- Тогда объединение и®'а принадлежит Се. Действительно, иначе и®'« было бы противоречиво. Существовал бы вывод противоречия из конечного числа формул. Пусть они содержатся хв е' ,..., е'а . Среди е'^, ..., е'а есть множество, содержащее остальные п—1; оно было бы противоречиво вопреки предположению.
Вывод из леммы Цорна: в множестве Св существует максимальный элемент, т. е. такое непротиворечивое множество е'эе, ЧТО если аф.ъ', ТО в' и {С} противоречиво.
Утверждается, что е' полно. Действительно, предположим, что Р замкнута, Рф.Р, и придем к противоречию. Из максимальности е' следует, что
5*
67
г и {Т3} I—е' и {"1 Р} I—ГДе ^ — любая формула. По лемме о дедукции е' — Р-*Я, е' |— ~| Р-*Ц. Тавтология (Я -* 1?) -»((Д Я -* й) -*? ? и МР дают е' —что несовместимо с непротиворечивостью е'.
6.11. Доказательство леммы 6.7. Чтобы построить язык с достаточным алфавитом для непротиворечивого множества формул г', содержащего е и Ах V, поступим самым естественным образом.
а) Добавим к алфавиту языка Ь множество новых констант той же мощности, что и алфавит Ь. Получится язык V.
б) Рассмотрим множество формул еДАхЬ' в языке Ь', где АхЬ'— все логические аксиомы языка Ь'. Оно непротиворечиво. Действительно, если бы существовал вывод противоречия из е у АхЬ
в Ь', то следующая процедура превратила бы его в вывод противоречия из е в Ь: возмем конечное множество всех новых констант, входящих в формулы этого вывода, и заменим эти константы старыми переменными (из Ь), не входящими в формулы этого вывода. Легко проверить, что вывод противоречия останется выводом противоречия и будет проходить целиком в Ь.
в) В и возьмем множество всех формул Р(х), содержащих ровно одну свободную переменную. Для каждой такой формулы Р выберем свою новую константу сР, определим формулу
Яр: ДухР(*)-^ДР(Ср) и положим окончательно
е' = е и Ах Ь' и {ЯД.
Очевидно, осталось проверить только, что е' непротиворечиво. Если бы из г' выводилось противоречие, то оно выводилось бы с участием конечного числа формул Яр. Поэтому достаточно проверить, что добавление одной формулы Яр не может привести к противоречию, если Яр добавляется к непротиворечивому множеству. Изменив обозначения, можно считать, что это непротиворечивое множество И есть 8 У АхЬ'.
Предположим обратное: ? У АхЬ'и {ЯД противоречиво. Тогда» в частности е у Ах Ь' и {ЯД \- Д Яр и по лемме о дедукции б и и АхЬ' у Яр — Д Яр. Тавтология (Яр—? Д ЯД —>? Д Яр и МР дают
8 и Ах Ь'|— Д Яр — Д (Д у х Р (•*) -ДР(сД).
Пользуясь тавтологиями Д (Р —* ~| <2) —> Р А Q» Р А Q —1"Р. Р Л Ф — <2, получаем б У Ах Ь' |— Д ул'Р^Д.гД АхЬ' |— Р (ср).
Покажем, что тогда множество ? и Ах Ь' противоречиво вопреки предположению.
Действительно, в выводе Р (ср) из s (J Ах L' всюду заменим ср переменной у, не входящей в этот вывод. Получим вывод Р (у)~ из sQ?xL'. После этого Gen, аксиома специализации, МР и снова Gen приведут к выводу ухР(л:).
6.12. Доказательство л е м м ы 6.8. Пусть L — язык класса &\, s — множество формул в нем. Вложим е в полное непро-тиворечивое множество е', затем к (L, е') применим лемму 6.7. Получившиеся язык и множество формул обозначим через L*,. е*. Положим, далее, по индукции
(L(0), s(0)) = (L, е); (L(i+I), e(l+1,) = (L(,)*, S(0*)
и наконец,
L(0o)=U L(i), e(00) = U s(0.
i=0 /=0
Множество e(00) непротиворечиво, ибо иначе вывод противоречия получался бы „на конечном уровне“, а все е(1) непротиворечивы. Оно полно, ибо каждая замкнутая формула L(0O) записывается в алфавите L(l), для какого-то /, a s(<+1) содержит пополнение s(i>
в Ь(г). Наконец, алфавит L(00) достаточен для s(0O) по тем же соображениям.
Этим заканчивается доказательство лемм.
6.13. Вывод теоремы 6.2 из лемм. Пусть Г—геделево множество формул в L. Применяя к нему лемму 6.8, вложим (L, Т)
~в (L<co), jT(00)), где пара (L(00), Г(сс)) удовлетворяет лемме 6.5. Пусть <р(00)—интерпретация L(00), существование которой утверждает лемма 6.5. Мощность М(со) не превышает card (алфавит L) + &„. Ограничение <р интерпретации <р(00) на L удовлетворяет условию TciTL. Докажем, что T — T^L. Действительно, пусть PG TL. Если Р замкнута, то Р(Е7\ ибо в силу полноты либо Р, либо ~\ Р лежит в Т, а второе несовместимо с ^-истинностью Р. Если она незамкнута и xv ..., хп — переменные, входящие в Р свободно, то YM. • • УхлР замкнута и принадлежит Т. По аксиоме специализации, Р выводима из Т (J {у*!- • -У-*л^}» откуда Р$?Т в силу замкнутости Т относительно выводов.
Это доказывает первое утверждение теоремы.
Второе следует из аналогичного рассуждения: применяя его к s вместо Т, находим модель ф для е; тогда и T?Lгеделево.
6.14. Заметим в заключение, что если алфавит L содержит символ =, для которого в 8 (или Т) включены аксиомы равенства, то существует нормальная интерпретация, удовлетворяющая те-
69
ореме 6.2 и переводящая = в равенство. Для доказательства следует построенную выше модель М профакторизовать по отношению эквивалентности ф(=), как в п. 4.6.
