Игра Эренфойхта
Вернемся от алгебры к логике и сформулируем общий критерий элементарной эквивалентности двух интерпретаций некоторой сигнатуры. Будем считать, что наша сигнатура содержит только предикатные символы. (Это ограничение не очень существенно, так как функцию можно заменить предикатом , имеющим на один аргумент больше.) Кроме того, будем считать, что сигнатура конечна (в некоторый момент наших рассуждений это будет существенно).
Критерий будет сформулирован в терминах некоторой игры, называемой игрой Эренфойхта. В ней участвуют два игрока, называемые Новатором (Н) и Консерватором (К). Игра определяется выбранной парой интерпретаций; как мы докажем, интерпретации элементарно эквивалентны тогда и только тогда, когда К имеет выигрышную стратегию в этой игре.
В начале игры Новатор объявляет натуральное число . Далее они ходят по очереди, начиная с Н; каждый из игроков делает
ходов, после чего определяется победитель.
На -м ходу Н выбирает элемент в одной из интерпретаций (в любой из двух, причем выбор может зависеть от номера хода) и помечает его числом . В ответ К выбирает некоторый элемент из другой интерпретации и также помечает его числом . После ходов игра заканчивается. При этом в каждой интерпретации элементов оказываются помеченными числами от до (мы не учитываем, кто именно из игроков их пометил). Обозначим эти элементы (для первой интерпретации; элемент имеет пометку ) и (для второй). Элементы и (с одним и тем же ) будем называть соответствующими друг другу. Посмотрим, найдется ли предикат сигнатуры, который различает помеченные элементы первой и второй интерпретации (то есть истинен на некотором наборе помеченных элементов в одной интерпретации, но ложен на соответствующих элементах другой). Если такой предикат найдется, то выигрывает Новатор, в противном случае — Консерватор.
Прежде чем доказывать, что эта игра дает критерий элементарной эквивалентности, рассмотрим несколько простых примеров.
- Среди элементов и могут быть одинаковые. Если в нашей сигнатуре есть предикат равенства и в обеих интерпретациях он интерпретируется как совпадение элементов, то Консерватор обязан повторять ходы, если их повторил Новатор (скажем, если , а , то Новатор выигрывает, поскольку предикат равенства истинен в одной интерпретации, но ложен на соответствующих элементах другой).
- Если интерпретации изоморфны, то у Консерватора есть очевидный способ выиграть: изоморфизм заранее группирует все элементы в пары соответствующих. (Это согласуется с тем, что изоморфные интерпретации элементарно эквивалентны.)
-
Рассмотрим сигнатуру упорядоченных множеств (предикаты и ) и ее естественные интерпретации в и . Они не являются элементарно эквивалентными, поскольку среди натуральных чисел есть наименьшее, а среди целых — нет. Покажем, что в игре Эренфойхта для данных интерпретаций выигрывает Новатор.
Н объявляет, что игра будет проведена в два хода и на первом ходу помечает число из интерпретации . В ответ К вынужден пометить некоторое число из . На втором ходу Н помечает в некоторое число, меньшее (например, ). Теперь К проигрывает при любом ответном ходе, поскольку пометить число, меньшее нуля, он не может.
Для той же сигнатуры рассмотрим интерпретации в и . Эти интерпретации не элементарно эквивалентны, поскольку порядок на рациональных числах плотен, а на целых — нет. Покажем, что в игре Эренфойхта снова выигрывает Новатор.
Игра будет проходить в три хода. На первых двух ходах Н
помечает числа и из . К
должен пометить некоторые элементы и из . При этом должно быть (иначе Н заведомо выиграет). Тогда на третьем ходу Н
помечает любое рациональное число, лежащее строго между и . Так как между и нет натуральных чисел, К не может соблюсти требования игры и проигрывает при любом ходе.
Рассмотрим теперь упорядоченные множества и . Как мы видели, они элементарно эквивалентны, и потому должна существовать выигрышная стратегия для Консерватора. Как же он должен играть? Кажется разумным поддерживать одинаковые расстояния между соответствующими элементами в и . Проблема в том, что в некоторые расстояния бесконечны (между элементами разных слагаемых). Что же делать Консерватору, если Новатор пометил два таких элемента?
К счастью для К, он знает заранее, сколько ходов осталось до конца игры. Ясно, что если игра скоро кончится, то Н не удастся отличить бесконечное расстояние от достаточно большого. Более точно, если до конца игры остается ходов, то К может считать все расстояния, большие или равные , бесконечно большими. В конце (при ) это означает, что все ненулевые расстояния отождествляются (что правильно, так как в конце важен лишь порядок).
Таким образом, К стремится поддерживать такой "инвариант" (как сказали бы программисты): соответствующие элементы в и в идут в одном и том же порядке, и расстояния между соответствующими парами соседей одинаковы (при этом все бесконечно большие расстояния считаются одинаковыми). Ясно, что такая стратегия гарантирует ему выигрыш; надо лишь проверить, что поддержать инвариант можно.
При очередном ходе Н возможны несколько случаев. Н мог разбить "конечный" (меньший , где — число оставшихся ходов) промежуток на две части. В этом случае соответствующий промежуток в другом множестве также "конечен" и имеет ту же длину, так что К должен лишь выбрать элемент на том же расстоянии от концов. Пусть Н разбил "бесконечный" (длины или больше) промежуток на две части. Тогда хотя бы одна из частей будет иметь длину
или больше, то есть на следующем шаге будет считаться "бесконечной". Если обе части "бесконечны" (с точки зрения следующего шага), то К должен разбить "бесконечный" (длины или более) промежуток другого множества на две "бесконечные" (длины или более) части; это, очевидно, возможно. Если одна часть " бесконечна", а другая "конечна", то надо отложить то же "конечное" расстояние в другом множестве. Наконец, обе части не могут быть "конечными" (если каждая меньше , то в сумме будет меньше ).
Наконец, новый элемент мог быть больше (или меньше) всех уже отмеченных элементов интерпретации; в этом случае К должен отметить элемент другой интерпретации, находящийся на том же расстоянии от наибольшего (наименьшего) отмеченного элемента (или на "бесконечном" расстоянии, если такова была ситуация с выбранным Н элементом).
85. Кто выигрывает в игре Эренфойхта для упорядоченных множеств (а) и ; (б) и ; (в) и ? Как он должен играть?
Приведенные примеры делают правдоподобной связь между наличием формулы, различающей интерпретации, и выигрышной стратегии для Н.
При этом число ходов, которое понадобится Новатору, соответствует кванторной глубине различающей интерпретации формулы. Кванторная глубина формулы определяется так:
- Глубина атомарных формул равна нулю.
- Глубина формул и равна максимуму глубин формул и .
- Глубина формулы равна глубине формулы .
- Глубина формул и на единицу больше глубины формулы .
Другими словами, глубина формулы — это наибольшая "глубина вложенности" кванторов (максимальная длина цепочки вложенных кванторов).
Рассмотрим позицию, которая складывается в игре после
ходов Н и К (перед очередным ходом Н) и за ходов до конца игры (таким образом, общая длина игры есть ). В этот момент в каждой из интерпретаций совместными усилиями Н и К выбрано по
элементов. Пусть это будут элементы в одной интерпретации (назовем ее ) и в другой ().
Лемма. Если существует формула глубины с параметрами , отличающая от , то в указанной позиции Н имеет выигрышную стратегию; в противном случае ее имеет К.
Поясним смысл условия леммы. Пусть — формула глубины , все параметры которой содержатся в списке . Тогда имеет смысл ставить вопрос о ее истинности в интерпретации при значениях параметров , а также в интерпретации при значениях параметров . Если окажется, что в одном случае формула истинна, а в другом ложна, то мы говорим, что отличает от .
Пусть такая формула существует. Она представляет собой логическую (бескванторную) комбинацию некоторых формул вида и , где — формула глубины . Хотя бы одна из формул, входящих в эту комбинацию, должна также отличать от . Переходя к отрицанию, можно считать, что эта формула начинается с квантора существования. Пусть формула , имеющая вид истинна для и ложна для . Тогда найдется такое , для которого в истинно
Это и будет выигрывающим ходом Новатора; при любом ответном ходе Консерватора формула
будет ложной. Таким образом, некоторая формула глубины
отличает от и потому, рассуждая по индукции, мы можем считать, что в оставшейся -ходовой игре Н имеет выигрышную стратегию. (В конце концов мы придем к ситуации, когда некоторая бескванторная формула отличает элементов в от соответствующих элементов в , то есть Н выиграет.)
Обратное рассуждение ( если наборы не отличимы никакой формулой глубины , то К имеет выигрышную стратегию в оставшейся -ходовой игре) аналогично, но чуть более сложно. Здесь важно, что по существу есть лишь конечное число различных формул глубины .
Точнее говоря, будем называть две формулы (с параметрами) эквивалентными, если они одновременно истинны или ложны в любой интерпретации на любой оценке. Поскольку сигнатура конечна, существует лишь конечное число атомарных формул, все параметры которых содержатся среди . Существует лишь конечное число булевых функций с данным набором аргументов, поэтому существует лишь конечное число неэквивалентных бескванторных формул, все параметры которых содержатся среди . Отсюда следует, что существует лишь конечное число неэквивалентных формул вида и потому лишь конечное число неэквивалентных формул глубины , параметры которых содержатся среди . (Здесь мы снова используем утверждение о конечности числа булевых функций с данным конечным списком аргументов, а также возможность переименовывать переменную под квантором, благодаря которой мы можем считать, что эта переменная есть .) Продолжая эти рассуждения, мы заключаем, что для любого и для любого набора переменных существует лишь конечное число неэквивалентных формул глубины , все параметры которых содержатся среди . (Здесь мы существенно используем конечность сигнатуры.)
Теперь можно закончить рассуждения про игру Эренфойхта. Пусть элементы нельзя отличить от элементов с помощью формул глубины . Опишем выигрышную стратегию для К. Пусть Н выбрал произвольный элемент в одной из интерпретаций, скажем, . Рассмотрим все формулы глубины с параметрами (с точностью до эквивалентности их конечное число); некоторые из них будут истинны на , а некоторые ложны. Тогда формула, утверждающая существование с ровно такими свойствами (после квантора существования идет конъюнкция всех истинных формул и отрицаний всех ложных) будет формулой глубины , истинной на . По предположению эта формула должна быть истинной и на , и потому существует с теми же свойствами, что и .Этот элемент и должен пометить К. Теперь предположение индукции позволяет заключить, что в возникшей позиции (где до конца игры
ходов) у К есть выигрышная стратегия.
Лемма доказана. Ее частным случаем является обещанный критерий элементарной эквивалентности:
Теорема 41. Интерпретации и элементарно эквивалентны тогда и только тогда, когда в соответствующей игре Эренфойхта выигрывает Консерватор.
86. Покажите, что условие конечности сигнатуры существенно (без него из элементарной эквивалентности не следует существование выигрышной стратегии для К).
Заметим, что в некоторых случаях (например, для и ) игра Эренфойхта дает нам новый способ доказательства элементарной эквивалентности.