Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 20
Текст из файла (страница 20)
Поскольку автоморфизм оставляет на месте все рациональные числа, он должен быть тождественным.)В этом случае предикат x = γ выразим тогда и только тогда,когда γ — алгебраическое число. Это легко следует из теоремыТарского – Зайденберга (раздел 3.8, с. 109).61. Покажите, что предикат y = x + 1 невыразим в интерпретации(Z, =, f ), где f — одноместная функция x 7→ (x + 2).62. Покажите, что предикат x = 2 невыразим в множестве целых положительных чисел с предикатами равенства и «x делит y».3.6. Невыразимые предикаты: элиминация кванторовПри всей простоте метод доказательства невыразимости с помощью автоморфизмов страдает очевидным недостатком: очень частотребуемого автоморфизма нет. Например, натуральные числа с операцией прибавления единицы вообще не допускают никакого нетривиального автоморфизма. (Тем не менее там выразимо очень немногое, как мы вскоре увидим.) Целые числа с операцией прибавления единицы допускают автоморфизмы (сдвиги), но эти автоморфизмы не позволяют доказать, что отношение порядка невыразимо(поскольку оно устойчиво относительно сдвигов).Более прямой метод доказательства состоит в том, что мы предъявляем некоторый класс E предикатов, который содержит все выразимые предикаты и не содержит интересующего нас предиката.
Приэтом мы доказываем, что E содержит все выразимые предикаты, так:проверяем, что E содержит все предикаты, выразимые атомарными формулами, а также замкнут относительно логических операций(объединение, пересечение, дополнение) и операции проекции (соответствующей навешиванию квантора существования; квантор всеобщности выражается через квантор существования). Часто класс E90Языки первого порядка[гл. 3]совпадает с классом всех предикатов, выразимых бескванторнымиформулами (иногда надо расширить сигнатуру), и потому этот метод называют методом «элиминации кванторов».
(Это краткое описание, возможно, станет яснее из приводимых далее примеров.)Начнём с такого примера. Пусть сигнатура содержит равенство,одноместную функцию S (прибавление единицы) и константу 0. Носителем интерпретации будет множество Z целых чисел, символысигнатуры интерпретируются естественным образом. В этой ситуации изоморфизмов не существует, так что предыдущий способ доказательства невыразимости здесь неприменим.Тем не менее класс выразимых предикатов весьма ограничен: этопредикаты, выразимые бескванторными формулами. Будем называть две формулы (рассматриваемой нами сигнатуры) эквивалентными (в данной интерпретации), если они выражают один и тот жепредикат, то есть истинны при одних и тех же значениях переменных.Теорема 28. Для всякой формулы рассматриваемой нами сигнатуры существует эквивалентная ей бескванторная формула.
Будем доказывать индукцией по построению (или, если угодно,по длине) формулы ϕ существование эквивалентной ей в (Z, =, S, 0)бескванторной формулы. Для удобства (чтобы рассматривать одинслучай, а не два) будем считать, что наша формула может содержатьтолько кванторы существования, но не всеобщности. Это законно,так как формулы ∀ξ ψ и ¬∃ξ ¬ψ эквивалентны.Случай, когда ϕ есть атомарная формула, очевиден — она и такбескванторная. Если ϕ является конъюнкцией, дизъюнкцией или импликацией двух частей, достаточно заменить каждую часть на эквивалентную бескванторную (что можно сделать по предположениюиндукции).Единственный содержательный случай — когда формула ϕ начинается с квантора существования, то есть имеет вид ∃xτ (пустьпод квантором стоит переменная x). Мы рассуждаем по индукции,поэтому можем считать, что формула τ — бескванторная.
Она имеет(возможно) и другие параметры, скажем, x1 , . . . , xn . Чтобы подчеркнуть это, обычно вместо τ пишут τ (x, x1 , . . . , xn ). Нам надо найтибескванторную формулу нашей сигнатуры, эквивалентную формуле∃x τ (x, x1 , . . . , xn ).Формула τ (x, x1 , . . . , xn ) представляет собой булеву комбинацию атомарных формул. Посмотрим на те атомарные формулы, которые со-[п. 6]Элиминация кванторов91держат переменную x. Атомарная формула представляет собой равенство двух термов S(S(. . . (S(u)) . . . )) = S(S(.
. . (S(v)) . . . )); здесьu и v — либо переменные, либо константа 0. Если переменная x входит и в левую, и в правую часть, то (в этой интерпретации) такаяатомарная формула либо всегда истинна, либо всегда ложна, и еёможно заменить на какую-нибудь тождественно истинную или тождественно ложную формулу, не содержащую x. После этого останутся атомарные формулы, которые можно записать какx = t1 ,x = t2 ,...,x = tk .Здесь ti — либо целая константа, либо выражение вида xj + c, гдеxj — какая-то другая переменная, а c — целое число. Мы позволилисебе слегка отступить от канонов, разрешив прибавлять и вычитатьцелые константы вместо того, чтобы применять функцию S в левойи правой частях равенства.
Ясно, что это не меняет класса выразимых формул, зато позволяет оставить x в левой части, а константуперенести в правую.Теперь сравним формулуϕ = ∃x τ (x, x1 , . . . , xn )с формулойτ (t1 , x1 , . . . , xn ) ∨ τ (t2 , x1 , . .
. , xn ) ∨ . . . ∨ τ (tk , x1 , . . . , xn ),которую мы будет обозначать ϕ0 . Формула ϕ0 представляет собойдизъюнкцию формул, полученных в результате подстановки различных ti вместо x в бескванторную формулу τ (x, x1 , . . . , xn ). (Послеподстановки можно вернуться к обычному виду записи формулы,заменив прибавление констант на нужное количество примененийфункции S с той или другой стороны равенства.)Очевидно, что если для каких-то значений переменных x1 , . . . , xnформула ϕ0 истинна, то для этих значений x1 , . . . , xn истинна и формула ϕ.
В самом деле, если истинен i-й член дизъюнкции, то в формуле ϕ в качестве x можно взять значение выражения ti .Верно ли обратное? Не обязательно. Вполне возможно, что тотx, который существует и делает формулу ϕ истинной, отличаетсяот всех ti . Но мы пропустили по существу только один случай —все такие x в некотором смысле одинаковы, так как они делают всеатомарные формулы, содержащие x, ложными, поэтому всё равно,92Языки первого порядка[гл. 3]какой из таких x выбрать. Отметим также, что хотя бы один такойx найдётся, поскольку Z бесконечно, а выражений ti лишь конечноечисло.Обозначим через ϕ00 формулу, которая получится из τ заменойвсех атомарных формул, содержащих x, на тождественно ложныеформулы.
Сказанное выше объясняет, почему формула ϕ эквивалентна дизъюнкции ϕ0 ∨ ϕ00 . Мы достигли цели — нашли бескванторную формулу, эквивалентную формуле ϕ. Легко понять, что отношение порядка x > y не выражается бескванторной формулой нашей сигнатуры, поскольку такая формуламожет включать лишь атомарные формулы вида x = y + c и длянеё случай, когда y сильно больше x, неотличим от случая, когда yсильно меньше x. Тем самым мы доказали (чего нельзя было сделать методом автоморфизмов), что отношение x > y невыразимо (вданной интерпретации данной сигнатуры).Немного более сложное рассуждение понадобится, если добавитьк сигнатуре отношение порядка.Теорема 29.
Всякая формула в (Z, =, <, S) (где S — функция прибавления единицы) эквивалентна некоторой бескванторной формуле. (Как говорят, (Z, =, <, S) допускает элиминацию кванторов.) Полностью утверждение теоремы звучит так: для всякой формулы сигнатуры, содержащей равенство, порядок и символ S, найдётся бескванторная формула той же сигнатуры, которая эквивалентна ей в интерпретации, где носителем является Z, а символысигнатуры интерпретируются естественным образом. (В дальнейшеммы будем опускать такие пояснения.)Доказательство следует прежней схеме. Правда, теперь атомарных формул больше — помимо формул x = ti у нас будут формулыx < ti . Поэтому нельзя рассчитывать на то, что все значения x, невстречающиеся среди {t1 , .
. . , tk }, ведут себя одинаково, и наш приёмс выделением случая, когда все равенства ложны, более не проходит.Как же быть? Для данных значений x1 , . . . , xn числа t1 , . . . , tk делят числовую ось (точнее, множество Z целых чисел) на промежутки, и для выяснения истинности формулы ϕ нам надо попробовать(помимо всех ti ) хотя бы по одному числу из каждого промежутка.Это будет гарантировано, если мы напишем дизъюнкцию, в которую, помимо всех формул τ (ti , x1 , .
. . , xn ), войдут также формулыτ (ti + 1, x1 , . . . , xn ) и τ (ti − 1, x1 , . . . , xn ). Это позволяет нам обойтисьбез формулы ϕ00 и благополучно завершить доказательство. 63. Проверьте, что добавление константы 0 к этой сигнатуре не пре-[п. 6]Элиминация кванторов93пятствует элиминации кванторов.Что будет, если мы из этой сигнатуры удалим функцию S? Легко понять, что класс выразимых множеств не изменится, так какy = S(x) можно выразить как «y является наименьшим элементом,бо́льшим x».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
