Арифметика Пресбургера

Разбить на страницы

Показывать лекцию целиком

Арифметика Пресбургера

В этом разделе мы описываем выразимые множества в $$(\mathbb{Z},{=},{<},{+},0,1)$$. Отметим сразу же, что с такой сигнатурой элиминация кванторов невозможна. В самом деле, формула $$\exists y\, (x\hm={y+y})$$, истинная для четных $$x$$, не эквивалентна никакой бескванторной формуле. Поэтому нам нужно, прежде чем проводить элиминацию кванторов, расширить сигнатуру. Приведенный пример формулы подсказывает, какое расширение нам необходимо. Рассмотрим счетное семейство двуместных предикатных символов $$\equiv_2, \equiv_3,\equiv_4,\dots$$ Символ $$\equiv_c$$ будет интерпретироваться как равенство по модулю $$c$$. Другими словами, формула $$x\equiv_c y$$ будет истинна в нашей интерпретации, если $$x$$ сравнимо с $$y$$ по модулю $$c$$ (остатки по модулю $$c$$ равны; $$x-y$$ кратно $$c$$ ).

Важно иметь в виду, что индекс $$c$$ в $$x\equiv_c y$$ не является переменной: у нас не трехместный предикат, а счетное семейство двуместных предикатов.

Такое расширение не меняет класса выразимых предикатов, поскольку, например, $$x\equiv_3 y$$ можно выразить как $$\exists z\, (x=y+z+z+z)$$. Зато после этого всякая формула эквивалентна бескванторной, как показывает следующая теорема (называемая теоремой об элиминации кванторов в арифметике Пресбургера).

Теорема 32. В $$\langle\bbZ,=,<,+,0,1,\equiv_2,\equiv_3,\dots\rangle$$ выполнима элиминация кванторов.

Мы будем применять метод, опробованный в предыдущем разделе: выбор представительного множества термов (после некоторых преобразований формулы).

Напомним, как это делается. Мы хотим доказать, что всякая формула эквивалентна бескванторной. Рассуждая по индукции, мы должны лишь проверить, что всякая формула вида$$\exists x\, \tau(x,x_1,\dots,x_n),$$ где $$\tau(x,x_1,\dots,x_n)$$ обозначает бескванторную формулу, все переменные которой содержатся среди $$x,x_1,\dots,x_n$$, эквивалентна некоторой бескванторной формуле (с теми же переменными, не считая $$x$$ ).

Посмотрим, какие атомарные формулы, содержащие переменную $$x$$, входят в $$\tau$$. Перенося члены в одну сторону, эти атомарные формулы можно записать в одном из трех видов: $$L(x,x_1,\dots,x_n)\hm=0$$, $$L(x,x_1,\dots,x_n)\hm>0$$ или $$L(x,x_1,\dots,x_n)\hm\equiv_c 0$$, где $$L(x,x_1,\dots,x_n)$$ представляет собой линейную комбинацию переменных $$x,x_1,\dots,x_n$$ с целыми коэффициентами и целочисленным свободным членом. (В отличие от ситуации в $$\mathbb{Q}$$, здесь нельзя делить на коэффициент при $$x$$.) Перенося $$x$$ в левую часть, а все остальное — в правую, получаем соотношение одного из четырех видов:$$\begin{align*} kx = l(x_1,\dots,x_n);\\ kx < l(x_1,\dots,x_n);\\ kx > l(x_1,\dots,x_n);\\ kx \equiv_c l(x_1,\dots,x_n), \end{align*}$$ где $$k$$ — положительное целое число (разное для разных атомарных формул), а $$l$$ — линейная комбинация переменных $$x_1,\dots,x_n$$ с целыми коэффициентами и свободным членом.

Как мы говорили, коэффициенты в левой части (а также, разумеется, правые части) у разных атомарных формул разные. Однако мы можем их унифицировать, перейдя к общему кратному. В самом деле, неравенства и равенства можно умножать на число, сравнения — тоже, если модуль сравнения (индекс $$c$$ в $$\equiv_c$$ ) умножить на то же самое число. Поэтому можно считать, что наша формула имеет вид $$\exists x\,\tau(kx,x_1,\dots,x_n)$$, понимая под этим, что $$x$$ появляется только в левых частях и везде с коэффициентом $$k$$. Такую формулу можно переписать как$$\exists y\, (\tau(y,x_1,\dots,x_n) \land (y\equiv_k 0)).$$ Таким образом, без ограничения общности можно считать, что $$k=1$$, поскольку новая формула имеет тот же самый вид$$\exists y\, \tau(y,x_1,\dots,x_n),$$ что и исходная, но уже безо всякого коэффициента при $$y$$ (и с модифицированной формулой $$\tau$$ ). Пусть $$l_1,\dots,l_k$$ — выражения, стоящие в правых частях равенств, неравенств и сравнений с левой частью $$y$$.

Мы хотим, как и в предыдущем разделе, указать представительный набор значений $$Y_1,\dots,Y_N$$. Каждое из $$Y_i$$ представляет собой линейную комбинацию переменных $$x_1,\dots,x_n$$ с целыми коэффициентами и свободным членом. "Представительность" означает, что если для каких-то $$x_1,\dots,x_n$$ найдется $$y$$, для которого $$\tau(y,x_1,\dots,x_n)$$, то такой $$y$$ можно найти и среди значений $$Y_1,\dots,Y_N$$ (при тех же $$x_1,\dots,x_n$$ ).

