Игра Эренфойхта — Фраиса

Основная идея игры заключается в том, что мы имеем две структуры и два игрока (определены ниже). Один из игроков хочет показать, что эти две структуры отличны, в то время как другой игрок хочет показать, что они элементарно эквивалентны (удовлетворяют тем же предложения первого порядка). Игра ведётся поочерёдно по раундам. Раунд протекает следующим образом: Сначала первый игрок Новатор[2] выбирает любой элемент из одной из структур, а другой игрок выбирает элемент из другой структуры. Целью второго игрока всегда является выбор элемента, который «похож» на элемент, выбранный Новатором. Второй игрок (Консерватор) выигрывает, если существует изоморфизм между выбранными элементами в двух различных структурах.

Игра завершается за фиксированное число шагов (${\displaystyle \gamma }$) (ординал, но обычно конечное число или ${\displaystyle \omega }$).

Предположим, что нам даны две структуры ${\displaystyle {\mathfrak {A}}}$ and ${\displaystyle {\mathfrak {B}}}$ с одинаковыми множеством отношений символов и дано фиксированное натуральное число n. Мы можем тогда определить игру Эренфойхта — Фраиса ${\displaystyle G_{n}({\mathfrak {A}},{\mathfrak {B}})}$ как игру между двумя игроками, Новатором и Консерватором, следующим образом:

1. Первый игрок, Новатор, выбирает либо члена ${\displaystyle a_{1}}$ структуры ${\displaystyle {\mathfrak {A}}}$, или члена ${\displaystyle b_{1}}$ структуры ${\displaystyle {\mathfrak {B}}}$.
2. Если Новатор выбирает члена структуры ${\displaystyle {\mathfrak {A}}}$, Консерватор выбирает члена ${\displaystyle b_{1}}$ структуры ${\displaystyle {\mathfrak {B}}}$. В противном случае Консерватор выбирает члена ${\displaystyle a_{1}}$ структуры ${\displaystyle {\mathfrak {A}}}$.
3. Новатор выбирает либо члена ${\displaystyle a_{2}}$ структуры ${\displaystyle {\mathfrak {A}}}$ или члена ${\displaystyle b_{2}}$ структуры ${\displaystyle {\mathfrak {B}}}$.
4. Консерватор выбирает элемент ${\displaystyle a_{2}}$ или ${\displaystyle b_{2}}$ в модели, из которой Новатор не выбирал.
5. Новатор и Консерватор продолжают выбирать члены из структур ${\displaystyle {\mathfrak {A}}}$ и ${\displaystyle {\mathfrak {B}}}$ ещё на ${\displaystyle n-2}$ шагах.
6. Под конец игры мы выбрали различные элементы ${\displaystyle a_{1},\dots ,a_{n}}$ структуры ${\displaystyle {\mathfrak {A}}}$ и ${\displaystyle b_{1},\dots ,b_{n}}$ структуры ${\displaystyle {\mathfrak {B}}}$. Мы поэтому имеем две структуры на множестве ${\displaystyle \{1,\dots ,n\}}$, одна получена из структуры ${\displaystyle {\mathfrak {A}}}$ отображением ${\displaystyle i}$ в ${\displaystyle a_{i}}$, а другая получена из ${\displaystyle {\mathfrak {B}}}$ отражением ${\displaystyle i}$ в ${\displaystyle b_{i}}$. Консерватор выигрывает, если эти структуры одинаковы. Новатор выигрывает, если они не одинаковы.

Для любого n мы определяем отношение ${\displaystyle {\mathfrak {A}}{\stackrel {n}{\sim }}{\mathfrak {B}}}$, если Консерватор выигрывает в игре с n ходами ${\displaystyle G_{n}({\mathfrak {A}},{\mathfrak {B}})}$. Это все отношения эквивалентности на классе структур с заданными символами отношений. Пересечение всех этих отношений снова является отношением эквивалентности ${\displaystyle {\mathfrak {A}}\sim {\mathfrak {B}}}$.

Легко доказать, что если Консерватор выигрывает игру для всех n, то есть ${\displaystyle {\mathfrak {A}}\sim {\mathfrak {B}}}$, то ${\displaystyle {\mathfrak {A}}}$ и ${\displaystyle {\mathfrak {B}}}$ элементарно эквивалентны. Если множество отношений символов конечно, обратное тоже верно.

Челночный метод (или метод подбора), использованный в игре Эренфойхта — Фраиса для проверки элементарной эквивалентности предложил Роланд Фрейсе в своей диссертации[3][4]. Метод сформулировал в виде игры Анджей Эренфойхт[5]. Названия Spoiler и Duplicator дал Joel Spencer[6]. Также используются названия Eloise и Abelard (и обозначаются часто ${\displaystyle \exists }$ и ${\displaystyle \forall }$) по именам Элоиза и Абеляр, по схеме именований, предложенной Вильфридом Ходжисом в его книге Теория моделей.

Глава 1 книги Пуазы по теории моделей[7] содержат введение в игру Эренфойхта — Фраиса. Главы 6, 7 и 13 книги Розенштейна о линейных порядках[8] также содержит введение в игру. Простые примеры игры Эренфойхта — Фраиса есть в одной из колонок MathTrek Иварса Петерсона[9].

Введение в игру Эренфойхта — Фраиса и некоторые простые примеры этой игры можно найти в книге Верещагина и Шеня[10].

Слайды Фокион Колайтиса[11] и глава книги Нейла Иммермана[12] об играх Эренфойхта — Фраиса обсуждают приложения в информатике, методологической теореме для доказательства невыразимости и некоторые простые доказательства невыразимости с помощью этой методологии.

• Six Lectures Ehrenfeucht-Fraïssé games at MATH EXPLORERS' CLUB, Cornell Department of Mathematics.
• Modeloids I, Miroslav Benda, Transactions of the American Mathematical Society, Vol. 250 (Jun 1979), pp. 47 – 90 (44 pages)