Выразимость в арифметике

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

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

Выразимость в арифметике

Рассмотрим сигнатуру, имеющую два двуместных функциональных символа — сложение и умножение (как обычно, мы будем писать $$x+y$$ вместо $$+(x,y)$$ и т. д.) и двуместный предикатный символ равенства. Рассмотрим интерпретацию этой сигнатуры, носителем которой является множество $$\mathbb{N}$$ натуральных чисел, а сложение, умножение и равенство интерпретируются стандартным образом.

Выразимые с помощью формул этой сигнатуры предикаты называются арифметическими и играют в математической логике важную роль. Соответствующие множества также называются арифметическими. О них подробно рассказано в другой нашей книжке [5]; оказывается, что почти всякое множество, которое можно описать словами, является арифметическим.

58. Докажите, что существует множество натуральных чисел, не являющееся арифметическим. (Указание: семейство всех подмножеств множества $$\mathbb{N}$$ несчетно, а арифметических множеств счетное число.)

Для начала мы установим арифметичность довольно простых предикатов.

Предикат $$x\le y$$ является арифметическим. В самом деле, его можно записать как $$\exists z\, (x+z=y)$$.

Предикаты $$x=0$$ и $$x=1$$ являются арифметическими. В самом деле, $$x=0$$ тогда и только тогда, когда $$x\le y$$ для любого $$y$$ (а также когда $$x+x=x$$ ). А $$x=1$$ тогда и только тогда, когда $$x$$ представляет собой наименьшее число, отличное от нуля. (Можно также воспользоваться тем, что $$y\cdot 1=y$$ при любом $$y$$.)

Вообще для любого фиксированного числа $$c$$ предикат $${x=c}$$ является арифметическим. (Например, можно написать сумму из большого числа единиц.)

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

Предикат $$x|y$$ (число $$x$$ является делителем числа $$y$$ ), очевидно, арифметичен (формула $$\exists z\, (xz=y)$$ ).

Предикат " $$x$$ — простое число" арифметичен. В самом деле, число просто, если оно отлично от $$1$$ и любой его делитель равен $$1$$ или самому числу. Это сразу же записывается в виде формулы.

