Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 27
Текст из файла (страница 27)
ТеперьК проигрывает при любом ответном ходе, поскольку пометитьчисло, меньшее нуля, он не может.• Для той же сигнатуры рассмотрим интерпретации в Z и Q.Эти интерпретации не элементарно эквивалентны, посколькупорядок на рациональных числах плотен, а на целых — нет.Покажем, что в игре Эренфойхта снова выигрывает Новатор.Игра будет проходить в три хода. На первых двух ходах Нпомечает числа 0 и 1 из Z. К должен пометить некоторые элементы b1 и b2 из Q. При этом должно быть b1 < b2 (иначе Нзаведомо выиграет). Тогда на третьем ходу Н помечает любоерациональное число, лежащее строго между b1 и b2 . Так какмежду 0 и 1 нет натуральных чисел, К не может соблюсти требования игры и проигрывает при любом ходе.• Рассмотрим теперь упорядоченные множества Z и Z + Z.
Какмы видели (с. 113), они элементарно эквивалентны, и потомудолжна существовать выигрышная стратегия для Консерватора. Как же он должен играть? Кажется разумным поддерживать одинаковые расстояния между соответствующими элементами в Z и Z+Z. Проблема в том, что в Z+Z некоторые расстояния бесконечны (между элементами разных слагаемых). Чтоже делать Консерватору, если Новатор пометил два таких элемента?[п. 10]Игра Эренфойхта119К счастью для К, он знает заранее, сколько ходов осталось доконца игры. Ясно, что если игра скоро кончится, то Н не удастся отличить бесконечное расстояние от достаточно большого.Более точно, если до конца игры остаётся s ходов, то К можетсчитать все расстояния, большие или равные 2s , бесконечнобольшими. В конце (при s = 0) это означает, что все ненулевые расстояния отождествляются (что правильно, так как вконце важен лишь порядок).
Таким образом, К стремится поддерживать такой «инвариант» (как сказали бы программисты):соответствующие элементы в A и в B идут в одном и том же порядке, и расстояния между соответствующими парами соседейодинаковы (при этом все бесконечно большие расстояния считаются одинаковыми). Ясно, что такая стратегия гарантируетему выигрыш; надо лишь проверить, что поддержать инвариант можно.При очередном ходе Н возможны несколько случаев. Н мог разбить «конечный» (меньший 2s , где s — число оставшихся ходов) промежуток на две части.
В этом случае соответствующийпромежуток в другом множестве также «конечен» и имеет туже длину, так что К должен лишь выбрать элемент на том жерасстоянии от концов. Пусть Н разбил «бесконечный» (длины2s или больше) промежуток на две части. Тогда хотя бы однаиз частей будет иметь длину 2s−1 или больше, то есть на следующем шаге будет считаться «бесконечной». Если обе части«бесконечны» (с точки зрения следующего шага), то К долженразбить «бесконечный» (длины 2s или более) промежуток другого множества на две «бесконечные» (длины 2s−1 или более)части; это, очевидно, возможно. Если одна часть «бесконечна», а другая «конечна», то надо отложить то же «конечное»расстояние в другом множестве.
Наконец, обе части не могутбыть «конечными» (если каждая меньше 2s−1 , то в сумме будетменьше 2s ).Наконец, новый элемент мог быть больше (или меньше) всехуже отмеченных элементов интерпретации; в этом случае Кдолжен отметить элемент другой интерпретации, находящийсяна том же расстоянии от наибольшего (наименьшего) отмеченного элемента (или на «бесконечном» расстоянии, если таковабыла ситуация с выбранным Н элементом).120Языки первого порядка[гл. 3]85. Кто выигрывает в игре Эренфойхта для упорядоченных множеств(а) Z и R; (б) R и Q; (в) N и N + Z? Как он должен играть?Приведённые примеры делают правдоподобной связь междуналичием формулы, различающей интерпретации, и выигрышнойстратегии для Н.
При этом число ходов, которое понадобится Новатору, соответствует кванторной глубине различающей интерпретации формулы. Кванторная глубина формулы определяется так:• Глубина атомарных формул равна нулю.• Глубина формул ϕ ∨ ψ и ϕ ∧ ψ равна максимуму глубин формулϕ и ψ.• Глубина формулы ¬ϕ равна глубине формулы ϕ.• Глубина формул ∃ξ ϕ и ∀ξ ϕ на единицу больше глубины формулы ϕ.Другими словами, глубина формулы — это наибольшая «глубинавложенности» кванторов (максимальная длина цепочки вложенныхкванторов).Рассмотрим позицию, которая складывается в игре после k ходовН и К (перед очередным ходом Н) и за l ходов до конца игры (таким образом, общая длина игры есть k + l). В этот момент в каждойиз интерпретаций совместными усилиями Н и К выбрано по k элементов. Пусть это будут элементы a1 , .
. . , ak в одной интерпретации(назовём её A) и b1 , . . . , bk в другой (B).Лемма. Если есть формула глубины l с параметрами x1 , . . . , xk ,отличающая a1 , . . . , ak от b1 , . . . , bk , то в указанной позиции Н имеетвыигрышную стратегию; в противном случае её имеет К.Поясним смысл условия леммы. Пусть ϕ — формула глубины l,все параметры которой содержатся в списке x1 , . . . , xk . Тогда имеет смысл ставить вопрос о её истинности в интерпретации A призначениях параметров a1 , . .
. , ak , а также в интерпретации B призначениях параметров b1 , . . . , bk . Если окажется, что в одном случае формула ϕ истинна, а в другом ложна, то мы говорим, что ϕотличает a1 , . . . , ak от b1 , . . . , bk .Пусть такая формула ϕ существует.
Она представляет собойлогическую (бескванторную) комбинацию некоторых формул вида∀ξ ψ и ∃ξψ, где ψ — формула глубины l − 1. Хотя бы одна из формул,входящих в эту комбинацию, должна также отличать a1 , . . . , ak от[п. 10]Игра Эренфойхта121b1 , . . . , bk . Переходя к отрицанию, можно считать, что эта формуланачинается с квантора существования. Пусть формула ϕ, имеющаявид∃xk+1 ψ(x1 , .
. . , xk , xk+1 ),истинна для a1 , . . . , ak и ложна для b1 , . . . , bk . Тогда найдётся такоеak+1 , для которого в A истинноψ(a1 , . . . , ak , ak+1 ).Это ak+1 и будет выигрывающим ходом Новатора; при любом ответном ходе bk+1 Консерватора формулаψ(b1 , . . . , bk , bk+1 )будет ложной. Таким образом, некоторая формула глубины l − 1отличает a1 , . . . , ak , ak+1 от b1 , . .
. , bk , bk+1 ; рассуждая по индукции,мы можем считать, что в оставшейся (l − 1)-ходовой игре Н имеетвыигрышную стратегию. (В конце концов мы придём к ситуации,когда некоторая бескванторная формула отличает k + l элементовв A от соответствующих элементов в B, то есть Н выиграет.)Обратное рассуждение (если наборы не отличимы никакой формулой глубины l, то К имеет выигрышную стратегию в оставшейсяl-ходовой игре) чуть более сложно.
Здесь важно, что по существуесть лишь конечное число различных формул глубины k.Точнее говоря, будем называть две формулы (с параметрами) эквивалентными, если они одновременно истинны или ложны в любой интерпретации на любой оценке.
Поскольку сигнатура конечна,существует лишь конечное число атомарных формул, все параметры которых содержатся среди u1 , . . . , us . Существует лишь конечное число булевых функций с данным набором аргументов, поэтомусуществует лишь конечное число неэквивалентных бескванторныхформул, все параметры которых содержатся среди u1 , . .
. , us . Отсюда следует, что существует лишь конечное число неэквивалентныхформул вида∃us ψ(u1 , . . . , us ),и потому лишь конечное число неэквивалентных формул глубины 1,параметры которых содержатся среди u1 , . . . , us−1 . (Здесь мы сноваиспользуем утверждение о конечности числа булевых функций с данным конечным списком аргументов, а также возможность переименовывать переменную под квантором, благодаря которой мы можем122Языки первого порядка[гл. 3]считать, что эта переменная есть us .) Продолжая эти рассуждения,мы заключаем, что для любого l и для любого набора переменныхu1 , . . .
, un существует лишь конечное число неэквивалентных формул глубины l, все параметры которых содержатся среди u1 , . . . , un .(Здесь мы существенно используем конечность сигнатуры.)Вернёмся к игре Эренфойхта. Пусть элементы a1 , . . . , ak нельзяотличить от элементов b1 , . . . , bk с помощью формул глубины l. Опишем выигрышную стратегию для К. Пусть Н выбрал произвольныйэлемент в одной из интерпретаций, скажем, ak+1 . Рассмотрим всеформулы глубины l − 1 с k + 1 параметрами (с точностью до эквивалентности их конечное число); некоторые из них будут истиннына a1 , .
. . , ak+1 , а некоторые ложны. Тогда формула, утверждающаясуществование ak+1 с ровно такими свойствами (после квантора существования идёт конъюнкция всех истинных формул и отрицанийвсех ложных) будет формулой глубины l, истинной на a1 , . . . , ak . Попредположению эта формула должна быть истинной и на b1 , . . . , bk ,и потому существует bk+1 с теми же свойствами, что и ak+1 . Этотэлемент bk+1 и должен пометить К. Теперь предположение индукции позволяет заключить, что в возникшей позиции (где до концаигры l − 1 ходов) у К есть выигрышная стратегия.Лемма доказана. Её частным случаем является обещанный критерий элементарной эквивалентности:Теорема 41.
Интерпретации A и B элементарно эквивалентны тогда и только тогда, когда в соответствующей игре Эренфойхта выигрывает Консерватор.86. Покажите, что условие конечности сигнатуры существенно (безнего из элементарной эквивалентности не следует существование выигрышной стратегии для К).Заметим, что в некоторых случаях (например, для Z и Z+Z) играЭренфойхта даёт нам новый способ доказательства элементарнойэквивалентности.3.11.
Понижение мощностиВ этом разделе мы опишем приём, позволяющей в интерпретации большой мощности выделять часть, которая будет элементарноэквивалентна исходной (и, более того, исходная будет её элементарным расширением в смысле определения на с. 115). Например, вовсяком бесконечном упорядоченном множестве этот приём позволитнайти счётное подмножество, элементарно эквивалентное исходномукак интерпретация сигнатуры (=, <).[п. 11]Понижение мощности123С помощью этой конструкции (составляющей содержание теоремы Левенгейма – Сколема об элементарной подмодели) легко датьобещанное на с. 95 другое доказательство того, что любые два плотно упорядоченных множества без первого и последнего элемента элементарно эквивалентны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
