Диаграммы

Теория полугрупп

Наш второй пример — теория полугрупп. Ее сигнатура состоит из равенства и единственного двуместного функционального символа, называемого умножением; результат умножения $$x$$ и $$y$$ мы будем обозначать $$(xy)$$.

Теория состоит из аксиом равенства (включая корректность умножения: $$(x_1\hm=x_2)\hm\land (y_1\hm=y_2) \hm\to (x_1y_1\hm=x_2y_2)$$ ; мы опускаем внешние кванторы всеобщности) и аксиомы ассоциативности$$\forall x \forall y \forall z \, ((xy)z=x(yz)).$$

Нормальные модели этой теории называются полугруппами.

Теорема 69. Множество теорем теории полугрупп (множество замкнутых формул указанной сигнатуры, истинных во всех полугруппах) неразрешимо.

Нам понадобится конкретный способ задания полугрупп с помощью образующих и соотношений. Пусть фиксировано некоторое конечное множество, называемое алфавитом. Элементы его называют буквами, а конечные последовательности букв — словами (данного алфавита). На словах определена операция соединения (приписывания), относительно которой они образуют полугруппу, которая называется свободной полугруппой. Эта полугруппа имеет нейтральный элемент — пустое слово, приписывание которого к любому слову не меняет последнего.

Пусть фиксирован алфавит $$A$$, а также конечное число пар слов $$(X_1, Y_1),\dots,(X_n,Y_n)$$ этого алфавита. Два слова алфавита $$A$$ назовем эквивалентными, если одно можно превратить в другое, многократно делая замены подслов вида $$X_i\hm\leftrightarrow Y_i$$. Легко проверить, что получается отношение эквивалентности и что операция приписывания корректно определена на классах эквивалентности и ассоциативна. Получается полугруппа. Ее называют полугруппой с образующими из $$A$$ и соотношениями $$X_i=Y_i$$.

141. Сколько элементов в полугруппе с образующими $$a$$ и $$b$$ и соотношениями $$a^2=\Lambda$$, $$b^2=\Lambda$$, $$ab=ba$$ (через $$\Lambda$$ мы обозначаем пустое слово)? (Ответ: $$4$$ ; это группа $$(\mathbb Z/2\mathbb Z)\times(\mathbb Z/2\mathbb Z)$$.)

Известно, что существуют такие образующие и соотношения, при которых проблема равенства слов (выяснить, принадлежат ли два данных слова одному классу эквивалентности) является алгоритмически неразрешимой (подробнее см. в [5]). Мы сейчас покажем, что этот вопрос можно свести к вопросу о выводимости некоторой формулы в теории полугрупп, так что если бы она была разрешимой, то получилось бы противоречие.

Построение такой формулы происходит весьма естественным образом; мы поясним его на примере. Пусть мы хотим узнать, будут ли слова $$bb$$ и $$a$$ равны в полугруппе с образующими $$a$$ и $$b$$ и соотношениями $$ab\hm=aa$$ и $$bab=b$$. (Другими словами, мы хотим узнать, можно ли из слова $$bb$$ получить слово $$a$$ с помощью замен подслов $$ab\hm\leftrightarrow aa$$ и $$bab\hm\leftrightarrow b$$.) Как сформулировать этот вопрос в терминах формул? Напишем такую формулу:$$\forall a\forall b\,((ab=aa)\land(bab=b)\to(bb=a)).$$ Она является теоремой теории полугрупп (истинна во всех полугруппах, выводима из аксиом полугрупп) тогда и только тогда, когда слова $$bb$$ и $$a$$ эквивалентны в указанной полугруппе, заданной образующими и соотношениями. В самом деле, если одно слово можно получить из другого заменами, то эти замены (в предположении $$ab=aa$$ и $$bab=a$$ ) ничего не меняют и $$bb\hm=a$$, так что написанная формула истинна во всех полугруппах.