Операции частного и остатка арифметичны (в том смысле, что трехместные предикаты " $$q$$ есть частное при делении $$a$$ на $$b$$ " и " $$r$$ есть остаток при делении $$a$$ на $$b$$ " арифметичны. Например, первый из них записывается формулой $$\exists r\, ((a=bq+r)\land (r<b))$$ (как мы уже говорили, использование арифметического предиката $$(r<b)$$ не создает проблем).

Этот список можно продолжать: для многих предикатов их определение по существу уже является нужной формулой. Например, свойства "быть наибольшим общим делителем", "быть наименьшим общим кратным", "быть взаимно простыми" все относятся к этой категории.

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

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

Два наиболее известных способа доказывать арифметичность основаны на возможности "кодирования" конечных множеств и последовательностей. Один восходит к Геделю (так называемая $$\beta$$ -функция Геделя), второй изложен в книге "Теория формальных систем" [24]. Ее написал Р.Смаллиан, известный также как автор популярных сборников "логических задач" и анекдотов. (Один из таких сборников имеет парадоксальное название "Как же называется эта книга?" [23].)

В некоторых отношениях метод Геделя предпочтительней, и мы рассказываем о нем в книжке о вычислимых функциях [5], но сейчас для разнообразия рассмотрим другой способ. Зафиксируем взаимно однозначное соответствие между натуральными числами и двоичными словами:$$\begin{array}{cccccccccc} 0 1 2 3 4 5 6 7 8\dots \\ \Lambda 0 1 00 01 10 11 000 001 \ldots \end{array}$$ Это соответствие задается так: чтобы получить слово, соответствующее числу $$n$$, надо записать $$n+1$$ в двоичной системе и удалить первую единицу. Например, нулю соответствует пустое слово $$\Lambda$$, числу $$15$$ — слово $$0000$$ и т. д. Теперь можно говорить об арифметичности предикатов, определенных на двоичных словах, имея в виду арифметичность соответствующих предикатов на $$\mathbb{N}$$.

Предикат "слово $$x$$ состоит из одних нулей" арифметичен. В самом деле, при переходе к числам ему соответствует предикат " $$x+1$$ есть степень двойки", который (как мы видели) арифметичен.

Предикат "слова $$x$$ и $$y$$ имеют одинаковую длину" арифметичен. В самом деле, это означает, что найдется степень двойки $$c$$, для которой $$c-1\hm\le x,y\hm<2c-1$$ (именно такой промежуток заполняют числа, которым соответствуют слова одной длины).

Предикат "слово $$z$$ является конкатенацией слов $$x$$ и $$y$$ " (проще говоря, $$z$$ получается приписыванием $$y$$ справа к слову $$x$$ ) арифметичен. В самом деле, его можно выразить так: найдется слово $$y'$$ из одних нулей, имеющее ту же длину, что и слово $$y$$, при этом $$(z+1)\hm=(x+1)(y'+1)+(y-y')$$ (умножение на $$y'+1$$ соответствует дописыванию нулей, а добавление $$y-y'$$ заменяет нули на буквы слова $$y$$ ).

Предикат "слово $$x$$ является началом слова $$y$$ " арифметичен. В самом деле, это означает, что существует слово $$t$$, при котором $$y$$ есть конкатенация $$x$$ и $$t$$.

То же самое верно для предикатов " $$x$$ есть конец слова $$y$$ ", " $$x$$ есть подслово слова $$y$$ " (последнее означает, что найдутся слова $$u$$ и $$v$$, для которых $$y$$ есть конкатенация $$u$$, $$x$$ и $$v$$ ; конкатенация трех слов выразима через конкатенацию двух).

Существует арифметический трехместный предикат $$S(x,a,b)$$ с такими свойствами: (а) для любых $$a$$ и $$b$$ множество $$S_{ab}=\{x\mid S(x,a,b)\}$$ конечно; (б) среди множеств $$S_{ab}$$ при различных парах $$a,b$$ встречаются все конечные множества. Например, в качестве такого предиката можно взять " $$axa$$ есть подслово слова $$b$$ " (здесь $$axa$$ есть конкатенация трех слов: $$a$$, $$x$$ и снова $$a$$ ).

В самом деле, ясно, что слово $$x$$ не длиннее слова $$b$$, и потому множество $$S_{ab}$$ всегда конечно. С другой стороны, пусть имеется некоторое конечное множество слов $$x_1,\dots, x_n$$. Положим $$a=100\dots001$$, где число нулей больше длины любого из слов $$x_i$$, и $$b\hm=ax_1ax_2a\dots ax_na$$.

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

Теперь мы можем выразить, что число $$x$$ является степенью числа $$4$$, следующим образом: существует конечное множество $$U$$, которое содержит число $$x$$ и обладает таким свойством: всякий элемент $$u\in U$$ либо равен $$1$$, либо делится на $$4$$ и $$u/4$$ также принадлежит $$U$$. Теперь надо везде заменить множество $$U$$ на его код $$u_1,u_2$$, а утверждение $$x\in U$$ на $$S(x,u_1,u_2)$$, где $$S$$ — построенный нами кодирующий предикат.

Немного сложнее выразить двуместный предикат $$x\hm=4^k$$. Здесь нам хотелось бы сказать так: существует последовательность $$x_0,x_1,\dots,x_k$$, для которой $$x_0=1$$, каждый следующий член вчетверо больше предыдущего ( $$x_{i+1}\hm=4x_i$$ ) и $$x_k\hm= x$$. Как научиться говорить о последовательностях, если мы умеем говорить о множествах? Вспомним, что в терминах теории множеств последовательность есть функция, определенная на начальном отрезке натурального ряда, то есть конечное множество пар $$\{\langle 0,x_0\rangle, \langle 1, x_1\rangle,\dots, \langle k, x_k\rangle\}$$. Пары можно кодировать числами. Например, можно считать кодом пары $$\langle x,y\rangle$$ число $$c\hm=(x+y)^2+x$$, поскольку по нему арифметически восстанавливается $$x+y$$ (как наибольшее число, квадрат которого не превосходит $$c$$ ), а затем $$x$$ и $$y$$. Теперь конечное множество пар можно заменить конечным множеством их кодов, которое в свою очередь можно закодировать парой чисел.

59. Проведите это рассуждение подробно.

60. Покажите, что двуместный предикат " $$x$$ есть $$n$$ -ое по порядку простое число" арифметичен.

Невыразимые предикаты: автоморфизмы

Мы видели, как можно доказать выразимость некоторых свойств. Сейчас мы покажем, каким образом можно доказывать невыразимость.

Начнем с такого примера. Пусть сигнатура содержит двуместный предикат равенства ( $$=$$ ) и двуместную операцию сложения ( $$+$$ ). Рассмотрим ее интерпретацию, носителем которой являются целые числа, а равенство и сложение интерпретируются стандартным образом. Оказывается, что предикат $${x>y}$$ не является выразимым.

Причина очевидна: с точки зрения сложения целые числа устроены симметрично, положительные ничем не отличаются от отрицательных. Если мы изменим знак у всех переменных, входящих в формулу, то ее истинность не может измениться. Но при этом $$x>y$$ заменится на $$x<y$$, и потому это свойство не является выразимым.

Формально говоря, надо доказывать по индукции такое свойство: если формула $$\varphi$$ указанной сигнатуры истинна при оценке $$\pi$$, то она истинна и при оценке $$\pi'$$, в которой значения всех переменных меняют знак. (Подробно мы объясним это в общей ситуации дальше.)

Сформулируем общую схему, которой следует это рассуждение. Пусть имеется некоторая сигнатура $$\sigma$$ и интерпретация этой сигнатуры, носителем которой является множество $$M$$. Взаимно однозначное отображение $$\alpha\colon M\to M$$ называется автоморфизмом интерпретации, если все функции и предикаты, входящие в интерпретацию, устойчивы относительно $$\alpha$$. При этом $$k$$ -местный предикат $$P$$ называется устойчивым относительно $$\alpha$$, если$$P(\alpha(m_1),\dots,\alpha(m_k)) \Leftrightarrow P(m_1,\dots, m_k)$$ для любых элементов $$m_1,\dots,m_k\hm\in M$$. Аналогичным образом $$k$$ -местная функция $$f$$ называется устойчивой относительно $$\alpha$$, если$$f(\alpha(m_1),\dots,\alpha(m_k))= \alpha(f(m_1,\dots, m_k)).$$ Это определение обобщает стандартное определение автоморфизма для групп, колец, полей и т. д.

Теорема 27. Предикат, выразимый в данной интерпретации, устойчив относительно ее автоморфизмов.

Проведем доказательство этого (достаточно очевидного) утверждения формально.

Пусть $$\pi$$ — некоторая оценка, то есть отображение, ставящее в соответствие всем индивидным переменным некоторые элементы носителя. Через $$\alpha\circ\pi$$ обозначим оценку, которая получится, если к значению каждой переменной применить отображение $$\alpha$$ ; другими словами, $$\alpha\circ\pi(\xi)=\alpha(\pi(\xi))$$ для любой переменной $$\xi$$.

Первый шаг состоит в том, чтобы индукцией по построению терма $$t$$ доказать такое утверждение: значение терма $$t$$ при оценке $$\alpha\circ\pi$$ получается применением $$\alpha$$ к значению терма $$t$$ при оценке $$\pi$$:$$[t](\alpha\circ\pi)=\alpha([t](\pi)).$$ Для переменных это очевидно, а шаг индукции использует устойчивость всех функций интерпретации относительно $$\alpha$$.

Теперь индукцией по построению формулы $$\varphi$$ легко доказать такое утверждение:$$[\varphi](\alpha\circ\pi) = [\varphi] (\pi).$$ Мы не будем выписывать эту проверку; скажем лишь, что взаимная однозначность $$\alpha$$ используется, когда мы разбираем случай кванторов. (В самом деле, если с одной стороны изоморфизма берется какой-то объект, то взаимная однозначность позволяет взять соответствующий ему объект с другой стороны изоморфизма.)

Теорема 27 позволяет доказать невыразимость какого-то предиката, предъявив автоморфизм интерпретации, относительно которого интересующий нас предикат неустойчив. Вот несколько примеров:

$$(\mathbb{Z},{=},{<})$$ Сигнатура содержит равенство и отношение порядка. Интерпретация: целые числа. Невыразимый предикат: $$x=0$$. Автоморфизм: $$x\mapsto x+1$$.

$$(\mathbb{Q},{=},{<},{+})$$ Сигнатура содержит равенство, отношение порядка и операцию сложения. Интерпретация: рациональные числа. Невыразимый предикат: $$x=1$$. Автоморфизм: $$x\hm\mapsto 2x$$.

Заметим, что сложение позволяет выразить предикат $$x=0$$. Кроме того, отметим, что вместо рациональных чисел можно взять действительные (но не целые, так как в этом случае единица описывается как наименьшее число, большее нуля).

$$(\mathbb{R},{=},{<},0,1)$$ Сигнатура содержит равенство, порядок и константы $$0$$ и $$1$$. Интерпретация: действительные числа. Невыразимый предикат: $$x=1/2$$. (Автоморфизм упорядоченного множества $$\mathbb{R}$$, сохраняющий $$0$$ и $$1$$, но не $$1/2$$, построить легко.)

$$(\mathbb{R},{=},{+}, 0, 1)$$ Сигнатура содержит равенство, сложение, константы $$0$$ и $$1$$. Интерпретация: действительные числа. Одноместный предикат $$x=\gamma$$ выразим для рациональных $$\gamma$$ и невыразим для иррациональных $$\gamma$$.

В самом деле, выразимость для рациональных $$\gamma$$ очевидна. Невыразимость для иррациональных $$\gamma$$ следует из того, что для любых двух иррациональных $$\gamma_1$$ и $$\gamma_2$$ существует автоморфизм, переводящий $$\gamma_1$$ в $$\gamma_2$$. (В самом деле, рассмотрим $$\mathbb{R}$$ как бесконечномерное векторное пространство над $$\mathbb{Q}$$. Векторы $$1,\gamma_1$$ линейно независимы и потому их можно дополнить до базиса Гамеля (подробности смотри в книжке по теории множеств [6]). Сделаем то же самое с векторами $$1,\gamma_2$$. Получатся равномощные базисы, после чего мы берем $$\mathbb{Q}$$ -линейный оператор, переводящий $$1$$ в $$1$$ и $$\gamma_1$$ в $$\gamma_2$$.)

$$(\mathbb{C},{=},{+},{\times},0,1)$$ В сигнатуру входят предикат равенства, операции сложения и умножения, а также константы $$0$$ и $$1$$. Интерпретация: комплексные числа. Предикат $$x=\gamma$$, где $$\gamma$$ — некоторое комплексное число, выразим для рациональных $$\gamma$$ и невыразим для иррациональных $$\gamma$$.

В самом деле, если $$\gamma$$ иррационально, то оно может быть алгебраическим или трансцендентным. В первом случае рассмотрим многочлен из $$\mathbb{Q}[x]$$ минимальной степени, обращающийся в $$0$$ в точке $$\gamma$$ ; по предположению он имеет степень больше $$1$$ и потому имеет другой корень $$\gamma'$$. В алгебре доказывается (с использованием трансфинитной индукции или леммы Цорна, а также базисов трансцендентности), что существует автоморфизм $$\mathbb{C}$$ над $$\mathbb{Q}$$, переводящий $$\gamma$$ в $$\gamma'$$.

В случае трансцендентного $$\gamma$$ мы используем такой факт: для любых трансцендентных $$\gamma_1, \gamma_2\hm\in\mathbb{C}$$ существует автоморфизм поля $$\mathbb{C}$$ над $$\mathbb{Q}$$, который переводит $$\gamma_1$$ в $$\gamma_2$$.

Отметим, что для поля $$\mathbb{R}$$ вместо $$\mathbb{C}$$ такое рассуждение не проходит, так как это поле не имеет нетривиальных автоморфизмов. (Отношение порядка выразимо: положительные числа суть квадраты, поэтому любой автоморфизм сохраняет порядок. Поскольку автоморфизм оставляет на месте все рациональные числа, он должен быть тождественным.)

В этом случае предикат $$x=\gamma$$ выразим тогда и только тогда, когда $$\gamma$$ — алгебраическое число. Это легко следует из теоремы Тарского-Зайденберга.

61. Покажите, что предикат $$y=x+1$$ невыразим в интерпретации $$(\mathbb{Z}, {=}, f)$$, где $$f$$ — одноместная функция $$x\hm\mapsto(x+2)$$.

62. Покажите, что предикат $$x=2$$ невыразим в множестве целых положительных чисел с предикатами равенства и " $$x$$ делит $$y$$ ".

Элиминация кванторов: элиминация кванторов

При всей простоте метод доказательства невыразимости с помощью автоморфизмов страдает очевидным недостатком: очень часто требуемого автоморфизма нет. Например, натуральные числа с операцией прибавления единицы вообще не допускают никакого нетривиального автоморфизма. (Тем не менее там выразимо очень немногое, как мы вскоре увидим.) Целые числа с операцией прибавления единицы допускают автоморфизмы (сдвиги), но эти автоморфизмы не позволяют доказать, что отношение порядка невыразимо (поскольку оно устойчиво относительно сдвигов).

Более прямой метод доказательства состоит в том, что мы предъявляем некоторый класс $$\mathcal{E}$$ предикатов, который содержит все выразимые предикаты и не содержит интересующего нас предиката. При этом мы доказываем, что $$\mathcal{E}$$ содержит все выразимые предикаты, таким способом: проверяем, что $$\mathcal{E}$$ содержит все предикаты, выразимые атомарными формулами, а также замкнут относительно логических операций (объединение, пересечение, дополнение) и операции проекции (соответствующей навешиванию квантора существования; квантор всеобщности выражается через квантор существования). Часто класс $$\mathcal{E}$$ совпадает с классом всех предикатов, выразимых бескванторными формулами (иногда надо расширить сигнатуру), и потому этот метод называют методом "элиминации кванторов". (Это краткое описание, возможно, станет яснее из приводимых далее примеров.)

Начнем с такого примера. Пусть сигнатура содержит равенство, одноместную функцию $$S$$ (прибавление единицы) и константу $$0$$. Носителем интерпретации будет множество $$\mathbb{Z}$$ целых чисел, символы сигнатуры интерпретируются естественным образом. В этой ситуации изоморфизмов не существует, так что предыдущий способ доказательства невыразимости здесь неприменим.

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

Теорема 28. Для всякой формулы рассматриваемой нами сигнатуры существует эквивалентная ей бескванторная формула.

Будем доказывать индукцией по построению (или, если угодно, по длине) формулы $$\varphi$$ существование эквивалентной ей в $$(\mathbb{Z},=,S,0)$$ бескванторной формулы. Для удобства (чтобы рассматривать один случай, а не два) будем считать, что наша формула может содержать только кванторы существования, но не всеобщности. Это законно, так как формулы $$\forall \xi \,\psi$$ и $$\lnot\exists\xi\,\lnot\psi$$ эквивалентны.

Случай, когда $$\varphi$$ есть атомарная формула, очевиден — она и так бескванторная. Если $$\varphi$$ является конъюнкцией, дизъюнкцией или импликацией двух частей, достаточно заменить каждую часть на эквивалентную бескванторную (что можно сделать по предположению индукции).

Единственный содержательный случай — когда формула $$\varphi$$ начинается с квантора существования, то есть имеет вид $$\exists x \tau$$ (пусть под квантором стоит переменная $$x$$ ). Мы рассуждаем по индукции, поэтому можем считать, что формула $$\tau$$ — бескванторная. Она имеет (возможно) и другие параметры, скажем, $$x_1,\dots,x_n$$. Чтобы подчеркнуть это, обычно вместо $$\tau$$ пишут $$\tau(x,x_1,\dots,x_n)$$. Нам надо найти бескванторную формулу нашей сигнатуры, эквивалентную формуле$$\exists x\, \tau(x,x_1,\dots,x_n).$$ Формула $$\tau(x,x_1,\dots,x_n)$$ представляет собой булеву комбинацию атомарных формул. Посмотрим на те атомарные формулы, которые содержат переменную $$x$$. Атомарная формула представляет собой равенство двух термов $$S(S(\dots(S(u))\dots))=S(S(\dots(S(v))\dots))$$ ; здесь $$u$$ и $$v$$ — либо переменные, либо константа $$0$$. Если переменная $$x$$ входит и в левую, и в правую часть, то (в этой интерпретации) такая атомарная формула либо всегда истинна, либо всегда ложна, и ее можно заменить на какую-нибудь тождественно истинную или тождественно ложную формулу, не содержащую $$x$$. После этого останутся атомарные формулы, которые можно записать как$$x = t_1,\quad x = t_2,\quad\dots,\quad x = t_k.$$ Здесь $$t_i$$ — либо целая константа, либо выражение вида $$x_j+c$$, где $$x_j$$ — какая-то другая переменная, а $$c$$ — целое число. Мы позволили себе слегка отступить от канонов, разрешив прибавлять и вычитать целые константы вместо того, чтобы применять функцию $$S$$ в левой и правой частях равенства. Ясно, что это не меняет класса выразимых формул, зато позволяет оставить $$x$$ в левой части, а константу перенести в правую.

Теперь сравним формулу$$\varphi=\exists x \,\tau(x,x_1,\dots,x_n)$$ с формулой$$\tau(t_1,x_1,\dots,x_n) \lor \tau(t_2,x_1,\dots,x_n) \lor \ldots \lor \tau(t_k,x_1,\dots,x_n),$$ которую мы будет обозначать $$\varphi'$$. Формула $$\varphi'$$ представляет собой дизъюнкцию формул, полученных в результате подстановки различных $$t_i$$ вместо $$x$$ в бескванторную формулу $$\tau(x,x_1,\dots,x_n)$$. (После подстановки можно вернуться к обычному виду записи формулы, заменив прибавление констант на нужное количество применений функции $$S$$ с той или другой стороны равенства.)

Очевидно, что если для каких-то значений переменных $$x_1,\dots,x_n$$ формула $$\varphi'$$ истинна, то для этих значений $$x_1,\dots,x_n$$ истинна и формула $$\varphi$$. В самом деле, если истинен $$i$$ -й член дизъюнкции, то в формуле $$\varphi$$ в качестве $$x$$ можно взять значение выражения $$t_i$$.

Верно ли обратное? Не обязательно. Вполне возможно, что тот $$x$$, который существует и делает формулу $$\varphi$$ истинной, отличается от всех $$t_i$$. Но мы пропустили по существу только один случай — все такие $$x$$ в некотором смысле одинаковы, так как они делают все атомарные формулы, содержащие $$x$$, ложными, поэтому все равно, какой из таких $$x$$ выбрать. Отметим также, что хотя бы один такой $$x$$ найдется, поскольку $$\mathbb{Z}$$ бесконечно, а выражений $$t_i$$ лишь конечное число.

Обозначим через $$\varphi''$$ формулу, которая получится из $$\tau$$ заменой всех атомарных формул, содержащих $$x$$, на тождественно ложные формулы. Сказанное выше объясняет, почему формула $$\varphi$$ эквивалентна дизъюнкции $$\varphi'\lor\varphi''$$. Мы достигли цели — нашли бескванторную формулу, эквивалентную формуле $$\varphi$$.

Легко понять, что отношение порядка $$x>y$$ не выражается бескванторной формулой нашей сигнатуры, поскольку такая формула может включать лишь атомарные формулы вида $$x=y+c$$ и для нее случай, когда $$y$$ сильно больше $$x$$, неотличим от случая, когда $$y$$ сильно меньше $$x$$. Тем самым мы доказали (чего нельзя было сделать методом автоморфизмов), что отношение $$x>y$$ невыразимо (в данной интерпретации данной сигнатуры).

Немного более сложное рассуждение понадобится, если добавить к сигнатуре отношение порядка.

Теорема 29. Всякая формула в $$(\mathbb{Z},{=},{<}, S)$$ (где $$S$$ — функция прибавления единицы) эквивалентна некоторой бескванторной формуле. (Как говорят, $$(\mathbb{Z},{=},{<},S)$$ допускает элиминацию кванторов.)

Полностью утверждение теоремы звучит так: для всякой формулы сигнатуры, содержащей равенство, порядок и символ $$S$$, найдется бескванторная формула той же сигнатуры, которая эквивалентна ей в интерпретации, где носителем является $$\mathbb{Z}$$, а символы сигнатуры интерпретируются естественным образом. (В дальнейшем мы будем опускать такие пояснения.)

Доказательство следует прежней схеме. Правда, теперь атомарных формул больше — помимо формул $$x=t_i$$ у нас будут формулы $$x<t_i$$. Поэтому нельзя рассчитывать на то, что все значения $$x$$, не встречающиеся среди $$\{t_1,\dots,t_k\}$$, ведут себя одинаково, и наш прием с выделением случая, когда все равенства ложны, более не проходит.

Как же быть? Для данных значений $$x_1,\dots,x_n$$ числа $$t_1,\dots,t_k$$ делят числовую ось (точнее, множество $$\mathbb{Z}$$ целых чисел) на промежутки, и для выяснения истинности формулы $$\varphi$$ нам надо попробовать (помимо всех $$t_i$$ ) хотя бы по одному числу из каждого промежутка. Это будет гарантировано, если мы напишем дизъюнкцию, в которую, помимо всех формул $$\tau(t_i,x_1,\dots,x_n)$$, войдут также формулы $$\tau(t_i+1,x_1,\dots,x_n)$$ и $$\tau(t_i-1,x_1,\dots,x_n)$$. Это позволяет нам обойтись без формулы $$\varphi''$$ и благополучно завершить доказательство.

63. Проверьте, что добавление константы $$0$$ к этой сигнатуре не препятствует элиминации кванторов.

Что будет, если мы из этой сигнатуры удалим функцию $$S$$? Легко понять, что класс выразимых множеств не изменится, так как $$y=S(x)$$ можно выразить как " $$y$$ является наименьшим элементом, большим $$x$$ ". Однако при этом мы использовали кванторы, так что для $$(\mathbb{Z},{=},{<})$$ элиминация кванторов невозможна.

64. Убедитесь, что в самом деле формула $$y\hm=S(x)$$ не эквивалентна никакой бескванторной формуле этой сигнатуры.

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

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

Теорема 30. Всякая формула в $$(\mathbb{Q},{=},{<})$$ эквивалентна некоторой бескванторной формуле.

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

В данном случае можно избавится от отрицаний, заменив $$\lnot(x=y)$$ на $$((x<y)\lor (x>y))$$, а $$\lnot(x<y)$$ — на $$((x=y)\lor(x>y))$$. После этого надо воспользоваться дистрибутивностью и вновь придти к дизъюнктивной нормальной форме — с большим числом членов, но уже без отрицаний.

Теперь надо воспользоваться тем, что квантор существования (который есть "бесконечная дизъюнкция") можно переставлять с дизъюнкцией. Точнее говоря, мы пользуемся тем, что формулы $$\exists x\,(\tau_1 \lor \tau_2)$$ и $$\exists x\,\tau_1 \lor \exists x\,\tau_2$$ эквивалентны. (Белый или черный единорог существует тогда и только тогда, когда существует белый единорог или существует черный единорог.) Это обстоятельство позволяет заменить формулу$$\exists x\, (\tau_1\lor\tau_2\lor\ldots\lor\tau_n)$$ на$$\exists x\, \tau_1\lor\exists x\,\tau_2\lor\ldots\lor\exists x\,\tau_n$$ и дальше разбираться с каждой из формул поодиночке.

Итак, нам осталось преобразовать к бескванторному виду формулу$$\exists x \, (\rho_1 \land \rho_2 \land\ldots\land\rho_k),$$ где каждая из формул $$\rho_i$$ соединяет какие-то две переменные знаком $$=$$ или $$<$$ (напомним, что от отрицаний мы уже избавились).

Некоторые из формул $$\rho_i$$ не содержат переменной $$x$$. Тогда их можно вынести за квантор: если $$x$$ не является параметром формулы $$\alpha$$, то формулы $$\exists x\, (\alpha\land\beta)$$ и $$\alpha \land \exists x\,\beta$$ эквивалентны (если $$\alpha$$ истинно для некоторых значений параметров, то в обеих формулах его можно опустить; если $$\alpha$$ ложно, то обе формулы ложны при этих значениях параметров).

Вынеся такие формулы, можно считать, что под квантором остались лишь формулы вида $$x<x_i$$, $$x=x_i$$ и $$x>x_i$$, сравнивающие переменную $$x$$ с какими-то другими переменными. Если там есть хоть одно равенство, то квантор существования вырождается — его можно удалить вместе с переменной $$x$$, заменив ее на ту переменную, которой она равна. Например, формулу $$\exists x\,((x\hm=y)\hm\land A(x))$$ можно заменить на $$A(y)$$.

Итак, остался случай, когда переменная $$x$$ встречается лишь в неравенствах. Другими словами, нас спрашивают, найдется ли значение $$x$$, большее каких-то переменных и меньшее каких-то других. Если все ограничения на $$x$$ одного знака (только снизу или только сверху), то такое значение $$x$$ существует при любых значениях других переменных (поскольку в множестве $$\mathbb{Q}$$ нет ни наибольшего, ни наименьшего элементов). Что делать, если есть ограничения разных знаков? Пусть наша формула, например, имеет вид$$\exists x \, ((x>a)\land (x>b)\land(x<c)\land(x<d)).$$ Как записать условия на $$a,b,c,d$$, при которых это верно, не используя кванторов? Надо написать такую формулу:$$(a<c)\land (a<d)\land (b<c) \land (b<d).$$ Мы хотим написать, что наибольшая из нижних границ меньше наименьшей из верхних, но поскольку заранее неизвестно, какая будет наибольшей и какая наименьшей, мы пишем, что любая нижняя граница меньше любой верхней. Поскольку множество $$\mathbb{Q}$$ является плотным (между любыми двумя элементами найдется третий), то эта формула равносильна исходной.

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

Заметим, что в этом доказательстве из свойств рациональных чисел мы использовали лишь отсутствие наибольшего и наименьшего элемента и плотность. Поэтому все наши преобразования остаются эквивалентными для любого упорядоченного множества с такими свойствами, а не только для $$\mathbb{Q}$$. Применив эти преобразования к замкнутой формуле (формуле без параметров), мы получим или тождественно истинную формулу, или тождественно ложную (только надо добавить в язык константы для истины и лжи, чтобы не использовать фиктивных переменных, когда надо написать тождественно истинное или тождественно ложное выражение). Отсюда мы заключаем, что во всех плотных упорядоченных множествах без первого и последнего элемента справедливы одни и те же формулы нашей сигнатуры. Как говорят, все такие множества элементарно эквивалентны с точки зрения нашей сигнатуры. (Другое доказательство этого факта можно получить, используя теорему Левенгейма-Сколема о счетной подмодели и теорему об изоморфизме счетных плотных линейно упорядоченных множеств без первого и последнего элементов.)

В частности, мы доказали, что для рациональных и действительных чисел истинны одни и те же формулы сигнатуры $$({=},{<})$$.

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

Элиминация кванторов остается возможной (и рассуждение даже немного упрощается), если рациональные (или действительные) числа рассматривать не только с равенством и порядком, но и со сложением и рациональными константами. В этом случае можно воспользоваться приведенной ранее схемой с конечным представительным набором термов. В самом деле, пусть $$x$$ — переменная, которую (вместе с квантором существования по ней) мы хотим элиминировать. Все атомарные формулы, ее содержащие, можно "разрешить" относительно $$x$$, получив некоторое количество формул вида $$x=t_i$$, $$x>t_i$$ и $$x<t_i$$, где $$t_i$$ — линейные комбинации остальных переменных с рациональными коэффициентами. (Разрешение рациональных коэффициентов вместо целых ничего не меняет, так как можно привести все к общему знаменателю и получить целые коэффициенты, затем перенести отрицательные коэффициенты в другую часть, а положительные заменить многократным сложением.)

Затем в качестве представительного набора надо взять набор, состоящий, во-первых, из всех $$t_i$$, во-вторых, из всех средних арифметических $$(t_i+t_j)/2$$, и, наконец, из выражений $$t_i-1$$ и $$t_i+1$$. Ясно, что как бы ни расположились точки $$t_i$$ на числовой оси, этот набор захватит как минимум по одной точке из каждого промежутка (средние арифметические нужны для интервалов, а прибавление и вычитание единицы — для лучей по краям).

65. Провести это рассуждение подробно.

Возможность элиминации кванторов в только что рассмотренной ситуации ( $$\mathbb{Q}, {=}, {<}, {+}$$, рациональные константы) имеет интересное геометрическое применение.

Теорема 31. Пусть единичный квадрат разрезан на несколько меньших квадратов. Тогда все они имеют рациональные стороны.

Пусть дано такое разрезание с $$n$$ меньшими квадратами. Напишем формулу с $$3n$$ параметрами ( $$n$$ из которых соответствуют размерам меньших квадратов, а $$2n$$ — координатам их левых верхних углов), которая говорит, что эти параметры действительно задают разрезание квадрата (квадраты содержатся внутри единичного, не имеют общих точек и всякая точка единичного квадрата покрывается хотя бы одним из меньших квадратов). Навесив кванторы существования по переменным, задающим координаты, получим формулу $$F(x_1,\dots,x_n)$$ с параметрами $$x_1,\dots,x_n$$, которая истинна, когда из квадратов размеров $$x_1,\dots,x_n$$ можно составить единичный квадрат.

Элиминация кванторов позволяет считать, что формула $$F$$ бескванторная, то есть представляет собой логическую комбинацию равенств и неравенств вида $$c_1x_1\hm+\ldots\hm+c_nx_n\hm+c_0\hm=0$$ и $$c_1x_1\hm+\ldots\hm+c_nx_n\hm+c_0\hm> 0$$ с различными рациональными коэффициентами. Посмотрим на все выражения, стоящие в левой части таких равенств и неравенств. Подставим в них числа $$\overline{x}_1,\dots,\overline{x}_n$$, соответствующие данному нам разрезанию. При этом получится истинная формула $$F(\overline{x}_1,\dots,\overline{x}_n)$$, в которой некоторые из левых частей равенств и неравенств будут равны нулю, а другие нет. Временно забудем про те, которые не равны нулю, а равные нулю будем воспринимать как левые части уравнений с неизвестными $$x_1,\dots,x_n$$ (с нулем в правой части) независимо от того, входили ли они в $$F$$ как левые части уравнений или неравенств. Получится система уравнений, для которой числа $$\overline{x}_1,\dots,\overline{x}_n$$ будут решениями. Если эти числа являются единственными ее решениями, то они рациональны (например, потому, что правила Крамера для решения системы уравнений содержат отношения определителей с рациональными элементами). Покажем, что другого быть не может.

В самом деле, если решение не единственно, то есть целая прямая, проходящая через точку $$\overline{x}= \langle\overline{x}_1,\dots,\overline{x}_n\rangle$$ и лежащая в множестве решений системы. Все точки прямой, достаточно близкие к $$\overline{x}$$, неотличимы от $$\overline{x}$$ с точки зрения формулы $$F$$ и потому делают формулу $$F$$ истинной. В самом деле, левые части, равные нулю в $$\overline{x}$$, равны нулю на всей прямой, а левые части, отличные от нуля в точке $$\overline{x}$$, сохраняют знак в некоторой окрестности этой точки. Пусть $$\langle h_1,\dots,h_n\rangle$$ — направляющий вектор этой прямой. Тогда при всех достаточно малых значениях $$t$$ из квадратов размеров$$\overline{x}_1+th_1, \overline{x}_2+th_2,\dots, \overline{x}_n+th_n$$ можно составить единичный квадрат. Но это невозможно. Чтобы убедиться в этом, достаточно оставить логику и вернуться к геометрии: площади этих квадратов в сумме должны равняться $$1$$, но площадь каждого есть многочлен второй степени по $$t$$, и коэффициент при $$t^2$$ положителен, поэтому сумма таких многочленов не может тождественно равняться единице ни на каком интервале.

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

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

66. Описать выразимые предикаты, проведя элиминацию кванторов (и расширив сигнатуру, если нужно) для (а) $$(M, {=})$$, где $$M$$ — произвольное бесконечное множество; (б) $$(\bbQ, {=},{+})$$ ; (в) $$(\mathbb{Q}, {=}, S)$$, где $$S$$ — операция прибавления единицы; (г) $$(\mathbb{N}, {=}, S)$$, где $$S$$ — операция прибавления единицы; (д) $$(\mathbb{N}, {=}, S, P)$$, где $$S$$ — операция прибавления единицы, а $$P$$ — одноместный предикат "быть степенью двойки".

Страницы: