Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 22

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 22)

. . + cn xn + c0 = 0 и c1 x1 + . . . ++ cn xn + c0 > 0 с различными рациональными коэффициентами. Посмотрим на все выражения, стоящие в левой части таких равенств[п. 6]Элиминация кванторов97и неравенств. Подставим в них числа x1 , . . . , xn , соответствующиеданному нам разрезанию. При этом получится истинная формулаF (x1 , . . . , xn ), в которой некоторые из левых частей равенств и неравенств будут равны нулю, а другие нет. Временно забудем про те,которые не равны нулю, а равные нулю будем воспринимать каклевые части уравнений с неизвестными x1 , .

. . , xn (с нулём в правой части) независимо от того, входили ли они в F как левые частиуравнений или неравенств. Получится система уравнений, для которой числа x1 , . . . , xn будут решениями. Если эти числа являютсяединственными её решениями, то они рациональны (например, потому, что правила Крамера для решения системы уравнений содержатотношения определителей с рациональными элементами). Покажем,что другого быть не может.В самом деле, если решение не единственно, то есть целая прямая, проходящая через точку x = hx1 , . . .

, xn i и лежащая в множестве решений системы. Все точки прямой, достаточно близкие кx, неотличимы от x с точки зрения формулы F и потому делаютформулу F истинной. В самом деле, левые части, равные нулю вx, равны нулю на всей прямой, а левые части, отличные от нуля вточке x, сохраняют знак в некоторой окрестности этой точки. Пустьhh1 , . . . , hn i — направляющий вектор этой прямой.

Тогда при всехдостаточно малых значениях t из квадратов размеровx1 + th1 , x2 + th2 , . . . , xn + thnможно составить единичный квадрат. Но это невозможно. Чтобыубедиться в этом, достаточно оставить логику и вернуться к геометрии: площади этих квадратов в сумме должны равняться 1, ноплощадь каждого есть многочлен второй степени по t, и коэффициент при t2 положителен, поэтому сумма таких многочленов не можеттождественно равняться единице ни на каком интервале. Насколько существенна в этом рассуждении ссылка на возможность элиминации кванторов? В принципе можно было бы рассуждать так. Пусть дано разрезание квадрата. Посмотрим на конфигурацию, образуемую меньшими квадратами, и напишем равенстваи неравенства на размеры частей, которые гарантируют, что в этойконфигурации нет щелей и перекрытий.

(Далее продолжаем рассуждение как раньше.) Конечно, возникает вопрос: почему мы уверены,что такую систему уравнений и неравенств можно написать? Глядяна конкретную конфигурацию, это сделать легко, но как провестиэто рассуждение строго для общего случая, не вполне понятно.98Языки первого порядка[гл. 3]Изложенные методы позволяют провести элиминацию кванторови описать выразимые множества во многих ситуациях; несколькопростых примеров такого рода предлагаются в качестве задач.

Дваболее сложных примера (арифметика Пресбургера и теория сложения и умножения действительных чисел) разбираются в двух следующих разделах.66. Описать выразимые предикаты, проведя элиминацию кванторов (ирасширив сигнатуру, если нужно) для (а) (M, =), где M — произвольноебесконечное множество; (б) (Q, =, +); (в) (Q, =, S), где S — операция прибавления единицы; (г) (N, =, S), где S — операция прибавления единицы;(д) (N, =, S, P ), где S — операция прибавления единицы, а P — одноместный предикат «быть степенью двойки».3.7. Арифметика ПресбургераСейчас мы опишем выразимые множества в (Z, =, <, +, 0, 1). Отметим сразу, что с такой сигнатурой элиминация кванторов невозможна.

В самом деле, формула ∃y (x = y + y), истинная для чётных x, не эквивалентна никакой бескванторной формуле. Поэтомунам нужно, прежде чем проводить элиминацию кванторов, расширить сигнатуру. Приведённый пример формулы подсказывает, какое расширение нам необходимо. Рассмотрим счётное семейство двуместных предикатных символов ≡2 , ≡3 , ≡4 , . .

. Символ ≡c будет интерпретироваться как равенство по модулю c. Другими словами,формула x ≡c y будет истинна, если x сравнимо с y по модулю c(остатки по модулю c равны; x − y кратно c).Важно иметь в виду, что индекс c в x ≡c y не является переменной: у нас не трёхместный предикат, а счётное семейство двуместныхпредикатов.Такое расширение не меняет класса выразимых предикатов, поскольку, например, x ≡3 y можно выразить как ∃z (x = y + z + z + z).Зато после этого всякая формула эквивалентна бескванторной, какпоказывает следующая теорема (называемая теоремой об элиминации кванторов в арифметике Пресбургера).Теорема 32. В hZ, =, <, +, 0, 1, ≡2 , ≡3 , .

. . i выполнима элиминациякванторов. Мы будем применять метод, опробованный в предыдущем разделе: выбор представительного множества термов (после некоторыхпреобразований формулы).Напомним, как это делается. Мы хотим доказать, что всякаяформула эквивалентна бескванторной. Рассуждая по индукции, мы[п. 7]Арифметика Пресбургера99должны лишь проверить, что всякая формула вида∃x τ (x, x1 , .

. . , xn ),где τ (x, x1 , . . . , xn ) обозначает бескванторную формулу, все переменные которой содержатся среди x, x1 , . . . , xn , эквивалентна некоторойбескванторной формуле (с теми же переменными, не считая x).Посмотрим, какие атомарные формулы содержат переменную xи входят в τ . Перенося члены в одну сторону, эти атомарные формулы можно записать в одном из трёх видов: L(x, x1 , . . .

, xn ) = 0,L(x, x1 , . . . , xn ) > 0 или L(x, x1 , . . . , xn ) ≡ c 0, где L(x, x1 , . . . , xn )представляет собой линейную комбинацию переменных x, x1 , . . . , xnс целыми коэффициентами и целочисленным свободным членом. (Вотличие от ситуации в Q, здесь нельзя делить на коэффициент приx.) Перенося x в левую часть, а всё остальное — в правую, получаемсоотношение одного из четырёх видов:kx = l(x1 , . . .

, xn );kx < l(x1 , . . . , xn );kx > l(x1 , . . . , xn );kx ≡c l(x1 , . . . , xn ),где k — положительное целое число (разное для разных атомарныхформул), а l — линейная комбинация переменных x1 , . . . , xn с целыми коэффициентами и свободным членом.Как мы говорили, коэффициенты в левой части (а также, разумеется, правые части) у разных атомарных формул разные.

Однакомы можем их унифицировать, перейдя к общему кратному. В самомделе, неравенства и равенства можно умножать на число, сравнения — тоже, если модуль сравнения (индекс c в ≡c ) умножить на тоже самое число. Поэтому можно считать, что наша формула имеетвид ∃x τ (kx, x1 , . .

. , xn ), понимая под этим, что x появляется тольков левых частях и везде с коэффициентом k. Такую формулу можнопереписать как∃y (τ (y, x1 , . . . , xn ) ∧ (y ≡k 0)).Таким образом, без ограничения общности можно считать, что k = 1,поскольку новая формула имеет тот же самый вид∃y τ (y, x1 , .

. . , xn ),100Языки первого порядка[гл. 3]что и исходная, но уже безо всякого коэффициента при y (и с модифицированной формулой τ ). Пусть l1 , . . . , lk — выражения, стоящиев правых частях равенств, неравенств и сравнений с левой частью y.Мы хотим, как и в предыдущем разделе, указать представительный набор значений Y1 , . .

. , YN . Каждое из Yi представляет собойлинейную комбинацию переменных x1 , . . . , xn с целыми коэффициентами и свободным членом. «Представительность» означает, что если для каких-то x1 , . . . , xn найдётся y, для которого τ (y, x1 , . . . , xn ),то такой y можно найти и среди значений Y1 , . . . , YN (при тех жеx1 , . .

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

. , xn найдётся некоторое y, для которого τ (y, x1 , . . . , xn ). Посмотрим, какие значения принимают правые части равенств и неравенств при данных x1 , . . . , xn . Если значение y попало в объединение D-окрестностей этих значений, то доказывать нечего. Если же нет, начнём смещать y, двигаясь шагамиразмера D в направлении какой-то точки из этого объединения.

Миновать мы её не можем (ширина окрестности равна 2D, а размершага равен D), поэтому в какой-то момент мы впервые попадём вэто объединение. Обозначим эту точку (первую попавшую в объединение) через y 0 . Тогда y 0 при подстановке в τ даёт те же самыерезультаты, что и y. В самом деле, для сравнений это гарантировано, потому что сдвиг кратен модулю сравнений. Но это верно идля равенств и неравенств, поскольку на предыдущем шаге мы были вне D-окрестности всех правых частей и потому не могли перейтис одной стороны на другую.Таким образом, среди представительного набора есть значение(а именно, y 0 ), удовлетворяющее формуле τ , что и требовалось до-[п. 8]Теорема Тарского – Зайденберга101казать.

Характеристики

Список файлов книги