Чтобы указать представительный набор, разделим все атомарные формулы в $$\tau$$, содержащие $$y$$, на два типа — сравнения по модулю и остальные (равенства и неравенства). Посмотрим, по каким модулям проводятся сравнения. Пусть $$D$$ — общее кратное всех этих модулей. В этом случае изменение значения переменной $$y$$ на величину, кратную $$D$$, не влияет на результаты сравнений. Теперь возьмем все выражения, встречающиеся в правых частях равенств или неравенств, и будем прибавлять к ним всевозможные целые числа из отрезка от $$-D$$ до $$D$$. Это и будет представительный набор. Другими словами, в представительный набор входят все выражения $$l+c$$, где $$l$$ — одна из правых частей равенств или неравенств, содержащих $$y$$ в левой части, а $$c$$ — целое число, не превосходящее $$D$$ по абсолютной величине.

Покажем, что полученный набор действительно будет представительным. Пусть при данных $$x_1,\dots,x_n$$ найдется некоторое $$y$$, для которого $$\tau(y,x_1,\dots,x_n)$$. Посмотрим, какие значения принимают правые части равенств и неравенств при данных $$x_1,\dots,x_n$$. Если значение $$y$$ попало в объединение $$D$$ -окрестностей этих значений, то доказывать нечего. Если же нет, начнем смещать $$y$$, двигаясь шагами размера $$D$$ в направлении какой-то точки из этого объединения. Миновать мы ее не можем (ширина окрестности равна $$2D$$, а размер шага равен $$D$$ ), поэтому в какой-то момент мы впервые попадем в это объединение. Обозначим эту точку (первую попавшую в объединение) через $$y'$$. Тогда $$y'$$ при подстановке в $$\tau$$ дает те же самые результаты, что и $$y$$. В самом деле, для сравнений это гарантировано, потому что сдвиг кратен модулю сравнений. Но это верно и для равенств и неравенств, поскольку на предыдущем шаге мы были вне $$D$$ -окрестности всех правых частей и потому не могли перейти с одной стороны на другую.

