И.А. Пушкарев логика

формуле Сk +1 : утверждается наличие элемента, не совпадающего ни с одним из k отмеченных.

QED

Пример 3. Теорема Тарского-Зайденберга

Теорема 7.6. (теорема Тарского-Зайденберга) В элементарной теории действительных чисел (сигнатура {+, ´, <, =, 0, 1}) выполнима элиминация

кванторов.

Замечания.

алгебраических уравнений и неравенств. Множества, которые можно описать при помощи таких совокупностей, называются полуалгебраическими.

(2) Переход от формулы P(x, y, ...) к формуле ExP(x, y, ...) соответствует

проектированию полуалгебраического множества параллельно осиx. Поэтому

теорема Тарского-Зайденберга равносильна , чтотому проекция

полуалгебраического множества является полуалгебраическим множеством.

(3)В частности, проекция полуалгебраического множества (на самом деле

–просто алгебраического) в R3 , заданного уравнением x2 + px + q = 0 , вдоль оси x, есть полуалгебраическое множество. Немного подумав, мы даже можем написать неравенство, которое его описывает: p2 - 4q ³ 0 . Соответствующая

конструкция для алгебраических уравнений других видов тоже называется дискриминант. Теорема Тарского-Зайденберга гарантирует его существование в любой ситуации J.

(4) Аналогично, рассмотрение системы двух алгебраических уравнений приводит к неконструктивному доказательству существования того, что обычно называют результантом.

72

(5) Практически все теоремы курса элементарной геометрии могут быть

записаны в координатах. Возможность элиминации кванторов означает

разрешимость соответствующей теории, так что из теоремы Тарского-

Зайденберга следует разрешимость элементарной геометрии(которая была обещана в предисловии).

Доказательство. Как и ранее, достаточно элиминировать квантор из

формулы ExB(x, y1, y2 , ..., yn ), где формула B(x, y1, y2 , ..., yn ) уже является

бескванторной. Следует доказать, что эта формула эквивалентна некоторой бескванторной формуле B¢(y1, y2 , ..., yn ). Не умаляя общности, можно считать,

переписать эти формулы в виде уравнений и неравенств на многочлены от переменной x, коэффициенты которых являются многочленами от переменных

y j . Формула B¢(y1, y2 , ..., yn ) выражает некоторое свойство этих многочленов,

и нам следует показать, что множество тех многочленов, для которых она истинна, является полуалгебраическим.

упорядоченный набор всех чисел, являющихся корнями каких-то многочленов

рассмотренного набора. Составим таблицу, k строк которой соответствуют рассмотренным многочленам, а 2m+1 столбец – числам a j и интервалам между ними. Таблица заполнена символами +, – и 0, соответствующим тому, является ли многочлен положительным, отрицательным, или он равен нулю в соответствующей точке или на соответствующем промежутке. Эта таблица и называется диаграммой набора.

73

Пример. Две тройки многочленов: x2 -1, x , 0 и x2 - 9 , 2x - 3 , 0 имеют

одинаковую диаграмму:

+ 0 - - - 0 +

- - - 0 + + +

0 0 0 0 0 0 0

Втом случае, когда коэффициенты многочленов от переменнойx

являются, в свою очередь, многочленами от переменныхy1, y2 , ..., yn ,

соответствующая диаграмма, конечно, тоже зависит от y1, y2 , ..., yn . При этом

многочленов. Следовательно, количество возможных диаграмм для данного

набора многочленов конечно, поэтому пространство R n всевозможных

значений векторов (y1, y2 , ..., yn ) разбивается на конечное число частей, каждая из которых соответствует некоторой диаграмме.

Заметим, что для доказательства теоремы достаточно доказать, что все эти

части будут полуалгебраическими множествами. Действительно, область

истинности формулы ExB(x, y1, y2 , ..., yn ) является объединением нескольких таких частей, тех самых, на которых все уравнения, входящие в формулу обращаются в верные равенства, а все неравенства имеют