Напротив, если слово $$a$$ не получается из $$bb$$ заменой, то существует полугруппа, в которой эта формула не истинна: надо взять как раз полугруппу с образующими $$a$$ и $$b$$ и соотношениями $$ab\hm=aa$$ и $$bab\hm=b$$, значением переменной $$a$$ считать класс слова $$a$$, а значением переменной $$b$$ считать класс слова $$b$$. Тогда значением терма $$ab$$ будет класс слова $$ab$$, равный классу слова $$aa$$ по построению полугруппы. Аналогичным образом при такой оценке будет истинно и равенство $$bab\hm=b$$. А равенство $$bb=a$$ не будет истинно, так как значение терма $$bb$$ есть класс слова $$bb$$, значение терма $$a$$ есть класс слова $$a$$, а эти классы различны по предположению.

Таким образом, любой алгоритм, проверяющий истинность формул в классе всех полугрупп, можно было бы использовать для проверки равенства двух слов в полугруппе, заданной образующими и соотношениями. А среди таких полугрупп есть неразрешимые.

Теория групп (в которой, помимо ассоциативности, есть еще аксиомы существования единицы и обратного), также неразрешима, но доказательство этого сложнее, чем для полугрупп. Это и не удивительно, поскольку из неразрешимости теории групп формально выводится неразрешимость теории полугрупп, как показывает следующая задача.

142. Пусть теория $$T$$ разрешима, а теория $$T'$$ той же сигнатуры получается из $$T$$ добавлением конечного числа аксиом. Тогда теория $$T'$$ разрешима. (Указание: дополнительные аксиомы соединяем конъюнкциями и помещаем в посылку импликации.)

Добавление аксиом может сделать неразрешимую теорию разрешимой. Например, как мы уже упоминали, это происходит с теорией групп при добавлении аксиомы коммутативности.

Формальная арифметика

Рассмотрим множество натуральных чисел с операциями сложения и умножения и его элементарную теорию $$\Th(\mathbb{N},{=},{+},{\times})$$, то есть множество всех истинных (в натуральном ряду) формул со сложением и умножением. Это множество, очевидно, полно. Можно доказать ([5]), что оно неразрешимо (и, более того, неарифметично, как говорит теорема Тарского).

Отсюда следует, что теория $$\Th(\mathbb{N},{=},{+},{\times})$$ не является конечно аксиоматизируемой. (В самом деле, эта теория полна и неразрешима, и можно сослаться на теорему 67.) Более того, это же рассуждение показывает, что не существует разрешимого множества теорем этой теории, из которых бы выводились все другие теоремы. Отсюда следует, что классическая система аксиом формальной арифметики, называемая также арифметикой Пеано (свойства арифметических операций плюс аксиомы индукции), не может быть полной: существуют истинные формулы, невыводимые в формальной арифметике. Это утверждение составляет содержание знаменитой теоремы Геделя о неполноте.

143. Покажите, что нельзя добавить к языку теории $$\Th(\mathbb{N},{=},{+},{\times})$$ конечное число выразимых предикатов так, чтобы после этого проходила элиминация кванторов. (Указание: арифметическая иерархия не ограничивается никаким конечным числом уровней.)

144. Покажите, что элементарная теория целых чисел со сложением и умножением сводится к элементарной теории натуральных чисел со сложением и умножением: по замкнутой формуле $$\varphi$$ со сложением и умножением можно алгоритмически построить формулу $$\varphi'$$ с таким свойством: $$\varphi$$ истинна в $$\mathbb{Z}$$ тогда и только тогда, когда $$\varphi'$$ истинна в $$\mathbb{N}$$. (Указание: целые числа можно кодировать парами натуральных.)

145. (Продолжение) Покажите, что верно и обратное: элементарная теория натуральных чисел сводится к элементарной теории целых чисел. (Указание. Если бы в целых числах был порядок, это было бы совсем просто. Чтобы его ввести, можно использовать теорему Лагранжа о том, что всякое натуральное число представимо в виде суммы четырех квадратов.)

