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

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

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

Всякое расширение B A (в котором A является под-

структурой) является моделью теории D(A). В самом деле, истинность бескванторных формул из D(A) никак не зависит от присутствия или отсутствия дополнительных элементов, раз операции на элементах из A те же самые). Обратно, любую модель B теории D(A) можно считать расширением интерпретации A, если отождествить a A

со значением соответствующей константы в B. (Как и раньше, различные элементы A не склеиваются | формула a1 6= a2 является бескванторной.)

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

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

C Если ˝1-формула истинна в некоторой структуре,

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

вложено в поле? Теорема 71 требует, чтобы в K выполнялись все ˝1-теоремы теории полей. Оказывается, что достаточно выполнения единственного ˝ 1-свойства: отсутствия делителей нуля:

x y ((xy = 0) → ((x = 0) (y = 0))):

Вэтом случае кольцо может быть вложено в поле.

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

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

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

Теорема 72. Пусть даны две теории (с равенством) T1 и T2 некоторой сигнатуры. Тогда следующие свойства равносильны:

(а) существует нормальная модель теории T1 и её расширение, являющееся нормальной моделью теории T2;

(б) объединение T1 со всеми ˝1-теоремами теории T2 совместно;

(в) объединение T2 со всеми ˚1-теоремами теории T1 совместно.

C Прежде всего отметим, что из (а) очевидно следуют (б) и (в). В самом деле, если M1 M2 | модели

соответствующих теорий, то в M1 истинны все теоремы теории T1 и все ˝1-теоремы теории T2 (поскольку они на-

следуются из M2), а в M2 истинны все теоремы теории T2 и все ˚1-теоремы теории T1.

Легко проверить, что симметричные условия (б) и (в) равносильны друг другу, а также такому свойству: не

существует ˚1-теоремы x1 : : : xn ' теории T1 и отрицающей её ˝1-теоремы x1 : : : xn ¬' теории T2. Пусть, например, теория T1 несовместна с ˝1-следствиями тео-

рии T2. В этом противоречии участвует конечное число ˝1-формул, которые можно объединить в одну (см. раздел 4.7, с. 194). Получится ˝1-формула, она будет выводима в теории T2, а её отрицание | в T1.

Нам осталось доказать, что любое из свойств (б) и (в) влечёт (а). Здесь нам придётся нарушить симметрию и использовать именно (б). По условию есть интерпретация M1, в которой истинны все теоремы теории T1 и все ˝1-теоремы теории T2. Согласно теореме 71 найдётся её расширение M2, являющееся моделью T2, что и требовалось доказать. B

Можно было бы пытаться рассуждать симметричным образом, начав с модели теории T2, в которой истинны все ˝1-теоремы теории T1, и пытаться выделить в ней подструктуру, являющуюся моделью теории T1. Однако этот план не проходит, поскольку аналог теоремы 71 для подструктур неверен.

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

силу элементарной эквивалентности верны и в N.)

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

Напомним, что нормальная интерпретация A сигнатуры является подструктурой нормальной интерпретации B той же сигнатуры, если B является расширением

формул типа ). Такие формулы не устойчивы ни от-

носительно расширений, ни относительно подструктур. Рассмотрим, например, утверждение об отсутствии наибольшего элемента в упорядоченном множестве. Оно записывается в виде -формулы. Истинность его в неко-

тором множестве вовсе не влечёт его истинность в подмножествах и в расширениях. Тем не менее кое-что об этом утверждении сказать можно: если ни одно из множеств возрастающей цепи M0 M1 M2 : : : не имеет

наибольшего элемента, то и объединение iMi не имеет

наибольшего элемента (проверьте). Именно это свойство, как мы вскоре увидим, характеризует ˝ 2-формулы.

Пусть дана последовательность

M0 M1 M2 : : :

нормальных (в этом разделе мы другие не рассматриваем) интерпретаций сигнатуры , причём Mi является подструктурой Mi+1 (предикаты и функции согласованы). Тогда объединение этой возрастающей цепи интерпретаций также является (нормальной) интерпретацией сигнатуры . (Подобная конструкция используется в теории полей, когда строится алгебраическое замыкание счётного поля: мы расширяем поле, добавляя по очереди корни различных многочленов, а потом берём объединение этих полей.)

Заметим, что любая ˝2-формула устойчива относительно объединения цепей: если она истинна во всех Mi, то она истинна и в их объединении. В самом деле, пусть формула x y '(x; y) с бескванторной частью '(x; y) ис-

тинна во всех Mi. Тогда она истинна и в их объединении. В самом деле, любое x из объединения принадлежит какому-то Mi, и в том же самом Mi можно найти подходящее y. (Если переменных несколько, рассуждение аналогично.)

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

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

C Доказательство этой теоремы использует понятие

элементарного расширения. Напомним, что 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 .

Для этого, начав с любой модели M0 теории T 0, мы построим цепь интерпретаций

M0 = M0 M1 M2 M3 : : : ;

в которой чередуются модели теории T 0 (интерпретации

M0; M2; M4; : : : ), которые являются элементарными расширениями друг друга, и модели теории T (интерпрета-

ции M1; M3; M5; : : : ; они, впрочем, также будут моделями теории T 0).

Объединение всех Mi будет моделью теории T , так как эта теория устойчива относительно расширений. С другой стороны, по лемме Тарского это объединение эле-

ментарно эквивалентно интерпретациям M0; M2; M4; : : :

Поэтому все они, включая исходную модель M0 = M0,

будут моделями теории T , что и требовалось доказать.

Осталось построить требуемую цепь. Интерпретация M0 = M0 уже есть. Будем строить цепь по шагам, про-

должая её на каждом шаге на два звена вперёд. Возможность этого обеспечивает такая лемма:

Лемма о расширении . Если все ˝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).