Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 43
Текст из файла (страница 43)
Любое конечное подмножествополученной теории имеет модель (возьмём стандартный натуральный ряд и в качестве c выберем достаточно большое число). Следовательно (теорема 50 о компактности), и вся эта теория совместна.Рассмотрим её счётную нормальную модель и забудем о символе c;получится некоторая интерпретация сигнатуры (=, +, ×). Она будетэлементарно эквивалентна стандартному натуральному ряду (все истинные в N формулы будут истинны по построению, а все ложныебудут ложны, так как их отрицания истинны).Осталось показать, что она не будет изоморфной натуральномуряду.
В самом деле, рассмотрим элемент, который является значением константы c в нестандартной модели. Он не может переходитьни в какое натуральное число i, поскольку для соответствующих(друг другу при изоморфизме) элементов выполнены одни и те жеформулы, Ei (i) истинно в натуральном ряду и Ei (c) ложно в новойинтерпретации.194Теории и модели[гл. 5]146. Покажите, что найдётся нормальная интерпретация сколь угоднобольшой мощности, элементарно эквивалентная натуральным числам сосложением и умножением.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. Если Π1 -формула истинна в некоторой структуре, то она истинна и в подструктуре (область, по которой пробегают переменные в кванторах всеобщности, только уменьшается).
Если некотороерасширение B интерпретации A является моделью теории T , то всеΠ1 -формулы, выводимые из T , истинны в B, а потому и в A.Осталось доказать обратное: если в A истинны все Π1 -следствияформул из T , то существует искомое расширение. Согласно сказан-[п. 5]Диаграммы и расширения195ному выше, достаточно доказать, что теория D(A) ∪ T непротиворечива. Если это не так, то из T выводится некоторая бескванторная формула ϕ(a1 , . . . , an ), ложная в A.
Но в формулы теории Tконстанты a1 , . . . , an не входят, поэтому их можно заменить на свежие переменные x1 , . . . , xn и вывести формулу ϕ(x1 , . . . , xn ) и затем ∀x1 ∀x2 . . . ∀xn ϕ(x1 , . . . , xn ) Таким образом, мы нашли Π1 -теорему теории T , которая ложна в A (поскольку формула ϕ(a1 , . . . , an )ложна), вопреки нашему предположению. Рассмотрим пример из алгебры. Пусть F — множество с заданной на нём операцией. В каком случае его можно вложить вкоммутативную группу? Согласно теореме 71, для этого необходимо и достаточно, чтобы в F выполнялись все Π1 -следствия аксиом коммутативной группы (записанных в сигнатуре с единственнойоперацией умножения).
Некоторые из этих аксиом сами являютсяΠ1 -формулами. Таковы, например, свойства коммутативности и ассоциативности. Другие аксиомы (существование единицы и обратного) не лежат в Π1 (например, аксиома о существовании единицыимеет вид ∃e∀x . . . ). Поэтому они не обязаны выполняться в F . Ноих Π1 -следствия, например, правило сокращения∀x∀y∀z ((xy = xz) → (y = z)),должны выполняться. В данном случае оказывается, что этих трёхутверждений достаточно: всякая коммутативная полугруппа с сокращением может быть вложена в коммутативную группу.147. Докажите это утверждение. (Указание.
Элементами группы можно считать классы формальных выражений вида x − y, как это делается,когда от натуральных чисел переходят к целым. В общей ситуации этугруппу называют группой Гротендика.)Вот ещё один хорошо известный пример из алгебры. В какомслучае коммутативное кольцо K может быть вложено в поле? Теорема 71 требует, чтобы в K выполнялись все Π1 -теоремы теории полей.Оказывается, что достаточно выполнения единственного Π1 -свойства: отсутствия делителей нуля:∀x∀y ((xy = 0) → ((x = 0) ∨ (y = 0))).В этом случае кольцо может быть вложено в поле.148.
Докажите это утверждение. (Указание. Это поле называют полем частных ; его элементами являются формальные дроби вида m/n приестественных определениях равенства и операций.)196Теории и модели[гл. 5]Не всегда, однако, можно указать простые критерии вложимости.Мы не зря требовали коммутативности: известный советский алгебраист и логик А. И. Мальцев доказал, что не всякое некоммутативноекольцо без делителей нуля вкладывается в тело и что никакое конечное число Π1 -формул не дают критерия вложимости полугруппыв группу (подробнее см.
в книге Куроша [14], глава II, параграф 5).Мы знаем теперь, когда данную интерпретацию можно расширить до модели данной теории. Это позволяет легко ответить и натакой вопрос: когда существует модель данной теории и её расширение, являющееся моделью другой теории.Теорема 72. Пусть даны две теории (с равенством) T1 и T2 некоторой сигнатуры. Тогда следующие свойства равносильны:(а) существует нормальная модель теории T1 и её расширение,являющееся нормальной моделью теории T2 ;(б) объединение T1 со всеми Π1 -теоремами теории T2 совместно;(в) объединение T2 со всеми Σ1 -теоремами теории T1 совместно. Прежде всего отметим, что из (а) очевидно следуют (б) и (в).В самом деле, если 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, с. 159). Получится Π1 -формула, она будет выводима в теории T2 , а её отрицаниевыводимо в T1 .Нам осталось доказать, что любое из свойств (б) и (в) влечёт (а).Здесь нам придётся нарушить симметрию и использовать именно (б).По условию есть интерпретация M1 , в которой истинны все теоремытеории T1 и все Π1 -теоремы теории T2 . Согласно теореме 71 найдётся её расширение M2 , являющееся моделью T2 , что и требовалосьдоказать.
Можно было бы пытаться рассуждать симметричным образом,начав с модели теории T2 , в которой истинны все Π1 -теоремы теории T1 , и пытаться выделить в ней подструктуру, являющуюся моделью теории T1 . Однако этот план не проходит, поскольку аналогтеоремы 71 для подструктур неверен.[п. 5]Диаграммы и расширения197149. Покажите, что возможна такая ситуация: все ˚1 -теоремы некоторой теории T истинны в некоторой интерпретации M , но M не имеет подструктуры, являющейся моделью теории T . (Указание.
Рассмотрим теорию линейно упорядоченных множеств без минимального элемента. Всееё ˚1 -следствия верны в N + Z, поскольку переносятся из Z, поэтому всилу элементарной эквивалентности верны и в N.)Вот ещё одно следствие доказанных в этом разделе результатов.Теорию T называют Π1 -аксиоматизируемой, если существует множество Π1 -формул, из которого выводятся все теоремы теории T итолько они.Напомним, что нормальная интерпретация A сигнатуры σ является подструктурой нормальной интерпретации B той же сигнатуры, если B является расширением A, то есть носитель интерпретацииA есть подмножество носителя интерпретации B и функциональныеи предикатные символы интерпретируются одинаково на аргументах из A. (Другими словами, чтобы задать какую-либо подструктуруданной нормальной интерпретации B, нужно выбрать подмножествоносителя B, замкнутое относительно сигнатурных операций.)Теорема 73 (Лося – Тарского).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
