Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 37
Текст из файла (страница 37)
Нам осталосьпоказать, что если теория T совместна с аксиомами равенства, тоона имеет нормальную модель.Возьмём произвольную интерпретацию, в которой истинны формулы из T и аксиомы равенства. Пусть M — её носитель. В этой интерпретации предикат = не обязан быть настоящим равенством; онпредставляет собой некоторое бинарное отношение на M . Поскольку выполнены аксиомы равенства, это отношение рефлексивно, симметрично и транзитивно (является отношением эквивалентности).Следовательно, множество M разбивается на классы эквивалентности; множество этих классов обозначим M 0 (его можно назвать фактор-множеством M по данному отношению эквивалентности).
Классэлемента x будем обозначать [x].Аксиомы равенства позволяют корректно определить интерпретацию c носителем M 0 . В самом деле, истинность аксиомы для функционального символа f (приведённой выше в качестве примера) гарантирует, что класс [f (x, y)] зависит лишь от классов [x] и [y], но неот выбора x и y внутри класса. Аналогичным образом аксиомы дляпредикатных символов позволяют корректно определить предикатына классах.Полученная интерпретация с носителем M 0 по построению нормальна. Осталось убедиться, что в ней истинны те же самые формулы, что и в M (в том числе все формулы теории T ). Это почтиочевидно с интуитивной точки зрения: M отличается от M 0 лишьтем, что каждый элемент представлен несколькими равноправнымикопиями, которые со всех точек зрения ведут себя одинаково.Формально говоря, мы доказываем, что формула ϕ истинна винтерпретации M на оценке π тогда и только тогда, когда ϕ истиннав M 0 на оценке π 0 , при которой значение любой переменной ξ естькласс, содержащий значение переменной ξ при оценке π.
Это легкосделать индукцией по построению формулы ϕ. 111. Покажите, что из аксиом равенства для сигнатуры σ выводится[п. 1]Аксиомы равенства169формулаϕ ∧ (x = y) → ϕ(y/x),если подстановка в правой части корректна. (Указание: это очевидно следует из теоремы о полноте, но можно провести и чисто синтаксическоерассуждение индукцией по построению формулы ϕ.)112. Покажите, что если теория T (не обязательно с равенством) имеетмодель мощности α, то она имеет и модель любой большей мощности.(Указание: элементы модели можно «клонировать» в любом количестве.)Из теоремы о полноте для нормальных моделей легко следуетаналог теоремы о компактности (теорема 50, с. 153) для нормальныхмоделей.Теорема 60 (компактности для нормальных моделей).
Если всякоеконечное подмножество теории T в сигнатуре с равенством имеетнормальную модель, то и теория T имеет нормальную модель. Любое конечное подмножество теории T остаётся непротиворечивым при добавлении аксиом равенства (поскольку имеет нормальную модель). Значит, и вся теория T остаётся непротиворечивой придобавлении аксиом равенства (вывод противоречия использует конечное число формул) и потому имеет нормальную модель. 113. Применив теорему о компактности, докажите, что всякий частичный порядок может быть продолжен до линейного. (Указание. Рассмотрим частично упорядоченное множество как модель теории, в сигнатуре которой есть равенство, порядок и константы для всех элементовмножества, а формулами являются равенства и неравенства между константами. Добавим к ней утверждение о сравнимости любых двух элементов.
Покажите, что любое конечное множество формул полученнойтеории непротиворечиво, используя тот факт, что частичный порядок наконечном множестве продолжается до линейного.)114. Используя теорему о компактности, докажите, что для всякогополя k сушествует его расширение k0 , в котором всякий многочлен с коэффициентами из k имеет корень. (Указание. Утверждение о существованиикорня у многочлена с данными коэффициентами можно записать в видеформулы. Любое конечное множество таких формул совместно с аксиомами поля, так как можно по очереди присоединить корни соответствующихмногочленов.)115.
Пусть ` — множество замкнутых формул в сигнатуре с равенством. Покажите, что замкнутая формула ϕ этой сигнатуры истинна вовсех нормальных моделях ` тогда и только тогда, когда она выводима из` и аксиом равенства.Утверждение последней задачи является аналогом теоремы 51(с. 154) для теорий с равенством. Иногда вообще рассматриваюттолько такие теории. При этом равенство является обязательным170Теории и модели[гл. 5]элементом сигнатуры, аксиомы равенства (их число зависит от сигнатуры) считаются частью исчисления предикатов, а интерпретациирассматриваются только нормальные. При этом теория имеет [нормальную] модель тогда и только тогда, когда она непротиворечива[вместе с аксиомами равенства]; формула выводима из теории Γ [иаксиом равенства] тогда и только тогда, когда она верна во всех [нормальных] моделях теории Γ и т.
п. (в квадратных скобках указаныподразумеваемые слова).5.2. Повышение мощностиТеорема Левенгейма – Сколема (теорема 42 в разделе 3.11) позволяла уменьшать мощность интерпретации (она утверждала, что длялюбой бесконечной интерпретации конечной или счётной сигнатурысуществует элементарно эквивалентная ей счётная подструктура).В этом разделе мы рассмотрим обратную задачу — расширение интерпретации до элементарно эквивалентной интерпретации большеймощности.
Соответствующее утверждение также называют теоремой Левенгейма – Сколема.Прежде всего отметим, что без требования нормальности такоеутверждение бессодержательно: как уже говорилось на с. 169, мыможем дублировать элементы интерпретации в произвольном количестве. Поэтому мы предполагаем, что все рассматриваемые интерпретации нормальны (равенство интерпретируется как тождественное совпадение).Теорема 61 (Левенгейма – Сколема о повышении мощности).
ПустьA — бесконечная нормальная интерпретация некоторой сигнатуры σс равенством. Тогда существует нормальная интерпретация B ⊃ Aсколь угодно большой мощности, являющаяся элементарным расширением A.(Это означает, согласно определению на с. 115, напомним, чтоинтерпретация предикатных и функциональных символов в B продолжает их интерпретацию в A и что формулы сигнатуры σ, параметрам которых приданы значения из A, одновременно истинны в Aи в B.) Сформулируем утверждение теоремы в терминах теорий и моделей. Пусть A — произвольная нормальная интерпретация сигнатуры σ. Рассмотрим сигнатуру σA , которая получается из σ добавлением констант — по одной для каждого элемента множества A. Этасигнатура имеет естественную нормальную интерпретацию с носите-[п. 2]Повышение мощности171лем A: значением каждой константы является соответствующий ейэлемент. (Возможно, что в σ изначально было достаточно константи всякий элемент A был значением некоторой константы.
Тогда этапроцедура лишняя, но и вреда от неё нет.)Рассмотрим теорию ThA (A), состоящую из формул сигнатуры σA ,истинных в A при указанной интерпретации. Всякое элементарноерасширение B интерпретации A будет моделью теории ThA (A). В самом деле, замкнутая формула ϕ(a1 , . . . , an ) сигнатуры σA получаетсяподстановкой констант a1 , . . . , an вместо параметров в какую-то формулу ϕ(x1 , . .
. , xn ) сигнатуры σ. (Мы используем не вполне корректные обозначения, в частности, отождествляем элементы a1 , . . . , anмножества A с константами для них.) Её истинность в B (или в A)равносильна истинности формулы ϕ(x1 , . . . , xn ) при значениях параметров x1 7→ a1 , . . . , xn 7→ an — формально говоря, следует воспользоваться леммой 2 на с. 137. Поэтому по определению элементарногорасширения все формулы из ThA (A) будут истинны и в B.Верно и обратное: любая нормальная модель теории ThA (A) естественно определяет элементарное расширение интерпретации A. Всамом деле, пусть дана нормальная модель этой теории с носителем B.
Тогда каждый элемент множества A (точнее, соответствующая этому элементу константа) интерпретируется некоторым элементом множества B. Разным элементам множества A соответствуют разные элементы в B, так как формула a1 6= a2 , истинная в A,должна быть истинной и в B. Таким образом, A вкладывается в B иможно отождествить его с некоторым подмножеством множества B.Это отождествление корректно в том смысле, что предикаты и функциональные символы интерпретируются согласованным образом. Всамом деле, атомарные формулы вида P (a1 , . . . , an ), а также формулы ¬P (a1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
