Элементарная эквивалентность
Пока что мы в основном использовали технику элиминации кванторов для какой-то одной интерпретации (формула заменялась на бескванторную, которая эквивалентна исходной в данной интерпретации). Однако, этот метод позволяет сравнивать различные интерпретации. Мы приведем несколько примеров такого рода.
Начнем с определения. Пусть фиксирована некоторая сигнатура . Две интерпретации этой сигнатуры называются элементарно эквивалентными, если в них истинны одни и те же замкнутые формулы этой сигнатуры.
Легко доказать, что изоморфные интерпретации будут элементарно эквивалентны — надо только дать формальное определение изоморфизма для двух интерпретаций данной сигнатуры.
Пусть и — две интерпретации сигнатуры . Биекция (взаимно однозначное отображение) называется изоморфизмом этих интерпретаций, если она сохраняет все функции и предикаты сигнатуры. Это означает, что если и — два -местных предиката в и , соответствующих одному предикатному символу сигнатуры, то
для всех . Аналогичное условие для функций: если -местные функции и соответствуют одному функциональному символу, то
для всех .
Две интерпретации называются изоморфными, если между ними существует изоморфизм.
Легко понять, что это определение обобщает обычные определения изоморфизма для групп, колец, упорядоченных множеств и т. д.
73. Докажите, что тождественное отображение есть изоморфизм. Докажите, что отображение, обратное изоморфизму, есть изоморфизм. Докажите, что композиция двух изоморфизмов есть изоморфизм. (Отсюда следует, что отношение изоморфности есть отношение эквивалентности на интерпретациях данной сигнатуры.)
Теперь можно сформулировать и доказать обещанное утверждение:
Теорема 35. Изоморфные интерпретации элементарно эквивалентны.
Естественно доказывать это утверждение по индукции. Для этого его надо обобщить на произвольные формулы (не только замкнутые). Вот это обобщение: пусть — изоморфизм, а — произвольная формула нашей сигнатуры. Тогда она истинна в при оценке тогда и только тогда, когда она истинна в при оценке .
Обычно истинность формулы в интерпретации
обозначают как . Если формула имеет параметры , ее часто обозначают ; при этом запись (где ) означает, что формула истинна при оценке, которая ставит в соответствие параметру значение . После всех этих приготовлений доказываемое по индукции утверждение можно записать так:
для любой формулы и для любых элементов .
После такого обобщения доказательство по индукции становится очевидным.
74. В каком месте индуктивного рассуждения существенно, что — взаимно однозначное соответствие? (Ответ: сюръективность используется, когда мы рассматриваем формулу, начинающуюся с квантора существования, и из ее истинности в выводим истинность в . Инъективность не используется, но она автоматически следует из определения изоморфизма, если сигнатура содержит равенство и интерпретации нормальны, то есть равенство интерпретируется как совпадение элементов.)
75. Рассуждение, использованное при доказательстве теоремы 35, нам по существу уже встречалось. Где?
Изоморфные интерпретации — это по существу одна и та же интерпретация, только ее элементы названы по-разному. Интересны скорее примеры, когда интерпретации не изоморфны, но тем не менее элементарно эквивалентны. Один такой пример мы уже коротко обсуждали раньше, сформулируем его более подробно.
Теорема 36. Естественные интерпретации сигнатуры в множестве рациональных и действительных чисел элементарно эквивалентны.
Для начала заметим, что эти интерпретации не изоморфны (поскольку мощности различны). Однако формулы этой сигнатуры допускают, как мы видели , элиминацию кванторов.При этом получающаяся формула будет эквивалентна исходной в обеих интерпретациях. Начав с замкнутой формулы, мы получим бескванторную формулу без переменных (или с фиктивными переменными, от значений которых ничего не зависит, тогда вместо них можно подставить, скажем, нули). Эта формула будет содержать только рациональные константы и потому будет одинаково истинной в и в .
Заметим, что при уменьшении сигнатуры элементарная эквивалентность сохраняется (по очевидным причинам), так что из теоремы 36 очевидно следует, что и
элементарно эквивалентны как упорядоченные множества (этот факт мы отмечали).
В этом примере элементарно эквивалентные, но не изоморфные структуры имеют различную мощность. В следующем примере это уже не так.
Теорема 37. Упорядоченные множества и (второе состоит из двух копий множества , причем все элементы первой копии считаются меньшими всех элементов второй копии) элементарно эквивалентны как интерпретации сигнатуры .
Здесь также можно применить элиминацию кванторов, только надо добавить одноместные функции взятия последующего и предыдущего элементов. После этого надо заметить, что стандартная процедура элиминации кванторов (см. доказательство теоремы 29) состоит из преобразований, сохраняющих эквивалентность в обеих интерпретациях.
76. Можно ли построить счетную интерпретацию сигнатуры , в которой равенство интерпретируется как совпадение элементов (такие интерпретации называют нормальными), элементарно эквивалентную множеству , но не изоморфную ему? Тот же вопрос для множества неотрицательных рациональных чисел. Почему существенна нормальность интерпретации?
77. Существует ли упорядоченное множество, элементарно эквивалентное упорядоченному множеству , но имеющее большую мощность?
78. Существуют ли два несчетных неизоморфных элементарно эквивалентных упорядоченных множества одинаковой мощности?
79. Будут ли упорядоченные множества
и
(пары целых чисел; сравниваются сначала вторые компоненты пар, а при их равенстве — первые) изоморфны? элементарно эквивалентны?
80. Будет ли упорядоченное множество элементарно эквивалентно ? Будет ли элементарно эквивалентно ?
Рассуждение, использованное при доказательстве теоремы Тарского-Зайденберга, также можно приспособить для доказательства элементарной эквивалентности. Сейчас мы рассмотрим более простой случай алгебраически замкнутых полей, соответствующий элиминации кванторов в ; к вещественному случаю мы вернемся.
Поле называется алгебраически замкнутым, если всякий многочлен, отличный от константы, имеет в нем хотя бы один корень. (Отсюда легко следует, что любой многочлен разлагается на линейные множители.) Характеристикой поля называют минимальное число слагаемых в сумме вида , при котором она обращается в нуль. Если никакая сумма такого вида не равна нулю, то поле называют полем характеристики .
В алгебраически замкнутых полях характеристики
справедливы все обычные свойства многочленов с комплексными коэффициентами. В частности, корень является кратным тогда и только тогда, когда он будет корнем производной, сумма корней с учетом кратности равна степени многочлена и т. д. Это позволяет заметить, что все преобразования, которые выполнялись при элиминации кванторов, являются эквивалентными в произвольных алгебраически замкнутых полях характеристики . Тем самым мы получаем такую теорему:
Теорема 38 (о полноте теории алгебраически замкнутых полей характеристики нуль) Любые два алгебраически замкнутых поля характеристики
элементарно эквивалентны.
(Название этой теоремы станет понятным, когда мы будем говорить о полных теориях.)
81. Покажите, что любые два алгебраически замкнутых поля одной и той же конечной характеристики элементарно эквивалентны.
Теорему 38 можно несколько усилить. Для этого нам понадобится понятие "элементарного расширения".
Пусть фиксирована сигнатура и две интерпретации этой сигнатуры с носителями и . Пусть при этом и интерпретации предикатных и функциональных символов в и согласованы, то есть на аргументах из символы интерпретируются одинаково. (Заметим, что отсюда следует замкнутость относительно сигнатурных операций.) В этом случае иногда называют подструктурой в , а — расширением .
Например, если мы рассматриваем группы как интерпретации сигнатуры , то подструктуры — это подгруппы.
82. Почему здесь важно, что операция обращения включена в сигнатуру?
Интерпретацию называют элементарным расширением ее подструктуры , если выполнено такое свойство: для всякой (не обязательно замкнутой формулы) и для всякой оценки со значениями в формула истинна в на этой оценке тогда и только тогда, когда она истинна в на той же оценке.
В частности, если формула замкнута (не содержит параметров), то ее истинность не зависит от оценки и мы получаем, что и элементарно эквивалентны.
83. Пусть сигнатура содержит константы для всех элементов интерпретации , которая является подструктурой интерпретации . Покажите, что если интерпретации
и элементарно эквивалентны, то является элементарным расширением .
Нам понадобится такой пример: пусть имеется поле и его расширение . Мы будем рассматривать поля
и как две интерпретации сигнатуры . Пусть имеется некоторая система полиномиальных уравнений с несколькими переменными с коэффициентами из . Тогда утверждение о том, что она имеет решение, записывается в виде формулы (содержащей кванторы существования по переменным и конъюнкцию уравнений; коэффициенты многочленов являются параметрами этой формулы). Поэтому если является элементарным расширением , то всякая система уравнений с коэффициентами в , имеющая решение в , имеет решение и в .
Теорема 39. Пусть — подполе поля , причем оба они алгебраически замкнуты и имеют характеристику . Тогда
(как интерпретация указанной сигнатуры) является элементарным расширением интерпретации .
В самом деле, элиминация кванторов преобразует любую формулу (с параметрами или без) в эквивалентную ей бескванторную, причем эквивалентность имеет место в обоих полях. А для бескванторной формулы ее истинность при оценке со значениями в никак не может зависеть от того, внутри какого поля эта истинность вычисляется.
Эту теорему называют теоремой о модельной полноте теории алгебраически замкнутых полей характеристики нуль. Из нее с учетом замечания перед ее формулировкой вытекает такой хорошо известный алгебраистам факт:
Теорема 40 (Гильберта о нулях). Всякая система полиномиальных уравнений с коэффициентами в алгебраически замкнутом поле характеристики нуль, имеющая решение в некотором расширении этого поля, имеет решение и в самом поле.
В самом деле, расширение можно еще расширить до алгебраически замкнутого (при этом решение не пропадет), а затем воспользоваться теоремой 39.
84. Другой вариант теоремы Гильберта о нулях формулируется так: пусть дана система уравнений
где все — многочлены с комплексными коэффициентами, причем эта система не имеет решения в . Тогда можно найти такие многочлены , что
тождественно равно единице.
Выведите это утверждение из доказанного нами варианта теоремы Гильберта о нулях. (Указание: рассмотрим в кольце
идеал, порожденный многочленами ; если он содержит единицу, то все доказано, если нет, то расширим его до максимального идеала ; тогда факторкольцо
будет полем, расширяющим , и в этом поле классы многочленов составляют решение нашей системы.)