Таким образом, среди представительного набора есть значение (а именно, $$y'$$ ), удовлетворяющее формуле $$\tau$$, что и требовалось доказать.

Итак, мы получили ответ на интересующий нас вопрос: выразимые в арифметике Пресбургера предикаты — это предикаты, выразимые бескванторными формулами, содержащими целые константы, сложение, равенство, отношение порядка и сравнения по любым фиксированным модулям.

Теорема Тарского-Зайденберга

В этом разделе мы покажем, что в элементарной теории действительных чисел со сложением и умножением выполнима элиминация кванторов. Более точно, рассмотрим сигнатуру, содержащую предикаты $$=$$ и $$<$$, константы $$0$$ и $$1$$, а также операции сложения и умножения. Рассмотрим интерпретацию этой сигнатуры, носителем которой является множество действительных чисел, а предикаты и операции понимаются естественным образом. Тогда для каждой формулы существует эквивалентная (выражающая тот же предикат) бескванторная формула. Это утверждение называют теоремой Тарского-Зайденберга.

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

Свойство $$x<y$$ можно выразить как "существует ненулевое $$z$$, для которого $$x+z^2=y$$ ". Таким образом, класс выразимых предикатов не изменится, если мы удалим символ $$<$$ из сигнатуры. (Но предикатов, выразимых бескванторными формулами, станет меньше: свойство $$x\hm>0$$, как легко понять, не эквивалентно никакой бескванторной формуле, содержащей константы, сложение, умножение и равенство.)

Бескванторную формулу нашей сигнатуры можно привести к дизъюнктивной нормальной форме, после чего она превратится в совокупность систем уравнений вида $$P=0$$ и неравенств вида $$P>0$$. В самом деле, в конъюнкциях могут еще быть отрицания, то есть отношения $$\ne$$ и $$\ge$$, но можно разбить $$P\ne 0$$ на $$(P<0)\lor (P>0)$$, а $$P\ge 0$$ на $$(P=0)\lor (P>0)$$, после чего воспользоваться дистрибутивностью.

Подмножества $$\mathbb R^n$$, задаваемые уравнениями вида $$P=0$$ и неравенствами вида $$P>0$$ (где $$P$$ — произвольный многочлен от нескольких переменных с целыми коэффициентами), а также множества, получаемые из них любым числом операций объединения и пересечения, называют полуалгебраическими. Предыдущее замечание показывает, что всякая бескванторная формула задает полуалгебраическое множество. (Полуалгебраические множества являются обобщениями алгебраических множеств, задаваемых системами полиномиальных уравнений.)

Из теоремы Тарского-Зайденберга вытекает, что проекция полуалгебраического множества $$A\subset\mathbb R^n$$ вдоль одной из осей является полуалгебраическим подмножеством пространства $$\mathbb R^{n-1}$$. В самом деле, переход к проекции приводит к добавлению квантора существования, который можно затем элиминировать. (Утверждение о полуалгебраичности проекции полуалгебраического множества по существу равносильно теореме Тарского-Зайденберга, так как элиминация квантора существования является единственным нетривиальным шагом в доказательстве этой теоремы.)

Пример: равенство $$x^2+px+q=0$$ задает полуалгебраическое (и даже алгебраическое) множество троек $$\langle x,p,q\rangle$$. Какова будет его проекция вдоль оси $$x$$ на плоскость $$p,q$$? Как учат в школе, это будет множество $$p^2-4q\ge 0$$, которое оказывается полуалгебраическим в полном согласии с теоремой Тарского-Зайденберга. Про аналогичные критерии разрешимости уравнений большей степени в школе не учат, но теорема Тарского-Зайденберга гарантирует их существование.

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

Большинство утверждений школьного курса геометрии с помощью метода координат можно записать как утверждения о действительных числах в нашей сигнатуре. (Исключение, впрочем, составляют утверждения, где речь идет не о треугольниках и четырехугольниках, а о $$n$$ - угольниках без указания конкретного $$n$$ ). Записав теоремы в виде замкнутых формул нашей сигнатуры, можно алгоритмически проверить их истинность. Тем самым мы получаем общий метод доказательства большинства теорем школьной геометрии (впрочем, он имеет лишь теоретическое значение, так как алгоритм работает необозримо долго на сколько-нибудь сложных формулах).

Теорема 33 (Тарского-Зайденберга). Для всякой формулы сигнатуры $$({=},{<},0,1,{+},{\times})$$ существует бескванторная формула, задающая тот же предикат на множестве действительных чисел.

Как обычно, достаточно рассматривать формулу с единственным квантором существования, то есть формулу $$\varphi$$ вида$$\exists x\, B(x,x_1,\dots,x_n),$$ где $$B(x,x_1,\dots,x_n)$$ — бескванторная формула, включающая в себя только переменные из числа $$x,x_1,\dots,x_n$$. Надо доказать, что найдется эквивалентная формуле $$\varphi$$ бескванторная формула $$B'(x_1,\dots,x_n)$$.

Посмотрим на атомарные формулы, входящие в формулу $$B$$. Перенося все переменные в одну часть, можно считать, что каждая атомарная формула имеет вид $$P(x,x_1,\dots,x_n)\hm=0$$ или $$P(x,x_1,\dots,x_n)\hm>0$$, где $$P$$ — некоторый многочлен с целыми коэффициентами от переменных $$x,x_1,\dots,x_n$$. Кольцо многочленов с целыми коэффициентами от переменных $$x,x_1,\dots,x_n$$ обозначается через $$\mathbb Z[x,x_1,\dots,x_n]$$. Группировка членов по степеням переменной $$x$$ дает многочлен от $$x$$, коэффициенты которого представляют собой многочлены от $$x_1,\dots,x_n$$. Символически это записывается так:$$\mathbb Z[x,x_1,\dots,x_n]=(\mathbb Z[x_1,\dots,x_n])[x]$$ (многочлены от $$n+1$$ переменных можно рассматривать как многочлены от одной переменной, коэффициенты которых лежат в кольце многочленов от $$n$$ переменных).

При фиксации значений переменных $$x_1,\dots,x_n$$ входящие в $$B$$ многочлены превращаются в многочлены от одной переменной $$x$$ с числовыми коэффициентами. Формула $$\varphi$$ выражает тогда какое-то свойство этих многочленов и может быть истинной или ложной. Нам надо доказать, что те $$\langle x_1,\dots,x_n\rangle$$, при которых она истинна, образуют полуалгебраическое множество.

Для этого введем понятие диаграммы семейства многочленов. Пусть $$Q_1(x),\dots,Q_k(x)$$ — многочлены от $$x$$ с действительными коэффициентами. Диаграммой набора $$Q_1,\dots,Q_k$$ будет таблица, которая строится так. Возьмем все корни всех многочленов $$Q_i$$ (не считая нулевых многочленов) и расположим их в порядке возрастания. Получим некоторый набор чисел $$\alpha_1<\alpha_2<\ldots<\alpha_m$$. Эти числа разбивают числовую ось на $$m+1$$ промежутков (два луча и $$m-1$$ интервалов), на каждом из которых знаки всех $$Q_i$$ постоянны. Составим таблицу, в которой будет $$k$$ строк (по одной для каждого из многочленов) и $$2m+1$$ столбцов, соответствующих $$m$$ корням и $$m+1$$ промежуткам (столбцы идут в порядке возрастания, так что корни чередуются с промежутками). В каждой ячейке таблицы запишем один из трех символов $$+$$, $$-$$ или $$0$$ в зависимости от того, является ли многочлен положительным, отрицательным или нулевым на соответствующем промежутке (или в соответствующем корне).

Пример. Выпишем диаграмму для системы многочленов $$x^2\hm-1$$, $$x$$, $$0$$. Корнями здесь будут числа $$-1$$, $$0$$, $$1$$, так что столбцы соответствуют четырем промежуткам и трем разделяющим их корням.$$\begin{array}{r|ccccccc} \mathstrut \langle -1\rangle \langle 0\rangle \langle 1\rangle \\[0.2ex] \hline\\[-2.3ex] x^2-1\mathstrut + 0 - - - 0 +\\ x - - - 0 + + +\\ 0 0 0 0 0 0 0 0 \end{array}$$ Отметим, что значения корней не являются частью диаграммы, так что, например, система многочленов $$x^2\hm-4$$, $$2x-1$$, $$0$$ имеет точно такую же диаграмму.

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

Теперь рассмотрим набор многочленов $$Q_1,\dots,Q_k\hm\in\mathbb Z[x,x_1,\dots,x_n]$$. При фиксированных значениях переменных $$x_1,\dots,x_n$$ мы получаем набор многочленов от одной переменной с действительными коэффициентами и можем построить его диаграмму. Эта диаграмма будет зависеть от выбора значений $$x_1,\dots,x_n$$. Число строк в диаграмме равно $$k$$, а ширина ее зависит от числа различных корней и может меняться, однако во всех случаях не превосходит $$2N+1$$, где $$N$$ — сумма степеней всех многочленов (рассматриваются степени по $$x$$, то есть степени соответствующих многочленов от $$x$$ с коэффициентами в $$\mathbb Z[x_1,\dots,x_n]$$ ).

Таким образом, число возможных диаграмм конечно, и пространство $$\mathbb R^n$$ возможных значений переменных $$x_1,\dots,x_n$$ разбивается на конечное число частей: каждая часть соответствует одному из возможных значений диаграммы.

Для доказательства теоремы Тарского-Зайденберга достаточно доказать, что эти части будут полуалгебраическими множествами. В самом деле, если в качестве многочленов $$Q_1,\dots, Q_k$$ взять многочлены, входящие в формулу $$B(x,x_1,\dots,x_n)$$, то область истинности формулы$$\varphi=\exists x\, B(x,x_1,\dots,x_n)$$ будет объединением нескольких частей соответствующего разбиения. В самом деле, если мы двигаем точку $$\langle x_1,\dots,x_n\rangle$$ в пределах одной части разбиения, то диаграмма не меняется, значит, и истинность формулы $$\varphi$$ не меняется (по диаграмме можно определить истинность формулы, перепробовав значения $$x$$, соответствующие всем столбцам).

Итак, нам осталось доказать, что для любого набора многочленов $$Q_1,\dots,Q_k\hm\in\mathbb Z[x,x_1,\dots,x_n]$$ части пространства $$\mathbb R^n$$, соответствующие различным значениям диаграммы, являются полуалгебраическими множествами. Начнем с такого очевидного наблюдения: если это верно для какого-то набора $$Q_1,\dots,Q_k$$, то это останется верным и для любого меньшего набора. В самом деле, диаграмму меньшего семейства многочленов можно получить из диаграммы большего семейства: выкидывая многочлен, надо выбросить соответствующую строку, а также столбцы, которые соответствовали корням этого многочлена (если они не были корнями других многочленов). При выбрасывании столбца два окружающих его столбца сливаются в один.

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

Напомним еще раз, что мы рассматриваем семейство многочленов из $$\mathbb Z[x,x_1,\dots,x_n]$$, которые разложены по степеням $$x$$, то есть записаны как многочлены от $$x$$ с коэффициентами в $$\mathbb Z[x_1,\dots,x_k]$$. Рассмотрим следующие операции:

отбрасывание старшего члена (с наибольшей степенью переменной $$x$$ ); эта операция понижает степень (по $$x$$ ) на единицу;

взятие старшего коэффициента (коэффициента при наибольшей степени переменной $$x$$ ); эта операция понижает степень (по $$x$$ ) до нуля;

дифференцирование по $$x$$ ; эта операция понижает степень (по $$x$$ ) на единицу;

взятие модифицированного остатка при делении одного многочлена на другой.

Говоря о "модифицированном остатке", мы имеем в виду следующее. При делении "уголком" многочлена $$A$$ на многочлен $$B$$ с остатком нам неоднократно приходится делить на старший коэффициент многочлена $$B$$. Поэтому в общем случае коэффициенты частного и остатка представляют собой дроби, в знаменателях которых стоят некоторые степени старшего коэффициента многочлена $$B$$.

Тем самым при вычислении остатка от деления $$A$$ на $$B$$ мы выходим за пределы кольца $$\mathbb Z[x,x_1,\dots,x_n]$$. Этого не случится, если старший коэффициент многочлена $$B$$ равен единице. Но в общем случае мы должны принять какие-то меры, если хотим оставаться в указанном кольце. Меры эти состоят в следующем: прежде чем делить $$A$$ на $$B$$, мы умножаем $$A$$ на старший коэффициент многочлена $$B$$ в достаточно большой степени. Если вспомнить процедуру деления уголком, легко сообразить, что достаточно взять степень $$a-b+1$$, где $$a$$ и $$b$$ — степени многочленов $$A$$ и $$B$$ (по переменной $$x$$ ). Например, при $$a=b$$ требуется всего один шаг деления, и достаточно умножить $$A$$ на старший коэффициент многочлена $$B$$ в первой степени.

Итак, операция модифицированного остатка применима к любым двум многочленам $$A,B\hm\in(\mathbb Z[x_1,\dots,x_n])[x]$$ степеней $$a$$ и $$b$$ (по $$x$$ ) и дает третий многочлен этого кольца, который есть остаток от деления $$A\beta^{a-b+1}$$ на $$B$$ (здесь $$\beta$$ — старший коэффициент многочлена $$B$$ ). Заметим, что степень этого многочлена меньше степени многочлена $$B$$. Мы будем предполагать, что $$a\ge b$$ (иначе остаток совпадает с $$A$$ и деление не дает ничего нового). Таким образом, результат этой операции имеет меньшую степень, чем оба операнда.

Заметим, что определение модифицированного остатка имеет смысл для многочленов с коэффициентами из произвольного кольца (не только $$\mathbb Z[x_1,\dots,x_n]$$ ).

Лемма 1. Для всякого конечного множества $$F$$ многочленов из $$(\mathbb Z[x_1,\dots,x_n])[x]$$ существует его конечное расширение, замкнутое относительно указанных четырех операций.

Это утверждение верно для любого кольца коэффициентов и почти очевидно следует из того, что степень результата операции меньше степени (любого) операнда. Более формально рассуждать надо так. Рассмотрим выражения, составленные из элементов $$F$$ с помощью четырех указанных операций. Глубина такого выражения не превосходит максимальной степени многочленов из $$F$$, поскольку каждая операция уменьшает степень. Поэтому таких выражений конечное число, и их множество очевидным образом замкнуто относительно указанных операций. Лемма 1 доказана.

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

Лемма 2. Пусть $$F$$ — конечное множество многочленов из $$(\mathbb Z[x_1,\dots,x_n])[x]$$, замкнутое относительно перечисленных операций. Пусть $$F_0$$ — его часть, состоящая только из многочленов степени $$0$$ по $$x$$ (они представляют собой многочлены из $$\mathbb Z[x_1,\dots,x_n]$$ ). Тогда диаграмма множества $$F$$ при данных $$x_1,\dots,x_n$$ полностью определяется диаграммой множества $$F_0$$ при тех же $$x_1,\dots,x_n$$.

Заметим, что диаграмма множества $$F_0$$ имеет всего один столбец, указывающий, какие из многочленов положительны, какие отрицательны и какие равны нулю при данных $$x_1,\dots,x_n$$. Поэтому различным вариантам диаграммы для множества $$F_0$$ соответствуют полуалгебраические подмножества в $$\mathbb {R}^n$$, и из леммы 2 следует, что те же самые множества составят искомое разбиение для полной системы $$F$$. Таким образом, нам осталось лишь доказать лемму 2.

Будем добавлять в множество $$F_0$$ многочлены по одному, в порядке возрастания (неубывания) их степеней, пока не получим все множество $$F$$. Достаточно показать, что на каждом шаге диаграмма расширенного множества (с новым многочленом) может быть однозначно восстановлена по диаграмме предыдущего множества. Мы сейчас опишем, как это делается.

Пусть добавляется многочлен $$P\hm\in(\mathbb Z[x_1,\dots,x_n])[x]$$, при этом многочлены всех меньших степеней из $$F$$ уже есть в диаграмме. В силу замкнутости $$F$$ старший коэффициент многочлена $$P$$ содержится в $$F$$ и, имея меньшую (нулевую) степень, уже представлен в диаграмме. (Соответствующая строка состоит из одинаковых знаков, так как он не зависит от $$x$$.) Если там стоят нули, то (при данных $$x_1,\dots,x_n$$ ) старший коэффициент равен нулю, и многочлен $$P$$ совпадает с многочленом, получающимся при отбрасывании старшего члена. Этот многочлен тоже есть в $$F$$ и в диаграмме, так что надо лишь продублировать соответствующую строку.

Итак, достаточно рассмотреть случай, когда старший коэффициент многочлена $$P$$ (при данных $$x_1,\dots,x_n$$ ) не равен нулю. Пополнение диаграммы включает в себя два шага: сначала мы должны определить знаки многочлена $$P$$ в точках (корнях), уже входящих в диаграмму. Затем надо пополнить диаграмму корнями многочлена $$P$$ (при этом число столбцов в ней увеличится).

Как найти знак многочлена $$P$$ в одной из старых точек? По определению диаграммы в этой точке (обозначим ее $$\alpha$$ ) один из старых многочленов равен нулю. Пусть $$Q$$ — такой многочлен. Можно считать, что старший коэффициент $$Q$$ (как многочлена от $$x$$ ) отличен от нуля при данных $$x_1,\dots,x_n$$. Если это не так, заменим $$Q$$ на многочлен, получающийся отбрасыванием старшего члена. Мы знаем, что множество $$F$$ замкнуто относительно четырех операций и что все многочлены из $$F$$, имеющие меньшую степень, уже входят в диаграмму. Поэтому вся необходимая информация для отбора подходящего $$Q$$ у нас есть.

Кроме того, по тем же причинам нам известен знак старшего коэффициента многочлена $$Q$$. Применим операцию модифицированного деления с остатком к $$P$$ и $$Q$$:$$\beta^s P = (\text{частное})\cdot Q + R$$ (здесь $$\beta$$ — старший коэффициент многочлена $$Q$$ ). Подставим в это равенство число $$\alpha$$. При этом $$Q$$ обратится в нуль, так как $$\alpha$$ является корнем $$Q$$ по построению. Многочлен $$R$$ входит в диаграмму в силу наших предположений, так что его знак в точке $$\alpha$$ нам известен, как и знак $$\beta$$. Тем самым можно найти знак $$P(\alpha)$$.

Итак, мы определили знак нового многочлена в старых корнях. Покажем, что этого достаточно, чтобы предсказать, на каких участках диаграммы появятся новые корни (многочлена $$P$$ ). При этом нам пригодится (пока что не использованная) операция дифференцирования.

Если в двух соседних старых корнях $$\alpha_1$$, $$\alpha_2$$ многочлен $$P$$ имеет один и тот же знак (скажем, положителен), то между ними нет нового корня. В самом деле, если бы на интервале $$(\alpha_1,\alpha_2)$$ многочлен $$P$$ обращался в нуль, то минимум многочлена $$P$$ на $$[\alpha_1,\alpha_2]$$ достигался бы в некоторой внутренней точке, в которой производная $$P'$$ равнялась бы нулю. Но производная $$P'$$ входит в множество $$F$$ и представлена в диаграмме, так что тогда $$\alpha_1$$ и $$\alpha_2$$ не были бы соседними корнями диаграммы.

Если в одной из точек $$\alpha_1$$ и $$\alpha_2$$ многочлен $$P$$ обращается в нуль, то на интервале $$(\alpha_1,\alpha_2)$$ он корней иметь не может (по теореме Ролля такой корень повлек бы за собой корень производной).

Наконец, если $$P(\alpha_1)$$ и $$P(\alpha_2)$$ имеют разные знаки, то по теореме о промежуточном значении многочлен $$P$$ имеет на интервале $$(\alpha_1,\alpha_2)$$ хотя бы один корень. При этом по уже понятным нам причинам (теорема Ролля) двух корней он иметь не может. Это позволяет вставить столбец для этого корня в диаграмму. При этом соответствующий интервал диаграммы разобьется на два, которые будут отличаться лишь в строке для многочлена $$P$$.

Осталось провести аналогичное рассуждение для лучей, стоящих с края диаграммы. Поведение многочлена $$P$$ на бесконечности определяется его старшим коэффициентом (который, напомним, не равен нулю — сейчас мы впервые используем это предположение). Поэтому если $$P$$ стремится, скажем, к $$+\infty$$ при $$x\to+\infty$$, а значение $$P$$ в самом правом корне было отрицательным, то на этом луче появляется новый корень (только один по теореме Ролля). Если же значение $$P$$ в самом правом корне равно нулю или имеет тот же знак, что и старший коэффициент, то мы повторяем рассуждение из предыдущего абзаца и убеждаемся, что корней $$P$$ на правом луче нет. Аналогично определяется и поведение $$P$$ слева от самого левого корня.

На этом доказательство леммы 2, а с ней и теоремы Тарского-Зайденбрега, завершается.

67. Докажите, что множество троек $$\langle p,q,r\rangle$$, при которых многочлен $$x^3+px^2+qx+r$$ имеет ровно два положительных корня, является полуалгебраическим.

Подобного рода задачи рассматривались в алгебре еще в прошлом веке (число перемен знака, правило Штурма и др.).

68. Докажите, что предикат $$x=\alpha$$, где $$\alpha$$ — некоторое действительное число, выразим тогда и только тогда, когда $$\alpha$$ является алгебраическим.

Разобравшись с действительными числами, можно перейти к комплексным. На самом деле (как часто бывает) здесь ситуация проще.

На комплексных числах нет естественного отношения порядка, поэтому рассмотрим сигнатуру $$({=},{0},{1},{+},{\times})$$. Будем, как всегда, считать две формулы эквивалентными, если они истинны при одних и тех же значениях параметров (в естественной интерпретации с носителем $$\mathbb C$$ ).

Теорема 34 (элиминация кванторов в поле комплексных чисел). Всякая формула этой сигнатуры эквивалентна бескванторной.

Эта теорема имеет много разных доказательств, но после доказательства теоремы Тарского-Зайденберга нам проще всего модифицировать его.

Теперь в диаграммах будут стоять не знаки $$-,0,+$$, а только знаки $$0$$ и $${\ne}0$$ (поскольку порядка на $$\mathbb C$$ нет). По той же причине мы не можем упорядочить корни, так что диаграмма будет состоять из неупорядоченных столбцов, соответствующих корням, и одного столбца, соответствующего дополнению к множеству корней (в котором будут стоять знаки $${\ne}0$$ для всех многочленов, кроме нулевых). Говоря о неупорядоченных столбцах, мы имеем в виду, что не различаем диаграммы, отличающиеся лишь порядком столбцов.

Основной шаг в доказательстве теоремы Тарского-Зайденберга (единственный, где важен порядок на действительных числах) состоял в пополнении диаграммы новым многочленом. Что будет с ним теперь?

Как и раньше, мы можем определить, в каких старых корнях новый многочлен равен нулю. Более того, мы можем определить кратность этих нулей, так как знаем все необходимое про его производные (которые уже включены в диаграмму). Поэтому основная теорема алгебры говорит нам, сколько будет новых корней (заметим, что все новые корни имеют кратность $$1$$, так как иначе они были бы корнями производной и не были бы новыми). Поскольку порядка на корнях нет, больше никакой информации нам и не нужно.

69. Провести доказательство элиминации кванторов в поле $$\mathbb C$$, не использующее диаграмм (это можно сделать, начав с приведения бескванторной формулы к дизъюнктивной нормальной форме, а затем применяя разные соображения из алгебры о наибольшем общем делителе многочленов). Для теоремы Тарского-Зайденберга это несколько сложнее; рассуждение такого рода приведено в книжке Энгелера [32]

70. Докажите, что множество тех четверок комплексных чисел $$\langle p,q,r,s\rangle$$, при которых многочлены $$z^2+pz+q=0$$ и $$z^2+rz+s=0$$ имеют общий корень, задается бескванторной формулой. Найти эту формулу.

Задача 70 хорошо знакома алгебраистам. Ответ в ней можно записать в виде $$R(p,q,r,s)=0$$, где $$R$$ — многочлен, называемый результантом и равный определителю матрицы$$\left| \begin{array}{cccc} 1 p q 0 \\ 0 1 p q \\ 1 r s 0 \\ 0 1 r s \end{array} \right|$$

71. Докажите, что множество всех пар комплексных чисел $$\langle p,q\rangle$$, при которых многочлен $$z^3+pz+q$$ имеет хотя бы один кратный корень, задается бескванторной формулой. Найти эту формулу. Как выглядит аналогичная формула для многочлена $$z^2+pz+q$$?

(Ответ к задаче тоже хорошо известен в алгебре; соответствующий многочлен называется дискриминантом.)

72. Обобщить утверждение предыдущей задачи на многочлены произвольной степени со старшим коэффициентом $$1$$ и найти выражение дискриминанта в виде определителя.

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

Пока что мы в основном использовали технику элиминации кванторов для какой-то одной интерпретации (формула заменялась на бескванторную, которая эквивалентна исходной в данной интерпретации). Однако, этот метод позволяет сравнивать различные интерпретации. Мы приведем несколько примеров такого рода.

Начнем с определения. Пусть фиксирована некоторая сигнатура $$\sigma$$. Две интерпретации этой сигнатуры называются элементарно эквивалентными, если в них истинны одни и те же замкнутые формулы этой сигнатуры.

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

Пусть $$M_1$$ и $$M_2$$ — две интерпретации сигнатуры $$\sigma$$. Биекция (взаимно однозначное отображение) $$\alpha\colon M_1\hm\to M_2$$ называется изоморфизмом этих интерпретаций, если она сохраняет все функции и предикаты сигнатуры. Это означает, что если $$P_1$$ и $$P_2$$ — два $$k$$ -местных предиката в $$M_1$$ и $$M_2$$, соответствующих одному предикатному символу сигнатуры, то$$P_1(a_1,\dots,a_k) \Leftrightarrow P_2(\alpha(a_1),\dots,\alpha(a_k))$$ для всех $$a_1,\dots,a_k\hm\in M_1$$. Аналогичное условие для функций: если $$k$$ -местные функции $$f_1$$ и $$f_2$$ соответствуют одному функциональному символу, то$$\alpha(f_1(a_1,\dots,a_k))=f_2(\alpha(a_1),\dots,\alpha(a_k))$$ для всех $$a_1,\dots,a_k\hm\in M_1$$.

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

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

73. Докажите, что тождественное отображение есть изоморфизм. Докажите, что отображение, обратное изоморфизму, есть изоморфизм. Докажите, что композиция двух изоморфизмов есть изоморфизм. (Отсюда следует, что отношение изоморфности есть отношение эквивалентности на интерпретациях данной сигнатуры.)

Теперь можно сформулировать и доказать обещанное утверждение:

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

Естественно доказывать это утверждение по индукции. Для этого его надо обобщить на произвольные формулы (не только замкнутые). Вот это обобщение: пусть $$\alpha\colon M_1\to M_2$$ — изоморфизм, а $$F$$ — произвольная формула нашей сигнатуры. Тогда она истинна в $$M_1$$ при оценке $$\pi$$ тогда и только тогда, когда она истинна в $$M_2$$ при оценке $$\alpha\circ\pi$$.

Обычно истинность формулы $$F$$ в интерпретации $$M$$ обозначают как $$M\vDash F$$. Если формула имеет параметры $$x_1,\dots,x_n$$, ее часто обозначают $$F(x_1,\dots,x_n)$$ ; при этом запись $$M\vDash F(m_1,\dots,m_n)$$ (где $$m_i\in M$$ ) означает, что формула $$F$$ истинна при оценке, которая ставит в соответствие параметру $$x_i$$ значение $$m_i$$. После всех этих приготовлений доказываемое по индукции утверждение можно записать так:$$M_1 \vDash F(a_1,\dots,a_n) \Leftrightarrow M_2 \vDash F(\alpha(a_1),\dots,\alpha(a_n))$$ для любой формулы $$F(x_1,\dots,x_n)$$ и для любых элементов $$a_1,\dots,a_n\hm\in M_1$$.

После такого обобщения доказательство по индукции становится очевидным.

74. В каком месте индуктивного рассуждения существенно, что $$\alpha$$ — взаимно однозначное соответствие? (Ответ: сюръективность $$\alpha$$ используется, когда мы рассматриваем формулу, начинающуюся с квантора существования, и из ее истинности в $$M_2$$ выводим истинность в $$M_1$$. Инъективность $$\alpha$$ не используется, но она автоматически следует из определения изоморфизма, если сигнатура содержит равенство и интерпретации нормальны, то есть равенство интерпретируется как совпадение элементов.)

75. Рассуждение, использованное при доказательстве теоремы 35, нам по существу уже встречалось. Где?

Изоморфные интерпретации — это по существу одна и та же интерпретация, только ее элементы названы по-разному. Интересны скорее примеры, когда интерпретации не изоморфны, но тем не менее элементарно эквивалентны. Один такой пример мы уже коротко обсуждали раньше, сформулируем его более подробно.

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

Для начала заметим, что эти интерпретации не изоморфны (поскольку мощности различны). Однако формулы этой сигнатуры допускают, как мы видели , элиминацию кванторов.При этом получающаяся формула будет эквивалентна исходной в обеих интерпретациях. Начав с замкнутой формулы, мы получим бескванторную формулу без переменных (или с фиктивными переменными, от значений которых ничего не зависит, тогда вместо них можно подставить, скажем, нули). Эта формула будет содержать только рациональные константы и потому будет одинаково истинной в $$\mathbb R$$ и в $$\mathbb Q$$.

Заметим, что при уменьшении сигнатуры элементарная эквивалентность сохраняется (по очевидным причинам), так что из теоремы 36 очевидно следует, что $$\mathbb R$$ и $$\mathbb Q$$ элементарно эквивалентны как упорядоченные множества (этот факт мы отмечали).

В этом примере элементарно эквивалентные, но не изоморфные структуры имеют различную мощность. В следующем примере это уже не так.

Теорема 37. Упорядоченные множества $$\mathbb Z$$ и $$\mathbb Z+\mathbb Z$$ (второе состоит из двух копий множества $$\mathbb Z$$, причем все элементы первой копии считаются меньшими всех элементов второй копии) элементарно эквивалентны как интерпретации сигнатуры $$({=},{<})$$.

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

76. Можно ли построить счетную интерпретацию сигнатуры $$(=,<)$$, в которой равенство интерпретируется как совпадение элементов (такие интерпретации называют нормальными), элементарно эквивалентную множеству $$\mathbb Q$$, но не изоморфную ему? Тот же вопрос для множества неотрицательных рациональных чисел. Почему существенна нормальность интерпретации?

77. Существует ли упорядоченное множество, элементарно эквивалентное упорядоченному множеству $$\mathbb R$$, но имеющее большую мощность?

78. Существуют ли два несчетных неизоморфных элементарно эквивалентных упорядоченных множества одинаковой мощности?

79. Будут ли упорядоченные множества $$\mathbb Z$$ и $$\mathbb Z\times\mathbb Z$$ (пары целых чисел; сравниваются сначала вторые компоненты пар, а при их равенстве — первые) изоморфны? элементарно эквивалентны?

80. Будет ли упорядоченное множество $$\mathbb N+\mathbb N$$ элементарно эквивалентно $$\mathbb N$$? Будет ли $$\mathbb N+\mathbb Z$$ элементарно эквивалентно $$\mathbb N$$?

Рассуждение, использованное при доказательстве теоремы Тарского-Зайденберга, также можно приспособить для доказательства элементарной эквивалентности. Сейчас мы рассмотрим более простой случай алгебраически замкнутых полей, соответствующий элиминации кванторов в $$\mathbb C$$ ; к вещественному случаю мы вернемся.

Поле называется алгебраически замкнутым, если всякий многочлен, отличный от константы, имеет в нем хотя бы один корень. (Отсюда легко следует, что любой многочлен разлагается на линейные множители.) Характеристикой поля называют минимальное число слагаемых в сумме вида $$1+1+\ldots+1$$, при котором она обращается в нуль. Если никакая сумма такого вида не равна нулю, то поле называют полем характеристики $$0$$.

В алгебраически замкнутых полях характеристики $$0$$ справедливы все обычные свойства многочленов с комплексными коэффициентами. В частности, корень является кратным тогда и только тогда, когда он будет корнем производной, сумма корней с учетом кратности равна степени многочлена и т. д. Это позволяет заметить, что все преобразования, которые выполнялись при элиминации кванторов, являются эквивалентными в произвольных алгебраически замкнутых полях характеристики $$0$$. Тем самым мы получаем такую теорему:

Теорема 38 (о полноте теории алгебраически замкнутых полей характеристики нуль) Любые два алгебраически замкнутых поля характеристики $$0$$ элементарно эквивалентны.

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

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

Теорему 38 можно несколько усилить. Для этого нам понадобится понятие "элементарного расширения".

Пусть фиксирована сигнатура $$\sigma$$ и две интерпретации этой сигнатуры с носителями $$M_1$$ и $$M_2$$. Пусть при этом $$M_1\hm\subset M_2$$ и интерпретации предикатных и функциональных символов в $$M_1$$ и $$M_2$$ согласованы, то есть на аргументах из $$M_1$$ символы интерпретируются одинаково. (Заметим, что отсюда следует замкнутость $$M_1$$ относительно сигнатурных операций.) В этом случае $$M_1$$ иногда называют подструктурой в $$M_2$$, а $$M_2$$ — расширением $$M_1$$.

Например, если мы рассматриваем группы как интерпретации сигнатуры $$({=},{\times},1, \text{обращение})$$, то подструктуры — это подгруппы.

82. Почему здесь важно, что операция обращения включена в сигнатуру?

Интерпретацию $$M_2$$ называют элементарным расширением ее подструктуры $$M_1$$, если выполнено такое свойство: для всякой (не обязательно замкнутой формулы) $$F$$ и для всякой оценки $$\pi$$ со значениями в $$M_1$$ формула $$F$$ истинна в $$M_1$$ на этой оценке тогда и только тогда, когда она истинна в $$M_2$$ на той же оценке.

В частности, если формула замкнута (не содержит параметров), то ее истинность не зависит от оценки и мы получаем, что $$M_1$$ и $$M_2$$ элементарно эквивалентны.

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

Нам понадобится такой пример: пусть имеется поле $$k_1$$ и его расширение $$k_2$$. Мы будем рассматривать поля $$k_1$$ и $$k_2$$ как две интерпретации сигнатуры $$({=},{+},{\times},0,1)$$. Пусть имеется некоторая система полиномиальных уравнений с несколькими переменными с коэффициентами из $$k_1$$. Тогда утверждение о том, что она имеет решение, записывается в виде формулы (содержащей кванторы существования по переменным и конъюнкцию уравнений; коэффициенты многочленов являются параметрами этой формулы). Поэтому если $$k_2$$ является элементарным расширением $$k_1$$, то всякая система уравнений с коэффициентами в $$k_1$$, имеющая решение в $$k_2$$, имеет решение и в $$k_1$$.

Теорема 39. Пусть $$k_1$$ — подполе поля $$k_2$$, причем оба они алгебраически замкнуты и имеют характеристику $$0$$. Тогда $$k_2$$ (как интерпретация указанной сигнатуры) является элементарным расширением интерпретации $$k_1$$.

В самом деле, элиминация кванторов преобразует любую формулу (с параметрами или без) в эквивалентную ей бескванторную, причем эквивалентность имеет место в обоих полях. А для бескванторной формулы ее истинность при оценке со значениями в $$k_1$$ никак не может зависеть от того, внутри какого поля эта истинность вычисляется.

Эту теорему называют теоремой о модельной полноте теории алгебраически замкнутых полей характеристики нуль. Из нее с учетом замечания перед ее формулировкой вытекает такой хорошо известный алгебраистам факт:

Теорема 40 (Гильберта о нулях). Всякая система полиномиальных уравнений с коэффициентами в алгебраически замкнутом поле характеристики нуль, имеющая решение в некотором расширении этого поля, имеет решение и в самом поле.

В самом деле, расширение можно еще расширить до алгебраически замкнутого (при этом решение не пропадет), а затем воспользоваться теоремой 39.

84. Другой вариант теоремы Гильберта о нулях формулируется так: пусть дана система уравнений$$\left\{ \begin{aligned} P_1(x_1,\dots,x_n)=0,\\ \dots\dots\dots\dots\dots\dots\\ P_k(x_1,\dots,x_n)=0, \end{aligned} \right.$$ где все $$P_i$$ — многочлены с комплексными коэффициентами, причем эта система не имеет решения в $$\mathbb C$$. Тогда можно найти такие многочлены $$Q_i(x_1,\dots,x_n)$$, что$$P_1(x_1,\dots,x_n)Q_1(x_1,\dots,x_n)+\ldots+ P_k(x_1,\dots,x_n)Q_k(x_1,\dots,x_n)$$ тождественно равно единице.

Выведите это утверждение из доказанного нами варианта теоремы Гильберта о нулях. (Указание: рассмотрим в кольце $$\bbC[x_1,\dots,x_n]$$ идеал, порожденный многочленами $$P_1,\dots,P_k$$ ; если он содержит единицу, то все доказано, если нет, то расширим его до максимального идеала $$I$$ ; тогда факторкольцо $$\mathbb C[x_1,\dots,x_n]/I$$ будет полем, расширяющим $$\mathbb C$$, и в этом поле классы многочленов $$x_1,\dots,x_n$$ составляют решение нашей системы.)

Страницы: