Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
7. СЧЕТНЫЕ МОДЕЛИ И ПАРАДОКС СКОЛЕМА
«7 know what you're thinking about», said Tweedledum, «but it isn't so, nohow». «Contrariwise», continued Tweedledee, «if it was so, it might be; if it were so, it would be: but as it isn’t, it ain’t. That's logic».
Lewis Carroll, Through the Looking Glass.
7.1. В этом параграфе изложена техника «урезания моделей», в частности, для LiSet.
Пусть L—язык класса S’u M^N — два множества (или класса в V), ф, ф— интерпретации L в М, N соответственно, согласованные в очевидном смысле слова, jraK что ф есть расширение ф.
Интерпретационные классы М, N естественно вложены: M<=N.
7.2. Определение.
Формула Р языка L называется (М, N)-абсолютной, если для всех 1<=М имеем'
\P\m(1) = \P\n&).
Мы пишем вместо ||ф и т. п.
Свойство абсолютности используется обычно так: если Р абсолютна и к тому же N истинна, то она заведомо Af-истинна. Стандартный механизм нарушения абсолютности: если формула
gxQ(x) А'-истинна, значит в N есть объект со свойством Q, но в М такого объекта может не оказаться. Доказательство следующего факта описывает, как с этим бороться.
7.3. Предложение.
Пусть е — множество формул языка L, ф — интерпретация L в N, Mq^N — некоторое подмножество. Существует множество М, M0<=M^N, мощности scrcardMo-f-card такое, что все фор-
мулы из е (М, N)-абсолютны.
7.4. Следствие (Левенсейм — Сколем).
Если алфавит L счетен и N является моделью г, то в N существует счетная подмодель &.
(Ее можно строить, сохранив абсолютность всех формул L, в частности истинность всех формул, которые были истинными.)
Доказательство. Пусть множество M^N, 0, уже определено. Положим
Ml+l=Mt и {xv \V = V (X, Р, 5)}.
70
где х пробега_ет переменные Ь; Р —подформулы формул из е; |— точки из Ми. а при фиксированной тройке (л:, Р, |) \ является каким-нибудь одним изменением | ПО X СО СВОЙСТВОМ |Р|1у(?') = 1, если оно существует; в противном случае (л:, Р, ?) не вносит вклада в Мш.
Положим далее Л1 = У М{. Утверждение о мощности М оче-
видно. Покажем теперь, что все подформулы формул из а (М, У)-абсолютны. Проведем индукцию по числу кванторов в формуле. Для атомарных формул результат очевиден; индуктивный шаг, отвечающий конструкции новой формулы с помощью связок, также ясен. Квантор у сводится стандартным способом в д.
Итак, пусть Р абсолютна. Установим абсолютность дхР. Достаточно считать, что х входит в Р свободно. Имеем для
Но условия за фигурной скобкой эквивалентны. Действительно, существует такое изменение ^ точки ? по переменным, не входящим свободно в Р, что гдля подходящего и Тогда в случае |а^|Л,(9 = 1а^и(г|)=1 существует ?'6еУ с |Р|дг(5')=1 существует г/^АК-н с |^1«'(Л/) = |-Р|лг(г1,)==1. л'—изменение л по х в силу конструкции М{+1 и индуктивного предположения. Это доказывает требуемое.
7.5. Применим теперь следствие 7.4 к стандартной интерпретации Ь13е4 в универсуме фон Неймана У и к множеству е аксиом Цермело — Френкеля. Мы получим счетную модель У для этой системы аксиом, у которой, однако, будет один недостаток: если ХеУ, некоторые элементы X могут не принадлежать Лг, т. е. У не будет транзитивна. Следующий результат Мостовского показывает, как заменить У транзитивной счетной моделью.
Пусть У^У— некоторый подкласс, е^УХ-У^— бинарное отношение на нем. Мы будем писать ХеУ вместо {X, У)(=е. Для любого ХеУ положим
Предположим, что [Х]еУ для всех XеУ, т. е. что [X] —множества, а не классы. Рассмотрим интерпретацию ф языка Ь^е! в классе У, для которой ф(<=) есть е, и ф(=) —равенство.
00
( 1, если существует $'?У, изменение Е по X,
1, если существует Е" изменение Е ПО X,
[Х]={У | УеХ}.
71
7.6. Предложение (Мостовский).
Предположим, что аксиомы объемности и пустого множества ф-истинны и в N не существует бесконечной цепочки ХпгХп-1е... вХ\еХо.
Тогда существует единственный транзитивный класс М^У и единственный изоморфизм /: (X, е).
Применяя это утверждение к счетной модели (X, (=) аксиом Цермело — Френкеля из п. 7.5, мы найдем транзитивную счетную (М, е) — «маленький универсум». (Условие об обрыве цепочек выполнено в У, а не только в X; [X] есть подмножество ЙГр) и потому является элементом V.)
7.7. Д о к а з ат е л ь ст в о предложения 7.6. Для каждого ординала а мы построим трансфинитной рекурсией (см. приложение Универсум фон Нейман) множества N Ма57, согласованные изоморфизмы. /а: (Хае )д, ) ~ (Ма ,
и покажем, что иМа=М.
а) Из (р-истинности аксиомы объемности и того, что <р (=)—равенство," без труда получаем X, = Х2 <±:=> [А',] = [Х2] 'для всех Хи Х2 ?ЕN. Пусть 0Л,€5У— интерпретация константы 0 языка Ь^еЕ Согласно сделанному замечанию, с учетом истинности аксиомы пустого множества находим, что 0я—единственный элемент У, для которого [0л]=0е7. Положим
АГо={0*}, М0= {0}; fo(0N) —0.
б) Рекурсивное построение. Пусть а—ординал. Допустим, что Ха, /И , / уже построены. Положим:
К+1 {X) = {/« (К) I к €= [X]} для X е Л/а+1\.Уа; /а+1 = /в;
АГа+1-образ /в+1.
Если р — предельный ординал, положим
и ЛГв; = и М,-, /3 = и /а.
3 а<3 3 а<3 3 а<3
Наконец, положим М— и Ма, [—и[а по всем ординалам.
