Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 23
Текст из файла (страница 23)
Итак, мы получили ответ на интересующий нас вопрос: выразимые в арифметике Пресбургера предикаты — это предикаты, выразимые бескванторными формулами, содержащими целые константы, сложение, равенство, отношение порядка и сравнения по любымфиксированным модулям.3.8. Теорема Тарского – ЗайденбергаВ этом разделе мы покажем, что в элементарной теории действительных чисел со сложением и умножением выполнима элиминациякванторов. Более точно, рассмотрим сигнатуру, содержащую предикаты = и <, константы 0 и 1, а также операции сложения и умножения.
Рассмотрим интерпретацию этой сигнатуры, носителем которойявляется множество действительных чисел, а предикаты и операции понимаются естественным образом. Тогда для каждой формулы существует эквивалентная (выражающая тот же предикат) бескванторная формула. Это утверждение называют теоремой Тарского – Зайденберга.Прежде чем доказывать эту теорему, сделаем несколько комментариев:• Свойство x < y можно выразить как «существует ненулевое z,для которого x+z 2 = y». Таким образом, класс выразимых предикатов не изменится, если мы удалим символ < из сигнатуры.(Но предикатов, выразимых бескванторными формулами, станет меньше: свойство x > 0, как легко понять, не эквивалентноникакой бескванторной формуле, содержащей константы, сложение, умножение и равенство.)• Бескванторную формулу нашей сигнатуры можно привести кдизъюнктивной нормальной форме, после чего она превратится в совокупность систем уравнений вида P = 0 и неравенстввида P > 0.
В самом деле, в конъюнкциях могут ещё быть отрицания, то есть отношения 6= и >, но можно разбить P 6= 0на (P < 0) ∨ (P > 0), а P > 0 на (P = 0) ∨ (P > 0), после чеговоспользоваться дистрибутивностью.• Подмножества Rn , задаваемые уравнениями вида P = 0 инеравенствами вида P > 0 (где P — произвольный многочленот нескольких переменных с целыми коэффициентами), а также множества, получаемые из них конечным числом операций102Языки первого порядка[гл. 3]объединения и пересечения, называют полуалгебраическими.Из предыдущего замечания видно, что всякая бескванторнаяформула задаёт полуалгебраическое множество.
(Полуалгебраические множества являются обобщениями алгебраическихмножеств, задаваемых системами полиномиальных уравнений.)• Из теоремы Тарского – Зайденберга вытекает, что проекция полуалгебраического множества A ⊂ Rn вдоль одной из осей будет полуалгебраическим подмножеством в Rn−1 . В самом деле, переход к проекции соответствует добавлению квантора существования, который можно затем элиминировать. (Утверждение о полуалгебраичности проекции полуалгебраическогомножества по существу равносильно теореме Тарского – Зайденберга, так как элиминация квантора существования является единственным нетривиальным шагом в доказательстве этойтеоремы.)• Пример: равенство x2 +px+q = 0 задаёт полуалгебраическое (идаже алгебраическое) множество троек hx, p, qi.
Какова будетего проекция вдоль оси x на плоскость p, q? Как учат в школе,это будет множество p2 − 4q > 0, которое оказывается полуалгебраическим в полном согласии с теоремой Тарского – Зайденберга. Про аналогичные критерии разрешимости уравненийбольшей степени в школе не учат, но теорема Тарского – Зайденберга гарантирует их существование.• Как и во всех предыдущих случаях элиминации кванторов,преобразование формулы в бескванторную формулу эффективно (выполняется некоторым алгоритмом). В частности, этоталгоритм можно применить к замкнутой формуле (формулебез параметров).
Тогда получится бескванторная формула безпараметров (формально говоря, там могут быть параметры,от значений которых ничего не зависит, но их можно заменить, скажем, нулями). Истинность такой формулы можно алгоритмически проверить. Тем самым можно алгоритмическипроверить истинность любого утверждения о действительныхчислах, выраженного формулой нашей сигнатуры. Как говорят, элементарная теория действительных чисел со сложениеми умножением разрешима.[п.
8]Теорема Тарского – Зайденберга103• Большинство утверждений школьного курса геометрии с помощью метода координат можно записать как утверждения одействительных числах в нашей сигнатуре. (Исключение, впрочем, составляют утверждения, где речь идёт не о треугольниках и четырёхугольниках, а о n-угольниках без указания конкретного n). Записав теоремы в виде замкнутых формул нашейсигнатуры, можно алгоритмически проверить их истинность.Тем самым мы получаем общий метод доказательства большинства теорем школьной геометрии (впрочем, он имеет лишьтеоретическое значение, так как алгоритм работает необозримодолго на сколько-нибудь сложных формулах).Теорема 33 (Тарского – Зайденберга).
Для всякой формулы сигнатуры (=, <, 0, 1, +, ×) существует бескванторная формула, задающаятот же предикат на множестве действительных чисел. Как обычно, достаточно рассматривать формулу с единственным квантором существования, то есть формулу ϕ вида∃x B(x, x1 , . . . , xn ),где B(x, x1 , . . . , xn ) — бескванторная формула, включающая в себятолько переменные из числа x, x1 , . .
. , xn . Надо доказать, что найдётся эквивалентная формуле ϕ бескванторная формула B 0 (x1 , . . . , xn ).Посмотрим на атомарные формулы, входящие в формулу B. Перенося все переменные в одну часть, можно считать, что все ониимеют вид P (x, x1 , . . . , xn ) = 0 или P (x, x1 , . . . , xn ) > 0, где P — некоторый многочлен с целыми коэффициентами. Кольцо многочленовс целыми коэффициентами от переменных x, x1 , . . . , xn обозначаетсячерез Z[x, x1 , . .
. , xn ]. Группировка членов по степеням x даёт многочлен от x, коэффициенты которого представляют собой многочленыот x1 , . . . , xn . Символически это записывается так:Z[x, x1 , . . . , xn ] = (Z[x1 , . . . , xn ])[x](многочлены от n + 1 переменных можно рассматривать как многочлены от одной переменной, коэффициенты которых лежат в кольцемногочленов от n переменных).При фиксации значений переменных x1 , . . . , xn входящие в Bмногочлены превращаются в многочлены от одной переменной x счисловыми коэффициентами.
Формула ϕ выражает тогда какое-тосвойство этих многочленов и может быть истинной или ложной. Нам104Языки первого порядка[гл. 3]надо доказать, что те hx1 , . . . , xn i, при которых она истинна, образуют полуалгебраическое множество.Для этого введём понятие диаграммы семейства многочленов.Пусть Q1 (x), . . . , Qk (x) — многочлены от x с действительными коэффициентами. Диаграммой набора Q1 , . . .
, Qk будет таблица, которая строится так. Возьмём все корни всех многочленов Qi (несчитая нулевых многочленов) и расположим их в порядке возрастания. Получим некоторый набор чисел α1 < α2 < . . . < αm . Этичисла разбивают числовую ось на m + 1 промежутков (два луча иm − 1 интервалов), на каждом из которых знаки всех Qi постоянны.Составим таблицу, в которой будет k строк (по одной для каждого из многочленов) и 2m + 1 столбцов, соответствующих m корнями m + 1 промежуткам (столбцы идут в порядке возрастания, такчто корни чередуются с промежутками). В каждой ячейке таблицызапишем один из трёх символов +, − или 0 в зависимости от того, является ли многочлен положительным, отрицательным или нулевымна соответствующем промежутке (или в соответствующем корне).Пример.
Выпишем диаграмму для системы многочленов x2 − 1,x, 0. Корнями здесь будут числа −1, 0, 1, так что столбцы соответствуют четырём промежуткам и трём разделяющим их корням.h−1i2x −1 +x −0 00−0h0i−−0−00h1i−+00+0++0Отметим, что значения корней не являются частью диаграммы, такчто, например, система многочленов x2 − 4, 2x − 1, 0 имеет точнотакую же диаграмму.Если ни один из многочленов не имеет корней, то они сохраняютзнак на всей прямой, и диаграмма состоит из единственного столбца,в котором записаны все эти знаки.Теперь рассмотрим многочлены Q1 , . .
. , Qk ∈ Z[x, x1 , . . . , xn ]. Прификсированных значениях переменных x1 , . . . , xn мы получаем набор многочленов от одной переменной с действительными коэффициентами и можем построить его диаграмму. Эта диаграмма будетзависеть от выбора значений x1 , . . . , xn . Число строк в диаграммеравно k, а ширина её зависит от числа различных корней и можетменяться, однако во всех случаях не превосходит 2N + 1, где N —сумма степеней всех многочленов (рассматриваются степени по x, то[п.
8]Теорема Тарского – Зайденберга105есть степени соответствующих многочленов от x с коэффициентамив Z[x1 , . . . , xn ]).Таким образом, число возможных диаграмм конечно, и пространство Rn возможных значений переменных x1 , . . . , xn разбивается наконечное число частей: каждая часть соответствует одному из возможных значений диаграммы.Для доказательства теоремы Тарского – Зайденберга достаточнодоказать, что эти части будут полуалгебраическими множествами.В самом деле, если в качестве многочленов Q1 , . . .
, Qk взять многочлены, входящие в формулу B(x, x1 , . . . , xn ), то область истинностиформулыϕ = ∃x B(x, x1 , . . . , xn )будет объединением нескольких частей соответствующего разбиения. В самом деле, если мы двигаем точку hx1 , . . . , xn i в пределаходной части разбиения, то диаграмма не меняется, значит, и истинность формулы ϕ не меняется (по диаграмме можно определить истинность формулы, перепробовав значения x, соответствующие всемстолбцам).Итак, нам осталось доказать, что для любого набора многочленов Q1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