Будет ли теория $$\Th(\mathbb{N},{=},{+},{\times})$$ категоричной в счетной мощности? Другими словами, имеет ли она счетную модель, не изоморфную стандартной? Раньше, для более простых ситуаций, нам удавалось указать такие модели явно. Теперь это не удастся, но есть простое общее рассуждение, устанавливающее существование нестандартной модели. (Оно аналогично рассуждению, использованному при доказательстве теоремы 52.)

Рассмотрим последовательность формул $$E_0(x)$$, $$E_1(x)$$, $$E_2(x),\dots$$ с единственным параметром $$x$$, где $$E_i(x)$$ — любая формула, выражающая в стандартной модели свойство $$x=i$$. (Если бы у нас в языке была константа $$1$$, можно было бы считать $$E_i(x)$$ бескванторной формулой $$x=1+1+\ldots+1$$, в правой части которой стоит терм с $$i$$ единицами.)

Добавим к сигнатуре новую константу $$c$$ и рассмотрим теорию, получаемую из $$\Th(\mathbb{N},{=},{+},{\times})$$ добавлением счетного семейства формул $$\lnot E_i(c)$$ (по существу мы добавляем формулы $$c\hm\ne 0,\,c\hm\ne 1,\dots$$, записанные подходящим образом). Любое конечное подмножество полученной теории имеет модель (возьмем стандартный натуральный ряд и в качестве $$c$$ выберем достаточно большое число). Следовательно (теорема 50 о компактности), и вся эта теория совместна. Рассмотрим ее счетную нормальную модель и забудем о символе $$c$$ ; получится некоторая интерпретация сигнатуры $$({=},{+},{\times})$$. Она будет элементарно эквивалентна стандартному натуральному ряду (все истинные в $$\mathbb{N}$$ формулы будут истинны по построению, а все ложные будут ложны, так как их отрицания истинны).

Осталось показать, что она не будет изоморфной натуральному ряду. В самом деле, рассмотрим элемент, который является значением константы $$c$$ в нестандартной модели. Он не может переходить ни в какое натуральное число $$i$$, поскольку для соответствующих (друг другу при изоморфизме) элементов выполнены одни и те же формулы, $$E_i(i)$$ истинно в натуральном ряду и $$E_i(c)$$ ложно в новой интерпретации.

146. Покажите, что найдется нормальная интерпретация сколь угодно большой мощности, элементарно эквивалентная натуральным числам со сложением и умножением.

Диаграммы и расширения

В разделе "Повышение мощности" мы видели, что элементарные расширения интерпретации $$A$$ суть модели теории $$\Th_A(A)$$. А что можно сказать о расширениях (без требования элементарности)? Оказывается, что ситуация тут аналогична, только теория будет бескванторной.

Пусть дана нормальная интерпретация $$A$$ сигнатуры $$\sigma$$ (включающей равенство). Как и в прошлом разделе, рассмотрим сигнатуру $$\sigma_A$$, которая получается добавлением к $$\sigma$$ констант для всех элементов интерпретации $$A$$. Рассмотрим теперь все бескванторные формулы сигнатуры $$\sigma_A$$, истинные в $$A$$. Это множество называется диаграммой интерпретации $$A$$ и обозначается $$D(A)$$.

Всякое расширение $$B\supset A$$ (в котором $$A$$ является подструктурой) является моделью теории $$D(A)$$. В самом деле, истинность бескванторных формул из $$D(A)$$ никак не зависит от присутствия или отсутствия дополнительных элементов, раз операции на элементах из $$A$$ те же самые). Обратно, любую модель $$B$$ теории $$D(A)$$ можно считать расширением интерпретации $$A$$, если отождествить $$a\in A$$ со значением соответствующей константы в $$B$$. (Как и раньше, различные элементы $$A$$ не склеиваются — формула $$a_1\ne a_2$$ является бескванторной.)

Теперь мы готовы дать ответ на такой вопрос. Пусть есть нормальная интерпретация $$A$$ сигнатуры $$\sigma$$ и некоторая теория $$T$$ (с равенством) этой сигнатуры. В каком случае существует расширение $$B$$ интерпретации $$A$$, являющееся нормальной моделью теории $$T$$?

Теорема 70. Нормальная интерпретация $$A$$ сигнатуры $$\sigma$$ может быть расширена до нормальной модели теории $$T$$ (с равенством) тогда и только тогда, когда все $$\Pi_1$$ -формулы сигнатуры $$\sigma$$, выводимые из $$T$$, истинны в $$A$$.

Если $$\Pi_1$$ -формула истинна в некоторой структуре, то она истинна и в подструктуре (область, по которой пробегают переменные в кванторах всеобщности, только уменьшается). Если некоторое расширение $$B$$ интерпретации $$A$$ является моделью теории $$T$$, то все $$\Pi_1$$ -формулы, выводимые из $$T$$, истинны в $$B$$, а потому и в $$A$$.

Осталось доказать обратное: если в $$A$$ истинны все $$\Pi_1$$ -следствия формул из $$T$$, то существует искомое расширение. Согласно сказанному выше, достаточно доказать, что теория $$D(A) \hm\cup T$$ непротиворечива. Если это не так, то из $$T$$ выводится некоторая бескванторная формула $$\varphi(a_1,\dots,a_n)$$, ложная в $$A$$. Но в формулы теории $$T$$ константы $$a_1,\dots,a_n$$ не входят, поэтому их можно заменить на свежие переменные $$x_1,\dots,x_n$$ и вывести формулу $$\varphi(x_1,\dots,x_n)$$ и затем $$\forall x_1\forall x_2\ldots\forall x_n\, \varphi(x_1,\dots,x_n)$$ Таким образом, мы нашли $$\Pi_1$$ -теорему теории $$T$$, которая ложна в $$A$$ (поскольку формула $$\varphi(a_1,\dots,a_n)$$ ложна), вопреки нашему

Рассмотрим пример из алгебры. Пусть $$F$$ — множество с заданной на нем операцией. В каком случае его можно вложить в коммутативную группу? Согласно теореме 70, для этого необходимо и достаточно, чтобы в $$F$$ выполнялись все $$\Pi_1$$ - следствия аксиом коммутативной группы (записанных в сигнатуре с единственной операцией умножения). Некоторые из этих аксиом сами являются $$\Pi_1$$ -формулами. Таковы, например, свойства коммутативности и ассоциативности. Другие аксиомы (существование единицы и обратного) не лежат в $$\Pi_1$$ (например, аксиома о существовании единицы имеет вид $$\exists e \forall x\dots$$ ). Поэтому они не обязаны выполняться в $$F$$. Но их $$\Pi_1$$ - следствия, например, правило сокращения$$\forall x\forall y\forall z\, ({(xy=xz)}\hm\to{(y=z)}),$$ должны выполняться. В данном случае оказывается, что этих трех утверждений достаточно: всякая коммутативная полугруппа с сокращением может быть вложена в коммутативную группу.

147. Докажите это утверждение. (Указание. Элементами группы можно считать классы формальных выражений вида $$x-y$$, как это делается, когда от натуральных чисел переходят к целым. В общей ситуации эту группу называют группой Гротендика.)

Вот еще один хорошо известный пример из алгебры. В каком случае коммутативное кольцо $$K$$ может быть вложено в поле? Теорема 70 требует, чтобы в $$K$$ выполнялись все $$\Pi_1$$ -теоремы теории полей. Оказывается, что достаточно выполнения единственного $$\Pi_1$$ -свойства: отсутствия делителей нуля:$$\forall x \forall y \, ((xy=0)\to ((x=0)\lor (y=0))).$$ В этом случае кольцо может быть вложено в поле.

148. Докажите это утверждение. (Указание. Это поле называют полем частных; его элементами являются формальные дроби вида $$m/n$$ при естественных определениях равенства и операций.)

Не всегда, однако, можно указать простые критерии вложимости. Мы не зря требовали коммутативности: известный советский алгебраист и логик А.И.Мальцев доказал, что не всякое некоммутативное кольцо без делителей нуля вкладывается в тело и что никакое конечное число $$\Pi_1$$ -формул не дают критерия вложимости полугруппы в группу (подробнее см. в книге Куроша [14],глава II, параграф 5).

Мы знаем теперь, когда данную интерпретацию можно расширить до модели данной теории. Это позволяет легко ответить и на такой вопрос: когда существует модель данной теории и ее расширение, являющееся моделью другой теории.

Теорема 71. Пусть даны две теории (с равенством) $$T_1$$ и $$T_2$$ некоторой сигнатуры. Тогда следующие свойства равносильны:

(а) существует нормальная модель теории $$T_1$$ и ее расширение, являющееся нормальной моделью теории $$T_2$$ ;

(б) объединение $$T_1$$ со всеми $$\Pi_1$$ -теоремами теории $$T_2$$ совместно;

(в) объединение $$T_2$$ со всеми $$\Sigma_1$$ -теоремами теории $$T_1$$ совместно.

Прежде всего отметим, что из (а) очевидно следуют (б) и (в). В самом деле, если $$M_1\subset M_2$$ — модели соответствующих теорий, то в $$M_1$$ истинны все теоремы теории $$T_1$$ и все $$\Pi_1$$ -теоремы теории $$T_2$$ (поскольку они наследуются из $$M_2$$ ), а в $$M_2$$ истинны все теоремы теории $$T_2$$ и все $$\Sigma_1$$ -теоремы теории $$T_1$$.

Легко проверить, что симметричные условия (б) и (в) равносильны друг другу, а также такому свойству: не существует $$\Sigma_1$$ - теоремы $$\exists x_1\ldots\exists x_n\,\varphi$$ теории $$T_1$$ и отрицающей ее $$\Pi_1$$ -теоремы $$\forall x_1\ldots\forall x_n\,\lnot\varphi$$ теории $$T_2$$. Пусть, например, теория $$T_1$$ несовместна с $$\Pi_1$$ -следствиями теории $$T_2$$. В этом противоречии участвует конечное число $$\Pi_1$$ -формул, которые можно объединить в одну. Получится $$\Pi_1$$ -формула, она будет выводима в теории $$T_2$$, а ее отрицание — в $$T_1$$.

Нам осталось доказать, что любое из свойств (б) и (в) влечет (а). Здесь нам придется нарушить симметрию и использовать именно (б). По условию есть интерпретация $$M_1$$, в которой истинны все теоремы теории $$T_1$$ и все $$\Pi_1$$ -теоремы теории $$T_2$$. Согласно теореме 70 найдется ее расширение $$M_2$$, являющееся моделью $$T_2$$, что и требовалось доказать.

Можно было бы пытаться рассуждать симметричным образом, начав с модели теории $$T_2$$, в которой истинны все $$\Pi_1$$ -теоремы теории $$T_1$$, и пытаться выделить в ней подструктуру, являющуюся моделью теории $$T_1$$. Однако этот план не проходит, поскольку аналог теоремы 70 для подструктур неверен.

149. Покажите, что возможна такая ситуация: все $$\Sigma_1$$ -теоремы некоторой теории $$T$$ истинны в некоторой интерпретации $$M$$, но $$M$$ не имеет подструктуры, являющейся моделью теории $$T$$. (Указание. Рассмотрим теорию линейно упорядоченных множеств без минимального элемента. Все ее $$\Sigma_1$$ -следствия верны в $$\mathbb{N}\hm+\mathbb{Z}$$, поскольку переносятся из $$\mathbb{Z}$$, поэтому в силу элементарной эквивалентности верны и в $$\mathbb{N}$$.)

Вот еще одно следствие доказанных в этом разделе результатов. Теорию $$T$$ называют $$\Pi_1$$ -аксиоматизируемой, если существует множество $$\Pi_1$$ -формул, из которого выводятся все теоремы теории $$T$$ и только они.

Напомним, что нормальная интерпретация $$A$$ сигнатуры $$\sigma$$ является подструктурой нормальной интерпретации $$B$$ той же сигнатуры, если $$B$$ является расширением $$A$$, то есть носитель интерпретации $$A$$ есть подмножество носителя интерпретации $$B$$ и функциональные и предикатные символы интерпретируются одинаково на аргументах из $$A$$. (Другими словами, чтобы задать какую-либо подструктуру данной нормальной интерпретации $$B$$, нужно выбрать подмножество носителя $$B$$, замкнутое относительно сигнатурных операций.)

Теорема 72 (Лося-Тарского). Теория $$\Pi_1$$ -аксиоматизируема тогда и только тогда, когда она устойчива относительна перехода к подструктурам, то есть когда любая подструктура любой ее нормальной модели является ее моделью.

Очевидно, $$\Pi_1$$ -аксиоматизируемая теория устойчива относительно перехода к подструктурам (все формулы из ее $$\Pi_1$$ -аксиоматизации остаются истинными). Обратно, пусть $$T$$ — произвольная теория, устойчивая относительно перехода к подструктурам. Рассмотрим множество $$T_1$$ всех $$\Pi_1$$ - формул, выводимых в $$T$$. Проверим, что все теоремы $$T$$ выводятся из $$T_1$$. Пусть какая-то формула $$\varphi$$ выводится из $$T$$, но не из $$T_1$$. Тогда теория $$T_1+\lnot\varphi$$ непротиворечива и по теореме 71 найдется (нормальная) модель теории $$\{\lnot\varphi\}$$ и ее расширение, являющееся моделью теории $$T$$, что противоречит предположению.

150. Докажите, что если формула устойчива относительно перехода к подструктурам, то она выводимо эквивалентна $$\Pi_1$$ -формуле той же сигнатуры.

Симметричное рассуждение доказывает симметричное утверждение про $$\Sigma_1$$ -аксиоматизируемые теории.

Теорема 73. Теория является $$\Sigma_1$$ -аксиоматизируемой тогда и только тогда, когда она устойчива относительно перехода к расширениям.

151. Проведите подробно соответствующее рассуждение (дав необходимые определения).

152. Докажите, что если формула устойчива относительно перехода к расширениям, то она выводимо эквивалентна $$\Sigma_1$$ -формуле той же сигнатуры.

Теоретико-модельные критерии существуют и для других классов формул, в частности $$\Pi_2$$ -формул (то есть формул типа $$\forall\exists$$ ). Такие формулы не устойчивы ни относительно расширений, ни относительно подструктур. Рассмотрим, например, утверждение об отсутствии наибольшего элемента в упорядоченном множестве. Оно записывается в виде $$\forall\exists$$ -формулы. Истинность его в некотором множестве вовсе не влечет его истинность в подмножествах и в расширениях. Тем не менее кое- что об этом утверждении сказать можно: если ни одно из множеств возрастающей цепи $$M_0\hm\subset M_1\hm\subset M_2\hm\subset\dots$$ не имеет наибольшего элемента, то и объединение $$\cup_i M_i$$ не имеет наибольшего элемента (проверьте). Именно это свойство, как мы вскоре увидим, характеризует $$\Pi_2$$ -формулы.

Пусть дана последовательность$$M_0\hm\subset M_1\hm\subset M_2\hm\subset\ldots$$ нормальных (в этом разделе мы другие не рассматриваем) интерпретаций сигнатуры $$\sigma$$, причем $$M_i$$ является подструктурой $$M_{i+1}$$ (предикаты и функции согласованы). Тогда объединение этой возрастающей цепи интерпретаций также является (нормальной) интерпретацией сигнатуры $$\sigma$$. (Подобная конструкция используется в теории полей, когда строится алгебраическое замыкание счетного поля: мы расширяем поле, добавляя по очереди корни различных многочленов, а потом берем объединение этих полей.)

Заметим, что любая $$\Pi_2$$ -формула устойчива относительно объединения цепей: если она истинна во всех $$M_i$$, то она истинна и в их объединении. В самом деле, пусть формула $$\forall x \exists y\, \varphi(x,y)$$ с бескванторной частью $$\varphi(x,y)$$ истинна во всех $$M_i$$. Тогда она истинна и в их объединении. В самом деле, любое $$x$$ из объединения принадлежит какому-то $$M_i$$, и в том же самом $$M_i$$ можно найти подходящее $$y$$. (Если переменных несколько, рассуждение аналогично.)

Поэтому и любая теория, имеющая $$\Pi_2$$ -аксиоматизацию, устойчива относительно объединения. Обратное утверждение также верно:

Теорема 74 (Чэна-Лося-Сушко). Теория является $$\Pi_2$$ -аксиоматизируемой тогда и только тогда, когда она устойчива относительно объединения возрастающих цепей (объединение любой цепи ее моделей также является ее моделью).

Доказательство этой теоремы использует понятие элементарного расширения. Напомним, что $$M_2$$ называется элементарным расширением $$M_1$$, если $$M_1\hm\subset M_2$$ и в $$M_2$$ истинны те же формулы с константами из $$M_1$$, что и в $$M_1$$. (Обозначение: $$M_1\hm\prec M_2$$.)

153. Покажите, что если $$M_1\hm\prec M_2 \hm\prec M_3$$, то $$M_3$$ есть элементарное расширение $$M_1$$.

Лемма Тарского. Объединение цепи элементарных расширений $$M_1\hm\prec M_2\hm\prec M_3\hm\prec\ldots$$ является элементарным расширением каждой из интерпретаций цепи.

Доказательство леммы. Пусть параметрам формулы $$\varphi$$ приданы значения в каком-либо из $$M_i$$. Нам надо доказать, что полученная формула одновременно истинна или ложна в $$M_i$$ и в объединении цепи, которое мы обозначим через $$M$$. (Условие леммы гарантирует, что формула $$\varphi$$ с указанными значениями параметров одновременно истинна или ложна во всех интерпретациях цепи, начиная с $$M_i$$.)

Это утверждение доказывается индукцией по построению формулы $$\varphi$$. Для атомарных формул оно очевидно; для логических операций индукция также проходит автоматически. Единственный содержательный случай — это кванторы. Пусть формула $$\varphi$$ начинается с квантора $$\exists \xi$$. Если подходящее значение $$\xi$$ найдется уже в $$M_i$$, то оно годится и для $$M$$ (пользуемся предположением индукции). В обратную сторону: если подходящее $$\xi$$ найдется в $$M$$, то оно принадлежит $$M_j$$ при достаточно большом $$j$$, поэтому формула истинна в $$M_j$$ (предположение индукции). Остается вспомнить, что $$M_j$$ элементарно эквивалентно $$M_i$$.

Как всегда, квантор всеобщности можно выразить с помощью квантора сушествования (или провести двойственное рассуждение). Лемма Тарского доказана.

Теперь докажем теорему Чэна-Лося-Сушко. Предположим, что теория $$T$$ устойчива относительно объединения цепей. Обозначим через $$T'$$ множество всех $$\Pi_2$$ -теорем $$T$$. Нам надо доказать, что любая модель $$T'$$ является моделью $$T$$.

Для этого, начав с любой модели $$M'$$ теории $$T'$$, мы построим цепь интерпретаций$$M'= M_0\subset M_1\subset M_2\subset M_3\subset\ldots,$$ в которой чередуются модели теории $$T'$$ (интерпретации $$M_0,M_2,M_4,\dots$$ ), которые являются элементарными расширениями друг друга, и модели теории $$T$$ (интерпретации $$M_1,M_3,M_5,\dots$$ ; они, впрочем, также будут моделями теории $$T'$$ ).

Объединение всех $$M_i$$ будет моделью теории $$T$$, так как эта теория устойчива относительно расширений. С другой стороны, по лемме Тарского это объединение элементарно эквивалентно интерпретациям $$M_0,M_2,M_4,\dots$$ Поэтому все они, включая исходную модель $$M'\hm=M_0$$, будут моделями теории $$T$$, что и требовалось доказать.

Осталось построить требуемую цепь. Интерпретация $$M_0\hm=M'$$ уже есть. Будем строить цепь по шагам, продолжая ее на каждом шаге на два звена вперед. Возможность этого обеспечивает такая лемма:

Лемма о расширении. Если все $$\Pi_2$$ -следствия теории $$T$$ истинны в интерпретации $$A$$, то можно построить ее расширения $$A\subset B \subset C$$ так, чтобы $$B$$ было моделью теории $$T$$, а $$C$$ было элементарным расширением $$A$$.

Прежде чем доказывать лемму о расширении, покажем (хотя это нам и не понадобится), что сформулированное условие необходимо. Пусть $$A\hm\subset B\hm\subset C$$, причем $$C$$ — элементарное расширение $$A$$. Тогда любое $$\Pi_2$$ -утверждение, истинное в $$B$$, истинно и в $$A$$. В самом деле, пусть утверждение $$\forall x \exists y \varphi(x,y)$$ с бескванторной формулой $$\varphi$$ истинно в $$B$$. Проверим его истинность в $$A$$. Если оно ложно при $$x=a$$, то $$\exists y\,\varphi(a,y)$$ ложно и в $$A$$, и в $$C$$ (элементарность расширения) и потому не может быть истинным в $$B$$ (поскольку всякое $$y$$ из $$B$$ лежит и в $$C$$ ).

Доказательство леммы о расширении. Что требуется от данного расширения $$B$$ интерпретации $$A$$, чтобы можно было построить $$C$$ с требуемыми свойствами? Свойства эти состоят в том, что $$C$$ должно быть моделью теории $$\Th_A(A)$$ и расширением интерпретации $$B$$. Как раз про это говорит теорема 70, надо лишь в качестве $$\sigma$$ в этой теореме взять нашу сигнатуру $$\sigma$$ с добавленными константами для $$A$$ (мы обозначали ее $$\sigma_A$$ ), а в качестве теории $$T$$ из теоремы 70 взять $$\Th_A(A)$$, то есть множество всех истинных в $$A$$ формул с константами из $$A$$.

Применяя указанный в теореме 70 критерий, можно сформулировать утверждение, которое нам осталось доказать, так: найдется модель $$B$$ теории $$T$$, которая является расширением $$A$$ и в которой истинны все $$\Pi_1$$ -формулы сигнатуры $$\sigma_A$$, выводимые из $$\Th_A(A)$$. Вспоминая метод диаграмм, можно сказать, что нас интересует совместность теории $$T$$ с $$D(A)$$ и со всеми $$\Pi_1$$ - следствиями теории $$\Th_A(A)$$ в сигнатуре $$\sigma_A$$. В данном случае $$D(A)$$ можно и не упоминать явно, так как оно содержится в $$\Th_A(A)$$.

Итак, осталось доказать, что теория $$T$$ совместна со всеми $$\Pi_1$$ -формулами с константами из $$A$$, истинными в $$A$$. Если это не так, из $$T$$ выводится отрицание какой-то из этих формул, то есть некоторая $$\Sigma_1$$ -формула$$\exists \beta_1\dots\exists \beta_m\, \lnot\varphi(a_1,\dots,a_n,\beta_1,\dots,\beta_m),$$ ложная в $$A$$. Константы $$a_1,\dots,a_n$$ не входят в теорию $$T$$, поэтому из $$T$$ выводится и формула$$\forall \alpha_1\ldots\forall \alpha_n \exists \beta_1\dots\exists \beta_m\, \lnot\varphi(\alpha_1,\dots,\alpha_n,\beta_1,\dots,\beta_m),$$ которая будет выводимой из $$T$$ формулой класса $$\Pi_2$$, ложной в $$A$$, а таких формул не бывает по условию.

Лемма о расширении (а с ней и теорема Чэна-Лося-Сушко) доказана.

154. Докажите, что если формула устойчива относительно объединения возрастающих цепей, то она выводимо эквивалентна некоторой $$\Pi_2$$ -формуле той же сигнатуры.

155. Покажите, что две интерпретации одной сигнатуры элементарно эквивалентны тогда и только тогда, когда они имеют изоморфные элементарные расширения.