Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 26
Текст из файла (страница 26)
Упорядоченные множества Z и Z + Z (второе состоит из двух копий множества Z, причём все элементы первой копиисчитаются меньшими всех элементов второй копии) элементарно эквивалентны как интерпретации сигнатуры (=, <). Здесь также можно применить элиминацию кванторов, тольконадо добавить одноместные функции взятия последующего и предыдущего элементов.
После этого надо заметить, что стандартная процедура элиминации кванторов (см. доказательство теоремы 29) состоит из преобразований, сохраняющих эквивалентность в обеих интерпретациях. 76. Можно ли построить счётную интерпретацию сигнатуры (=, <), в114Языки первого порядка[гл. 3]которой равенство интерпретируется как совпадение элементов (такие интерпретации называют нормальными), элементарно эквивалентную множеству Q, но не изоморфную ему? Тот же вопрос для множества неотрицательных рациональных чисел. Почему существенна нормальность интерпретации?77.
Существует ли упорядоченное множество, элементарно эквивалентное упорядоченному множеству R, но имеющее бо́льшую мощность?78. Существуют ли два несчётных неизоморфных элементарно эквивалентных упорядоченных множества одинаковой мощности?79. Будут ли упорядоченные множества Z и Z × Z (пары целых чисел; сравниваются сначала вторые компоненты пар, а при их равенстве —первые) изоморфны? элементарно эквивалентны?80. Будет ли упорядоченное множество N + N элементарно эквивалентно N? Будет ли N + Z элементарно эквивалентно N?Рассуждение, использованное при доказательстве теоремы Тарского – Зайденберга, также можно приспособить для доказательстваэлементарной эквивалентности. Сейчас мы рассмотрим более простой случай алгебраически замкнутых полей, соответствующий элиминации кванторов в C; к вещественному случаю мы вернёмся нижена с.
183.Поле называется алгебраически замкнутым, если всякий многочлен, отличный от константы, имеет в нём хотя бы один корень. (Отсюда легко следует, что любой многочлен разлагается на линейныемножители.) Характеристикой поля называют минимальное числослагаемых в сумме вида 1 + 1 + . . . + 1, при котором она обращается в нуль. Если никакая сумма такого вида не равна нулю, то поленазывают полем характеристики 0.В алгебраически замкнутых полях характеристики 0 справедливы все обычные свойства многочленов с комплексными коэффициентами. В частности, корень является кратным тогда и только тогда,когда он будет корнем производной, сумма корней с учётом кратности равна степени многочлена и т.
д. Это позволяет заметить, что всепреобразования, которые выполнялись при элиминации кванторов,являются эквивалентными в произвольных алгебраически замкнутых полях характеристики 0. Тем самым получаем такую теорему:Теорема 38 (о полноте теории алгебраически замкнутых полей характеристики нуль). Любые два алгебраически замкнутых поля характеристики 0 элементарно эквивалентны.(Название этой теоремы станет понятным, когда мы будем говорить о полных теориях.)[п. 9]Элементарная эквивалентность11581. Покажите, что любые два алгебраически замкнутых поля одной итой же конечной характеристики элементарно эквивалентны.Теорему 38 можно несколько усилить. Для этого нам понадобитсяпонятие «элементарного расширения».Пусть фиксирована сигнатура σ и две интерпретации этой сигнатуры с носителями M1 и M2 . Пусть при этом M1 ⊂ M2 и интерпретации предикатных и функциональных символов в M1 и M2 согласованы, то есть на аргументах из M1 символы интерпретируютсяодинаково.
(Заметим, что отсюда следует замкнутость M1 относительно сигнатурных операций.) В этом случае M1 иногда называютподструктурой в M2 , а M2 — расширением M1 .Например, если мы рассматриваем группы как интерпретациисигнатуры (=, ×, 1, обращение), то подструктуры — это подгруппы.82. Почему здесь важно, что операция обращения входит в сигнатуру?Интерпретацию M2 называется элементарным расширением еёподструктуры M1 , если выполнено такое свойство: для всякой (необязательно замкнутой формулы) F и для всякой оценки π со значениями в M1 формула F истинна в M1 на этой оценке тогда и толькотогда, когда она истинна в M2 на той же оценке.В частности, если формула замкнута (не содержит параметров),то её истинность не зависит от оценки и мы получаем, что M1 и M2элементарно эквивалентны.83.
Пусть сигнатура содержит константы для всех элементов интерпретации M1 , которая является подструктурой интерпретации M2 . Покажите, что если интерпретации M1 и M2 элементарно эквивалентны, то M2является элементарным расширением M1 .Нам понадобится такой пример: пусть имеется поле k1 и его расширение k2 . Мы будем рассматривать поля k1 и k2 как две интерпретации сигнатуры (=, +, ×, 0, 1). Пусть имеется некоторая системаполиномиальных уравнений с несколькими переменными с коэффициентами из k1 . Тогда утверждение о том, что она имеет решение,записывается в виде формулы (содержащей кванторы существования по переменным и конъюнкцию уравнений; коэффициенты многочленов являются параметрами этой формулы).
Поэтому если k2является элементарным расширением k1 , то всякая система уравнений с коэффициентами в k1 , имеющая решение в k2 , имеет решениеи в k1 .Теорема 39. Пусть k1 — подполе поля k2 , причём оба они алгебраически замкнуты и имеют характеристику 0. Тогда k2 (как интерпретация указанной сигнатуры) является элементарным расширением116Языки первого порядка[гл. 3]интерпретации k1 . В самом деле, элиминация кванторов преобразует любую формулу (с параметрами или без) в эквивалентную ей бескванторную,причём эквивалентность имеет место в обоих полях. А для бескванторной формулы её истинность при оценке со значениями в k1 никакне может зависеть от того, внутри какого поля эта истинность вычисляется.
Эту теорему называют теоремой о модельной полноте теории алгебраически замкнутых полей характеристики нуль. Из неё с учётомзамечания перед её формулировкой вытекает такой хорошо известный алгебраистам факт:Теорема 40 (Гильберта о нулях). Всякая система полиномиальных уравнений с коэффициентами в алгебраически замкнутом полехарактеристики нуль, имеющая решение в некотором расширенииэтого поля, имеет решение и в самом поле.
В самом деле, расширение можно ещё расширить до алгебраически замкнутого (при этом решение не пропадёт), а затем воспользоваться теоремой 39. 84. Другой вариант теоремы Гильберта о нулях формулируется так:пусть дана система уравнений8>< P1 (x1 , . . . , xn ) = 0,..................>:Pk (x1 , . . . , xn ) = 0,где все Pi — многочлены с комплексными коэффициентами, причём этасистема не имеет решения в C.
Тогда можно найти такие многочленыQi (x1 , . . . , xn ), чтоP1 (x1 , . . . , xn )Q1 (x1 , . . . , xn ) + . . . + Pk (x1 , . . . , xn )Qk (x1 , . . . , xn )тождественно равно единице.Выведите это утверждение из доказанного нами варианта теоремыГильберта о нулях. (Указание: рассмотрим в кольце C[x1 , . . . , xn ] идеал,порождённый многочленами P1 , . . . , Pk ; если он содержит единицу, то всёдоказано, если нет, то расширим его до максимального идеала I; тогдафакторкольцо C[x1 , .
. . , xn ]/I будет полем, расширяющим C, и в этом поле классы многочленов x1 , . . . , xn составляют решение нашей системы.)3.10. Игра ЭренфойхтаВернёмся от алгебры к логике и сформулируем общий критерийэлементарной эквивалентности двух интерпретаций некоторой сиг-[п. 10]Игра Эренфойхта117натуры. Будем считать, что наша сигнатура содержит только предикатные символы. (Это ограничение не очень существенно, так какфункцию f (x1 , . . .
, xn ) можно заменить предикатом f (x1 , . . . , xn ) == y, имеющим на один аргумент больше.) Кроме того, будем считать,что сигнатура конечна (в некоторый момент наших рассуждений этобудет существенно).Критерий будет сформулирован в терминах некоторой игры, называемой игрой Эренфойхта. В ней участвуют два игрока, называемые Новатором (Н) и Консерватором (К).
Игра определяется выбранной парой интерпретаций; как мы докажем, интерпретации элементарно эквивалентны тогда и только тогда, когда К имеет выигрышную стратегию в этой игре.В начале игры Новатор объявляет натуральное число k. Далееони ходят по очереди, начиная с Н; каждый из игроков делает kходов, после чего определяется победитель.На i-м ходу Н выбирает элемент в одной из интерпретаций (влюбой из двух, причём выбор может зависеть от номера хода) и помечает его числом i.
В ответ К выбирает некоторый элемент из другой интерпретации и также помечает его числом i. После k ходовигра заканчивается. При этом в каждой интерпретации k элементов оказываются помеченными числами от 1 до k (мы не учитываем, кто именно из игроков их пометил). Обозначим эти элементыa1 , a2 , . . . , ak (для первой интерпретации; элемент ai имеет пометку i)и b1 , b2 , . . . , bk (для второй). Элементы ai и bi (с одним и тем же i)будем называть соответствующими друг другу. Посмотрим, найдётся ли предикат сигнатуры, который различает помеченные элементы первой и второй интерпретации (то есть истинен на некоторомнаборе помеченных элементов в одной интерпретации, но ложен насоответствующих элементах другой).
Если такой предикат найдётся,то выигрывает Новатор, в противном случае — Консерватор.Прежде чем доказывать, что эта игра даёт критерий элементарной эквивалентности, рассмотрим несколько простых примеров.• Среди элементов a1 , . . . , ak и b1 , . . . , bk могут быть одинаковые.Если в нашей сигнатуре есть предикат равенства и в обеих интерпретациях он интерпретируется как совпадение элементов,то Консерватор обязан повторять ходы, если их повторил Новатор (скажем, если ai = aj , а bi 6= bj , то Новатор выигрывает,поскольку предикат равенства истинен в одной интерпретации,но ложен на соответствующих элементах другой).118Языки первого порядка[гл.
3]• Если интерпретации изоморфны, то у Консерватора есть очевидный способ выиграть: изоморфизм заранее группирует всеэлементы в пары соответствующих. (Это согласуется с тем, чтоизоморфные интерпретации элементарно эквивалентны.)• Рассмотрим сигнатуру упорядоченных множеств (предикаты =и <) и её естественные интерпретации в N и Z. Они не являются элементарно эквивалентными, поскольку среди натуральных чисел есть наименьшее, а среди целых — нет. Покажем, чтов игре Эренфойхта для этих интерпретаций выигрывает Новатор.Н объявляет, что игра будет проведена в два хода и на первомходу помечает число 0 из интерпретации N. В ответ К вынужден пометить некоторое число m из Z. На втором ходу Н помечает в Z некоторое число, меньшее m (например, m−1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