верный знак для какой-то конъюнкции, входящей в ДНФ (не умаляя общности

лишних строк и слиянием соседних столбцов, оказавшихся после удаления строк идентичными (такие наборы столбцов возникают на месте столбцов,

соответствовавших корням удалённых многочленов и соседних с ними). При

объединение частей не может лишить их свойства«быть полуалгебраическими множествами». Поэтому утверждение необязательно доказывать для множества всевозможных наборов многочленов. Можно ограничиться рассмотрением некоторого множества наборов многочленов, такого что для любого набора в этом множестве найдётся некоторый набор, содержащий данный (больший по включению). Другими словами, при необходимости мы всегда можем добавить

коэффициента делителя, необходимую для того, чтобы деление с остатком можно было бы произвести. Очевидно, что достаточно умножить делимый многочлен на b deg P-degQ+1 , где P(x) – делимое, Q(x) – делитель, b –старший

коэффициент Q(x). Окончательно: модифицированным остатком от деления многочлена P(x) на многочленQ(x) в кольце (Z[y1, ..., yn ])[x] называется

75

остаток от деления на Q(x) многочлена b deg P-degQ+1Р(x) (при этом, разумеется,

можно предполагать, что deg P > deg Q , иначе деление происходит тривиально

и модифицированный остаток есть Q(x)).

Совершенно очевидно, что для любого конечного набора многочленов из

ним и уже имеющимися в множестве многочленами также лежат в этом

множества F0 , то, в силу конечности множестваF мы через конечное число шагов доберёмся до множестваF. При этом преобразование диаграммы на каждом шаге будет однозначным, поэтому «окончательная» диаграмма (для множества F) однозначно определяется «исходной» (для множества F0 ).

Итак, пусть на очередном шаге мы добавили к множеству многочлен P(x).

Поскольку все необходимые многочлены меньших степеней в множестве уже содержатся, там уже содержится старший коэффициент

76

Следовательно, в диаграмме уже содержится соответствующая строка. Если в ней содержатся только нули, то при данных значениях переменныхy1, ..., yn

многочлен P(x) совпадает с многочленом, полученным из P(x) отбрасыванием старшего члена, который тоже уже содержится в множестве, и нам, попросту,

следует продублировать соответствующую строку диаграммы.

Осталось рассмотреть случай, когда старший коэффициент не равен нулю.

При этом пополнение диаграммы будет происходить в два этапа. На первом этапе мы заполним для нового многочлена все имеющиеся к текущему моменту столбцы диаграммы. На втором этапе мы увеличим количество столбцов диаграммы за счёт «новых» корней многочлена P(x), не являющихся корнями никаких многочленов, ранее входивших в множество, и заполним соответствующие столбцы для всех многочленов.

Первый этап. Определим сначала знаки многочленаP(x) в столбцах,

соответствующих корням «старых» многочленов. Пусть столбец соответствует корню α многочлена Q(x). Можно считать, что его старший коэффициент отличен от нуля при данных значениях переменных y1, ..., yn (иначе его можно отбросить, перейдя к другому уже имеющемуся многочлену). Знак этого старшего коэффициента многочлена Q(x) тоже известен, так как в множестве содержится соответствующая этому коэффициенту строка. Применим к многочленам P(x) и Q(x) операцию модифицированного деления с остатком:

b s P(x)= D(x)× Q(x)+ R(x). Заметим, что b s P(a )= D(a )× Q(a )+ R(a )= R(a ), так

как Q(a )= 0 , многочлены R(x) и β содержатся в множестве, поэтому знак многочлена P(x) в точке α определяется однозначно.

Далее, определим, на каких участках, соответствующих столбцам диаграммы, содержатся «новые» корни многочлена P(x). Для этого вспомним,

что в множестве содержится производная по переменной x этого многочлена.

77

а) Если в двух столбцах, соответствующих соседним «старым» корням многочлен P(x) имеет один и тот же знак, то он имеет этот же знак и на

промежутке между этими корнями. Действительно, будь это не так, между этими «старыми» корнями обязательно бы находился экстремум многочлена, то есть – корень его производной, и корни не были бы соседними корнями

диаграммы.

б) Если в одном из соседних столбцов, или в обоих столбцах,

соответствующих «старым» корням многочлен P(x) принимает значение 0, то в интервале между этими корнями многочлен P(x) также не имеет корней, иначе эти корни снова не были бы соседними в силу теоремы Ролля: «между корнями функции есть корень производной».

в) Если в соседних столбцах многочлен P(x) имеет разные знаки, то один

корень на соответствующем интервале у многочлена имеется по крайней мере

рассматриваемый столбец диаграммы превращается в три. При этом понятно,

как заполняются клетки этих столбцов, соответствующие многочлену P(x).

г) Аналогично проводится рассуждение и для лучей, находящихся на краях диаграммы: там знак многочлена в пределе определяется знаком его старшего коэффициента.

Второй этап оказывается тривиален. «Новые» корни ничем не хуже

«старых», и заполнить для них остальные строки диаграммы, начав с самого низа, не составляет труда(а знаки старших коэффициентов, находящихся на нижнем уровне, постоянны во всей диаграмме). Тем самым, доказательство леммы 7.7 завершено.

QED

78

Завершение доказательства теоремы 7.6. теперь тоже почти тривиально:

как уже говорилось, диаграмма для множества F0 состоит из строк-«констант»,

поэтому на этом этапе диаграмма состоит всего из одного столбца. Поэтому

различным вариантам этих диаграмм соответствуют различные варианты

§8. Элементарная эквивалентность 1. Элементарная эквивалентность

Определение 8.1. (1) Пусть фиксирована некоторая сигнатура. Две

интерпретации этой сигнатуры называются элементарно эквивалентными, если в них истинны одни и те же формулы без параметров этой сигнатуры.

символа отношения Р и сего интерпретаций Р1 и Р2 (соответственно, в М1 и М2)

Р1(a1 , a2 ,...,an )=1 Û Р2 (a(a1 ),a(a2 ),...,a(an ))=1.

(3) Две интерпретации называются изоморфными, если между ними существует изоморфизм.

Замечания. (1) Определение изоморфных интерпретаций обобщает понятие изоморфизма чего угодно.

(2) Вторая и третья части определения8.1. нужны в основном для того,

чтобы сформулировать следующее очевидное утверждение.

Теорема 8.1. Изоморфные интерпретации элементарно эквивалентны.

QED

Замечание. Интересно как раз ,точто элементарно эквивалентными могут быть неизоморфные интерпретации.

79

Теорема 8.2. Естественные интерпретации сигнатуры{+, <, =, 0, 1} на множествах рациональных и действительных чисел элементарно эквивалентны.

Доказательство. Формулы этой сигнатуры допускают элиминацию кванторов. При этом результат этой элиминации, естественно, эквивалентен

исходной формуле в обеих интерпретациях. Однако эта формула содержит

интерпретации М1, если для любой (необязательно – без параметров!) формулы

р и для любой оценки π со значениями в М1 формула р истинна на этой оценке в

М1 тогда и только тогда, когда она истинна вМ2. Обратно, в описанной ситуации интерпретацию М1 будем называтьэлементарной подмоделью

интерпретации М2.

Вчастности, элементарное расширение некоторой интерпретации–

элементарно эквивалентная интерпретация (поскольку истинность формул без параметров, их ещё называют замкнутыми, тоже наследуется).

Пример. Примером расширения может служить обычное расширение полей (сигнатура {+, ´, =, 0, 1}). При этом соответствующие интерпретации являются элементарно эквивалентными, если любая система алгебраических уравнений, разрешимая в исходном поле, разрешима и в расширении.

80

2. Игра Эренфойхта

В этом разделе считаем, что сигнатура не содержит функциональных

символов. Это несущественное ограничение, так как функциональный символ всегда модно заменить семантически равносильным ему символом отношения.

Кроме того, будем считать сигнатуру конечной(а вот это– существенное ограничение).

Игрой Эренфойхта называют игру с двумя игроками: Новатором (Н) и

Консерватором (К). Сама игра идёт на двух интерпретациях рассматриваемой сигнатуры.

В начале игры Н объявляет натуральное числоk, после чего игроки по очереди делают поk ходов, Н ходит первым, К – вторым. На i–ом ходу Н

выбирает элемент одной из интерпретаций и помечает его числомi. В ответ К выбирает один из элементов другой интерпретации и тоже помечает его числом i. После разыгрывания партии, тем самым, оказываются отмечены некоторые

соответствующими друг другу. Н выигрывает, если некоторый предикат рассматриваемой сигнатуры различает эти наборы, а К – если никакой предикат не различает их (предикат, по определению, различает наборы, если принимает на них разные значения).

Теорема 8.3. Интерпретации элементарно эквивалентны, если при игре на

них у Консерватора есть выигрышная стратегия.

Прежде чем приступить к доказательству теоремы, приведём примеры