Пусть сигнатура $$\sigma$$ включает в себя двуместный предикат равенства (записываемый традиционно $$x=y$$ ). Интерпретация этой сигнатуры называется нормальной,если предикат равенства интерпретируется как тождественное совпадение элементов носителя.
Возникает естественный вопрос. Пусть имеется некоторая теория $$T$$ (множество замкнутых формул) в языке, сигнатура которого включает равенство. Мы знаем что теория имеет модель (интерпретацию, в которой все формулы из $$T$$ истинны) тогда и только тогда, когда она непротиворечива. В каком случае она имеет нормальную модель (нормальную интерпретацию, в которой все формулы из $$T$$ истинны)?
Чтобы ответить на этот вопрос, введем аксиомы равенства. Пусть $$\sigma$$ произвольная сигнатура. Аксиомами равенства
в сигнатуре $$\sigma$$ будут формулы$$\begin{align*}
\forall x\,(x=x),\\
\forall x\forall y \,((x=y)\to(y=x)),\\
\forall x\forall y\forall z\, (((x=y)\land (y=z))\to(x=z))
\end{align*}$$
(называемые аксиомами
Теорема 59 (полноты для нормальных моделей). Теория $$T$$ сигнатуры $$\sigma$$ с равенством имеет нормальную модель тогда и только тогда, когда она остается непротиворечивой при добавлении аксиом равенства.
Прежде всего заметим, что теоремы о корректности и полноте
(раздел "Полнота
В нормальной модели теории $$T$$ аксиомы равенства истинны, так что в одну сторону утверждение теоремы очевидно. Нам осталось показать, что если теория $$T$$ совместна с аксиомами равенства, то она имеет нормальную модель.
Возьмем произвольную интерпретацию, в которой
Аксиомы равенства позволяют корректно определить интерпретацию c
носителем $$M'$$. В самом деле, истинность аксиомы для
функционального символа $$f$$ (приведенной выше в качестве
примера) гарантирует, что класс $$[f(x,y)]$$ зависит лишь от
классов $$[x]$$ и $$[y]$$, но не от выбора $$x$$
и $$y$$ внутри класса. Аналогичным образом аксиомы для
Полученная интерпретация с носителем $$M'$$ по построению нормальна. Осталось убедиться, что в ней истинны те же самые формулы, что и в $$M$$ (в том числе все формулы теории $$T$$ ). Это почти очевидно с интуитивной точки зрения: $$M$$ отличается от $$M'$$ лишь тем, что каждый элемент представлен несколькими равноправными копиями, которые со всех точек зрения ведут себя одинаково.
Формально говоря, мы доказываем, что формула $$\varphi$$ истинна в интерпретации $$M$$ на оценке $$\pi$$ тогда и только тогда, когда $$\varphi$$ истинна в $$M'$$ на оценке $$\pi'$$, при которой значение любой переменной $$\xi$$ есть класс, содержащий значение переменной $$\xi$$ при оценке $$\pi$$. Это легко сделать индукцией по построению формулы $$\varphi$$.
111. Покажите, что из аксиом равенства для сигнатуры $$\sigma$$ выводится формула$$\varphi \land (x=y) \to \varphi(y/x),$$ если подстановка в правой части корректна. (Указание: это очевидно следует из теоремы о полноте, но можно провести и чисто синтаксическое рассуждение индукцией по построению формулы $$\varphi$$.)
112. Покажите, что если теория $$T$$ (не обязательно с равенством) имеет модель мощности $$\alpha$$, то она имеет и модель любой большей мощности. (Указание: элементы модели можно "клонировать" в произвольном количестве.)
Из теоремы о полноте для нормальных моделей легко следует аналог теоремы о компактности (теорема 50) для нормальных моделей.
Теорема 60 (компактности для нормальных моделей). Если всякое конечное подмножество теории $$T$$ в сигнатуре с равенством имеет нормальную модель, то и теория $$T$$ имеет нормальную модель.
Любое конечное подмножество теории $$T$$ остается непротиворечивым при добавлении аксиом равенства (поскольку имеет нормальную модель). Значит, и вся теория $$T$$ остается непротиворечивой при добавлении аксиом равенства (вывод противоречия использует конечное число формул) и потому имеет нормальную модель.
113. Применив теорему о компактности, докажите, что всякий частичный
порядок может быть продолжен до линейного. (Указание. Рассмотрим
114. Используя теорему о компактности, докажите, что для всякого поля $$k$$ сушествует его расширение $$k'$$, в котором всякий многочлен с коэффициентами из $$k$$ имеет корень. (Указание. Утверждение о существовании корня у многочлена с данными коэффициентами можно записать в виде формулы. Любое конечное множество таких формул совместно с аксиомами поля, так как можно по очереди присоединить корни соответствующих многочленов.)
115. Пусть $$\Gamma$$ — множество замкнутых формул в сигнатуре с равенством. Покажите, что замкнутая формула $$\varphi$$ этой сигнатуры истинна во всех нормальных моделях $$\Gamma$$ тогда и только тогда, когда она выводима из $$\Gamma$$ и аксиом равенства.
Утверждение последней задачи является аналогом
теоремы 51 для теорий с равенством.
Иногда вообще рассматривают только такие теории. При этом
равенство является обязательным элементом сигнатуры, аксиомы
равенства (их число зависит от сигнатуры) считаются частью
Теорема Левенгейма-Сколема позволяла уменьшать мощность интерпретации (она утверждала, что для любой бесконечной интерпретации конечной или счетной сигнатуры существует элементарно эквивалентная ей счетная подструктура). В этом разделе мы рассмотрим обратную задачу — расширение интерпретации до элементарно эквивалентной интерпретации большей мощности. Соответствующее утверждение также называют теоремой Левенгейма-Сколема.
Прежде всего отметим, что без требования нормальности это утверждение бессодержательно: как уже говорилось, мы можем дублировать элементы сигнатуры в произвольном количестве. Поэтому мы предполагаем, что все рассматриваемые интерпретации нормальны (равенство интерпретируется как тождественное совпадение).
Теорема 61 (Левенгейма-Сколема о повышении мощности). Пусть $$A$$ — бесконечная нормальная интерпретация некоторой сигнатуры $$\sigma$$ с равенством. Тогда существует нормальная интерпретация $$B\supset A$$ сколь угодно большой мощности, являющаяся элементарным расширением $$A$$.
(Это означает, согласно определению, напомним, что интерпретация предикатных и функциональных символов в $$B$$ продолжает их интерпретацию в $$A$$ и что формулы сигнатуры $$\sigma$$, параметрам которых приданы значения из $$A$$, одновременно истинны в $$A$$ и в $$B$$.)
Сформулируем утверждение теоремы в терминах теорий и моделей. Пусть $$A$$ — произвольная нормальная интерпретация сигнатуры $$\sigma$$. Рассмотрим сигнатуру $$\sigma_A$$, которая получается из $$\sigma$$ добавлением констант — по одной для каждого элемента множества $$A$$. Эта сигнатура имеет естественную нормальную интерпретацию с носителем $$A$$: значением каждой константы является соответствующий ей элемент. (Возможно, что в $$\sigma$$ изначально было достаточно констант и всякий элемент $$A$$ был значением некоторой константы. Тогда эта процедура лишняя, но и вреда от нее нет.)
Рассмотрим теорию $$\Th_A(A)$$, состоящую из формул сигнатуры $$\sigma_A$$, истинных в $$A$$ при указанной интерпретации. Всякое элементарное расширение $$B$$ интерпретации $$A$$ будет моделью теории $$\Th_A(A)$$. В самом деле, замкнутая формула $$\varphi(a_1,\dots,a_n)$$ сигнатуры $$\sigma_A$$ получается подстановкой констант $$a_1,\dots,a_n$$ вместо параметров из какой-то формулы $$\varphi(x_1,\dots,x_n)$$ сигнатуры $$\sigma$$. (Мы используем не вполне корректные обозначения, в частности, отождествляем элементы $$a_1,\dots,a_n$$ множества $$A$$ с константами для них.) Ее истинность в $$B$$ (или в $$A$$ ) равносильна истинности формулы $$\varphi(x_1,\dots,x_n)$$ при значениях параметров $$x_1\hm\mapsto a_1,\dots,x_n\hm\mapsto a_n$$ — формально говоря, следует воспользоваться леммой 2. Поэтому по определению элементарного расширения все формулы из $$\Th_A(A)$$ будут истинны и в $$B$$.
Верно и обратное: любая нормальная модель теории $$\Th_A(A)$$ естественно
определяет элементарное расширение интерпретации $$A$$. В самом
деле, пусть дана нормальная модель этой теории с носителем $$B$$.
Тогда каждый элемент множества $$A$$ (точнее, соответствующая этому элементу константа)
интерпретируется некоторым элементом множества $$B$$. Разным элементам
множества $$A$$ соответствуют разные элементы в $$B$$, так как формула $$a_1\ne
a_2$$, истинная в $$A$$, должна быть истинной и
в $$B$$. Таким образом, $$A$$ вкладывается в $$B$$ и можно отождествить его
с некоторым подмножеством множества $$B$$. Это
Таким образом, для доказательства теоремы Левенгейма-Сколема о повышении мощности осталось построить нормальную модель теории $$\Th_A(A)$$, имеющую сколь угодно большую мощность. Это можно сделать так: добавим множество новых констант $$c_i$$ и формулы $$c_i\ne c_j$$ (для всех $$i\hm\ne j$$ ) к теории $$\Th_A(A)$$. Полученная теория будет совместной по теореме компактности для нормальных моделей. (В самом деле, любая конечная часть ее имеет нормальную модель, поскольку содержит конечное число новых констант, и им можно придать различные значения в $$A$$.) Поэтому и вся теория имеет нормальную модель. Всем константам $$c_i$$ соответствуют в этой модели разные элементы (поскольку истинна формула $$c_i\hm\ne c_j$$ ), поэтому мощность этой модели может быть сколь угодно большой, если использовать достаточно много констант.
Этот же прием будет использован нами при построении нестандартной модели арифметики
Приведенное рассуждение дает оценку мощности снизу. Можно получить и в точности нужную мощность:
Теорема 62. Пусть $$A$$ — бесконечная нормальная интерпретация сигнатуры $$\sigma$$ (с равенством) и пусть $$\beta$$ — мощность, не меньшая мощностей сигнатуры $$\sigma$$ и интерпретации $$A$$. Тогда существует нормальное элементарное расширение $$B\hm\supset A$$ мощности $$\beta$$.
Мощность сигнатуры $$\sigma_A$$ есть максимум из мощностей $$\sigma$$ и $$A$$ ; после добавления новых констант в количестве $$\beta$$ штук получится сигнатура мощности $$\beta$$, и согласно теореме 48 найдется модель множества $$\Th_A(A)$$ мощности $$\beta$$. Преобразование ее в нормальную модель (факторизация) может лишь уменьшить мощность, но $$\beta$$ различных элементов у нас заведомо есть.
Аналогичный прием (добавление констант) позволяет легко доказать такое утверждение:
Теорема 63. Если теория (в произвольной сигнатуре с равенством) имеет сколь угодно большие конечные нормальные модели, то она имеет и бесконечную нормальную модель.
Добавим к теории бесконечное число новых констант и аксиомы о том, что все они различны. Любой конечный фрагмент расширенной теории имеет нормальную модель (возьмем достаточно большую конечную модель и проинтерпретируем в ней константы). По теорме компактности и вся расширенная теория имеет нормальную модель, которая и будет бесконечной нормальной моделью исходной теории.
Вообще можно задать себе такой естественный вопрос. Пусть есть некоторая теория (или даже просто одна формула). Каковы могут быть мощности ее нормальных моделей? Как мы видели, для теорий с конечной сигнатурой верно одно из двух: либо бесконечных моделей вовсе нет, либо есть бесконечные модели всех мощностей. Это гарантируют теоремы Левенгейма-Сколема об элементарной подмодели (теорема 42) и о повышении мощности (теорема 61).
Что можно сказать про мощности конечных моделей? Для каждой формулы рассмотрим множество всех возможных мощностей ее конечных моделей. Его иногда называют спектром формулы. Это множество может быть устроено довольно сложным образом: например, для формулы, выражающей аксиомы поля, спектр состоит из всех степеней простых чисел.
116. (а) Укажите формулу, спектр которой состоит из всех четных положительных чисел. (б) Укажите формулу, спектр которой состоит из всех нечетных чисел. (в) Укажите формулу, спектр которой состоит из всех составных чисел.
Любопытно, что проблема конечного спектра (приведенная в книге Кейслера и Чэна под номером 1 среди "старых проблем теории моделей"), неожиданно оказалась связана с центральной проблемой теории сложности вычислений — так называемой "проблемой перебора". (Проблема конечного спектра состоит в следующем: верно ли, что дополнение (до $$\mathbb{N}$$ ) к спектру любой формулы является спектром некоторой другой формулы?)
В качестве примера использования теоремы о повышении мощности докажем теорему Гильберта о нулях (теорема 40), не проводя элиминацию кванторов. Пусть система уравнений имеет решение в поле $$k'$$, являющемся расширением алгебраически замкнутого поля $$k$$. Покажем, что она имеет решение и в $$k$$. Построим элементарное расширение $$k''\hm\supset k$$ очень большой мощности. Теперь $$k'$$ можно вложить в $$k''$$ (это вложение строится по трансфинитной рекурсии: добавляя алгебраический элемент, мы пользуемся алгебраической замкнутостью $$k''$$, добавляя трансцендентный элемент, мы пользуемся большой мощностью $$k''$$ ). Значит, система имеет решение в $$k''$$. Поскольку $$k''$$ было элементарным расширением, то система имеет решение в $$k$$.
Другое любопытное применение теоремы о повышении мощности таково. Назовем линейно упорядоченное множество $$M$$ однородным, если для любых двух возрастающих последовательностей $$x_1\hm<x_2\hm<\ldots\hm<x_n$$ и $$y_1\hm<y_2\hm<\ldots\hm<y_n$$ найдется автоморфизм множества $$M$$, переводящий $$x_i$$ в $$y_i$$ (при всех $$i\hm=1,\ldots,n$$ ).
Теорема 64. Для всякой бесконечной мощности найдется однородное линейно упорядоченное множество такой мощности.
Множество рациональных чисел (и вообще любое счетное плотное линейно упорядоченное множество) однородно. В самом деле, соответствие между двумя наборами его элементов постепенно продолжается до автоморфизма (добавляем элементы поочередно с той или другой стороны). Другой способ убедиться в этом — вспомнить о том, что это рациональные числа, и взять кусочно-линейный автоморфизм.
Для каждого $$n$$ фиксируем способ продолжения автоморфизмов с $$n$$ -элементных подмножеств в виде функции $$f_n$$ с $$2n+1$$ аргументами: $$f(z,x_1,\dots,x_n,y_1,\dots,y_n)$$ означает элемент, в который переходит $$z$$ при автоморфизме, переводящем $$x_i$$ в $$y_i$$. Рассмотрим теперь $$\mathbb{Q}$$ как интерпретацию сигнатуры, включающей порядок и все $$f_i$$. По теореме о повышении мощности можно найти элементарно эквивалентную интерпретацию любой заданной мощности. Поскольку свойства функций $$f_n$$ выражаеются формулами, получится однородное линейно упорядоченное множество заданной мощности.
В этом разделе мы попытаемся систематизировать уже известные нам понятия и факты.
Говорят, что замкнутая формула $$\varphi$$ выводима в теории $$T$$ (является теоремой теории $$T$$ ),
если формула $$\varphi$$ получается из аксиом
Формула $$\varphi$$ выводима в теории $$T$$ тогда и
только тогда, когда в
Формула $$\varphi$$ семантически следует из $$T$$, если она истинна в любой
модели теории $$T$$ (обозначение: $$T\hm\vDash\varphi$$ ).
Семантическое следование равносильно выводимости
(теорема 51). Взяв в качестве $$\varphi$$
тождественно ложную формулу $$\perp$$ (скажем, отрицание
117. Покажите, что добавление к теории любой ее теоремы не меняет множества теорем.
Прежде чем переходить к примерам, сделаем два простых наблюдения.
Теорема 65 (критерий Лося-Воота). Непротиворечивая теория $$T$$ с равенством в конечной или счетной сигнатуре, не имеющая конечных моделей и категоричная в счетной мощности, полна.
Предположим, что ни одна из формул $$\varphi$$ и $$\lnot\varphi$$ не выводима в теории $$T$$. Тогда обе теории $$T\cup\{\lnot\varphi\}$$ и $$T\cup\{\varphi\}$$ непротиворечивы. По
теореме 47) они имеют счетные модели, которые остаются счетными после
факторизации (перехода к нормальным моделям), поскольку
теория $$T$$ не имеет конечных моделей. Эти счетные модели должны
быть изоморфными (в силу категоричности). С другой стороны, в
одной из них
Аналогично доказывается и общая форма критерия Лося-Воота:
Теорема 66. Непротиворечивая теория с равенством в конечной или счетной сигнатуре, не имеющая конечных моделей и категоричная в данной несчетной мощности $$\alpha$$, полна.
Пусть теория $$T$$ не полна и к ней можно присоединить без противоречия любую из формул $$\varphi$$ и $$\lnot\varphi$$. Рассмотрим счетные нормальные модели теорий $$T\hm\cup\{\varphi\}$$ и $$T\hm\cup\{\lnot\varphi\}$$. По теореме 62 увеличим их мощности до $$\alpha$$ и получим противоречие.
118. Условие конечности или счетности сигнатуры в этой теореме можно ослабить. Как это сделать?
Вот пример применения теоремы 66. Теория алгебраически замкнутых полей характеристики $$0$$ категорична в любой несчетной мощности. (Это можно доказать, используя базисы трансцендентности: такое поле имеет базис трансцендентности над полем алгебраических чисел, мощность которого равна мощности всего поля, а два поля с равномощными базисами трансцендентности изоморфны). Следовательно, эта теория полна.
Заметим, что это наблюдение согласовано со знаменитой (и трудной!) теоремой Морли; эта теорема утверждает, что теория с равенством, категоричная в одной несчетной мощности, категорична и во всех несчетных мощностях. (Подробно о теореме Морли можно прочесть, например, в учебнике Кейслера и Чэна [13])
Теорема 67. Конечно аксиоматизируемая полная теория в конечной сигнатуре разрешима.
Пусть дана произвольная формула $$\varphi$$. Будем перебирать все
выводы в
Это доказательство неконструктивно в том смысле, что не дает никакой оценки на время работы алгоритма. Отметим также, что не обязательно требовать конечной аксиоматизируемости теории; достаточно, чтобы она имела разрешимое или перечислимое множество аксиом (см. [5]).
Проиллюстрируем все эти понятия на нескольких (в основном уже обсуждавшихся нами) примерах.
Рассмотрим сигнатуру, содержащую
Рациональные числа образуют счетную модель этой теории, а действительные — несчетную. Как мы уже упоминали, эта теория категорична в счетной мощности, все ее счетные нормальные модели изоморфны. Отсюда по теореме 65 получаем, что она полна. Следовательно, в ней выводятся все истинные в $$\mathbb{Q}$$ (или в любой другой модели, в частности, в $$\mathbb{R}$$ ) формулы ее сигнатуры (в самом деле, из формул $$\varphi$$ и $$\lnot\varphi$$ ровно одна истинна и ровно одна выводима, и выводимая формула должна быть истинной). Наконец, по теореме 67 эта теория разрешима.
Другое доказательство тех же фактов дает элиминация кванторов
(теорема 30). Как мы отмечали в разделе "Элиминация кванторов", для каждой формулы $$\varphi$$ нашей сигнатуры существует бескванторная
формула $$\varphi'$$, эквивалентная $$\varphi$$ в любой
нормальной интерпретации теории плотных линейно упорядоченных множеств без
первого и последнего элементов. Поэтому эквивалентность $$\varphi\leftrightarrow\varphi'$$ (с
Сказанное можно интерпретировать и так: мы доказали конечную аксиоматизируемость теории $$\Th(\mathbb{Q},{=},{<})$$, предъявив список аксиом.
119. Покажите, что эта теория не является категоричной в мощности континуум.
Отсюда следует (по теореме Морли), что теория плотных линейно упорядоченных множеств без первого и последнего элемента не будет категоричной ни в какой несчетной мощности.
120. Не используя теоремы Морли, укажите примеры неизоморфных плотных линейно упорядоченных множеств заданной несчетной мощности.
121. Покажите, что элементарные теории $$\Th([0,1],{=},{<})$$ и $$\Th([0,+\infty),{=},{<})$$ конечно аксиоматизируемы, полны и разрешимы. Будут ли они категоричными в мощности континуум?
122. Рассмотрим теорию плотных линейно упорядоченных множеств (не добавляя аксиом про наименьший и наибольший элемент). Будет ли она категорична в какой-либо мощности? полна? разрешима?
В этом примере мы действуем в обратном порядке, начав с конкретной интерпретации (целые числа с равенством, функцией прибавления единицы и константой $$0$$ ) и построив явную систему аксиом. Для этого вспомним процедуру элиминации кванторов из раздела "Элиминация кванторов" (теорема 28). Какими свойствами должна обладать нормальная интерпретация языка, чтобы преобразования, использованные при элиминации кванторов, были эквивалентными? Помимо аксиом равенства, нам нужно, чтобы функция $$S$$ была биекцией и чтобы для любого $$x$$ все элементы$$\dots,S^{-1}(S^{-1}(x)), S^{-1}(x), x,S(x),S(S(x)),\dots$$ были различны. Другими словами, элиминация кванторов дает формулу, эквивалентную исходной во всех моделях такой теории:
Ограничиваясь замкнутыми формулами, мы (как и в предыдущем
примере) видим, что $$\Th(\mathbb{Z},{=},{S},0)$$ совпадает с
множеством всех формул, выводимых из перечисленных аксиом, так
что теория с этими аксиомами полна. Она разрешима (как любая
полная теория с
В отличие от предыдущего примера, эта теория не является категоричной в счетной мощности — например, $$\mathbb{Z}+\mathbb{Z}$$ является ее моделью, не изоморфной исходной.
123. Опишите все модели этой теории.
124. Покажите, что эта теория категорична в любой несчетной мощности.
Покажем в заключение, что эта теория не является конечно аксиоматизируемой. В самом деле, пусть имеется конечное множество $$F$$ теорем этой теории, из которой следуют все остальные теоремы. Каждая из теорем множества $$F$$ выводима из аксиом, и этот вывод использует конечное число аксиом. Это означает, что все остальные аксиомы (не используемые в выводе формул из $$F$$ ) вообще лишние. А это не так: в конечной модели, составленной из остатков по модулю $$N$$, верны все аксиомы, кроме $$S^{N}(x)\ne x,\,S^{2N}(x)\ne x,\dots$$, поэтому эти аксиомы не следуют из остальных.
125. Докажите, что использованное нами рассуждение носит общий характер: если теория бесконечна, но конечно аксиоматизируема, то некоторая ее конечная часть равносильна всей теории (имеет те же теоремы).
Что изменится, если мы добавим к сигнатуре, помимо прибавления
единицы, еще и
Можно обойтись и без элиминации кванторов, рассуждая иначе.
Рассмотрим теорию линейно упорядоченных множеств со
следующим и предыдущим элементом и опишем все ее модели. Именно,
мы покажем, что любая нормальная модель $$M$$ этой теории имеет вид $$\mathbb{Z}\times A$$, где $$A$$ — произвольное линейно
упорядоченное множество (порядок на парах таков: сначала
сравниваются $$A$$ -компоненты, а в случае равенства — $$\mathbb{Z}$$ -компоненты.) В самом деле, будем говорить, что
элементы $$x$$ и $$y$$ лежат "в одной галактике", если
между ними конечное число элементов. (Легко проверить, что это
действительно
Теперь с помощью игры Эренфойхта (см. раздел "Элементарная эквивалентность",
теорема 37) мы показываем, что все нормальные модели этой теории элементарно эквивалентны. Отсюда
заключаем, что теория полна (как в доказательстве
теоремы 65, где мы по существу использовали элементарную эквивалентность моделей, а не их
126. Покажите, что теория $$\text{Th}(\mathbb{Z},{=},{<},S,0)$$ не категорична ни в какой несчетной мощности.
127. Будет ли теория $$\text{Th}(\mathbb{Z},{=},{<})$$ конечно аксиоматизируемой? разрешимой? категоричной?
128. Будет ли теория $$\text{Th}(\mathbb{N},{=},{<})$$ конечно аксиоматизируемой? разрешимой? категоричной?
Эту теорию мы рассматривали в разделе "Элиминация кванторов". Мы ограничимся двумя константами $$0$$ и $$1$$, поскольку любую атомарную формулу можно привести к общему знаменателю и получить целые константы, которые можно выразить через $$0$$ и $$1$$.
Мы хотим указать явно набор аксиом этой теории, то есть множество формул, из которых выводятся все теоремы этой теории и только они. Как и в предыдущих примерах, это можно сделать, проанализировав процесс элиминации кванторов и выявив все использованные при этом свойства интерпретации. (Все рассматриваемые нами интерпретации предполагаются нормальными, а аксиомы равенства изначально включаются в строимую нами теорию.)
Прежде всего, нам важно, что по сложению мы имеем абелеву группу
(и $$0$$ является ее нулем). Это позволяет в равенствах переносить
члены с одной стороны в другую. Для операций с неравенствами нам
надо знать, что порядок является линейным и что он согласован со
сложением (то есть что из $$x\hm<y$$ следует $${x+z}\hm<{y+z}$$ ).
Кроме того, мы умножали равенства и неравенства на рациональные
числа. Чтобы это было законно, мы должны знать, что группа
является
Кроме этих аксиом (которых счетное число) мы при элиминации
ничего не использовали, так что для любой формулы $$\varphi$$ есть
бескванторная формула $$\varphi'$$, которая эквивалентна $$\varphi$$ в любой
129. Покажите, что эта теория не является конечно аксиоматизируемой. (Указание: делимость любого элемента группы на простое число $$p$$ не вытекает из делимости на все меньшие простые числа — рассмотрим рациональные числа, знаменатель которых взаимно прост с $$p$$.)
130. Покажите, что эта теория разрешима.
131. Покажите, что эта теория не является категоричной.
132. Покажите, что теория $$\text{Th}(\mathbb{Q},{=},{+},{0})$$ не является категоричной в счетной мощности, но категорична в любой несчетной мощности. (Указание: ее модели — векторные пространства над полем рациональных чисел.)
В разделе "Арифметика Пресбургера" мы занимались элиминацией кванторов в теории $$(\mathbb{Z},{=},{<},{+},{0},{1})$$, которая потребовала добавления бесконечного числа дополнительных предикатов (сравнимость по модулю $$N$$ для всех целых $$N>1$$ ).
Проанализировав это рассуждение, можно извлечь из него явную
Можно проверить, что все шаги элиминации кванторов сохраняют равносильность в такой ситуации. Проверим, например, что сравнения можно умножать на целое положительное число. Почему, скажем, $${a\equiv b \pmod 3}$$ равносильно $${a+a}\hm\equiv{b+b\pmod 6}$$? По определению первое означает, что $$a-b=u+u+u$$ для некоторого $$u$$, а второе — что $${(a-b)}\hm+{(a-b)}\hm=v\hm+v\hm+v\hm+v\hm+v\hm+v$$ для некоторого $$v$$, и достаточно сослаться на то, что в упорядоченной группе из $${x+x}\hm=0$$ следует $$x\hm=0$$ (поскольку из $$x\hm>0$$ следует $$x\hm+x\hm>x\hm>0$$ ). Наиболее сложный шаг — доказательство представительности набора. Здесь надо рассмотреть все случаи расположения произвольного $$y$$ относительно правых частей. В каждом из случаев мы заменяли $$y$$ на первый элемент из окрестности правых частей, встречающийся при движении шагами $$D$$. Эту процедуру можно понимать как деление расстояния (до ближайшей правой части) на $$D$$ с остатком; возможность этого гарантируется нашими аксиомами.
133. Покажите, что теория $$(\mathbb{Z},{=},{<},{+},{0},{1})$$ разрешима.
134. Покажите, что эта теория не категорична в счетной мощности
и опишите все ее счетные модели. (Указание: они имеют вид $$\mathbb{Z}\times A$$, где $$A$$ —
135. Покажите, что эта теория не конечно аксиоматизируема. (Указание: рассмотрите интерпретацию $$\mathbb{Z}\times A$$, когда в $$A$$ возможно деление на простые числа, меньшие некоторого $$p$$, но не на $$p$$.)
Теорема 34 устанавливает возможность элиминации кванторов в поле комплексных чисел. Как мы уже отмечали (теорема 38), это преобразование дает формулу, равносильную во всех алгебраически замкнутых полях характеристики $$0$$. Отсюда следует, как обычно, что теория алгебраически замкнутых полей характеристики $$0$$ полна. (Ее аксиомы таковы: аксиомы равенства, аксиомы поля, счетный набор утверждений о том, что любой многочлен степени $$n\hm>0$$ с ненулевым старшим коэффициентом имеет корень, а также счетный набор утверждений вида $$1\hm+1\hm+1+\ldots+1\ne 0$$.) Эта теория совпадает с элементарной теорией поля комплексных чисел.
Другое доказательство полноты этой теории можно получить с помощью критерия Лося-Воота (теорема 66) и утверждения следующей задачи.
136. Покажите, что теория алгебраически замкнутых полей характеристики $$0$$ не категорична в счетной мощности, но категорична в любой несчетной мощности. (Указание: алгебраически замкнутое поле имеет базис трансцендентности над $$\mathbb{Q}$$ ; если поле несчетно, то базис равномощен полю.)
137. Покажите, что теория алгебраически замкнутых полей данной характеристики $$p$$ полна.
138. Покажите, что если некоторая формула в сигнатуре $$({=},{+},{\times})$$ истинна в алгебраически замкнутых полях характеристики $$0$$, то она истинна и во всех алгебраически замкнуты
Более сложно сформулировать, какие свойства вещественных чисел реально используются при доказательстве теоремы Тарского-Зайденберга (раздел "Теоремы Тарского-Зайденберга"). Дело в том, что мы ссылались на разные факты из анализа (понятие производной, теорема Ролля, асимптотика многочленов). Однако на самом деле достаточно некоторых алгебраических свойств поля — как говорят, поле должно быть "вещественно замкнутым".
Поле называется упорядоченным, если на нем задан линейный порядок, причем он согласован со сложением ( $$x<y$$ влечет $$x+z<y+z$$ ) и умножением ( $$x,y>0$$ влечет $$xy>0$$ ).
139. Покажите, что любое упорядоченное поле имеет характеристику $$0$$ и что в любом упорядоченном поле сумма квадратов не может равняться $$-1$$.
Упорядоченное поле называется вещественно замкнутым, если любой многочлен, имеющий на концах отрезка разные знаки, имеет корень на этом отрезке. (Отметим в скобках, что существует несколько эквивалентных определений вещественно замкнутого поля, см. учебник ван дер Вардена [4] мы выбрали наиболее удобное для наших целей.)
Мы не можем записать определение вещественной замкнутости в виде формулы, поскольку степень многочлена может быть любой. Но можно написать много формул — по одной для каждой степени многочлена. Например, для многочленов степени $$2$$ получится формула $$\begin{multline*} (u<v)\ \land\ (a\ne 0)\ \land\ ((au^2+bu+c)(av^2+bv+c)<0) \to\\ \to\exists x\, ((u<x)\land (x<v)\land\ (ax^2+bx+c=0)). \end{multline*} $$
Теория, состоящая из аксиом упорядоченного поля (в том числе аксиом равенства) и этих дополнительных аксиом, называется теорией вещественно замкнутых полей. Покажем, что в любом вещественно замкнутом поле выполнены основные факты о многочленах и их производных. Прежде всего заметим, что в алгебре естественно определять производную многочлена не как предел, а чисто формально: $$(x^n)'=nx^{n-1}$$ (для любого положительного целого $$n$$ ), далее по линейности. Степень производной многочлена на единицу меньше степени самого многочлена. Выполнены основные правила дифференцирования (линейность, правило дифференцирования произведения, формула Тейлора).
Теперь отметим некоторые свойства многочленов, связанные с порядком. Пусть многочлен в какой-то точке равен нулю, а производная его в этой точке больше нуля. Тогда в некоторой окрестности этой точки он положителен справа и отрицателен слева. (В самом деле, можно применить формулу Тейлора и оценки, показывающие, что вблизи нуля знак определяется линейной частью.)
Справедливо и свойство сохранения знака: если в какой-то точке многочлен положителен, то и в достаточно близких точках он положителен. Слова "достаточно близких" понимаются в обычном смысле ( $$\exists \varepsilon > 0$$ ), только теперь $$\varepsilon$$ — не действительное число, а элемент поля.
Аналогичным образом можно сформулировать и доказать такое
утверждение: при всех достаточно больших значениях аргумента
знак многочлена определяется его
Более сложно доказывается, что что если производная многочлена $$P(x)$$ положительна на интервале $$(a,b)$$, то он неубывает на отрезке $$[a,b]$$. Пусть это не так. Добавив к многочлену константу, можно считать, что для каких-то точек $$c,d$$ этого отрезка имеют место неравенства $$c<d$$, $$P(c)\hm>0$$, $$P(d)\hm<0$$ и потому $$P$$ имеет корень на интервале $$(c,d)$$ (вещественная замкнутость).
Число корней многочлена (в любом поле) конечно, поэтому среди корней многочлена $$P(x)$$ на интервале $$(c,d)$$ есть наименьший корень $$\alpha$$. Слева от $$\alpha$$ многочлен $$P$$ должен быть положительным (поскольку корень первый), но одновременно вблизи $$\alpha$$ и отрицательным (так как $$P'(\alpha)\hm>0$$ по предположению).
Теперь легко понять, что многочлен с положительной производной на $$(a,b)$$ строго возрастает на $$[a,b]$$: если бы в двух точках он принимал одинаковые значения, то между ними он был бы константой (чего не может быть для непостоянного многочлена).
Следствие: многочлен, производная которого не имеет корней на $$(a,b)$$, либо строго возрастает, либо строго убывает на $$[a,b]$$. В самом деле, свойство вещественной замкнутости можно применить и к производной, следовательно она либо всюду положительна, либо всюду отрицательна. В частности, справедлива теорема Ролля (многочлен с равными значениями на концах отрезка имеет нуль производной).
После такой тренировки наши рассуждения про знаки многочленов диаграммы легко провести для произвольного поля. Легко понять также, что деление с остатком (точнее, операция модифицированного остатка) имеет смысл для любого поля, и что целые числа (которые были коэффициентами многочленов) содержатся в любом поле.
Итак, элиминация кванторов дает формулу, равносильную исходной в любом вещественно замкнутом поле. Отсюда, как обычно, следует, что теория вещественно замкнутых полей совпадает с элементарной теорией упорядоченного поля вещественных чисел и потому полна, а также разрешима, и что все вещественно замкнутые упорядоченные поля элементарно эквивалентны.
Пусть сигнатура $$\sigma$$ включает в себя двуместный предикат равенства (записываемый традиционно $$x=y$$ ). Интерпретация этой сигнатуры называется нормальной,если предикат равенства интерпретируется как тождественное совпадение элементов носителя.
Возникает естественный вопрос. Пусть имеется некоторая теория $$T$$ (множество замкнутых формул) в языке, сигнатура которого включает равенство. Мы знаем что теория имеет модель (интерпретацию, в которой все формулы из $$T$$ истинны) тогда и только тогда, когда она непротиворечива. В каком случае она имеет нормальную модель (нормальную интерпретацию, в которой все формулы из $$T$$ истинны)?
Чтобы ответить на этот вопрос, введем аксиомы равенства. Пусть $$\sigma$$ произвольная сигнатура. Аксиомами равенства
в сигнатуре $$\sigma$$ будут формулы$$\begin{align*}
\forall x\,(x=x),\\
\forall x\forall y \,((x=y)\to(y=x)),\\
\forall x\forall y\forall z\, (((x=y)\land (y=z))\to(x=z))
\end{align*}$$
(называемые аксиомами
Теорема 59 (полноты для нормальных моделей). Теория $$T$$ сигнатуры $$\sigma$$ с равенством имеет нормальную модель тогда и только тогда, когда она остается непротиворечивой при добавлении аксиом равенства.
Прежде всего заметим, что теоремы о корректности и полноте
(раздел "Полнота
В нормальной модели теории $$T$$ аксиомы равенства истинны, так что в одну сторону утверждение теоремы очевидно. Нам осталось показать, что если теория $$T$$ совместна с аксиомами равенства, то она имеет нормальную модель.
Возьмем произвольную интерпретацию, в которой
Аксиомы равенства позволяют корректно определить интерпретацию c
носителем $$M'$$. В самом деле, истинность аксиомы для
функционального символа $$f$$ (приведенной выше в качестве
примера) гарантирует, что класс $$[f(x,y)]$$ зависит лишь от
классов $$[x]$$ и $$[y]$$, но не от выбора $$x$$
и $$y$$ внутри класса. Аналогичным образом аксиомы для
Полученная интерпретация с носителем $$M'$$ по построению нормальна. Осталось убедиться, что в ней истинны те же самые формулы, что и в $$M$$ (в том числе все формулы теории $$T$$ ). Это почти очевидно с интуитивной точки зрения: $$M$$ отличается от $$M'$$ лишь тем, что каждый элемент представлен несколькими равноправными копиями, которые со всех точек зрения ведут себя одинаково.
Формально говоря, мы доказываем, что формула $$\varphi$$ истинна в интерпретации $$M$$ на оценке $$\pi$$ тогда и только тогда, когда $$\varphi$$ истинна в $$M'$$ на оценке $$\pi'$$, при которой значение любой переменной $$\xi$$ есть класс, содержащий значение переменной $$\xi$$ при оценке $$\pi$$. Это легко сделать индукцией по построению формулы $$\varphi$$.
111. Покажите, что из аксиом равенства для сигнатуры $$\sigma$$ выводится формула$$\varphi \land (x=y) \to \varphi(y/x),$$ если подстановка в правой части корректна. (Указание: это очевидно следует из теоремы о полноте, но можно провести и чисто синтаксическое рассуждение индукцией по построению формулы $$\varphi$$.)
112. Покажите, что если теория $$T$$ (не обязательно с равенством) имеет модель мощности $$\alpha$$, то она имеет и модель любой большей мощности. (Указание: элементы модели можно "клонировать" в произвольном количестве.)
Из теоремы о полноте для нормальных моделей легко следует аналог теоремы о компактности (теорема 50) для нормальных моделей.
Теорема 60 (компактности для нормальных моделей). Если всякое конечное подмножество теории $$T$$ в сигнатуре с равенством имеет нормальную модель, то и теория $$T$$ имеет нормальную модель.
Любое конечное подмножество теории $$T$$ остается непротиворечивым при добавлении аксиом равенства (поскольку имеет нормальную модель). Значит, и вся теория $$T$$ остается непротиворечивой при добавлении аксиом равенства (вывод противоречия использует конечное число формул) и потому имеет нормальную модель.
113. Применив теорему о компактности, докажите, что всякий частичный
порядок может быть продолжен до линейного. (Указание. Рассмотрим
114. Используя теорему о компактности, докажите, что для всякого поля $$k$$ сушествует его расширение $$k'$$, в котором всякий многочлен с коэффициентами из $$k$$ имеет корень. (Указание. Утверждение о существовании корня у многочлена с данными коэффициентами можно записать в виде формулы. Любое конечное множество таких формул совместно с аксиомами поля, так как можно по очереди присоединить корни соответствующих многочленов.)
115. Пусть $$\Gamma$$ — множество замкнутых формул в сигнатуре с равенством. Покажите, что замкнутая формула $$\varphi$$ этой сигнатуры истинна во всех нормальных моделях $$\Gamma$$ тогда и только тогда, когда она выводима из $$\Gamma$$ и аксиом равенства.
Утверждение последней задачи является аналогом
теоремы 51 для теорий с равенством.
Иногда вообще рассматривают только такие теории. При этом
равенство является обязательным элементом сигнатуры, аксиомы
равенства (их число зависит от сигнатуры) считаются частью
Теорема Левенгейма-Сколема позволяла уменьшать мощность интерпретации (она утверждала, что для любой бесконечной интерпретации конечной или счетной сигнатуры существует элементарно эквивалентная ей счетная подструктура). В этом разделе мы рассмотрим обратную задачу — расширение интерпретации до элементарно эквивалентной интерпретации большей мощности. Соответствующее утверждение также называют теоремой Левенгейма-Сколема.
Прежде всего отметим, что без требования нормальности это утверждение бессодержательно: как уже говорилось, мы можем дублировать элементы сигнатуры в произвольном количестве. Поэтому мы предполагаем, что все рассматриваемые интерпретации нормальны (равенство интерпретируется как тождественное совпадение).
Теорема 61 (Левенгейма-Сколема о повышении мощности). Пусть $$A$$ — бесконечная нормальная интерпретация некоторой сигнатуры $$\sigma$$ с равенством. Тогда существует нормальная интерпретация $$B\supset A$$ сколь угодно большой мощности, являющаяся элементарным расширением $$A$$.
(Это означает, согласно определению, напомним, что интерпретация предикатных и функциональных символов в $$B$$ продолжает их интерпретацию в $$A$$ и что формулы сигнатуры $$\sigma$$, параметрам которых приданы значения из $$A$$, одновременно истинны в $$A$$ и в $$B$$.)
Сформулируем утверждение теоремы в терминах теорий и моделей. Пусть $$A$$ — произвольная нормальная интерпретация сигнатуры $$\sigma$$. Рассмотрим сигнатуру $$\sigma_A$$, которая получается из $$\sigma$$ добавлением констант — по одной для каждого элемента множества $$A$$. Эта сигнатура имеет естественную нормальную интерпретацию с носителем $$A$$: значением каждой константы является соответствующий ей элемент. (Возможно, что в $$\sigma$$ изначально было достаточно констант и всякий элемент $$A$$ был значением некоторой константы. Тогда эта процедура лишняя, но и вреда от нее нет.)
Рассмотрим теорию $$\Th_A(A)$$, состоящую из формул сигнатуры $$\sigma_A$$, истинных в $$A$$ при указанной интерпретации. Всякое элементарное расширение $$B$$ интерпретации $$A$$ будет моделью теории $$\Th_A(A)$$. В самом деле, замкнутая формула $$\varphi(a_1,\dots,a_n)$$ сигнатуры $$\sigma_A$$ получается подстановкой констант $$a_1,\dots,a_n$$ вместо параметров из какой-то формулы $$\varphi(x_1,\dots,x_n)$$ сигнатуры $$\sigma$$. (Мы используем не вполне корректные обозначения, в частности, отождествляем элементы $$a_1,\dots,a_n$$ множества $$A$$ с константами для них.) Ее истинность в $$B$$ (или в $$A$$ ) равносильна истинности формулы $$\varphi(x_1,\dots,x_n)$$ при значениях параметров $$x_1\hm\mapsto a_1,\dots,x_n\hm\mapsto a_n$$ — формально говоря, следует воспользоваться леммой 2. Поэтому по определению элементарного расширения все формулы из $$\Th_A(A)$$ будут истинны и в $$B$$.
Верно и обратное: любая нормальная модель теории $$\Th_A(A)$$ естественно
определяет элементарное расширение интерпретации $$A$$. В самом
деле, пусть дана нормальная модель этой теории с носителем $$B$$.
Тогда каждый элемент множества $$A$$ (точнее, соответствующая этому элементу константа)
интерпретируется некоторым элементом множества $$B$$. Разным элементам
множества $$A$$ соответствуют разные элементы в $$B$$, так как формула $$a_1\ne
a_2$$, истинная в $$A$$, должна быть истинной и
в $$B$$. Таким образом, $$A$$ вкладывается в $$B$$ и можно отождествить его
с некоторым подмножеством множества $$B$$. Это
Таким образом, для доказательства теоремы Левенгейма-Сколема о повышении мощности осталось построить нормальную модель теории $$\Th_A(A)$$, имеющую сколь угодно большую мощность. Это можно сделать так: добавим множество новых констант $$c_i$$ и формулы $$c_i\ne c_j$$ (для всех $$i\hm\ne j$$ ) к теории $$\Th_A(A)$$. Полученная теория будет совместной по теореме компактности для нормальных моделей. (В самом деле, любая конечная часть ее имеет нормальную модель, поскольку содержит конечное число новых констант, и им можно придать различные значения в $$A$$.) Поэтому и вся теория имеет нормальную модель. Всем константам $$c_i$$ соответствуют в этой модели разные элементы (поскольку истинна формула $$c_i\hm\ne c_j$$ ), поэтому мощность этой модели может быть сколь угодно большой, если использовать достаточно много констант.
Этот же прием будет использован нами при построении нестандартной модели арифметики
Приведенное рассуждение дает оценку мощности снизу. Можно получить и в точности нужную мощность:
Теорема 62. Пусть $$A$$ — бесконечная нормальная интерпретация сигнатуры $$\sigma$$ (с равенством) и пусть $$\beta$$ — мощность, не меньшая мощностей сигнатуры $$\sigma$$ и интерпретации $$A$$. Тогда существует нормальное элементарное расширение $$B\hm\supset A$$ мощности $$\beta$$.
Мощность сигнатуры $$\sigma_A$$ есть максимум из мощностей $$\sigma$$ и $$A$$ ; после добавления новых констант в количестве $$\beta$$ штук получится сигнатура мощности $$\beta$$, и согласно теореме 48 найдется модель множества $$\Th_A(A)$$ мощности $$\beta$$. Преобразование ее в нормальную модель (факторизация) может лишь уменьшить мощность, но $$\beta$$ различных элементов у нас заведомо есть.
Аналогичный прием (добавление констант) позволяет легко доказать такое утверждение:
Теорема 63. Если теория (в произвольной сигнатуре с равенством) имеет сколь угодно большие конечные нормальные модели, то она имеет и бесконечную нормальную модель.
Добавим к теории бесконечное число новых констант и аксиомы о том, что все они различны. Любой конечный фрагмент расширенной теории имеет нормальную модель (возьмем достаточно большую конечную модель и проинтерпретируем в ней константы). По теорме компактности и вся расширенная теория имеет нормальную модель, которая и будет бесконечной нормальной моделью исходной теории.
Вообще можно задать себе такой естественный вопрос. Пусть есть некоторая теория (или даже просто одна формула). Каковы могут быть мощности ее нормальных моделей? Как мы видели, для теорий с конечной сигнатурой верно одно из двух: либо бесконечных моделей вовсе нет, либо есть бесконечные модели всех мощностей. Это гарантируют теоремы Левенгейма-Сколема об элементарной подмодели (теорема 42) и о повышении мощности (теорема 61).
Что можно сказать про мощности конечных моделей? Для каждой формулы рассмотрим множество всех возможных мощностей ее конечных моделей. Его иногда называют спектром формулы. Это множество может быть устроено довольно сложным образом: например, для формулы, выражающей аксиомы поля, спектр состоит из всех степеней простых чисел.
116. (а) Укажите формулу, спектр которой состоит из всех четных положительных чисел. (б) Укажите формулу, спектр которой состоит из всех нечетных чисел. (в) Укажите формулу, спектр которой состоит из всех составных чисел.
Любопытно, что проблема конечного спектра (приведенная в книге Кейслера и Чэна под номером 1 среди "старых проблем теории моделей"), неожиданно оказалась связана с центральной проблемой теории сложности вычислений — так называемой "проблемой перебора". (Проблема конечного спектра состоит в следующем: верно ли, что дополнение (до $$\mathbb{N}$$ ) к спектру любой формулы является спектром некоторой другой формулы?)
В качестве примера использования теоремы о повышении мощности докажем теорему Гильберта о нулях (теорема 40), не проводя элиминацию кванторов. Пусть система уравнений имеет решение в поле $$k'$$, являющемся расширением алгебраически замкнутого поля $$k$$. Покажем, что она имеет решение и в $$k$$. Построим элементарное расширение $$k''\hm\supset k$$ очень большой мощности. Теперь $$k'$$ можно вложить в $$k''$$ (это вложение строится по трансфинитной рекурсии: добавляя алгебраический элемент, мы пользуемся алгебраической замкнутостью $$k''$$, добавляя трансцендентный элемент, мы пользуемся большой мощностью $$k''$$ ). Значит, система имеет решение в $$k''$$. Поскольку $$k''$$ было элементарным расширением, то система имеет решение в $$k$$.
Другое любопытное применение теоремы о повышении мощности таково. Назовем линейно упорядоченное множество $$M$$ однородным, если для любых двух возрастающих последовательностей $$x_1\hm<x_2\hm<\ldots\hm<x_n$$ и $$y_1\hm<y_2\hm<\ldots\hm<y_n$$ найдется автоморфизм множества $$M$$, переводящий $$x_i$$ в $$y_i$$ (при всех $$i\hm=1,\ldots,n$$ ).
Теорема 64. Для всякой бесконечной мощности найдется однородное линейно упорядоченное множество такой мощности.
Множество рациональных чисел (и вообще любое счетное плотное линейно упорядоченное множество) однородно. В самом деле, соответствие между двумя наборами его элементов постепенно продолжается до автоморфизма (добавляем элементы поочередно с той или другой стороны). Другой способ убедиться в этом — вспомнить о том, что это рациональные числа, и взять кусочно-линейный автоморфизм.
Для каждого $$n$$ фиксируем способ продолжения автоморфизмов с $$n$$ -элементных подмножеств в виде функции $$f_n$$ с $$2n+1$$ аргументами: $$f(z,x_1,\dots,x_n,y_1,\dots,y_n)$$ означает элемент, в который переходит $$z$$ при автоморфизме, переводящем $$x_i$$ в $$y_i$$. Рассмотрим теперь $$\mathbb{Q}$$ как интерпретацию сигнатуры, включающей порядок и все $$f_i$$. По теореме о повышении мощности можно найти элементарно эквивалентную интерпретацию любой заданной мощности. Поскольку свойства функций $$f_n$$ выражаеются формулами, получится однородное линейно упорядоченное множество заданной мощности.
В этом разделе мы попытаемся систематизировать уже известные нам понятия и факты.
Говорят, что замкнутая формула $$\varphi$$ выводима в теории $$T$$ (является теоремой теории $$T$$ ),
если формула $$\varphi$$ получается из аксиом
Формула $$\varphi$$ выводима в теории $$T$$ тогда и
только тогда, когда в
Формула $$\varphi$$ семантически следует из $$T$$, если она истинна в любой
модели теории $$T$$ (обозначение: $$T\hm\vDash\varphi$$ ).
Семантическое следование равносильно выводимости
(теорема 51). Взяв в качестве $$\varphi$$
тождественно ложную формулу $$\perp$$ (скажем, отрицание
117. Покажите, что добавление к теории любой ее теоремы не меняет множества теорем.
Прежде чем переходить к примерам, сделаем два простых наблюдения.
Теорема 65 (критерий Лося-Воота). Непротиворечивая теория $$T$$ с равенством в конечной или счетной сигнатуре, не имеющая конечных моделей и категоричная в счетной мощности, полна.
Предположим, что ни одна из формул $$\varphi$$ и $$\lnot\varphi$$ не выводима в теории $$T$$. Тогда обе теории $$T\cup\{\lnot\varphi\}$$ и $$T\cup\{\varphi\}$$ непротиворечивы. По
теореме 47) они имеют счетные модели, которые остаются счетными после
факторизации (перехода к нормальным моделям), поскольку
теория $$T$$ не имеет конечных моделей. Эти счетные модели должны
быть изоморфными (в силу категоричности). С другой стороны, в
одной из них
Аналогично доказывается и общая форма критерия Лося-Воота:
Теорема 66. Непротиворечивая теория с равенством в конечной или счетной сигнатуре, не имеющая конечных моделей и категоричная в данной несчетной мощности $$\alpha$$, полна.
Пусть теория $$T$$ не полна и к ней можно присоединить без противоречия любую из формул $$\varphi$$ и $$\lnot\varphi$$. Рассмотрим счетные нормальные модели теорий $$T\hm\cup\{\varphi\}$$ и $$T\hm\cup\{\lnot\varphi\}$$. По теореме 62 увеличим их мощности до $$\alpha$$ и получим противоречие.
118. Условие конечности или счетности сигнатуры в этой теореме можно ослабить. Как это сделать?
Вот пример применения теоремы 66. Теория алгебраически замкнутых полей характеристики $$0$$ категорична в любой несчетной мощности. (Это можно доказать, используя базисы трансцендентности: такое поле имеет базис трансцендентности над полем алгебраических чисел, мощность которого равна мощности всего поля, а два поля с равномощными базисами трансцендентности изоморфны). Следовательно, эта теория полна.
Заметим, что это наблюдение согласовано со знаменитой (и трудной!) теоремой Морли; эта теорема утверждает, что теория с равенством, категоричная в одной несчетной мощности, категорична и во всех несчетных мощностях. (Подробно о теореме Морли можно прочесть, например, в учебнике Кейслера и Чэна [13])
Теорема 67. Конечно аксиоматизируемая полная теория в конечной сигнатуре разрешима.
Пусть дана произвольная формула $$\varphi$$. Будем перебирать все
выводы в
Это доказательство неконструктивно в том смысле, что не дает никакой оценки на время работы алгоритма. Отметим также, что не обязательно требовать конечной аксиоматизируемости теории; достаточно, чтобы она имела разрешимое или перечислимое множество аксиом (см. [5]).
Проиллюстрируем все эти понятия на нескольких (в основном уже обсуждавшихся нами) примерах.
Рассмотрим сигнатуру, содержащую
Рациональные числа образуют счетную модель этой теории, а действительные — несчетную. Как мы уже упоминали, эта теория категорична в счетной мощности, все ее счетные нормальные модели изоморфны. Отсюда по теореме 65 получаем, что она полна. Следовательно, в ней выводятся все истинные в $$\mathbb{Q}$$ (или в любой другой модели, в частности, в $$\mathbb{R}$$ ) формулы ее сигнатуры (в самом деле, из формул $$\varphi$$ и $$\lnot\varphi$$ ровно одна истинна и ровно одна выводима, и выводимая формула должна быть истинной). Наконец, по теореме 67 эта теория разрешима.
Другое доказательство тех же фактов дает элиминация кванторов
(теорема 30). Как мы отмечали в разделе "Элиминация кванторов", для каждой формулы $$\varphi$$ нашей сигнатуры существует бескванторная
формула $$\varphi'$$, эквивалентная $$\varphi$$ в любой
нормальной интерпретации теории плотных линейно упорядоченных множеств без
первого и последнего элементов. Поэтому эквивалентность $$\varphi\leftrightarrow\varphi'$$ (с
Сказанное можно интерпретировать и так: мы доказали конечную аксиоматизируемость теории $$\Th(\mathbb{Q},{=},{<})$$, предъявив список аксиом.
119. Покажите, что эта теория не является категоричной в мощности континуум.
Отсюда следует (по теореме Морли), что теория плотных линейно упорядоченных множеств без первого и последнего элемента не будет категоричной ни в какой несчетной мощности.
120. Не используя теоремы Морли, укажите примеры неизоморфных плотных линейно упорядоченных множеств заданной несчетной мощности.
121. Покажите, что элементарные теории $$\Th([0,1],{=},{<})$$ и $$\Th([0,+\infty),{=},{<})$$ конечно аксиоматизируемы, полны и разрешимы. Будут ли они категоричными в мощности континуум?
122. Рассмотрим теорию плотных линейно упорядоченных множеств (не добавляя аксиом про наименьший и наибольший элемент). Будет ли она категорична в какой-либо мощности? полна? разрешима?
В этом примере мы действуем в обратном порядке, начав с конкретной интерпретации (целые числа с равенством, функцией прибавления единицы и константой $$0$$ ) и построив явную систему аксиом. Для этого вспомним процедуру элиминации кванторов из раздела "Элиминация кванторов" (теорема 28). Какими свойствами должна обладать нормальная интерпретация языка, чтобы преобразования, использованные при элиминации кванторов, были эквивалентными? Помимо аксиом равенства, нам нужно, чтобы функция $$S$$ была биекцией и чтобы для любого $$x$$ все элементы$$\dots,S^{-1}(S^{-1}(x)), S^{-1}(x), x,S(x),S(S(x)),\dots$$ были различны. Другими словами, элиминация кванторов дает формулу, эквивалентную исходной во всех моделях такой теории:
Ограничиваясь замкнутыми формулами, мы (как и в предыдущем
примере) видим, что $$\Th(\mathbb{Z},{=},{S},0)$$ совпадает с
множеством всех формул, выводимых из перечисленных аксиом, так
что теория с этими аксиомами полна. Она разрешима (как любая
полная теория с
В отличие от предыдущего примера, эта теория не является категоричной в счетной мощности — например, $$\mathbb{Z}+\mathbb{Z}$$ является ее моделью, не изоморфной исходной.
123. Опишите все модели этой теории.
124. Покажите, что эта теория категорична в любой несчетной мощности.
Покажем в заключение, что эта теория не является конечно аксиоматизируемой. В самом деле, пусть имеется конечное множество $$F$$ теорем этой теории, из которой следуют все остальные теоремы. Каждая из теорем множества $$F$$ выводима из аксиом, и этот вывод использует конечное число аксиом. Это означает, что все остальные аксиомы (не используемые в выводе формул из $$F$$ ) вообще лишние. А это не так: в конечной модели, составленной из остатков по модулю $$N$$, верны все аксиомы, кроме $$S^{N}(x)\ne x,\,S^{2N}(x)\ne x,\dots$$, поэтому эти аксиомы не следуют из остальных.
125. Докажите, что использованное нами рассуждение носит общий характер: если теория бесконечна, но конечно аксиоматизируема, то некоторая ее конечная часть равносильна всей теории (имеет те же теоремы).
Что изменится, если мы добавим к сигнатуре, помимо прибавления
единицы, еще и
Можно обойтись и без элиминации кванторов, рассуждая иначе.
Рассмотрим теорию линейно упорядоченных множеств со
следующим и предыдущим элементом и опишем все ее модели. Именно,
мы покажем, что любая нормальная модель $$M$$ этой теории имеет вид $$\mathbb{Z}\times A$$, где $$A$$ — произвольное линейно
упорядоченное множество (порядок на парах таков: сначала
сравниваются $$A$$ -компоненты, а в случае равенства — $$\mathbb{Z}$$ -компоненты.) В самом деле, будем говорить, что
элементы $$x$$ и $$y$$ лежат "в одной галактике", если
между ними конечное число элементов. (Легко проверить, что это
действительно
Теперь с помощью игры Эренфойхта (см. раздел "Элементарная эквивалентность",
теорема 37) мы показываем, что все нормальные модели этой теории элементарно эквивалентны. Отсюда
заключаем, что теория полна (как в доказательстве
теоремы 65, где мы по существу использовали элементарную эквивалентность моделей, а не их
126. Покажите, что теория $$\text{Th}(\mathbb{Z},{=},{<},S,0)$$ не категорична ни в какой несчетной мощности.
127. Будет ли теория $$\text{Th}(\mathbb{Z},{=},{<})$$ конечно аксиоматизируемой? разрешимой? категоричной?
128. Будет ли теория $$\text{Th}(\mathbb{N},{=},{<})$$ конечно аксиоматизируемой? разрешимой? категоричной?
Эту теорию мы рассматривали в разделе "Элиминация кванторов". Мы ограничимся двумя константами $$0$$ и $$1$$, поскольку любую атомарную формулу можно привести к общему знаменателю и получить целые константы, которые можно выразить через $$0$$ и $$1$$.
Мы хотим указать явно набор аксиом этой теории, то есть множество формул, из которых выводятся все теоремы этой теории и только они. Как и в предыдущих примерах, это можно сделать, проанализировав процесс элиминации кванторов и выявив все использованные при этом свойства интерпретации. (Все рассматриваемые нами интерпретации предполагаются нормальными, а аксиомы равенства изначально включаются в строимую нами теорию.)
Прежде всего, нам важно, что по сложению мы имеем абелеву группу
(и $$0$$ является ее нулем). Это позволяет в равенствах переносить
члены с одной стороны в другую. Для операций с неравенствами нам
надо знать, что порядок является линейным и что он согласован со
сложением (то есть что из $$x\hm<y$$ следует $${x+z}\hm<{y+z}$$ ).
Кроме того, мы умножали равенства и неравенства на рациональные
числа. Чтобы это было законно, мы должны знать, что группа
является
Кроме этих аксиом (которых счетное число) мы при элиминации
ничего не использовали, так что для любой формулы $$\varphi$$ есть
бескванторная формула $$\varphi'$$, которая эквивалентна $$\varphi$$ в любой
129. Покажите, что эта теория не является конечно аксиоматизируемой. (Указание: делимость любого элемента группы на простое число $$p$$ не вытекает из делимости на все меньшие простые числа — рассмотрим рациональные числа, знаменатель которых взаимно прост с $$p$$.)
130. Покажите, что эта теория разрешима.
131. Покажите, что эта теория не является категоричной.
132. Покажите, что теория $$\text{Th}(\mathbb{Q},{=},{+},{0})$$ не является категоричной в счетной мощности, но категорична в любой несчетной мощности. (Указание: ее модели — векторные пространства над полем рациональных чисел.)
В разделе "Арифметика Пресбургера" мы занимались элиминацией кванторов в теории $$(\mathbb{Z},{=},{<},{+},{0},{1})$$, которая потребовала добавления бесконечного числа дополнительных предикатов (сравнимость по модулю $$N$$ для всех целых $$N>1$$ ).
Проанализировав это рассуждение, можно извлечь из него явную
Можно проверить, что все шаги элиминации кванторов сохраняют равносильность в такой ситуации. Проверим, например, что сравнения можно умножать на целое положительное число. Почему, скажем, $${a\equiv b \pmod 3}$$ равносильно $${a+a}\hm\equiv{b+b\pmod 6}$$? По определению первое означает, что $$a-b=u+u+u$$ для некоторого $$u$$, а второе — что $${(a-b)}\hm+{(a-b)}\hm=v\hm+v\hm+v\hm+v\hm+v\hm+v$$ для некоторого $$v$$, и достаточно сослаться на то, что в упорядоченной группе из $${x+x}\hm=0$$ следует $$x\hm=0$$ (поскольку из $$x\hm>0$$ следует $$x\hm+x\hm>x\hm>0$$ ). Наиболее сложный шаг — доказательство представительности набора. Здесь надо рассмотреть все случаи расположения произвольного $$y$$ относительно правых частей. В каждом из случаев мы заменяли $$y$$ на первый элемент из окрестности правых частей, встречающийся при движении шагами $$D$$. Эту процедуру можно понимать как деление расстояния (до ближайшей правой части) на $$D$$ с остатком; возможность этого гарантируется нашими аксиомами.
133. Покажите, что теория $$(\mathbb{Z},{=},{<},{+},{0},{1})$$ разрешима.
134. Покажите, что эта теория не категорична в счетной мощности
и опишите все ее счетные модели. (Указание: они имеют вид $$\mathbb{Z}\times A$$, где $$A$$ —
135. Покажите, что эта теория не конечно аксиоматизируема. (Указание: рассмотрите интерпретацию $$\mathbb{Z}\times A$$, когда в $$A$$ возможно деление на простые числа, меньшие некоторого $$p$$, но не на $$p$$.)
Теорема 34 устанавливает возможность элиминации кванторов в поле комплексных чисел. Как мы уже отмечали (теорема 38), это преобразование дает формулу, равносильную во всех алгебраически замкнутых полях характеристики $$0$$. Отсюда следует, как обычно, что теория алгебраически замкнутых полей характеристики $$0$$ полна. (Ее аксиомы таковы: аксиомы равенства, аксиомы поля, счетный набор утверждений о том, что любой многочлен степени $$n\hm>0$$ с ненулевым старшим коэффициентом имеет корень, а также счетный набор утверждений вида $$1\hm+1\hm+1+\ldots+1\ne 0$$.) Эта теория совпадает с элементарной теорией поля комплексных чисел.
Другое доказательство полноты этой теории можно получить с помощью критерия Лося-Воота (теорема 66) и утверждения следующей задачи.
136. Покажите, что теория алгебраически замкнутых полей характеристики $$0$$ не категорична в счетной мощности, но категорична в любой несчетной мощности. (Указание: алгебраически замкнутое поле имеет базис трансцендентности над $$\mathbb{Q}$$ ; если поле несчетно, то базис равномощен полю.)
137. Покажите, что теория алгебраически замкнутых полей данной характеристики $$p$$ полна.
138. Покажите, что если некоторая формула в сигнатуре $$({=},{+},{\times})$$ истинна в алгебраически замкнутых полях характеристики $$0$$, то она истинна и во всех алгебраически замкнуты
Более сложно сформулировать, какие свойства вещественных чисел реально используются при доказательстве теоремы Тарского-Зайденберга (раздел "Теоремы Тарского-Зайденберга"). Дело в том, что мы ссылались на разные факты из анализа (понятие производной, теорема Ролля, асимптотика многочленов). Однако на самом деле достаточно некоторых алгебраических свойств поля — как говорят, поле должно быть "вещественно замкнутым".
Поле называется упорядоченным, если на нем задан линейный порядок, причем он согласован со сложением ( $$x<y$$ влечет $$x+z<y+z$$ ) и умножением ( $$x,y>0$$ влечет $$xy>0$$ ).
139. Покажите, что любое упорядоченное поле имеет характеристику $$0$$ и что в любом упорядоченном поле сумма квадратов не может равняться $$-1$$.
Упорядоченное поле называется вещественно замкнутым, если любой многочлен, имеющий на концах отрезка разные знаки, имеет корень на этом отрезке. (Отметим в скобках, что существует несколько эквивалентных определений вещественно замкнутого поля, см. учебник ван дер Вардена [4] мы выбрали наиболее удобное для наших целей.)
Мы не можем записать определение вещественной замкнутости в виде формулы, поскольку степень многочлена может быть любой. Но можно написать много формул — по одной для каждой степени многочлена. Например, для многочленов степени $$2$$ получится формула $$\begin{multline*} (u<v)\ \land\ (a\ne 0)\ \land\ ((au^2+bu+c)(av^2+bv+c)<0) \to\\ \to\exists x\, ((u<x)\land (x<v)\land\ (ax^2+bx+c=0)). \end{multline*} $$
Теория, состоящая из аксиом упорядоченного поля (в том числе аксиом равенства) и этих дополнительных аксиом, называется теорией вещественно замкнутых полей. Покажем, что в любом вещественно замкнутом поле выполнены основные факты о многочленах и их производных. Прежде всего заметим, что в алгебре естественно определять производную многочлена не как предел, а чисто формально: $$(x^n)'=nx^{n-1}$$ (для любого положительного целого $$n$$ ), далее по линейности. Степень производной многочлена на единицу меньше степени самого многочлена. Выполнены основные правила дифференцирования (линейность, правило дифференцирования произведения, формула Тейлора).
Теперь отметим некоторые свойства многочленов, связанные с порядком. Пусть многочлен в какой-то точке равен нулю, а производная его в этой точке больше нуля. Тогда в некоторой окрестности этой точки он положителен справа и отрицателен слева. (В самом деле, можно применить формулу Тейлора и оценки, показывающие, что вблизи нуля знак определяется линейной частью.)
Справедливо и свойство сохранения знака: если в какой-то точке многочлен положителен, то и в достаточно близких точках он положителен. Слова "достаточно близких" понимаются в обычном смысле ( $$\exists \varepsilon > 0$$ ), только теперь $$\varepsilon$$ — не действительное число, а элемент поля.
Аналогичным образом можно сформулировать и доказать такое
утверждение: при всех достаточно больших значениях аргумента
знак многочлена определяется его
Более сложно доказывается, что что если производная многочлена $$P(x)$$ положительна на интервале $$(a,b)$$, то он неубывает на отрезке $$[a,b]$$. Пусть это не так. Добавив к многочлену константу, можно считать, что для каких-то точек $$c,d$$ этого отрезка имеют место неравенства $$c<d$$, $$P(c)\hm>0$$, $$P(d)\hm<0$$ и потому $$P$$ имеет корень на интервале $$(c,d)$$ (вещественная замкнутость).
Число корней многочлена (в любом поле) конечно, поэтому среди корней многочлена $$P(x)$$ на интервале $$(c,d)$$ есть наименьший корень $$\alpha$$. Слева от $$\alpha$$ многочлен $$P$$ должен быть положительным (поскольку корень первый), но одновременно вблизи $$\alpha$$ и отрицательным (так как $$P'(\alpha)\hm>0$$ по предположению).
Теперь легко понять, что многочлен с положительной производной на $$(a,b)$$ строго возрастает на $$[a,b]$$: если бы в двух точках он принимал одинаковые значения, то между ними он был бы константой (чего не может быть для непостоянного многочлена).
Следствие: многочлен, производная которого не имеет корней на $$(a,b)$$, либо строго возрастает, либо строго убывает на $$[a,b]$$. В самом деле, свойство вещественной замкнутости можно применить и к производной, следовательно она либо всюду положительна, либо всюду отрицательна. В частности, справедлива теорема Ролля (многочлен с равными значениями на концах отрезка имеет нуль производной).
После такой тренировки наши рассуждения про знаки многочленов диаграммы легко провести для произвольного поля. Легко понять также, что деление с остатком (точнее, операция модифицированного остатка) имеет смысл для любого поля, и что целые числа (которые были коэффициентами многочленов) содержатся в любом поле.
Итак, элиминация кванторов дает формулу, равносильную исходной в любом вещественно замкнутом поле. Отсюда, как обычно, следует, что теория вещественно замкнутых полей совпадает с элементарной теорией упорядоченного поля вещественных чисел и потому полна, а также разрешима, и что все вещественно замкнутые упорядоченные поля элементарно эквивалентны.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.