Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 44
Текст из файла (страница 44)
Теория Π1 -аксиоматизируема тогдаи только тогда, когда она устойчива относительна перехода к подструктурам, то есть когда любая подструктура любой её нормальноймодели является её моделью. Очевидно, Π1 -аксиоматизируемая теория устойчива относительно перехода к подструктурам (все формулы из её Π1 -аксиоматизации остаются истинными). Обратно, пусть T — произвольнаятеория, устойчивая относительно перехода к подструктурам.
Рассмотрим множество T1 всех Π1 -формул, выводимых в T . Проверим,что все теоремы T выводятся из T1 . Пусть какая-то формула ϕ выводится из T , но не из T1 . Тогда теория T1 + ¬ϕ непротиворечива ипо теореме 72 найдётся (нормальная) модель теории {¬ϕ} и её расширение, являющееся моделью теории T , что противоречит предположению. 150. Докажите, что если формула устойчива относительно перехода кподструктурам, то она выводимо эквивалентна некоторой ˝1 -формуле тойже сигнатуры.Симметричное рассуждение доказывает симметричное утверждение про Σ1 -аксиоматизируемые теории.Теорема 74. Теория является Σ1 -аксиоматизируемой тогда и только тогда, когда она устойчива относительно перехода к расширениям.198Теории и модели[гл.
5]151. Проведите подробно соответствующее рассуждение (дав необходимые определения).152. Докажите, что если формула устойчива относительно перехода красширениям, то она выводимо эквивалентна некоторой ˚1 -формуле тойже сигнатуры.Теоретико-модельные критерии существуют и для других классов формул, в частности Π2 -формул (то есть формул типа ∀∃). Такиеформулы не устойчивы ни относительно расширений, ни относительно подструктур. Рассмотрим, например, утверждение об отсутствиинаибольшего элемента в упорядоченном множестве. Оно записывается в виде ∀∃-формулы.
Истинность его в некотором множестве вовсене влечёт его истинность в подмножествах и в расширениях. Тем неменее кое-что об этом утверждении сказать можно: если ни одно измножеств возрастающей цепи M0 ⊂ M1 ⊂ M2 ⊂ . . . не имеет наибольшего элемента, то и объединение ∪i Mi не имеет наибольшегоэлемента (проверьте). Именно это свойство, как мы вскоре увидим,характеризует Π2 -формулы.Пусть дана последовательностьM0 ⊂ M1 ⊂ M2 ⊂ .
. .нормальных (в этом разделе мы другие не рассматриваем) интерпретаций сигнатуры σ, причём Mi является подструктурой Mi+1 (предикаты и функции согласованы). Тогда объединение этой возрастающей цепи интерпретаций также является (нормальной) интерпретацией сигнатуры σ. (Подобная конструкция используется в теорииполей, когда строится алгебраическое замыкание счётного поля: мырасширяем поле, добавляя по очереди корни различных многочленов, а потом берём объединение этих полей.)Заметим, что любая Π2 -формула устойчива относительно объединения цепей: если она истинна во всех Mi , то она истинна и в ихобъединении.
В самом деле, пусть формула ∀x∃y ϕ(x, y) с бескванторной частью ϕ(x, y) истинна во всех Mi . Тогда она истинна и вих объединении. В самом деле, любое x из объединения принадлежит какому-то Mi , и в том же самом Mi можно найти подходящее y.(Если переменных несколько, рассуждение аналогично.)Поэтому и любая теория, имеющая Π2 -аксиоматизацию, устойчива относительно объединения.
Обратное утверждение также верно:Теорема 75 (Чэна – Лося – Сушко). Теория является Π2 -аксиоматизируемой тогда и только тогда, когда она устойчива относительно[п. 5]Диаграммы и расширения199объединения возрастающих цепей (объединение любой цепи её моделей также является её моделью). Доказательство этой теоремы использует понятие элементарного расширения. Напомним, что M2 называется элементарным расширением M1 , если M1 ⊂ M2 и в M2 истинны те же формулы сконстантами из M1 , что и в M1 . (Обозначение: M1 ≺ M2 .)153. Покажите, что если M1 ≺ M2 ≺ M3 , то M3 есть элементарноерасширение M1 .Лемма Тарского. Объединение цепи элементарных расширенийM1 ≺ M2 ≺ M3 ≺ .
. . является элементарным расширением каждой из интерпретаций цепи.Доказательство леммы. Пусть параметрам формулы ϕ приданызначения в каком-либо из Mi . Нам надо доказать, что полученнаяформула одновременно истинна или ложна в Mi и в объединениицепи, которое мы обозначим через M . (Условие леммы гарантирует,что формула ϕ с указанными значениями параметров одновременноистинна или ложна во всех интерпретациях цепи, начиная с Mi .)Это утверждение доказывается индукцией по построению формулы ϕ.
Для атомарных формул оно очевидно; для логических операций индукция также проходит автоматически. Единственный содержательный случай — это кванторы. Пусть формула ϕ начинается с квантора ∃ξ. Если подходящее значение ξ найдётся уже в Mi ,то оно годится и для M (пользуемся предположением индукции). Вобратную сторону: если подходящее ξ найдётся в M , то оно принадлежит Mj при достаточно большом j, поэтому формула истинна вMj (предположение индукции). Остаётся вспомнить, что Mj элементарно эквивалентно Mi .Как всегда, квантор всеобщности можно выразить с помощьюквантора сушествования (или провести двойственное рассуждение).Лемма Тарского доказана.Теперь докажем теорему Чэна – Лося – Сушко.
Предположим, чтотеория T устойчива относительно объединения цепей. Обозначим через T 0 множество всех Π2 -теорем T . Нам надо доказать, что любаямодель T 0 является моделью T .Для этого, начав с любой модели M 0 теории T 0 , мы построимцепь интерпретацийM 0 = M0 ⊂ M1 ⊂ M2 ⊂ M3 ⊂ . . . ,в которой чередуются модели теории T 0 (стоящие на чётных местах интерпретации M0 , M2 , M4 , . . . ), которые являются элементар-200Теории и модели[гл. 5]ными расширениями друг друга, и модели теории T (интерпретацииM1 , M3 , M5 , . .
. ; они, впрочем, также будут моделями теории T 0 ).Объединение всех Mi будет моделью теории T , так как эта теорияустойчива относительно расширений. С другой стороны, по леммеТарского это объединение элементарно эквивалентно интерпретациям M0 , M2 , M4 , . . . Поэтому все они, включая исходную модель M 0 == M0 , будут моделями теории T , что и требовалось доказать.Осталось построить требуемую цепь. Интерпретация M0 = M 0уже есть. Будем строить цепь по шагам, продолжая её на каждомшаге на два звена вперёд. Возможность этого обеспечивает такаялемма:Лемма о расширении. Если все Π2 -следствия теории T истинныв интерпретации A, то можно построить её расширения A ⊂ B ⊂C так, чтобы B было моделью теории T , а C было элементарнымрасширением A.Прежде чем доказывать лемму о расширении, покажем (хотя этонам и не понадобится), что сформулированное условие необходимо.Пусть A ⊂ B ⊂ C, причём C — элементарное расширение A.
Тогдалюбое Π2 -утверждение, истинное в B, истинно и в A. В самом деле,пусть утверждение ∀x∃yϕ(x, y) с бескванторной формулой ϕ истиннов B. Проверим его истинность в A. Если оно ложно при x = a, то∃y ϕ(a, y) ложно и в A, и в C (элементарность расширения) и потомуне может быть истинным в B (поскольку всякое y из B лежит и в C).Доказательство леммы о расширении. Что требуется от данногорасширения B интерпретации A, чтобы можно было построить C стребуемыми свойствами? Свойства эти состоят в том, что C должнобыть моделью теории ThA (A) и расширением интерпретации B. Какраз про это говорит теорема 71, надо лишь в качестве σ в этой теореме взять сигнатуру σ с добавленными константами для A (мы обозначали её σA ), а в качестве теории T из теоремы 71 взять ThA (A),то есть множество всех истинных в A формул с константами из A.Применяя указанный в теореме 71 критерий, можно сформулировать утверждение, которое нам осталось доказать, так: найдётсямодель B теории T , которая является расширением A и в которой истинны все Π1 -формулы сигнатуры σA , выводимые из ThA (A).
Вспоминая метод диаграмм, можно сказать, что нас интересует совместность теории T с D(A) и со всеми Π1 -следствиями теории ThA (A) всигнатуре σA . В данном случае D(A) можно и не упоминать явно,так как оно содержится в ThA (A).Итак, докажем, что теория T совместна со всеми Π1 -формулами[п. 6]Ультрафильтры и компактность201с константами из A, истинными в A. Если это не так, из T выводитсяотрицание какой-то из этих формул, то есть некоторая Σ1 -формула∃β1 . . . ∃βm ¬ϕ(a1 , . . . , an , β1 , . . . , βm ),ложная в A. Константы a1 , .
. . , an не входят в теорию T , поэтому изT выводится и формула∀α1 . . . ∀αn ∃β1 . . . ∃βm ¬ϕ(α1 , . . . , αn , β1 , . . . , βm ),которая будет выводимой из T формулой класса Π2 , ложной в A, атаких формул не бывает по условию.Лемма о расширении (а с ней и теорема Чэна – Лося – Сушко) доказана. 154. Докажите, что если формула устойчива относительно объединения возрастающих цепей, то она выводимо эквивалентна ˝2 -формуле тойже сигнатуры.155.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
