Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 25
Текст из файла (страница 25)
89).Разобравшись с действительными числами, перейдём к комплексным. На самом деле (как часто бывает) здесь ситуация проще.На комплексных числах нет естественного отношения порядка,поэтому рассмотрим сигнатуру (=, 0, 1, +, ×). Будем, как всегда, считать две формулы эквивалентными, если они истинны при одних итех же значениях параметров (в естественной интерпретации с но-110Языки первого порядка[гл. 3]сителем C).Теорема 34 (элиминация кванторов в поле комплексных чисел).Всякая формула этой сигнатуры эквивалентна бескванторной.
Эта теорема имеет много разных доказательств, но после доказательства теоремы Тарского – Зайденберга нам проще всего модифицировать его.Теперь в диаграммах будут стоять не знаки −, 0, +, а только знаки 0 и 6=0 (поскольку порядка на C нет). По той же причине мыне можем упорядочить корни, так что диаграмма будет состоятьиз неупорядоченных столбцов, соответствующих корням, и одногостолбца, соответствующего дополнению к множеству корней (в котором будут стоять знаки 6=0 для всех многочленов, кроме нулевых).Говоря о неупорядоченных столбцах, мы имеем в виду, что не различаем диаграммы, отличающиеся лишь порядком столбцов.Основной шаг в доказательстве теоремы Тарского – Зайденберга(единственный, где важен порядок на действительных числах) состоял в пополнении диаграммы новым многочленом.
Что будет с нимтеперь?Как и раньше, мы можем определить, в каких старых корняхновый многочлен равен нулю. Более того, мы можем определитькратность этих нулей, так как знаем всё необходимое про его производные (которые уже включены в диаграмму). Поэтому основнаятеорема алгебры говорит нам, сколько будет новых корней (заметим,что все новые корни имеют кратность 1, так как иначе они были быкорнями производной и не были бы новыми). Поскольку порядка накорнях нет, больше никакой информации нам и не нужно. 69. Провести доказательство элиминации кванторов в поле C, не использующее диаграмм (это можно сделать, начав с приведения бескванторной формулы к дизъюнктивной нормальной форме, а затем применяяразные соображения из алгебры о наибольшем общем делителе многочленов).
Для теоремы Тарского – Зайденберга это несколько сложнее; рассуждение такого рода приведено в книжке Энгелера [32].70. Докажите, что множество четвёрок комплексных чисел hp, q, r, si,для которых многочлены z 2 + pz + q = 0 и z 2 + rz + s = 0 имеют общийкорень, задаётся бескванторной формулой. Найдите эту формулу.Задача 70 хорошо знакома алгебраистам. Ответ в ней можно записать в виде R(p, q, r, s) = 0, где R — многочлен, называемый ре-[п. 9]Элементарная эквивалентностьзультантом и равный определителю 1 p q 0 1 p 1 r s 0 1 r111матрицы0 q 0 s 71. Докажите, что множество всех пар комплексных чисел hp, qi, прикоторых многочлен z 3 +pz+q имеет хотя бы один кратный корень, задаётсябескванторной формулой.
Найдите эту формулу. Как выглядит аналогичная формула для многочлена z 2 + pz + q?(Ответ к задаче 71 тоже хорошо известен в алгебре; соответствующий многочлен называется дискриминантом.)72. Обобщите утверждение предыдущей задачи на многочлены произвольной степени со старшим коэффициентом 1 и найдите выражениедискриминанта в виде определителя.3.9. Элементарная эквивалентностьПока что мы в основном использовали технику элиминации кванторов для какой-то одной интерпретации (формула заменялась набескванторную, которая эквивалентна исходной в данной интерпретации). Однако, как упоминалось на с. 95, этот метод позволяет сравнивать различные интерпретации.
Мы приведём несколько примеровтакого рода.Начнём с определения. Пусть фиксирована некоторая сигнатура σ. Две интерпретации этой сигнатуры называются элементарноэквивалентными, если в них истинны одни и те же замкнутые формулы этой сигнатуры.Легко доказать, что изоморфные интерпретации будут элементарно эквивалентны — надо только дать формальное определениеизоморфизма для двух интерпретаций данной сигнатуры.Пусть M1 и M2 — две интерпретации сигнатуры σ. Биекция (взаимно однозначное отображение) α : M1 → M2 называется изоморфизмом этих интерпретаций, если она сохраняет все функции и предикаты сигнатуры.
Это означает, что если P1 и P2 — два k-местныхпредиката в M1 и M2 , соответствующих одному предикатному символу сигнатуры, тоP1 (a1 , . . . , ak ) ⇔ P2 (α(a1 ), . . . , α(ak ))для всех a1 , . . . , ak ∈ M1 . Аналогичное условие для функций: еслиk-местные функции f1 и f2 соответствуют одному функциональному112Языки первого порядка[гл.
3]символу, тоα(f1 (a1 , . . . , ak )) = f2 (α(a1 ), . . . , α(ak ))для всех a1 , . . . , ak ∈ M1 .Две интерпретации называются изоморфными, если между нимисуществует изоморфизм.Легко понять, что это определение обобщает обычные определения изоморфизма для групп, колец, упорядоченных множеств и т. д.73. Докажите, что тождественное отображение есть изоморфизм.
Докажите, что отображение, обратное изоморфизму, есть изоморфизм. Докажите, что композиция двух изоморфизмов есть изоморфизм. (Отсюдаследует, что отношение изоморфности есть отношение эквивалентности наинтерпретациях данной сигнатуры.)Сформулируем и докажем обещанное утверждение:Теорема 35. Если две интерпретации изоморфны, то они элементарно эквивалентны.
Естественно доказывать это утверждение по индукции. Дляэтого его надо обобщить на произвольные формулы (не только замкнутые). Вот это обобщение: пусть α : M1 → M2 — изоморфизм, аF — произвольная формула нашей сигнатуры. Тогда она истиннав M1 при оценке π тогда и только тогда, когда она истинна в M2 приоценке α ◦ π.Обычно истинность формулы F в интерпретации M обозначают как M F . Если формула имеет параметры x1 , .
. . , xn , её частообозначают F (x1 , . . . , xn ); при этом запись M F (m1 , . . . , mn ) (гдеmi ∈ M ) означает, что формула F истинна при оценке, которая ставит в соответствие параметру xi значение mi . После всех этих приготовлений доказываемое по индукции утверждение можно записатьтак:M1 F (a1 , . .
. , an ) ⇔ M2 F (α(a1 ), . . . , α(an ))для любой формулы F (x1 , . . . , xn ) и для любых элементов a1 , . . . , anмножества M1 .После такого обобщения доказательство по индукции становитсяочевидным. 74. В каком месте индуктивного рассуждения существенно, что α —взаимно однозначное соответствие? (Ответ: сюръективность α используется, когда мы рассматриваем формулу, начинающуюся с квантора существования, и из её истинности в M2 выводим истинность в M1 . Инъективность α не используется, но она автоматически следует из определения[п. 9]Элементарная эквивалентность113изоморфизма, если сигнатура содержит равенство и интерпретации нормальны, то есть равенство интерпретируется как совпадение элементов.)75.
Рассуждение, использованное при доказательстве теоремы 35, нампо существу уже встречалось. Где?Изоморфные интерпретации — это по существу одна и та же интерпретация, только её элементы названы по-разному. Интересныскорее примеры, когда интерпретации не изоморфны, но тем не менее элементарно эквивалентны. Один такой пример мы уже короткообсуждали раньше, сформулируем его более подробно.Теорема 36. Естественные интерпретации сигнатуры (=, <, +, 0, 1)в множестве рациональных и действительных чисел элементарно эквивалентны.
Для начала заметим, что эти интерпретации не изоморфны(поскольку мощности различны). Однако формулы этой сигнатурыдопускают, как мы видели на с. 96, элиминацию кванторов. При этомполучающаяся формула будет эквивалентна исходной в обеих интерпретациях. Начав с замкнутой формулы, мы получим бескванторную формулу без переменных (или с фиктивными переменными, отзначений которых ничего не зависит, тогда вместо них можно подставить, скажем, нули). Эта формула будет содержать только рациональные константы и потому будет одновременно истинной илиложной в R и в Q.
Заметим, что при уменьшении сигнатуры элементарная эквивалентность сохраняется (по очевидным причинам), так что из теоремы 36 очевидно следует, что R и Q элементарно эквивалентны какупорядоченные множества (этот факт мы отмечали на с. 95).В этом примере элементарно эквивалентные, но не изоморфныеструктуры имеют различную мощность. В следующем примере этоуже не так.Теорема 37.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
