Диаграммы и расширения
В разделе "Повышение мощности" мы видели, что элементарные расширения интерпретации суть модели теории . А что можно сказать о расширениях (без требования элементарности)? Оказывается, что ситуация тут аналогична, только теория будет бескванторной.
Пусть дана нормальная интерпретация
сигнатуры (включающей равенство). Как и в прошлом разделе, рассмотрим сигнатуру , которая получается добавлением к констант для всех элементов интерпретации . Рассмотрим теперь все бескванторные формулы сигнатуры , истинные в . Это множество называется диаграммой интерпретации и обозначается .
Всякое расширение (в котором является подструктурой) является моделью теории . В самом деле, истинность бескванторных формул из никак не зависит от присутствия или отсутствия дополнительных элементов, раз операции на элементах из те же самые). Обратно, любую модель теории можно считать расширением интерпретации , если отождествить со значением соответствующей константы в . (Как и раньше, различные элементы не склеиваются — формула
является бескванторной.)
Теперь мы готовы дать ответ на такой вопрос. Пусть есть нормальная интерпретация сигнатуры и некоторая теория (с равенством) этой сигнатуры. В каком случае существует расширение интерпретации , являющееся нормальной моделью теории ?
Теорема 70. Нормальная интерпретация сигнатуры может быть расширена до нормальной модели теории (с равенством) тогда и только тогда, когда все -формулы сигнатуры , выводимые из , истинны в .
Если -формула истинна в некоторой структуре, то она истинна и в подструктуре (область, по которой пробегают переменные в кванторах всеобщности, только уменьшается). Если некоторое расширение интерпретации является моделью теории , то все -формулы, выводимые из , истинны в , а потому и в .
Осталось доказать обратное: если в истинны все -следствия формул из , то существует искомое расширение. Согласно сказанному выше, достаточно доказать, что теория непротиворечива. Если это не так, то из выводится некоторая бескванторная формула , ложная в . Но в формулы теории константы не входят, поэтому их можно заменить на свежие переменные и вывести формулу и затем Таким образом, мы нашли -теорему теории , которая ложна в (поскольку формула ложна), вопреки нашему
Рассмотрим пример из алгебры. Пусть — множество с заданной на нем операцией. В каком случае его можно вложить в коммутативную группу? Согласно теореме 70, для этого необходимо и достаточно, чтобы в выполнялись все - следствия аксиом коммутативной группы (записанных в сигнатуре с единственной операцией умножения). Некоторые из этих аксиом сами являются -формулами. Таковы, например, свойства коммутативности и ассоциативности. Другие аксиомы (существование единицы и обратного) не лежат в (например, аксиома о существовании единицы имеет вид ). Поэтому они не обязаны выполняться в . Но их - следствия, например, правило сокращения
должны выполняться. В данном случае оказывается, что этих трех утверждений достаточно: всякая коммутативная полугруппа с сокращением может быть вложена в коммутативную группу.
147. Докажите это утверждение. (Указание. Элементами группы можно считать классы формальных выражений вида , как это делается, когда от натуральных чисел переходят к целым. В общей ситуации эту группу называют группой Гротендика.)
Вот еще один хорошо известный пример из алгебры. В каком случае коммутативное кольцо может быть вложено в поле? Теорема 70 требует, чтобы в выполнялись все -теоремы теории полей. Оказывается, что достаточно выполнения единственного -свойства: отсутствия делителей нуля:
В этом случае кольцо может быть вложено в поле.
148. Докажите это утверждение. (Указание. Это поле называют полем частных; его элементами являются формальные дроби вида при естественных определениях равенства и операций.)
Не всегда, однако, можно указать простые критерии вложимости. Мы не зря требовали коммутативности: известный советский алгебраист и логик А.И.Мальцев доказал, что не всякое некоммутативное кольцо без делителей нуля вкладывается в тело и что никакое конечное число -формул не дают критерия вложимости полугруппы в группу (подробнее см. в книге Куроша [14],глава II, параграф 5).
Мы знаем теперь, когда данную интерпретацию можно расширить до модели данной теории. Это позволяет легко ответить и на такой вопрос: когда существует модель данной теории и ее расширение, являющееся моделью другой теории.
Теорема 71. Пусть даны две теории (с равенством) и
некоторой сигнатуры. Тогда следующие свойства равносильны:
(а) существует нормальная модель теории и ее расширение, являющееся нормальной моделью теории ;
(б) объединение со всеми -теоремами теории совместно;
(в) объединение со всеми -теоремами теории совместно.
Прежде всего отметим, что из (а) очевидно следуют (б) и (в). В самом деле, если — модели соответствующих теорий, то в истинны все теоремы теории и все -теоремы теории (поскольку они наследуются из ), а в истинны все теоремы теории и все -теоремы теории .
Легко проверить, что симметричные условия (б) и (в) равносильны друг другу, а также такому свойству: не существует - теоремы
теории и отрицающей ее -теоремы теории . Пусть, например, теория несовместна с -следствиями теории . В этом противоречии участвует конечное число -формул, которые можно объединить в одну. Получится -формула, она будет выводима в теории , а ее отрицание — в .
Нам осталось доказать, что любое из свойств (б) и (в) влечет (а). Здесь нам придется нарушить симметрию и использовать именно (б). По условию есть интерпретация , в которой истинны все теоремы теории и все -теоремы теории . Согласно теореме 70 найдется ее расширение , являющееся моделью , что и требовалось доказать.
Можно было бы пытаться рассуждать симметричным образом, начав с модели теории , в которой истинны все -теоремы теории , и пытаться выделить в ней подструктуру, являющуюся моделью теории . Однако этот план не проходит, поскольку аналог теоремы 70 для подструктур неверен.
149. Покажите, что возможна такая ситуация: все -теоремы некоторой теории истинны в некоторой интерпретации , но не имеет подструктуры, являющейся моделью теории . (Указание. Рассмотрим теорию линейно упорядоченных множеств без минимального элемента. Все ее -следствия верны в , поскольку переносятся из , поэтому в силу элементарной эквивалентности верны и в .)
Вот еще одно следствие доказанных в этом разделе результатов. Теорию называют -аксиоматизируемой, если существует множество -формул, из которого выводятся все теоремы теории и только они.
Напомним, что нормальная интерпретация сигнатуры является подструктурой нормальной интерпретации той же сигнатуры, если является расширением , то есть носитель интерпретации есть подмножество носителя интерпретации и функциональные и предикатные символы интерпретируются одинаково на аргументах из . (Другими словами, чтобы задать какую-либо подструктуру данной нормальной интерпретации , нужно выбрать подмножество носителя , замкнутое относительно сигнатурных операций.)
Теорема 72 (Лося-Тарского). Теория -аксиоматизируема тогда и только тогда, когда она устойчива относительна перехода к подструктурам, то есть когда любая подструктура любой ее нормальной модели является ее моделью.
Очевидно, -аксиоматизируемая теория устойчива относительно перехода к подструктурам (все формулы из ее -аксиоматизации остаются истинными). Обратно, пусть — произвольная теория, устойчивая относительно перехода к подструктурам. Рассмотрим множество всех - формул, выводимых в . Проверим, что все теоремы выводятся из . Пусть какая-то формула выводится из , но не из . Тогда теория
непротиворечива и по теореме 71 найдется (нормальная) модель теории и ее расширение, являющееся моделью теории , что противоречит предположению.
150. Докажите, что если формула устойчива относительно перехода к подструктурам, то она выводимо эквивалентна -формуле той же сигнатуры.
Симметричное рассуждение доказывает симметричное утверждение про -аксиоматизируемые теории.
Теорема 73. Теория является -аксиоматизируемой тогда и только тогда, когда она устойчива относительно перехода к расширениям.
151. Проведите подробно соответствующее рассуждение (дав необходимые определения).
152. Докажите, что если формула устойчива относительно перехода к расширениям, то она выводимо эквивалентна -формуле той же сигнатуры.
Теоретико-модельные критерии существуют и для других классов формул, в частности -формул (то есть формул типа ). Такие формулы не устойчивы ни относительно расширений, ни относительно подструктур. Рассмотрим, например, утверждение об отсутствии наибольшего элемента в упорядоченном множестве. Оно записывается в виде -формулы. Истинность его в некотором множестве вовсе не влечет его истинность в подмножествах и в расширениях. Тем не менее кое- что об этом утверждении сказать можно: если ни одно из множеств возрастающей цепи
не имеет наибольшего элемента, то и объединение не имеет наибольшего элемента (проверьте). Именно это свойство, как мы вскоре увидим, характеризует -формулы.
Пусть дана последовательность
нормальных (в этом разделе мы другие не рассматриваем) интерпретаций сигнатуры , причем является подструктурой (предикаты и функции согласованы). Тогда объединение этой возрастающей цепи интерпретаций также является (нормальной) интерпретацией сигнатуры . (Подобная конструкция используется в теории полей, когда строится алгебраическое замыкание счетного поля: мы расширяем поле, добавляя по очереди корни различных многочленов, а потом берем объединение этих полей.)
Заметим, что любая -формула устойчива относительно объединения цепей: если она истинна во всех , то она истинна и в их объединении. В самом деле, пусть формула с бескванторной частью истинна во всех . Тогда она истинна и в их объединении. В самом деле, любое из объединения принадлежит какому-то , и в том же самом можно найти подходящее . (Если переменных несколько, рассуждение аналогично.)
Поэтому и любая теория, имеющая -аксиоматизацию, устойчива относительно объединения. Обратное утверждение также верно:
Теорема 74 (Чэна-Лося-Сушко). Теория является -аксиоматизируемой тогда и только тогда, когда она устойчива относительно объединения возрастающих цепей (объединение любой цепи ее моделей также является ее моделью).
Доказательство этой теоремы использует понятие элементарного расширения. Напомним, что называется элементарным расширением , если и в истинны те же формулы с константами из , что и в . (Обозначение: .)
153. Покажите, что если , то есть элементарное расширение .
Лемма Тарского. Объединение цепи элементарных расширений является элементарным расширением каждой из интерпретаций цепи.
Доказательство леммы. Пусть параметрам формулы приданы значения в каком-либо из . Нам надо доказать, что полученная формула одновременно истинна или ложна в и в объединении цепи, которое мы обозначим через . (Условие леммы гарантирует, что формула с указанными значениями параметров одновременно истинна или ложна во всех интерпретациях цепи, начиная с .)
Это утверждение доказывается индукцией по построению формулы . Для атомарных формул оно очевидно; для логических операций индукция также проходит автоматически. Единственный содержательный случай — это кванторы. Пусть формула начинается с квантора . Если подходящее значение найдется уже в , то оно годится и для (пользуемся предположением индукции). В обратную сторону: если подходящее найдется в , то оно принадлежит при достаточно большом , поэтому формула истинна в
(предположение индукции). Остается вспомнить, что
элементарно эквивалентно .
Как всегда, квантор всеобщности можно выразить с помощью квантора сушествования (или провести двойственное рассуждение). Лемма Тарского доказана.
Теперь докажем теорему Чэна-Лося-Сушко. Предположим, что теория устойчива относительно объединения цепей. Обозначим через множество всех -теорем . Нам надо доказать, что любая модель является моделью .
Для этого, начав с любой модели теории , мы построим цепь интерпретаций
в которой чередуются модели теории (интерпретации ), которые являются элементарными расширениями друг друга, и модели теории (интерпретации ; они, впрочем, также будут моделями теории ).
Объединение всех будет моделью теории , так как эта теория устойчива относительно расширений. С другой стороны, по лемме Тарского это объединение элементарно эквивалентно интерпретациям Поэтому все они, включая исходную модель , будут моделями теории , что и требовалось доказать.
Осталось построить требуемую цепь. Интерпретация уже есть. Будем строить цепь по шагам, продолжая ее на каждом шаге на два звена вперед. Возможность этого обеспечивает такая лемма:
Лемма о расширении.
Если все -следствия теории истинны в интерпретации , то можно построить ее расширения так, чтобы было моделью теории , а было элементарным расширением .
Прежде чем доказывать лемму о расширении, покажем (хотя это нам и не понадобится), что сформулированное условие необходимо. Пусть , причем — элементарное расширение . Тогда любое -утверждение, истинное в , истинно и в . В самом деле, пусть утверждение с бескванторной формулой
истинно в . Проверим его истинность в . Если оно ложно при , то ложно и в , и в (элементарность расширения) и потому не может быть истинным в (поскольку всякое из лежит и в ).
Доказательство леммы о расширении. Что требуется от данного расширения интерпретации , чтобы можно было построить с требуемыми свойствами? Свойства эти состоят в том, что должно быть моделью теории и расширением интерпретации . Как раз про это говорит теорема 70, надо лишь в качестве в этой теореме взять нашу сигнатуру с добавленными константами для (мы обозначали ее ), а в качестве теории из теоремы 70 взять , то есть множество всех истинных в формул с константами из .
Применяя указанный в теореме 70 критерий, можно сформулировать утверждение, которое нам осталось доказать, так: найдется модель теории , которая является расширением и в которой истинны все -формулы сигнатуры , выводимые из . Вспоминая метод диаграмм, можно сказать, что нас интересует совместность теории с и со всеми - следствиями теории в сигнатуре . В данном случае можно и не упоминать явно, так как оно содержится в .
Итак, осталось доказать, что теория совместна со всеми -формулами с константами из , истинными в . Если это не так, из выводится отрицание какой-то из этих формул, то есть некоторая -формула
ложная в . Константы не входят в теорию , поэтому из выводится и формула
которая будет выводимой из формулой класса , ложной в , а таких формул не бывает по условию.
Лемма о расширении (а с ней и теорема Чэна-Лося-Сушко) доказана.
154. Докажите, что если формула устойчива относительно объединения возрастающих цепей, то она выводимо эквивалентна некоторой -формуле той же сигнатуры.
155. Покажите, что две интерпретации одной сигнатуры элементарно эквивалентны тогда и только тогда, когда они имеют изоморфные элементарные расширения.
