# On some infinitary logics

Jouko Väänänen  Department of Mathematics and Statistics
Yliopistonkatu 3
00014 Helsinki, Finland<EMAIL_ADDRESS>http://www.math.helsinki.fi/logic/people/jouko.vaananen/ and  Boban Veličković
Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG)
Université Paris Cité
Bâtiment Sophie Germain
8 Place Aurélie Nemours
75013 Paris, France<EMAIL_ADDRESS>https://webusers.imj-
prg.fr/ boban.velickovic/

###### Abstract.

We define a new class of infinitary logics $\mathscr{L}^{1}_{\kappa,\alpha}$
generalizing Shelah’s logic $\mathbb{L}^{1}_{\kappa}$ defined in [14]. If
$\kappa=\beth_{\kappa}$ and $\alpha<\kappa$ is infinite then our logic
coincides with $\mathbb{L}^{1}_{\kappa}$. We study the relation between these
logics for different parameters $\kappa$ and $\alpha$. We give many examples
of classes of structures that can or cannot be defined in these logics.
Finally, we give a different version of Lindström’s Theorem for
$\mathbb{L}^{1}_{\kappa}$ in terms of the $\phi$-submodel relation.

###### Key words and phrases:

infinitary logic, interpolation theorems, partition relations

###### 2020 Mathematics Subject Classification:

Primary: 03Bxx, 03C55, 03C75, 03C95, 03Exx

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 The similarity game
    1. 3.1 Komjath-Shelah lemma
    2. 3.2 The Main Theorem
  4. 4 Examples
    1. 4.1 Cardinality
    2. 4.2 Covering every small set by countably many sets from a fixed list
    3. 4.3 The models $\Phi(A)$
    4. 4.4 The irrationals vs. the reals
    5. 4.5 The reals vs. the reals minus a point
    6. 4.6 $\kappa^{\leq\omega}$ and $\kappa^{\leq\omega}\setminus\\{b\\}$
    7. 4.7 Prikry forcing and the game $\rm DG^{\beta}_{<\kappa,\alpha}$
    8. 4.8 $\oplus_{n}\Phi$ and $\Phi$
  5. 5 A class of infinitary logics
  6. 6 Characterizing the logic $\mathbb{L}^{1}_{\kappa}$
  7. 7 Open problems
  8. 8 Acknowledgements

##  1\. Introduction

Lindström Theorem [8] characterizes first order logic as the maximal logic
satisfying the Compactness Theorem and the downward Löwenheim-Skolem Theorem.
Despite intensive efforts, no such model theoretic characterizations were
obtained for infinitary logics, until Shelah’s paper [14]. There is a
generally held intuition that if a logic has a model theoretic
characterization, it should satisfy the Craig Interpolation Theorem. Thus a
good direction to look for such logics is to look for infinitary logics with
the Craig Interpolation Theorem. Malitz [11] proved that infinitary logics
${\mathscr{L}}_{\kappa\omega}$, for $\kappa\geq\aleph_{2}$, fail to have
Interpolation but, if $\kappa$ is regular, any valid implication can be
interpolated in ${\mathscr{L}}_{(2^{<\kappa})^{+},\kappa}$. Shelah’s
$\mathbb{L}^{1}_{\kappa}$, which was defined in [14], has Interpolation, and
is actually between ${\mathscr{L}}_{\kappa\omega}$ and
${\mathscr{L}}_{\kappa\kappa}$ for strongly inaccessible $\kappa$, and also
for many other $\kappa$.

Thus $\mathbb{L}^{1}_{\kappa}$ satisfies the requirement of being a nice
logic, but has nevertheless attracted very little attention (this was actually
predicted by Shelah himself in [14]). In this paper we try to remedy this
situation. We first define a variation of Shelah’s game by adding an extra
ordinal parameter $\alpha$. Shelah’s game corresponds to setting
$\alpha=\omega$. We also introduce the infinite version of the game. We study
the relations between these games for various parameters and give examples of
properties that can or cannot be detected by our games. Finally, we consider a
class of logics $\mathscr{L}^{1}_{\kappa,\alpha}$, for a cardinal $\kappa$ and
ordinal $\alpha<\kappa$. If $\kappa=\beth_{\kappa}$ then these logics coincide
with $\mathbb{L}^{1}_{\kappa}$, for all $\alpha<\kappa$. We also give a
version of Lindström’s theorem characterizing the logic
$\mathbb{L}^{1}_{\kappa}$ in terms of a $\phi$-submodels relation, for all
formulas $\phi$.

The paper is organized as follows. In §2 we review the basic notions of
generalized logics and recall Lindström’s characterization of first order
logic. In §3 we define our variation $\rm DG^{\beta}_{\theta,\alpha}$ of
Shelah’s game and study the relation between these games for various
parameters. The main result of this section is a theorem that allows to reduce
the ordinal $\alpha$ in these games to $\omega$. More precisely, given a
cardinal $\theta$ and an ordinal $\beta$, we find $\theta^{*}$ and $\beta^{*}$
such that if $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ are two structures in
the same vocabulary, and if Eve has a winning strategy in ${\rm
DG}^{\beta^{*}}_{\theta^{*},\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$, then
she has a winning strategy in ${\rm
DG}^{\beta}_{\theta,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. In §4 we give
a number of examples of properties of structures that can or cannot be
detected by our games $\rm DG^{\beta}_{\theta,\alpha}$, for various parameters
$\beta,\theta$ and $\alpha$. In §5 we define a class of logics
$\mathscr{L}^{1}_{\kappa,\alpha}$ and show that they are regular. For the
above theorem on the reduction on $\alpha$ we deduce that for
$\kappa=\beth_{\kappa}$ all these logics coincide with Shelah’s
$\mathbb{L}^{1}_{\kappa}$. §6 contains our characterization of
$\mathbb{L}^{1}_{\kappa}$ in terms of the $\phi$-submodel relation
$\preceq_{\phi}$ that has the Union Property and the Löwenheim-Skolem number
below $\kappa$. We deduce Shelah’s characterizations of
$\mathbb{L}^{1}_{\kappa}$ as a corollary. Finally, in §7 we list some open
questions related to our logics $\mathscr{L}^{1}_{\kappa,\alpha}$.

##  2\. Preliminaries

We start by reviewing the general framework of generalized logics. We work in
von Neumann–Bernays–Gödel set theory (NBG) which allows us to speak of proper
classes. For simplicity we restrict ourselves to notions of logics based on
conventional algebraic structures with a single sorted vocabulary. For a more
systematic presentation we refer the reader to [1, Chapter 2]. Given a
vocabulary $\tau$ we denote by ${\rm Str}[\tau]$ the class of
$\tau$-structures. Given a structure $\mathfrak{A}$ we write
$\tau_{\mathfrak{A}}$ for the vocabulary of $\mathfrak{A}$. If
$\sigma\subseteq\tau$ are vocabularies and $\mathfrak{A}$ is a
$\tau$-structure we write $\mathfrak{A}\restriction\sigma$ for the
$\sigma$-reduct of $\mathfrak{A}$, which is obtained by ”forgetting” the
interpretations of the symbols of $\tau$ which do not belong to $\sigma$.
Given two vocabularies $\tau$ and $\sigma$, a bijection $\rho:\tau\to\sigma$
is called a renaming if it maps constant symbols to constant symbols, function
symbols to functions symbols of the same arity, and similarly for relation
symbols. Given a renaming $\rho:\tau\to\sigma$ and a $\tau$-structure
$\mathfrak{A}$ we can rename $\mathfrak{A}$ by $\rho$ in the natural way, thus
obtaining a $\sigma$-structure $\mathfrak{B}=\mathfrak{A}^{\rho}$. We now
recall the basic definition of a generalized logic.

######  Definition 2.1.

A logic is a pair $(\mathscr{L},\models_{\mathscr{L}})$ defined on
vocabularies, where $\mathscr{L}[\tau]$ is the set (or proper class) of all
$\mathscr{L}$-sentences of vocabulary $\tau$, and $\models_{\mathscr{L}}$ (the
$\mathscr{L}$-satisfaction relation) is a relation between $\tau$ structures
and $\mathscr{L}$-sentences and the following hold:

  1. (1)

If $\tau\subseteq\sigma$ then $\mathscr{L}[\tau]\subseteq\mathscr{L}[\sigma]$;

  2. (2)

If $\mathfrak{A}\models_{\mathscr{L}}\phi$ then
$\phi\in\mathscr{L}[\tau_{\mathfrak{A}}]$;

  3. (3)

(Isomorphism property) If $\mathfrak{A}\models_{\mathscr{L}}\phi$ and
$\mathfrak{B}\simeq\mathfrak{A}$ then $\mathfrak{B}\models_{\mathscr{L}}\phi$;

  4. (4)

(Reduct property) If $\phi\in\mathscr{L}[\tau]$, $\mathfrak{A}$ is a
structure, and $\tau\subseteq\tau_{\mathfrak{A}}$ then

$\mathfrak{A}\models_{\mathscr{L}}\phi\hskip 14.22636pt\mbox{ iff }\hskip
14.22636pt\mathfrak{A}\restriction\tau\models_{\mathscr{L}}\phi.$

  5. (5)

(Renaming property) Let $\rho:\tau\to\sigma$ be a renaming of vocabularies.
Then for each $\phi\in\mathscr{L}[\tau]$ there is a sentence $\phi^{\rho}$ in
$\mathscr{L}[\sigma]$ such that

$\mathfrak{A}\models_{\mathscr{L}}\phi\hskip 14.22636pt\mbox{ iff }\hskip
14.22636pt\mathfrak{A}^{\rho}\models_{\mathscr{L}}\phi^{\rho}.$

It is often convenient to have variables and formulas available in a logic.
This is achieved in a natural way by generalizing Definition 2.1. Suppose
$\tau$ is a vocabulary. Let $\\{c_{i}:i\in I\\}$ be a set of new constant
symbols. Let $\tau^{\prime}=\tau\cup\\{c_{i}:i\in I\\}$ and let $\phi$ be a
sentence in $\mathscr{L}[\tau^{\prime}]$. We consider $\phi$ as a formula in
$\mathscr{L}[\tau]$ and we write $\phi(\bar{x})$, where $\bar{x}=(x_{i}:i\in
I)$ and the $x_{i}$ are new variables. Given a $\tau$-structure $\mathfrak{A}$
and a sequence $(a_{i}:i\in I)$ of elements of $A$ we write
$\mathfrak{A}\models_{\mathscr{L}}\phi[\bar{a}]$ if by interpreting $c_{i}$ by
$a_{i}$ we obtain a $\tau^{\prime}$-structure
$\mathfrak{A}^{\prime}=(\mathfrak{A},a_{i};i\in I)$ such that
$\mathfrak{A}^{\prime}\models_{\mathscr{L}}\phi$. In this way we can replace
$\mathscr{L}$ by two functions ${\rm Sent}_{\mathscr{L}}[\tau]$ of
$\mathscr{L}$-sentences of vocabulary $\tau$ and ${\rm
Form}_{\mathscr{L}}[\tau]$ of $\mathscr{L}$-formulas of vocabulary $\tau$. We
can then define notions such as the free occurrence of variables in a
canonical way. For further details and discussion we refer the reader to [1,
Chapter 2].

Given a logic $\mathscr{L}$, a vocabulary $\tau$, and
$\phi\in\mathscr{L}[\tau]$, we let ${\rm Mod}_{\mathscr{L}}^{\tau}(\phi)$
denote the class of all models of $\phi$, i.e.

${\rm Mod}_{\mathscr{L}}^{\tau}(\phi)=\\{\mathfrak{A}\in{\rm
Str}[\tau]:\mathfrak{A}\models_{\mathscr{L}}\phi\\}.$

Given two sentences $\phi,\psi\in\mathscr{L}[\tau]$ we say that $\phi$
$\mathscr{L}$-implies $\psi$ and write

$\phi\models_{\mathscr{L}}\psi$

if ${\rm Mod}_{\mathscr{L}}^{\tau}(\phi)\subseteq{\rm
Mod}_{\mathscr{L}}^{\tau}(\psi)$, i.e. every $\tau$-structure that satisfies
$\phi$ also satisfies $\psi$.

We let ${\mathscr{L}}_{\omega,\omega}$ denote the usual first order logic. We
now recall some basic closure properties of a logic which ensure that it is at
least as strong as ${\mathscr{L}}_{\omega,\omega}$.

######  Definition 2.2.

Let $\mathscr{L}$ be a logic. We have:

  1. (1)

(Atom property) For all $\tau$ and all atomic
$\phi\in{\mathscr{L}}_{\omega,\omega}[\tau]$, there is
$\psi\in\mathscr{L}[\tau]$ such that

${\rm Mod}^{\tau}_{\mathscr{L}}(\psi)={\rm
Mod}^{\tau}_{\mathscr{L}_{\omega,\omega}}(\phi).$

  2. (2)

(Negation property) For all $\tau$ and all $\phi\in\mathscr{L}[\tau]$, there
is a $\psi\in\mathscr{L}[\tau]$, denoted by $\neg\phi$, such that:

${\rm Mod}^{\tau}_{\mathscr{L}}(\psi)={\rm Str}[\tau]\setminus{\rm
Mod}^{\tau}_{\mathscr{L}}(\phi).$

  3. (3)

(Conjunction property) For all $\tau$ and
$\phi_{0},\phi_{1}\in\mathscr{L}[\tau]$ there is $\psi\in\mathscr{L}[\tau]$,
denoted by $\phi_{0}\wedge\phi_{1}$, such that:

${\rm Mod}^{\tau}_{\mathscr{L}}(\psi)={\rm
Mod}^{\tau}_{\mathscr{L}}(\phi_{0})\cap{\rm
Mod}^{\tau}_{\mathscr{L}}(\phi_{1}).$

  4. (4)

(Particularization property) If $\tau$ is a vocabulary and $c\in\tau$ is a
constant symbol, then for every $\phi\in\mathscr{L}[\tau]$ there is
$\psi\in\mathscr{L}[\tau\setminus\\{c\\}]$ such that for all
$(\tau\setminus\\{c\\})$-structures $\mathfrak{A}$ we have
$\mathfrak{A}\models_{\mathscr{L}}\psi$ iff there is $a\in A$ (the universe of
$\mathfrak{A}$), such that $(\mathfrak{A},a)\models_{\mathscr{L}}\phi$. If
such $\psi$ exists we denote it by $\exists c\phi$.

Let $\tau$ be a vocabulary and $\mathfrak{A}\in{\rm Str}[\tau]$. We say that
$C\subseteq A$ is $\tau$-closed if $C$ is nonempty, $c^{\mathfrak{A}}\in C$,
for all constant symbols $c\in\tau$, and $C$ is closed under
$f^{\mathfrak{A}}$, for all function symbols $f\in\tau$.

######  Definition 2.3.

(Relativization property) We say that a logic $\mathscr{L}$ satisfies the
relativization property if the following holds. Suppose $\sigma$ and $\tau$
are vocabularies, $c$ a constant symbol with $c\notin\sigma\cup\tau$,
$\chi\in\mathscr{L}[\sigma\cup\\{c\\}]$ and $\phi\in\mathscr{L}[\tau]$. Then
there is $\psi\in\mathscr{L}[\sigma\cup\tau]$ such that if $\mathfrak{B}$ is a
$(\sigma\cup\tau)$-structure and $\chi^{\mathfrak{B}}=\\{b\in
B:(\mathfrak{B},b)\models_{\mathscr{L}}\chi\\}$ is $\tau$-closed in
$\mathfrak{B}$, then

$\mathfrak{B}\models_{\mathscr{L}}\psi\hskip 14.22636pt\mbox{iff}\hskip
14.22636pt(\mathfrak{B}\restriction\tau)|\chi^{\mathfrak{B}}\models_{\mathscr{L}}\phi.$

Intuitively, $\psi$ is the relativization of $\phi$ to $\chi^{\mathfrak{B}}$
and is often written as $\phi^{\\{c|\chi(c)\\}}$. If $\chi$ is the formula
$P(c)$, for some unary predicate symbol $P$, we then simply write it as
$\phi^{P}$.

Relativization allows us to represent one $\tau$-structure in another one by
relativizing to a definable subset of the bigger structure. However, if we
want to be able to talk about many $\tau$-structures inside a
$\sigma$-structure $\mathfrak{A}$ we should be able to express the
parameterized version of the symbols of $\tau$ in the vocabulary of
$\mathfrak{A}$ and then we should be able to say that for each suitable choice
of the parameters the corresponding induced structure satisfies a given
$\mathscr{L}[\tau]$-sentence sentence $\phi$. We only state a weaker form of
substitution called atomic substitution which is sufficient for our needs.

######  Definition 2.4.

(Atomic substitution) We say that a logic $\mathscr{L}$ satisfies atomic
substitution if the following holds. Suppose that $\tau$ and $\sigma$ are
vocabularies. Let $U\in\sigma$ be a binary relation. Suppose for every
constant symbol $c\in\tau$, we have a unary function symbol $K_{c}\in\sigma$,
for every $n$-ary relation symbol $R\in\tau$, we have an $n+1$-ary relation
symbol $K_{R}\in\sigma$, and for every $n$-ary function symbol $f\in\tau$, we
have an $n+1$-ary function symbol $K_{f}\in\sigma$. Finally, let $d\in\sigma$
be a constant symbol. Now, let $\mathfrak{A}$ be a $\sigma$-structure and let
$a=d^{\mathfrak{A}}$. Let

$B_{a}=\\{b\in A:U^{\mathfrak{A}}(b,a)\\}.$

If $R\in\tau$ is an $n$-ary relation symbol we can define an $n$-ary relation
$R^{\mathfrak{B}_{a}}$ on $B_{a}$ by letting

$R^{\mathfrak{B}_{a}}(b_{0},\ldots,b_{n-1})\hskip 14.22636pt\mbox{iff}\hskip
14.22636ptK_{R}^{\mathfrak{A}}(b_{0},\ldots,b_{n-1},a).$

If $c\in\tau$ is a constant symbol, we
$c^{\mathfrak{B}_{a}}=K_{c}^{\mathfrak{A}}(a)$. If $f\in\tau$ is an $n$-ary
function symbol, we can define an $n$-ary function $f^{\mathfrak{B}_{a}}$ by
letting $f^{\mathfrak{B}_{a}}(\bar{b})=K_{f}^{\mathfrak{A}}(\bar{b},a)$, for
all $\bar{b}\in A^{n}$. If $B_{a}$ is closed under these interpretation of the
symbols of $\tau$ we obtain a $\tau$-structure $\mathfrak{B}_{a}$. We require
that for each $\tau$-sentence $\phi$, there is a $\sigma$-sentence $\psi$ such
that

$\mathfrak{A}\models_{\mathscr{L}}\psi\hskip 14.22636pt\mbox{iff \hskip
14.22636pt $\mathfrak{B}_{a}$ is a $\tau$-structure and
}\mathfrak{B}_{a}\models_{\mathscr{L}}\phi.$

Let us note that the stronger form of substitution is obtained if the
interpretation of the symbols of $\tau$ in the structure $\mathfrak{B}_{a}$ is
given not by interpretations of corresponding symbols of $\sigma$, but by
$\mathscr{L}[\sigma]$-formulas.

We say that a logic $\mathscr{L}$ is small, if for every signature $\tau$, the
collection $\mathscr{L}[\tau]$ of $\tau$ sentences is a set. We say that a
logic $\mathscr{L}$ is regular if it is small and satisfies all the properties
of Definition 2.1 and Definition 2.4. Note that relativization follows from
atomic substitution.

We shall also need the notion of the occurrence number. Given a logic
$\mathscr{L}$, the occurrence number of $\mathscr{L}$, if it exists is the
smallest cardinal $\gamma$ such that:

$\mathscr{L}[\tau]=\bigcup_{\tau_{0}\in[\tau]^{<\gamma}}\mathscr{L}[\tau_{0}].$

Note that the occurrence number of the usual first order logic is $\omega$ and
the occurrence number of the infinitary logic, $\mathscr{L}_{\kappa,\lambda}$
is $\lambda$, see [3].

There is a natural way to compare logics.

######  Definition 2.5.

Suppose $\mathscr{L}$ and $\mathscr{L}^{\prime}$ are regular logics.

  1. (1)

We say that $\mathscr{L}^{\prime}$ is stronger than $\mathscr{L}$, and write
$\mathscr{L}\leq\mathscr{L}^{\prime}$, if for every vocabulary $\tau$ and
every $\mathscr{L}[\tau]$-sentence $\phi$ there is an
$\mathscr{L}^{\prime}[\tau]$ sentence $\psi$ such that ${\rm
Mod}^{\tau}_{\mathscr{L}^{\prime}}(\psi)={\rm
Mod}^{\tau}_{\mathscr{L}}(\phi)$.

  2. (2)

We say that $\mathscr{L}$ and $\mathscr{L}^{\prime}$ are equivalent and write
$\mathscr{L}\equiv\mathscr{L}^{\prime}$ if
$\mathscr{L}\leq\mathscr{L}^{\prime}$ and
$\mathscr{L}^{\prime}\leq\mathscr{L}$.

We now recall some desirable properties of logics. We will restrict ourselves
to regular logics to avoid some pathologies.

######  Definition 2.6.

Let $\mathscr{L}$ be a regular logic and let $\kappa$ be an infinite cardinal.

  1. (1)

We say that $\mathscr{L}$ is $\kappa$-weakly compact if for every vocabulary
$\tau$ of cardinality at most $\kappa$, and every set $T$ of
$L[\tau]$-sentences, if every $T_{0}\subseteq T$ of cardinality $<\kappa$ has
a model, then so does $T$. We say that $\mathscr{L}$ is $\kappa$-compact if
this holds without any restriction on the cardinality of $\tau$.

  2. (2)

We say that $\mathscr{L}$ has the $\kappa$-Löwenheim-Skolem property, if for
every vocabulary $\tau$ and $\phi\in\mathscr{L}[\tau]$, if $\phi$ has a model
then it has a model of cardinality $<\kappa$.

  3. (3)

We say that $\mathscr{L}$ satisfies the Craig interpolation property if for
every vocabularies $\tau_{0}$ and $\tau_{1}$, and
$\phi_{0}\in\mathscr{L}[\tau_{0}]$ and $\phi_{1}\in\mathscr{L}[\tau_{1}]$, if
$\phi_{0}\models_{\mathscr{L}}\phi_{1}$ then there is
$\psi\in\mathscr{L}[\tau_{0}\cap\tau_{1}]$ such that
$\phi_{0}\models_{\mathscr{L}}\psi$ and $\psi\models_{\mathscr{L}}\phi_{1}$.

There are numerous other interesting properties of abstract logics, such as
for instance the Beth definability property. We refer the reader to [1] and
[6] for details.

One of the first results in abstract model theory is the following well-known
result of Lindström.

######  Theorem 2.7 ([8]).

Let $\mathscr{L}$ be a regular logic. Then the following are equivalent:

  1. (1)

$\mathscr{L}$ is $\omega$-compact and has the $\omega_{1}$-Löwenheim-Skolem
property.

  2. (2)

$\mathscr{L}\equiv\mathscr{L}_{\omega,\omega}$.

It is possible to replace $(1)$ by a variety of other conditions. For
instance, given a logic $\mathscr{L}$ we can define the
$\mathscr{L}$-elementary submodel relation $\prec_{\mathscr{L}}$ as follows.
Given two structures $\mathfrak{A}$ and $\mathfrak{B}$ in the same vocabulary
$\tau$ such that $\mathfrak{A}$ is a substructure of $\mathfrak{B}$, we enrich
$\tau$ by adding a constant symbol $c_{a}$, for every element $a\in A$. We
then say that $\mathfrak{A}\prec_{\mathscr{L}}\mathfrak{B}$ if the expanded
structures $(\mathfrak{A},a)_{a\in A}$ and $(\mathfrak{B},a)_{a\in A}$ have
the same $\mathscr{L}$ theories, i.e. satisfies the same sentences in the
expanded language. Note that if the occurrence number of $\mathscr{L}$ is
$\gamma$ then this is equivalent to saying that for every $\bar{a}\in
A^{<\gamma}$ we have,
$(\mathfrak{A},\bar{a})\equiv_{\mathscr{L}}(\mathfrak{B},\bar{a})$.

######  Definition 2.8.

Let $\mathscr{L}$ be a regular logic. We say that $\mathscr{L}$ satisfies the
union property if, for every vocabulary $\tau$, and an increasing sequence of
$\tau$-structures $(\mathfrak{A}_{n})_{n}$ such that
$\mathfrak{A}_{0}\prec_{\mathscr{L}}\mathfrak{A}_{1}\prec_{\mathscr{L}}\ldots$,
if we let $\mathfrak{A}$ denote the union of the $\mathfrak{A}_{n}$, we have
that $\mathfrak{A}_{n}\prec_{\mathscr{L}}\mathfrak{A}$, for all $n$.

In [9] Lindström showed that (1) in Theorem 2.7 can be replaced by:

  * ($1^{\prime}$)

$\mathscr{L}$ is $\omega$-compact and has the union property.

It was felt that Lindström’s theorem underscores the importance of first order
logic as a maximal logic having some desirable properties. It then became a
holy grail of Abstract Model Theory to find stronger logics which have similar
characterizations by varying the defining properties. The search of such
logics has been largely unsuccessful until Shelah introduced his logic
$\mathbb{L}^{1}_{\kappa}$ in [14]. Unfortunately, by that time there were very
few people left working in Abstract Model Theory and therefore, as predicted
by Shelah himself, the ideas were not picked up by other researchers. One of
the goals of the current paper is to revive interest in this subject by
initiating a systematic study of Shelah’s logic and its variations.

##  3\. The similarity game

A logic measures the similarity of two structures of the same vocabulary. The
strongest similarity is if the two structures are isomorphic. Quite often we
can think of a logic as a type of a game between two players, Adam and Eve.
Let us suppose $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ are two structures in
the same vocabulary $\tau$. We will write $M_{i}$ for the universe of
$\mathfrak{M}_{i}$, and we will always assume that they are disjoint so that
no ambiguity arises. If they are not, this can be arranged by a standard
coding argument.

Now, we think of our game as follows. Eve claims to know that
$\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ are isomorphic, but she won’t tell
us the isomorphism. Instead she will answer a series of Adam’s questions of a
particular kind. In the process she has to match some elements of $M_{0}$ with
elements of $M_{1}$, i.e. she reveals a part of the unknown isomorphism. So if
at some position the matching Eve played is not a partial isomorphism then Eve
loses the game. The game may be finite or infinite, in fact we may allow games
of uncountable length, although this will not be done in this paper.

For the logics we are interested in we will start by defining the positions in
the game and then describe the moves from one position to another. Our basic
definition is a slight generalization of the one from [14]. Throughout this
section we fix two structures $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ in the
same vocabulary $\tau$.

######  Definition 3.1.

Given ordinals $\alpha$ and $\beta$, and a cardinal $\theta$, a
$(\beta,\theta,\alpha)$-_position_ for $(\mathfrak{M}_{0},\mathfrak{M}_{1})$
is a tuple $p=(\beta_{p},A_{p}^{0},A_{p}^{1},g_{p},h_{p})$, where

  1. (1)

$\beta_{p}\leq\beta$.

  2. (2)

$A_{p}^{0}\in[M_{0}]^{\leq\theta}$ and $A_{p}^{1}\in[M_{1}]^{\leq\theta}$.

  3. (3)

$g_{p}:A_{p}^{0}\to A_{p}^{1}$ a partial isomorphism.

  4. (4)

$h_{p}:A_{p}^{0}\cup A_{p}^{1}\to\alpha$.

  5. (5)

$h_{p}^{-1}(0)\cap A_{p}^{0}\subseteq\mathop{{\rm dom}}(g_{p})$ and
$h_{p}^{-1}(0)\cap A_{p}^{1}\subseteq\mathop{{\rm ran}}(g_{p})$.

We refer to $\beta_{p}$ as the height of $p$. For $a\in\mathop{{\rm
dom}}(h_{p})$, we refer to $h_{p}(a)$ as the height of $a$ in the position
$p$. We say that a position $q$ _extends_ position $p$, and write $q<p$, if

  1. (1)

$\beta_{q}<\beta_{p}$.

  2. (2)

$A_{q}^{0}\supseteq A_{p}^{0}$ and $A_{q}^{1}\supseteq A_{p}^{1}$.

  3. (3)

$g_{q}\restriction A_{p}^{0}=g_{p}$.

  4. (4)

If $a\in A_{p}^{0}\cup A_{p}^{1}$, then $h_{q}(a)\leq h_{p}(a)$, and if
$h_{p}(a)>0$, then $h_{q}(x)<h_{p}(a)$.

Note that any $(\beta,\theta,\alpha)$-position is also an
$(\beta^{\prime},\theta^{\prime},\alpha^{\prime})$-position, for any
$\beta^{\prime}\geq\beta$, $\theta^{\prime}\geq\theta$, and
$\alpha^{\prime}\geq\alpha$.

######  Definition 3.2.

Given ordinals $\alpha$ and $\beta$, and a cardinal $\theta$, the game $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ is played
between two players, Adam and Eve. The starting position is
$(\beta,\emptyset,\emptyset,\emptyset,\emptyset)$. Eve consecutively plays
$(\beta,\theta,\alpha)$-positions according to the following rule. If the
current position is $p$ then:

  * •

Adam chooses $\beta^{\prime}<\beta_{p}$, $B_{0}\in[M_{0}]^{\leq\theta}$ and
$B_{1}\in[M_{1}]^{\leq\theta}$,

  * •

Eve chooses a position $q<p$ such that $\beta_{q}=\beta^{\prime}$,
$B_{0}\subseteq A_{q}^{0}$ and $B_{1}\subseteq A_{q}^{1}$.

We declare the next position to be $q$. The player who cannot move loses and
the opponent wins.

The intuition is the following. A position describes a partial information
about an unknown isomorphism between $\mathfrak{M}_{0}$ and
$\mathfrak{M}_{1}$. We think of $\gamma$ as the height of the position. This
height is chosen by Adam and it should be at most $\beta$. Elements of
$A_{0}\cup A_{1}$ are assigned heights by Eve and they must be ordinals
$<\alpha$. Going from one position $p$ to the next one $p^{\prime}$, Adam asks
questions about the unknown isomorphism by requiring that the next sets
$A^{\prime}_{0}$ and $A^{\prime}_{1}$ contain $B_{0}$ and $B_{1}$
respectively. Each time he does this he must decrease the height of the
position. Eve is not required to answer the questions immediately. Instead,
she assigns heights to elements of $A_{0}\cup A_{1}$. These heights are
ordinals $<\alpha$. Going from one position to the next one, Eve is required
to decrease the heights of the elements that were present in the old position.
Once the height of an element $A_{0}\cup A_{1}$ reaches $0$, Eve must match it
with an element of height $0$ in the other structure. This matching must be a
partial isomorphism, otherwise Eve loses. Since the heights of the positions
go down the game must stop after finitely many steps. There may still be
elements of $A_{0}\cup A_{1}$ whose heights are not $0$ and Eve is not obliged
to match them with elements of the other structure.

Since the game must end in finitely many moves, by the Gale-Stewart theorem
[4] it is determined. We will write
$A^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ if Adam has a
winning strategy, and
$E^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ if Eve has a
winning strategy in the game $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

We first observe that if Eve has a winning strategy, she has a _positional_
winning strategy, i.e. a strategy which at every move only depends on the
position of the game, not on the history how the game evolved into that
position.

######  Lemma 3.3.

Eve has a winning strategy in the game $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ if and only if
there is a set $K$ of $(\beta,\theta,\alpha)$-positions such that:

  1. (1)

$(\beta,\emptyset,\emptyset,\emptyset,\emptyset)\in K$.

  2. (2)

If $p\in K$, then for all $\beta^{\prime}<\beta_{p}$, for all $B_{0}\supseteq
A_{p}^{0}$ and $B_{1}\supseteq A_{p}^{1}$ such that
$B_{0}\in[M_{0}]^{\leq\theta}$ and $B_{1}\in[M_{1}]^{\leq\theta}$, there is a
position $q\in K$ with $q<p$ such that $\beta_{q}=\beta^{\prime}$,
$A_{q}^{0}\supseteq B_{0}$ and $A_{q}^{1}\supseteq B_{1}$.

###### Proof.

Let us first suppose such a set $K$ exists. Eve’s winning strategy is to play
so that the position of the game stays in $K$. Conversely, suppose $\tau$ is a
winning strategy for Eve. Let $K$ be the set of all positions arising when Eve
plays according to $\tau$ against all possible legal move combinations of
Adam, including the starting position
$(\beta,\emptyset,\emptyset,\emptyset,\emptyset)$. This $K$ clearly satisfies
the requirements. ∎

Let us start by making some comments on the effect of the parameters. First,
if $\alpha=1$, then the game $\rm
DG^{\beta}_{\theta,1}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ is essentially the
Ehrenfeucht-Fraïssé game of the usual infinitary logic
$\mathscr{L}_{\infty,\theta^{+}}$ for formulas of quantifier rank $\beta$. We
will write $\rm DG^{\beta}_{\theta}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ for
the game $\rm DG^{\beta}_{\theta,1}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. For
$1<n<\omega$, Eve has a winning strategy in $\rm
DG^{n\cdot\beta}_{\theta,n}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ iff she has
one in $\rm DG^{\beta}_{\theta}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.
Therefore, in order to get something new we should allow $\alpha$ to be
infinite. The case $\alpha=\omega$ is Shelah’s game from [14].

######  Proposition 3.4.

If $\beta\leq\alpha$, then Eve has a winning strategy in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$, for any
$\theta$ and any two structures $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ in
the same vocabulary.

###### Proof.

The winning strategy is to keep playing positions $p$ such that
$h_{p}(a)\geq\beta_{p}$, for all $a\in A^{0}_{p}\cup A^{1}_{p}$, and $g_{p}$
is the empty function. Given such a position $p$, Adam plays some
$\beta^{\prime}<\beta_{p}$, $B_{0}\in[M_{0}]^{\leq\theta}$ and
$B_{1}\in[M_{1}]^{\leq\theta}$. Eve defines the position $q$ by letting:
$A^{0}_{q}=A^{0}_{p}\cup B_{0}$, $A^{1}_{q}=A^{1}_{p}\cup B_{1}$, and $h_{q}$
is the constant function on $A^{0}_{q}\cup A^{1}_{q}$ taking the value
$\beta^{\prime}$. Given that the starting position is
$(\beta,\emptyset,\emptyset,\emptyset,\emptyset)$ and $\beta\leq\alpha$, she
can clearly do this throughout the game. ∎

######  Proposition 3.5.

Let $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ be two structures in the same
vocabulary. If Eve has a winning strategy in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ and
$\beta^{\prime}\leq\beta$, $\theta^{\prime}\leq\theta$ and
$\alpha^{\prime}\geq\alpha$, then she has one in the game $\rm
DG^{\beta^{\prime}}_{\theta^{\prime},\alpha^{\prime}}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

###### Proof.

We may assume that Eve’s winning strategy, say $\sigma$, in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ plays sets
$A^{0}_{p}$ and $A^{1}_{p}$ of the least possible size. Namely, suppose we are
in a position $p$ in the game $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ and Adam plays
some $\beta^{\prime}<\beta_{p}$, and sets $B_{0}\in[M_{0}]^{\leq\theta}$ and
$B_{1}\in[M_{1}]^{\leq\theta}$. Then $\sigma$ responds by playing a position
$q$ such that:

$|A^{0}_{q}|\leq\max(|A^{0}_{p}|,|B_{0}|,\aleph_{0}),$

and similarly for $A^{1}_{q}$. Then $\sigma$ is also a winning strategy for
Eve in $\rm
DG^{\beta^{\prime}}_{\theta^{\prime},\alpha^{\prime}}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.
∎

We now define the infinite version of the game $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

######  Definition 3.6.

Given two structures $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ in the same
vocabulary, the game $\rm
DG_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ is like $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ except that
Adam does not make moves in $\beta$. The game lasts $\omega$ moves.

Note that $\rm DG_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ is
closed for Eve, so by the Gale-Stewart theorem [4] it is determined.

######  Proposition 3.7.

Suppose $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ are two structures in the
same vocabulary. Let $\kappa=|M_{0}^{\theta}\cup M_{1}^{\theta}|$ and let
$\alpha<\kappa^{+}$. If Eve has a winning strategy in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$, for all
$\beta<\kappa^{+}$, then she has a winning strategy in $\rm
DG_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

###### Proof.

By Lemma 3.3, we know that Eve has a positional winning strategy in the game
$\rm DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$, for all
$\beta$. Let $K_{\beta}$ be such a strategy. We define a set $K$ as follows.
Let $(A^{0},A^{1},g,h)\in K$ iff the set

$\\{\beta:\exists\beta^{\prime}>\beta\;(\beta,A^{0},A^{1},g,h)\in
K_{\beta^{\prime}}\\}$

is unbounded in $\kappa^{+}$. We claim that $K$ is a positional winning
strategy for Eve in $\rm
DG_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. To see this, suppose
$p=(A^{0}_{p},A^{1}_{p},g_{p},h_{p})\in K$ is a position, and let
$B_{0}\in[M_{0}]^{\leq\theta}$ and $B_{1}\in[M_{1}]^{\leq\theta}$ be given.
For each $\beta<\kappa^{+}$ there are $\beta^{\prime}$ and
$\beta^{\prime\prime}$ such that $\beta<\beta^{\prime}<\beta^{\prime\prime}$
and $(\beta^{\prime},A^{0}_{p},A^{1}_{p},g_{p},h_{p})\in
K_{\beta^{\prime\prime}}$. Then $(\beta,B_{0},B_{1})$ is a legitimate move for
Adam in $\rm
DG^{\beta^{\prime\prime}}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$
in position $(\beta^{\prime},A^{0}_{p},A^{1}_{p},g_{p},h_{p})$. Pick
$q_{\beta}\in K_{\beta^{\prime\prime}}$ which extends
$(\beta^{\prime},A^{0}_{p},A^{1}_{p},g_{p},h_{p})$, and such that
$\beta_{q}=\beta$, $B_{0}\subseteq A^{0}_{q_{\beta}}$ and $B_{1}\subseteq
A^{1}_{q_{\beta}}$. Since there are at most $\kappa$ possibilities for
$(A^{0}_{q_{\beta}},A^{1}_{q_{\beta}},g_{q_{\beta}},h_{q_{\beta}})$, there
must be a single quadruple $(A^{0},A^{1},g,h)$ which appears for unboundedly
many $\beta<\kappa^{+}$. It follows that $q=(A^{0},A^{1},g,h)\in K$ and is a
legitimate reply to Adam’s move $(B_{0},B_{1})$ in the game $\rm
DG_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. ∎

While the game $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ is obviously
symmetric, the existence of a winning strategy for Eve may not be transitive.
In other words, if Eve wins $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ and $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{1},\mathfrak{M}_{2})$, she may not
win $\rm DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.
Nevertheless, there is a weak version of transitivity that we now explain. In
order to do this we will use natural sum of ordinals, see [15]. Recall that
for ordinals $\alpha$ and $\beta$, the natural sum of $\alpha$ and $\beta$,
denoted by $\alpha\oplus\beta$, is defined by simultaneous induction on
$\alpha$ and $\beta$ as the smallest ordinal greater than
$\alpha\oplus\gamma$, for all $\gamma<\beta$, and $\gamma\oplus\beta$, for all
$\gamma<\alpha$. Another way to define the natural sum of two ordinals
$\alpha$ and $\beta$ is to use the Cantor normal form: one can find a sequence
of ordinals $\gamma_{0}>\ldots\gamma_{n-1}$ and two sequences
($k_{0},\ldots,k_{n-1})$ and $(j_{0},\ldots,j_{n-1})$ of natural numbers
(including zero, but satisfying $k_{i}+j_{i}>0$, for all $i$) such that
$\alpha=\omega^{\gamma_{0}}\cdot k_{0}+\cdots+\omega^{\gamma_{n-1}}\cdot
k_{n-1}$ and $\beta=\omega^{\gamma_{0}}\cdot
j_{0}+\cdots+\omega^{\gamma_{n-1}}\cdot j_{n-1}$ and defines

$\alpha\oplus\beta=\omega^{\gamma_{0}}\cdot(k_{0}+j_{0})+\cdots+\omega^{\gamma_{n-1}}\cdot(k_{n-1}+j_{n-1}).$

What is important for us is that the natural sum is associative and
commutative. It is always greater or equal to the usual sum, but it may be
strictly greater.

######  Proposition 3.8.

Suppose $\mathfrak{M}_{0}$, $\mathfrak{M}_{1}$, and $\mathfrak{M}_{2}$ are
structures in the same vocabulary. Let $\beta$, $\alpha$ and $\alpha^{\prime}$
be ordinals and $\theta$ a cardinal. Suppose Eve wins the games $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ and $\rm
DG^{\beta}_{\theta,\alpha^{\prime}}(\mathfrak{M}_{1},\mathfrak{M}_{2})$. Then
she wins the game $\rm
DG^{\beta}_{\theta,\alpha\oplus\alpha^{\prime}}(\mathfrak{M}_{0},\mathfrak{M}_{2})$.

###### Proof.

We may assume that $M_{0}$, $M_{1}$, and $M_{2}$ are pairwise disjoint. Let
$K$ and $L$ be positional winning strategies for Eve in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ and $\rm
DG^{\beta}_{\theta,\alpha^{\prime}}(\mathfrak{M}_{1},\mathfrak{M}_{2})$,
respectively. Let

$M=\\{(p,q)\in K\times L:\beta_{p}=\beta_{q}\mbox{ and }A^{1}_{p}\subseteq
A^{0}_{q}\\}.$

Given $(p,q)\in M$ we define a position $r=p\circ q$ in $\rm
DG^{\beta}_{\theta,\alpha\oplus\alpha^{\prime}}(\mathfrak{M}_{0},\mathfrak{M}_{2})$
as follows. First, we let $\beta_{r}=\beta_{p}$, $A^{0}_{r}=A^{0}_{p}$,
$A^{1}_{r}=A^{1}_{q}$. We now define $h_{r}$. If $a\in A^{0}_{p}$ and
$h_{p}(a)>0$, we let $h_{r}(a)=h_{p}(a)\oplus\alpha^{\prime}$. If $h_{p}(a)=0$
then $g_{p}(a)$ is defined. We then let $h_{r}(a)=h_{q}(g_{p}(a))$. If $a\in
A^{1}_{q}$ the definition is symmetric. Namely, if $h_{q}(a)>0$ we let
$h_{r}(a)=\alpha\oplus h_{q}(a)$. If $h_{q}(a)=0$, then $g_{q}^{-1}(a)$ is
defined. So we let $h_{r}(a)=h_{p}(g_{q}^{-1}(a))$. Finally, we let
$g_{r}=g_{q}\circ g_{p}$. By this we mean $g_{r}(a)$ is defined if both
$h_{p}(a)=0$ and $h_{q}(g_{p}(a))=0$ in which case we let
$g_{r}(a)=g_{q}(g_{p}(a))$. Finally, we let

$K\circ L=\\{p\circ q:(p,q)\in M\\}.$

We claim that $K\circ L$ is a positional winning strategy for Eve. To see
this, suppose $r\in K\circ L$ and fix $(p,q)\in M$ such that $r=p\circ q$. Fix
$\beta^{\prime}<\beta_{r}$, and $B_{0}\in[M_{0}]^{\leq\theta}$ and
$B_{1}\in[M_{2}]^{\leq\theta}$. We need to show that there is $r^{\prime}<r$
with $r^{\prime}\in K\circ L$ such that $\beta_{r^{\prime}}=\beta^{\prime}$,
$B_{0}\subseteq A^{0}_{r}$ and $B_{1}\subseteq A^{1}_{r}$. Since $p\in K$ and
$K$ is a positional winning strategy for Eve in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$, we can find
$p^{\prime}<p$ such that $\beta_{p^{\prime}}=\beta$, $B_{0}\subseteq
A^{0}_{p^{\prime}}$ and $A^{0}_{q}\subseteq A^{1}_{p^{\prime}}$. Now, since
$L$ is a positional winning strategy for Eve in $\rm
DG^{\beta}_{\theta,\alpha^{\prime}}(\mathfrak{M}_{1},\mathfrak{M}_{2})$ we can
find $q^{\prime}<q$ with $\beta_{q^{\prime}}=\beta^{\prime}$ and such that
$A^{1}_{p^{\prime}}\subseteq A^{0}_{q^{\prime}}$ and $B_{1}\subseteq
A^{1}_{q^{\prime}}$. Let $r^{\prime}=p^{\prime}\circ q^{\prime}$. It is clear
that $r^{\prime}<r$, $\beta_{r^{\prime}}=\beta^{\prime}$, $B_{0}\subseteq
A^{0}_{r^{\prime}}$, and $B_{1}\subseteq A^{1}_{r^{\prime}}$. It follows that
$K\circ L$ is a positional winning strategy for Eve in $\rm
DG^{\beta}_{\theta,\alpha\oplus\alpha^{\prime}}(\mathfrak{M}_{0},\mathfrak{M}_{2})$.
∎

We now consider the question of reducing the ordinal $\alpha$ in the game.
More precisely, given $\beta,\alpha$ and $\theta$, we would like to find
$\beta^{*}$ and $\theta^{*}$ which are not too big relative to $\beta$ and
$\theta$ and such that
$E^{\beta^{*}}_{\theta^{*},\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ implies
$E^{\beta}_{\theta,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. As a warm-up
we first consider infinite games.

######  Proposition 3.9.

Let $\theta$ be a cardinal and let $\alpha<(2^{\theta})^{+}$ be an ordinal.
Suppose $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ are two structures in the
same vocabulary. If Eve wins $\rm
DG_{2^{\theta},\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ (the big game) then
she wins $\rm DG_{\theta,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ (the
small game).

###### Proof.

The two games are determined. Suppose towards a contradiction that Eve has a
winning strategy $\tau$ in the big game and Adam has a winning strategy
$\sigma$ in the small game. Let $\lambda$ be a sufficiently large regular
cardinal such that $\mathfrak{M}_{0}$, $\mathfrak{M}_{1}$, $\sigma$ and $\tau$
belong to $H(\lambda)$, where $H(\lambda)$ denotes the set of all sets whose
transitive closure is $<\lambda$. We fix an increasing $\in$-chain
$(H_{n})_{n}$ of elementary submodels of $H(\lambda)$ of size $2^{\theta}$,
containing all the relevant parameters and such that $H_{n}$ is closed under
$\theta$-sequence, for all $n$. We can also arrange that $2^{\theta}\subseteq
H_{0}$. Since $\alpha<(2^{\theta})^{+}$ and $\alpha\in H_{0}$, this implies
that $\alpha\subseteq H_{0}$, as well. Let $H=\bigcup_{n}H_{n}$. We take the
role of Adam and play one master play in the big game against $\tau$ as
follows. We start by playing $(M_{0}\cap H_{0},M_{1}\cap H_{0})$. Let $p_{0}$
be the response of $\tau$. Since $\tau,M_{0},M_{1},H_{0}\in H_{1}$, we have
that $p_{0}\in H_{1}$. We then play $(M_{0}\cap H_{1},M_{1}\cap H_{1})$, and
let $p_{1}$ be the reply of $\tau$. By a similar consideration, we have that
$p_{1}\in H_{2}$. We continue in this way: at stage $n$ we play $(M_{0}\cap
H_{n},M_{1}\cap H_{n})$. Let $(p_{n})_{n}$ be the sequence of $\tau$’s
responses. Let us say $p_{n}=(A^{0}_{n},A^{1}_{n},g_{n},h_{n})$, for all $n$.
Notice that $g_{n}\in H_{n+1}$, for all $n$. Let $g=\bigcup_{n}g_{n}$. Then
$g$ is an isomorphism between $M_{0}\cap H$ and $M_{1}\cap H$. Notice that if
$a\in(M_{0}\cup M_{1})\cap H_{n}$ then $a\in\mathop{{\rm dom}}(h_{k})$, for
all $k\geq n$. The sequence of values $\\{h_{k}(a):k\geq n\\}$ is decreasing
until it reaches $0$. When $h_{k}(a)=0$ then $a\in\mathop{{\rm dom}}(g_{k})$,
if $a\in M_{0}$, and $a\in\mathop{{\rm ran}}(g_{k})$, if $a\in M_{1}$. For
$a\in(M_{0}\cup M_{1})\cap H$, let:

$h(a)=\min\\{n:h_{n}(a)=0\\}.$

We now describe how to defeat Adam’s strategy $\sigma$ in the small game.
Suppose the first move of $\sigma$ is $(B^{0}_{0},B^{1}_{0})$. Since
$\sigma\in H_{0}$ it follows that $(B^{0}_{0},B^{1}_{0})\in H_{0}$. Since
$p_{0}\in H_{1}$, we can find $C^{0}_{0},C^{1}_{0}\in H_{1}$ of size
$\leq\theta$ such that

  1. (1)

$C^{i}_{0}\in[A^{i}_{0}]^{\leq\theta}$, for $i=0,1$,

  2. (2)

$B^{i}_{0}\subseteq C^{i}_{0}$, for $i=0,1$,

  3. (3)

$g_{0}[C^{0}_{0}]\subseteq C^{1}_{0}$ and $g_{0}^{-1}[C^{1}_{0}]\subseteq
C^{0}_{0}$.

To get $C^{1}_{0}$ we simply add to $B^{1}_{0}$ the images under $g_{0}$ of
elements of $B^{0}_{0}$ which are in $\mathop{{\rm dom}}(g_{0})$, and to get
$C^{0}_{0}$ we add to $B^{0}_{0}$ the preimages of elements of $B^{1}_{0}$ in
the range of $g_{0}$. Let $g_{0}^{*}=g_{0}\restriction C^{0}_{0}$ and
$h_{0}^{*}=h_{0}\restriction(C^{0}_{0}\cup C^{1}_{0})$. Since $C^{0}_{0}$ and
$C^{1}_{0}$ are of size $\leq\theta$ and $H_{1}$ is closed under $\theta$
sequence, we have that $g_{0}^{*},h_{0}^{*}\in H_{1}$. Therefore, the tuple
$q_{0}=(C^{0}_{0},C^{1}_{0},g_{0}^{*},h_{0}^{*})$ is an element of $H_{1}$ and
is a legitimate response of Eve to Adam’s play $(B^{0}_{0},B^{1}_{0})$ in the
small game. Suppose the move of $\sigma$ in position $q_{0}$ is
$(B^{0}_{1},B^{1}_{1})$. Since $\sigma\in H_{1}$ we also have that
$(B^{0}_{1},B^{1}_{0})\in H_{1}$. We now repeat the above procedure, this time
in $H_{2}$, to get sets $C^{0}_{1}$ and $C^{1}_{1}$. Let
$g_{1}^{*}=g_{1}\restriction C^{0}_{1}$. Define $h_{1}^{*}$ by letting, for
$a\in C^{0}_{1}\cup C^{1}_{1}$,

$h_{1}^{*}(a)=\begin{cases}h(a)-1,&\text{if $h(a)>0$}\\\ 0,&\text{if
$h(a)=0$}\end{cases}$

We get a tuple $q_{1}=(C^{0}_{1},C^{1}_{1},g_{1}^{*},h_{1}^{*})$ which is a
legitimate reply of Eve to the move $(B^{0}_{1},B^{1}_{1})$ of $\sigma$ in the
position $q_{0}$. As before, we argue that $q_{1}\in H_{2}$. Given the current
position $q_{n}\in H_{n+1}$ we let $(B^{0}_{n},B^{1}_{n})$ be the move of
$\sigma$. We then move to the next model $H_{n+2}$ to define Eve’s next move
$q_{n+1}$. At east step we decrease the previous heights of elements in
$C^{0}_{n}\cup C^{0}_{n}$ by $1$, unless they are already $0$, and for those
elements we use the function $g_{n}$ to define the function $g_{n}^{*}$. By
continuing like this for $\omega$ moves we defeat $\sigma$, which contradicts
our assumption that $\sigma$ is a winning strategy for Adam in the small game.
∎

###  3.1. Komjath-Shelah lemma

We now turn to a partition theorem due to Komjath-Shelah [7] that we will need
in the main theorem of this section. Given an ordinal $\gamma$ let
$FS(\lambda)$ denote the set of finite decreasing sequences of ordinals from
$\lambda$. So, elements of $FS(\gamma)$ are sequences $s$ of the form
$s(0)s(1)\ldots s(n-1)$ with $\lambda>s(0)>s(1)>\ldots s(n-1)$. Here $n=|s|$
is the length of $s$. Note that we can identify $s$ with a finite subset of
$\lambda$ given in the decreasing ordering. An immediate extension of a
sequence $s$ with one ordinal $\gamma$ is denoted by $s\gamma$. If $\alpha$ is
an ordinal, then an $\alpha$-system in $\lambda$ is a system of ordinals
$\\{e(s):s\in FS(\alpha)\\}$ from $\lambda$ such that:

  1. (1)

$e(\gamma)<e(\gamma^{\prime})<\lambda$, for $\gamma<\gamma^{\prime}<\lambda$,

  2. (2)

$e(s\gamma)<e(s\gamma^{\prime})<e(s)$, for $\gamma<\gamma^{\prime}<{\rm
min}(s)$, if $s\neq\emptyset$.

If $e$ is an $\alpha$-system in $\lambda$, we can define an embedding
$\pi_{e}:FS(\alpha)\to FS(\lambda)$ by letting $\pi_{e}(\emptyset)=\emptyset$,
and if $s\in FS(\alpha)$ is non empty,

$\pi_{e}(s)=e(s(0)),e(s(0)s(1)),\ldots e(s).$

We will need the following result of Komjath-Shelah [7].

######  Theorem 3.10 ([7]).

Assume that $\alpha$ is an ordinal and $\mu$ a cardinal. Set
$\lambda=(|\alpha|^{\mu^{\aleph_{0}}})^{+}$. Suppose
$F:FS(\lambda^{+})\to\mu$. Then there is $e$, an $\alpha$-system in $\lambda$,
and a function $c:\omega\to\mu$ such that $F(\pi_{e}(s))=c(|s|)$, for all
$s\in FS(\alpha)$.

###### Proof.

For completeness we produce a proof of this result. Suppose $\alpha$, $I$,
$\lambda$ and $F$ are as in the statement of the lemma. For $c:\omega\to I$,
we define the ranking function $r_{c}$ on $FS(\lambda^{+})$ as follows. First,
if $s\in FS(\lambda^{+})$ and there is $i\leq|s|$ such that $F(s\restriction
i)\neq c(i)$, then we let $r_{c}(s)=-1$. Otherwise we say that $r_{c}(s)\geq
0$. We define what it means that $r_{c}(s)\geq\xi$, by induction on $\xi$. We
say that $r_{c}(s)\geq\xi$ iff for every $\nu<\xi$ we have

${\rm otp}\\{\gamma<{\rm min}(s):r_{c}(s\gamma)\geq\nu\\}\geq\lambda.$

Here we consider that ${\rm min}(\emptyset)=\lambda^{+}$. Finally, we let
$r_{c}(s)=\xi$ if $r_{c}(s)\geq\xi$, but $r_{c}(s)\geq\xi+1$ is not true.

######  Lemma 3.11.

There is $c:\omega\to\mu$ such that $r_{c}(\emptyset)\geq\alpha$.

###### Proof.

Let $n$ be an integer. Let $\lambda^{\leq n}$ denote the tree of all sequences
of ordinals from $\lambda$ of length at most $n$. Let $T$ be a subtree of
$\lambda^{\leq n}$. We say that a node $s\in T$ is a $\lambda$-splitting node
if $|\\{\xi:s\xi\in T\\}|=\lambda$. We say that $T$ is fully splitting if
every non maximal node $s$ of $T$ is $\lambda$-splitting.

######  Claim 3.12.

Let $n$ be an integer and $T$ a fully splitting subtree of $\lambda^{\leq n}$.
Suppose $I$ is a set of cardinality $|\alpha|^{\mu^{\aleph_{0}}}$ and $F:T\to
I$ is a function. Then there is a fully splitting subtree $R$ of $T$ and a
function $d:n+1\to I$ such that $F(s)=d(|s|)$, for all $s\in R$.

###### Proof.

We prove this by induction on $n$. For $n=1$, since
$\lambda=(|\alpha|^{\mu^{\aleph_{0}}})^{+}$ this follows by the Pigeon Hole
Principle. Suppose the claim is true for fully splitting subtrees of
$\lambda^{\leq n}$ and let $T$ be a fully splitting subtree of $\lambda^{\leq
n+1}$. Let $L$ be the first level of $T$. For each $\gamma\in L$ let

$T_{\gamma}=\\{s\in\lambda^{\leq n}:\gamma s\in T\\}.$

Then $T_{\gamma}$ is a fully splitting subtree of $\lambda^{\leq n}$. By
inductive assumption we can find a fully splitting subtree $R_{\gamma}$ of
$T_{\gamma}$ and $d_{\gamma}:n+1\to I$ such that

$F(\gamma s)=d_{\gamma}(|s|),\mbox{ for all }s\in T_{\gamma}.$

Since $|I^{\omega}|=|I|$, we can find a subset $L^{*}$ of $L$ of cardinality
$\lambda$ and a fixed $d^{*}:n+1\to I$ such that $d_{\gamma}=d$, for all
$\gamma\in L^{*}$. By shrinking $L^{*}$ we can moreover arrange that
$F(\gamma)$ has a fixed value say $\rho$, for $\gamma\in L^{*}$. Let

$R=\\{\gamma s:\gamma\in L^{*}\mbox{ and }s\in R_{\gamma}\\}$

and let $d:n+2\to I$ be defined by: $d(0)=\rho$ and $d(k+1)=d^{*}(k)$, for
$k\leq n$. It is clear that $R$ and $d$ are as required.

∎

Let us say that a $(\lambda,n)$-assignment is a function $e:\lambda^{\leq
n}\to\lambda^{+}$ such that, for all $s\in\lambda^{<n}$,

$e(s\gamma)<e(s\gamma^{\prime})<e(s),\mbox{ for all
}\gamma<\gamma^{\prime}<\lambda.$

If $e$ is a $(\lambda,n)$-assignment we can define an embedding
$\pi_{e}:\lambda^{\leq n}\to FS(\lambda^{+})$ by letting

  1. (1)

$\pi_{e}(\emptyset)=\emptyset$,

  2. (2)

$\pi_{e}(s)=e(s(0)),e(s(0)s(1)),\ldots e(s)$, if $s\in\lambda^{\leq n}$ is non
empty.

Given a $(\lambda,n)$-assignment $e$ and $\gamma<\lambda^{+}$ we say that $e$
is above  $\gamma$ if $e(s)>\gamma$, for all $s\in\lambda^{\leq n}$. Note that
if $e$ is a $(\lambda,n)$-assignment which is above $\gamma+\lambda$ then $e$
can be extended to a $(\lambda,n+1)$-assignment which is above $\gamma$.
Finally, observe that $d$ is an $(\lambda,n)$-assignment and $T$ is a fully
splitting subtree of $\lambda{\leq n}$, then if we let $\sigma$ be the natural
isomorphism between $\lambda^{\leq n}$ and $T$ then $e\circ\sigma$ is a
$(\lambda,n)$-assignment as well.

Now, back to the proof of Lemma 3.11. Let us assume towards contradiction that
$r_{c}(\emptyset)<\alpha$, for all $c:\omega\to\mu$. We are going to construct
by induction on $n$, ordinals $d(n)$, and for each $c:\omega\to\mu$, ordinals
$\xi(c,n)$ with $-1\leq\xi(c,n)<\alpha$ such that for every
$\gamma<\lambda^{+}$ there is a $(\lambda,n)$-assignment $e$ which is above
$\gamma$ and such that, if $\pi_{e}$ be the embedding of $\lambda^{\leq n}$
derived from $e$, we have:

  1. (1)

$F(\pi_{e}(s))=d(|s|)$, for all $s\in\lambda^{\leq n}$,

  2. (2)

$r_{c}(\pi_{e}(s))=\xi(c,k)$, for all $s\in\lambda^{\leq n}$ and all
$c:\omega\to\mu$.

To start we let $d(0)=F(\emptyset)$ and $\xi(c,0)=r_{c}(\emptyset)$, for all
$c:\omega\to\mu$. For $\xi<\lambda^{+}$ we have: $F(\xi)\in\mu$ and
$r_{c}(\xi)<\alpha$, for all $c:\omega\to\mu$. By the Pigeon Hole Principle we
can find an ordinal $d(1)<\mu$ and, for each $c:\omega\to\mu$, an ordinal
$\xi(c,1)$ such that the set $W$ of ordinals $\xi<\lambda^{+}$ such that:

  1. (a)

$F(\xi)=d(1)$,

  2. (b)

$r_{c}(\xi)=\xi(c,1)$, for all $c:\omega\to\mu$.

is cofinal in $\lambda^{+}$. Now, for $\gamma<\lambda^{+}$ we construct a
$(\lambda,1)$-assignment satisfying (1) and (2). Fix $\gamma<\lambda^{+}$.
Since $W$ is cofinal in $\lambda^{+}$ we can find an increasing function
$f:\lambda\to W\setminus(\gamma+1)$. We now define $e:\lambda^{\leq
1}\to\lambda^{+}$ by letting $e(\emptyset)$ be any ordinal above ${\rm
ran}(f)$ and letting $e(\eta)=f(\eta)$, for all $\eta<\lambda$. It is clear
that $e$ satisfies (1) and (2) and is above $\gamma$.

Now suppose we have constructed $d(k)$, and $\xi(c,k)$, for all $k\leq n$ and
$c:\omega\to\mu$. For each $\gamma<\lambda^{+}$ pick a
$(\lambda,n)$-assignment $e_{\gamma}$ above $\gamma+\lambda$ which witnesses
the inductive hypothesis. We can extend $e_{\gamma}$ to a
$(\lambda,n+1)$-assignment $e_{\gamma}^{*}$ above $\gamma$. By Claim 3.12 we
can then find a fully splitting subtree $T_{\gamma}$ of $\lambda^{\leq n+1}$,
an ordinal $d_{\gamma}(n+1)<\mu$, and for $c:\omega\to\mu$,
$-1\leq\xi_{\gamma}(c,n+1)<\alpha$ such that, for every $s\in\lambda^{n+1}$,
we have

  * •

$F(\pi_{e_{\gamma}}(s))=d_{\gamma}(n+1)$, for all $s\in\lambda^{n+1}$,

  * •

$r_{c}(\pi_{e_{\gamma}}(s))=\xi_{\gamma}(c,n+1)$, for $s\in\lambda^{n+1}$ and
all $c:\omega\to\mu$.

Now, by the Pigeon Hole Principle again, we can find an unbounded subset $W$
of $\lambda^{+}$, a fixed ordinal $d(n+1)<\mu$, $-1\leq\xi(c,n+1)<\alpha$, for
all $c:\omega\to\mu$, such that $d_{\gamma}(n+1)=d(n+1)$ and
$\xi_{\gamma}(c,n+1)=\xi(c,n+1)$, for all $\gamma\in W$ and $c:\omega\to\mu$.
Therefore the $(\lambda,n+1)$-assignments $e_{\gamma}^{*}$, witness (1) and
(2) for the values $d(n+1)$ and $\xi(c,n+1)$, for $c:\omega\to\mu$. This
completes the inductive step. Once the whole construction is completed we get
a function $d:\omega\to\mu$. However, note that then we have

$\xi(d,0)>\xi(d,1)>\xi(d,2)>\ldots$

which is a contradiction. ∎

We now return to the proof of Theorem 3.10. Fix $c:\omega\to\mu$ such that
$r_{c}(\emptyset)\geq\alpha$. We construct an $\alpha$-system $e$ with the
additional property that for every $s\in FS(\alpha)$ of length $n>0$,

$r_{c}(\pi_{e}(s))\geq s(n-1).$

To show this we have to show that if we are given an $t\in FS(\lambda^{+})$
with $r_{c}(t)\geq\beta$ then we can choose ordinals
$\\{\xi_{\gamma}:\gamma<\beta\\}$

  1. (1)

if $\gamma<\gamma^{\prime}<\beta$ then
$\xi_{\gamma}<\xi_{\gamma^{\prime}}<{\rm min}(t)$,

  2. (2)

$r_{c}(t\xi_{\gamma})\geq\gamma$, for all $\gamma<\beta$.

To see this let $\delta_{\gamma}$ be the supremum of the $\lambda$ first
ordinals $\xi$ such that $r_{c}(s\xi)\geq\gamma$. Note that, if
$\gamma<\gamma^{\prime}$ then $\delta_{\gamma}\leq\delta_{\gamma^{\prime}}$.
We are going to select by transfinite recursion the elements
$\xi_{\gamma}<\delta_{\gamma}$ as needed. At step $\gamma$ we have already
selected the ordinals $\\{\xi_{\gamma^{\prime}}:\gamma^{\prime}<\gamma\\}$.
Since
$\sup(\\{\xi_{\gamma^{\prime}}:\gamma^{\prime}<\gamma\\})\leq\delta_{\gamma}$.
Since $\delta_{\gamma}$ has cofinality $\lambda$ and $\gamma<\lambda$ we have
that
$\sup(\\{\xi_{\gamma^{\prime}}:\gamma^{\prime}<\gamma\\})<\delta_{\gamma}$.
Hence we can choose $\xi_{\gamma}$ as required.

Now we can define $e(s)$, for $s\in FS(\alpha)$, by induction on the length of
$s$, and satisfy the requirement that $r_{c}(\pi_{e}(s))\geq s(n-1)$, where
$n=|s|$. Recall that $r_{c}(\pi_{e}(s))\geq 0$ implies that
$F(\pi_{e}(s\restriction i))=c(i)$, for all $i\leq|s|$. Hence we must have
that $F(\pi_{e}(s))=c(|s|)$, for all $s\in FS(\alpha)$. This completes the
proof of Theorem 3.10.

∎

###  3.2. The Main Theorem

We now turn back to the question of reducing the ordinal $\alpha$ in the game.
Our plan is to combine the ideas of Proposition 3.9 and Theorem 3.10. Suppose
$\theta$ is a cardinal, $\alpha$ and $\beta$ are ordinals. Let
$\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ be two structures in the same
vocabulary. We would like to find cardinals $\theta^{*}$ and $\beta^{*}$ such
that if Eve wins the game $\rm
DG^{\beta^{*}}_{\theta^{*},\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ (the
big game), then she wins $\rm
DG_{\theta,\omega}^{\beta}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ (the small
game). We define a sequence of ordinals $(\Gamma(\xi):\xi\leq\beta)$ as
follows:

  1. (1)

$\Gamma(0)=2$,

  2. (2)

$\Gamma(\xi+1)=((\Gamma(\xi))^{|\alpha|^{\theta}})^{++}$,

  3. (3)

$\Gamma(\nu)=\sup_{\xi<\nu}\Gamma(\xi)$, if $\nu$ is limit.

Note that if $\kappa=\beth_{\kappa}$ and $\alpha,\theta,\beta<\kappa$, then
also $\Gamma(\beta)<\kappa$.

######  Theorem 3.13.

Let $\theta$ be a cardinal, $\alpha$ and $\beta$ be ordinals with
$\alpha<(2^{\theta})^{+}$ and $\beta$ limit. Let $(\Gamma(\xi):\xi\leq\beta)$
be defined as above, and let $\Gamma=\Gamma(\beta)$. Suppose
$\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ are two structures in the same
vocabulary. If Eve wins $\rm
DG^{\Gamma}_{2^{\theta},\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ (the big
game) then she wins the game $\rm
DG^{\beta}_{\theta,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ (the small
game).

###### Proof.

Note that both game are determined. We assume that Adam has a winning strategy
$\sigma$ in the small game, and Eve has a winning strategy $\tau$ in the big
game, and we derive contradiction. Recall that for an ordinal $\lambda$,
$FS(\lambda)$ denotes the set of descending sequences in $\lambda$, ordered by
extension. If $f,g$ are ordinal valued functions, we write $f<g$ if

  1. (1)

${\rm dom}(g)\subseteq{\rm dom}(f)$

  2. (2)

$f(a)\leq g(a)$, for all $a\in{\rm dom}(g)$,

  3. (3)

if $a\in{\mathop{{\rm dom}}g}$ and $g(a)\neq 0$, then $f(a)<g(a)$.

Let $\theta$ be a sufficiently big regular cardinal. We pick models
$H_{s}\prec H(\theta),s\in FS(\Gamma)$, such that:

  1. (1)

$\mathfrak{M}_{0},\mathfrak{M}_{1},\sigma,\tau\in H_{\emptyset}$,

  2. (2)

$s\in H_{s}$, for all $s\in FS(\Gamma)$,

  3. (3)

If $\lambda<{\rm min}(s)$, then $H_{s}\cup\\{H_{s}\\}\subseteq H_{s\lambda}$,

  4. (4)

$|H_{s}|=2^{\theta}$,

  5. (5)

$H_{s}^{\theta}\subseteq H_{s}$.

For each $s\in FS(\Gamma)$ we describe a $(\Gamma,2^{\theta},\alpha)$-position
$p_{s}$ for $(\mathfrak{M}_{0},\mathfrak{M}_{1})$ as follows. We let
$p_{\emptyset}=(\Gamma,\emptyset,\emptyset,\emptyset,\emptyset)$. If $s$ is
non empty, $p_{s}$ will be of the form $p_{s}=({\rm
min}(s),A^{0}_{s},A^{1}_{s},g_{s},h_{s})$, for some
$A^{0}_{s}\in[M_{0}]^{2^{\theta}},A^{1}_{s}\in[M_{1}]^{2^{\theta}}$, $g_{s}$ a
partial isomorphism between $A^{0}_{s}$ and $A^{1}_{s}$, and
$h_{s}:A^{0}_{s}\cup A^{1}_{s}\to\alpha$ is the height function for this
position. We require that, for all $s\in FS(\Gamma)$ which are non empty:

  1. (1)

$p_{s}\in H_{s}$,

  2. (2)

$p_{s}$ is a winning position for Eve in the big game,

  3. (3)

if $\lambda<{\rm min}(s)$ then $p_{s\lambda}<p_{s}$,

  4. (4)

if $\lambda<{\rm min}(s)$ then $H_{s}\cap M_{0}\subseteq A^{0}_{s\lambda}$ and
$H_{s}\cap M_{1}\subseteq A^{1}_{s\lambda}$.

Such a family of positions is easy to construct by induction on the length on
$s$. Let $s\in FS(\Gamma)$, and assume $p_{s}$ has been chosen and satisfies
the above conditions. For each $\lambda<\min{s}$, we go to the model
$H_{s\lambda}$ and let Adam play $(\lambda,H_{s}\cap M_{0},H_{s}\cap M_{1})$
in position $p_{s}$. We then let $p_{s\lambda}$ be the reply of Eve’s strategy
$\tau$ to this move. Since $H_{s}\cup\\{H_{s}\\}\subseteq H_{s\lambda}$ this
move by Adam belongs to $H_{s\lambda}$. Moreover, since $\tau\in
H_{s\lambda}$, we have that $p_{s\lambda}\in H_{s\lambda}$, and $p_{s\lambda}$
is a winning position for Eve in the big game.

We now describe how to play against Adam’s strategy $\sigma$ in $\rm
DG^{\beta}_{\theta,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. Suppose
$\sigma$ starts by playing some $(\beta_{0},B^{0}_{0},B^{1}_{0})$, with
$B^{0}_{0}\in[M_{0}]^{\theta}$, $B^{1}_{0}\in[M_{1}]^{\theta}$, and
$\beta_{0}<\beta$. Let $B_{0}=B^{0}_{0}\cup B^{1}_{0}$, and let $I_{0}$ be the
set of all functions $h:B^{0}\to\alpha$. Since $\sigma\in H_{\emptyset}$ and
$H_{\emptyset}$ is closed under $\theta$-sequences, we have that
$B^{0}\subseteq H_{\emptyset}$. Consider some $\lambda<\Gamma$. Then
$p_{\lambda}$ is of the form
$p_{\lambda}=(\lambda,A^{0}_{\lambda},A^{1}_{\lambda},g_{\lambda},h_{\lambda})$,
where $H_{\emptyset}\cap M_{0}\subseteq A^{0}_{\lambda}$ and
$H_{\emptyset}\cap M_{1}\subseteq A^{1}_{\lambda}$. Since $\sigma\in
H_{\emptyset}$ we have that $B^{0}_{0}$ and $B^{1}_{0}\in H_{\emptyset}$.
Moreover $H_{\emptyset}$ is closed under $\theta$-sequences, so
$B^{0}_{0},B^{1}_{0}\subseteq H_{\emptyset}$ as well. It follows that
$B^{0}\subseteq{\rm dom}(h_{\lambda})$. Therefore, for all $s\in FS(\Gamma)$
which are non empty, we have that $B^{0}\subseteq{\rm dom}(h_{s})$. We define
the function $F_{0}:FS(\Gamma)\to I_{0}$ by:

$F_{0}(s)=h_{s}\restriction B^{0}.$

By Theorem 3.10 there is a $(\Gamma(\beta_{0})+1)$-system $e_{0}$ and a
function $c_{0}:\omega\to I_{0}$ such that:

$F_{0}(\pi_{e_{0}}(s))=c_{0}(|s|),\mbox{ for all }s\in
FS(\Gamma(\beta_{0})+1).$

Then $c_{0}(0)$ is the empty function, and $c_{0}(n)$ is a total function from
$B^{0}$ to $\alpha$, for $n>0$. Moreover, $c_{0}(n+1)<c_{0}(n)$, for all
$n>0$, meaning that:

  1. (1)

$c_{0}(n+1)(a)\leq c_{0}(n)(a)$, for all $a\in B^{0}$,

  2. (2)

if $c_{0}(n)(a)\neq 0$ then $c_{0}(n+1)(a)<c_{0}(n)(a)$.

It follows that for every $a\in B^{0}$, there is $k$ such that
$c_{0}(k)(a)=0$. Let $h_{0}^{\prime}(a)$ be the least such $k$. This defines
the height function on $B^{0}$.

Let $\lambda_{0}=e_{0}(\Gamma(\beta_{0}))$. Then $p_{\lambda_{0}}\in
H_{\lambda_{0}}$. Let

  1. (1)

$C^{0}_{0}=B^{0}_{0}\cup g_{\lambda_{0}}^{-1}[B^{1}_{0}]$,

  2. (2)

$C^{1}_{0}=B^{1}_{0}\cup g_{\lambda_{0}}[B^{0}_{0}]$,

  3. (3)

$g^{*}_{0}=g_{\lambda_{0}}\restriction C^{0}_{0}$.

Finally, define the function $h^{*}_{0}:C^{0}_{0}\cup C^{1}_{0}\to\omega$ by:

$h^{*}_{0}(a)=\begin{cases}h^{\prime}_{0}(a)&\text{ if $a\in B^{0}_{0}\cup
B^{1}_{0}$,}\\\ 0&\text{otherwise}\end{cases}$

Let $q_{0}=(\beta_{0},C^{0}_{0},C^{1}_{0},g^{*}_{0},h^{*}_{0})$. We let Eve
play $q_{0}$ as her first move in the small game. Note that $q_{0}$ is a
legitimate response to Adam’s move $(\beta_{0},B^{0}_{0},B^{1}_{0})$ in this
game.

Suppose in the next move Adam’s strategy $\sigma$ responds by playing some
$(\beta_{1},B^{0}_{1},B^{1}_{1})$. Note that $q_{0}\in H_{\lambda_{0}}$, and
hence $(\beta_{1},B^{0}_{1},B^{1}_{1})\in H_{\lambda_{0}}$, as well. We have
$\beta_{1}<\beta_{0}$, $B^{0}_{1}\in[M_{0}]^{\theta}$ and $C^{0}_{0}\subseteq
B^{0}_{1}$, $B^{1}_{1}\in[M_{1}]^{\theta}$ and $C^{1}_{0}\subseteq B^{1}_{1}$.
Let $B^{1}=B^{0}_{1}\cup B^{1}_{1}$ and let $I_{1}$ be the set of all
functions $h:B^{1}\to\alpha$.

Consider some $\lambda<\Gamma(\beta_{0})$. Then
$p_{\lambda_{0}e_{0}(\lambda)}$ is of the form

$p_{\lambda}=(\lambda,A^{0}_{\lambda_{0}e_{0}(\lambda)},A^{1}_{\lambda_{0}e_{0}(\lambda)},g_{\lambda
e_{0}(\lambda)},h_{\lambda_{0}e_{0}(\lambda)}),$

where $H_{\lambda_{0}}\cap M_{0}\subseteq A^{0}_{\lambda_{0}e_{0}(\lambda)}$
and $H_{\lambda_{0}}\cap M_{1}\subseteq A^{1}_{\lambda_{0}e_{0}(\lambda)}$.
Since $B^{1}\in H_{\lambda_{0}}$ and $H_{\lambda_{0}}$ is closed under
$\theta$-sequences we have that $B^{1}\subseteq H_{\lambda_{0}}$ and hence
$B^{1}\subseteq{\rm dom}(h_{\lambda_{0}e_{0}(\lambda)})$. To simplify
notation, if $s\in FS(\Gamma(\beta_{0}))$ let us write $t_{0}(s)$ for
$\pi_{e_{0}}(\beta_{0}s)$. By the above, for all such $s$, we have that
$B^{1}\subseteq{\rm dom}(h_{t_{0}(s)})$.

We define the function $F_{1}:FS(\Gamma(\beta_{0}))\to I_{1}$ by:

$F_{1}(s)=h_{t_{0}(s)}\restriction B^{1}.$

By Theorem 3.10 there is a $(\Gamma(\beta_{1})+1)$-system $e_{1}$ in
$\Gamma(\beta_{0})$ and a function $c_{1}:\omega\to I_{1}$ such that:

$F_{1}(\pi_{e_{1}}(s))=c_{1}(|s|),\mbox{ for all }s\in
FS(\Gamma(\beta_{1})+1).$

Then $c_{1}(n)$ is a function from $B^{1}$ to $\alpha$, for all $n$. Moreover,
$c_{1}(n+1)<c_{1}(n)$, for all $n$, meaning that:

  1. (1)

$c_{1}(n+1)(a)\leq c_{1}(n)(a)$, for all $a\in B^{1}$,

  2. (2)

if $c_{1}(n)(a)\neq 0$ then $c_{1}(n+1)(a)<c_{1}(n)(a)$.

It follows that for every $a\in B^{1}$, there is $k$ such that
$c_{1}(k)(a)=0$. Let $h_{1}^{\prime}(a)$ be the least such $k$. This defines
the height function on $B^{1}$. The key point is that, for all $n$,

$c_{1}(n)\restriction B^{0}=c_{0}(n+1).$

To see this fix $a\in B^{0}$ and some $s\in FS(\Gamma(\beta_{1}))$ of length
$n$. Then $F_{1}(s)(a)=h_{t_{0}(s)}(a)$, and since the length of $t_{0}(s)$ is
$n+1$, we have

$h_{t_{0}(s)}(a)=c_{0}(n+1)(a).$

It follows that if $a\in B^{0}$ and $h^{\prime}_{0}(a)\neq 0$, then
$h^{\prime}_{1}(a)=h^{\prime}_{0}(a)-1$.

Let $\lambda_{1}=e_{0}(e_{1}(\Gamma(\beta_{1})))$. Then
$p_{\lambda_{0}\lambda_{1}}\in H_{\lambda_{0}\lambda_{1}}$. Let

  1. (1)

$C^{0}_{1}=B^{0}_{1}\cup g_{\lambda_{0}\lambda_{1}}^{-1}[B^{1}_{1}]$,

  2. (2)

$C^{1}_{1}=B^{1}_{1}\cup g_{\lambda_{0}\lambda_{1}}[B^{0}_{1}]$,

  3. (3)

$g^{*}_{1}=g_{\lambda_{0}\lambda_{1}}\restriction C^{0}_{1}$.

Finally, define the function $h^{*}_{1}:C^{0}_{1}\cup C^{1}_{1}\to\omega$ by:

$h^{*}_{0}(a)=\begin{cases}h^{\prime}_{1}(a)&\text{ if $a\in B^{0}_{1}\cup
B^{1}_{1}$,}\\\ 0&\text{otherwise}\end{cases}$

Let $q_{1}=(\beta_{1},C^{0}_{1},C^{1}_{1},g^{*}_{1},h^{*}_{1})$ and note that
$q_{1}$ is a legitimate response by Eve to the second move played by the
strategy $\sigma$ in the small game. Eve can continue playing in this way
indefinitely; referring to the big game in order to decide what to play in the
small game. Since Adam has to play a decreasing sequence of ordinals
$\beta_{0}>\beta_{1}>\ldots$, the game has to end after finitely many moves,
and so Eve wins this run of the game. Therefore, $\sigma$ is not a winning
strategy for Adam in the small game, a contradiction.

∎

##  4\. Examples

We give some examples on properties that can or cannot be detected by our
games.

###  4.1. Cardinality

######  Proposition 4.1.

Suppose $\mbox{cof}(\theta)>\omega$, $\alpha$ is a countable ordinal and
$\beta>\alpha$. Let $M_{0}$ and $M_{1}$ be two structures in the empty
vocabulary such that $|M_{0}|\geq\theta$ and $|M_{1}|<\theta$. Then Adam has a
winning strategy in $\rm DG^{\beta}_{\theta,\alpha}(M_{0},M_{1})$.

###### Proof.

We describe a winning strategy for Adam. We start by picking a subset $U$ of
$M_{0}$ of size $\theta$ and play as our first move $(\alpha,U,\emptyset)$.
Eve then plays some $h_{0}:U\to\alpha$. Let $Z_{0}=h_{0}^{-1}(0)$. Eve also
has to play an injective function $g_{0}:Z_{0}\to M_{1}$. Note that $Z_{0}$
has to be of size $<\theta$. Since ${\rm cof}(\theta)>\omega$ and $\alpha$ is
countable, there is an ordinal $\alpha_{0}<\alpha$ such that
$U_{0}=h_{0}^{-1}(\alpha_{0})$ has cardinality $\theta$. We then play
$(\alpha_{0},\emptyset,\emptyset)$. Eve responds by playing some
$h_{1}:U\to\alpha$ such that $h_{1}<h_{0}$, meaning that for all $a\in U$,
$h_{1}(a)\leq h_{0}(a)$, and if $h_{0}(a)\neq 0$ then $h_{1}(a)<h_{0}(a)$. Let
$Z_{1}=h_{1}^{-1}(0)$. Eve also has to play an injective function
$g_{1}:Z_{1}\to M_{1}$ such that $g_{1}$ extends $g_{0}$. We find an ordinal
$\alpha_{1}<\alpha_{0}$ such that $U_{1}=h_{1}^{-1}(\alpha_{1})$ has
cardinality $\theta$. We continue like this until at some stage we reach
$\alpha_{n}=0$. At that point $U_{n}=Z_{n}$ and this set has cardinality
$\theta$. Since $R_{1}$ has cardinality smaller than $\theta$, Eve cannot play
an injective function $g_{n}:Z_{n}\to M_{1}$, so she loses the game. ∎

###  4.2. Covering every small set by countably many sets from a fixed list

Let $\mathscr{C}$ be a class of structure in a given vocabulary $\tau$. For a
cardinal $\theta$ and ordinals $\alpha$ and $\beta$, we say that the game $\rm
DG^{\beta}_{\theta,\alpha}$ detects membership in $\mathscr{C}$, if for any
two $\tau$-stuctures $\mathfrak{M}$ and $\mathfrak{N}$ such that
$\mathfrak{M}\in\mathscr{C}$ and $\mathfrak{N}\notin\mathscr{C}$, Adam has a
winning strategy in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M},\mathfrak{N})$.

Suppose $\theta$ is an infinite cardinal. Let $\mathscr{S}_{\theta}$ be the
class of structures $(M,R)$, $R\subseteq M^{2}$, where, for all $a\in M$,

$|\\{b\in M:R(a,b)\\}|<\theta.$

Let $\mathscr{T}_{\theta}$ be the class of structures $(M,R)$, $R\subseteq
M^{2}$, where for all $X\in[M]^{<\theta}$ there is a countable set $Y$ such
that

$X\subseteq\\{b\in M:\exists a\in YR(a,b)\\}.$

In this case we say that $Y$ is a cover of $X$. Let
$\mathscr{K}_{\theta}=\mathscr{S}_{\theta}\cap\mathscr{T}_{\theta}$. If
$(M,R)\in\mathscr{K}_{\theta}$, then $R$ codes subsets of size $<\theta$ such
that every subset of size $<\theta$ is covered by countably many of them. The
following is straightforward.

######  Proposition 4.2.

If $\lambda=\lambda^{\omega}$, then there is a model in $\mathscr{K}_{\theta}$
of cardinality $\lambda$ if and only if $\lambda^{<\theta}=\lambda$. ∎

######  Proposition 4.3.

Suppose $\theta$ is a cardinal with $\mbox{cof}(\theta)>\omega$, $\alpha$ is a
countable ordinal and $\beta>\alpha\cdot 2$. Then $\rm
DG^{\beta}_{\theta,\alpha}$ detects membership in $\mathscr{S}_{\theta}$.

###### Proof.

Suppose $R_{0}$ is a binary relation on $M_{0}$ and $R_{1}$ a binary relation
on $M_{1}$. Let $\mathfrak{M}_{0}=(M_{0},R_{0})$ and
$\mathfrak{M}_{1}=(M_{1},R_{1})$ Suppose that
$\mathfrak{M}_{0}\in\mathscr{S}_{\theta}$ and
$\mathfrak{M}_{1}\notin\mathscr{S}_{\theta}$. We describe a winning strategy
for Adam in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ Let $a_{1}\in
M_{1}$ be such that $\\{b\in M_{1}:R_{1}(a_{1},b)\\}$ has size at least
$\theta$. Adam lets $\beta_{0}=\alpha\cdot 2$ and plays
$(\beta_{0},\emptyset,\\{a_{1}\\}$. Eve must respond by playing some height
function $h_{0}$. The partial isomorphism $g_{0}$ played by Eve is not
important. The only important point is that $a_{1}\in{\rm dom}(h_{0}).$ In the
next move Adam plays $\beta_{1}=\alpha+h_{0}(a_{1})$. Even then plays a lower
height function $h_{1}$ and Adam responds by playing
$\beta_{2}=\alpha+h_{1}(a_{1})$. In finitely many steps we reach some $n$ such
that $h_{n}(a_{1})=0$. At that point Eve must have $a_{1}\in{\rm ran}(g_{n})$.
Let $a_{0}=g^{-1}(a_{1})$. We also have that $\beta_{n}>\alpha$. Since
$\\{b\in M_{0}:R(a_{0},b)\\}$ has size $<\theta$, from this point Adam can use
the strategy as in the proof of Proposition 4.1 to win the game. ∎

######  Proposition 4.4.

Suppose $\mbox{cof}(\theta)>\omega$, $\alpha$ is a countable ordinal and
$\beta>\alpha\cdot 2$. Then $\rm DG^{\beta}_{\theta,\alpha}$ detects
membership in $\mathscr{T}_{\theta}$.

###### Proof.

Suppose $\mathfrak{M}_{0}=(M_{0},R_{0})\in\mathscr{T}_{\theta}$ and
$\mathfrak{M}_{1}=(M_{1},R_{1})\notin\mathscr{T}_{\theta}$, where $R_{0}$ is a
binary relation on $M_{0}$ and $R_{1}$ is a binary relation on $M_{1}$. If
$A,B\subseteq M_{0}$ we say that $A$ is a cover of $B$, if for every $b\in B$
there is $a\in A$ such that $R_{0}(a,b)$. We define a similar notion for
subsets of $M_{1}$. By our assumption every subset of $M_{0}$ of cardinality
$<\theta$ has a countable cover, but this is not true for $M_{1}$. We show
that Eve does not have a winning strategy in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. Since this
game is determined this means that Adam has a winning strategy.

Now, suppose towards contradiction that $\sigma$ is a winning strategy for
Eve. Let $U$ be a subset of $M_{1}$ of cardinality $<\theta$ that does not
have a countable cover. Adam sets $\beta_{0}=\alpha\cdot 2$ and plays as his
first move $(\beta_{0},\emptyset,U)$. Eve follows her strategy $\sigma$ and
responds by playing a position $(\beta_{0},A^{0}_{0},A^{1}_{0},g_{0},h_{0})$.
Since $U$ does not have a countable cover and $\alpha$ is countable, there is
$\alpha_{0}<\alpha$ such that $h_{0}^{-1}(\alpha_{0})\cap U$ does not have a
countable cover. In his next move Adam plays $\beta_{1}=\alpha+\alpha_{0}$. In
her next move following $\sigma$ Eve chooses a lower height function $h_{1}$.
Adam then finds an ordinal $\alpha_{1}<\alpha_{0}$ such that
$h_{1}^{-1}(\alpha_{1})\cap U$ does not have a countable cover, and plays
$\beta_{2}=\alpha+\alpha_{1}$. By playing like this, in finitely many stages
they reach an integer $n$ such that $\alpha_{n}=0$. At this stage we have that
the set $B_{1}=h_{n}^{-1}(0)\cap U$ does not have a countable cover. We also
have that $B_{1}\subseteq{\rm ran}(g_{n})$. Let $B_{0}=g_{n}^{-1}[B_{1}]$.
Since $B_{0}$ is of cardinality $<\theta$ and
$\mathfrak{M}_{0}\in\mathscr{T}_{\theta}$ $B_{0}$ has a countable cover, say
$A_{0}$. Now, for each $a\in A_{0}$ Adam runs a separate run of the game in
which Eve is forced to reveal the image of $a$ in $M_{1}$. Namely, in the next
stage of the game Adam sets $\beta_{n}=\alpha$ and plays
$(\beta_{n},\\{a\\},\emptyset)$. In her next move by $\sigma$ Eve has to play
a height function $h_{n+1}$ with $a\in{\rm dom}(h_{n+1})$. In his next move
Adam plays $\beta_{n+1}=h_{n+1}(a)$. Eve then plays a lower height function
$h_{n+2}$ and Adam responds by playing $\beta_{n+2}=h_{n+2}(a)$. In finitely
many stages they reach an integer $k$ such that $h_{k}(a)=0$. At that point we
must have $a\in{\rm dom}(g_{k})$. Let us denote by $f(a)$ the value
$g_{k}(a)$, for this integer $k$. Therefore we obtain a function $f:A_{0}\to
M_{0}$. Note that, for each $a\in A_{0}$ we had a separate run of the game in
which Eve follows her strategy $\sigma$, so we do not know that the function
$f$ is injective. Nevertheless the set $A_{1}=f[A_{0}]$ is countable. We claim
that $A_{1}$ is a cover of $B_{1}$. Indeed, given $b_{1}\in B_{1}$ let
$b_{0}\in B_{0}$ be such that $g_{n}(b_{0})=b_{1}$. Since $A_{0}$ is a cover
of $B_{0}$ there is $a\in A_{0}$ such that $R(a,b_{0})$. By following the run
of the game corresponding to $a$ we must have that $R(f(a),b_{1})$. Therefore,
$A_{1}$ is a countable cover of $B_{1}$, which is a contradiction.

∎

######  Corollary 4.5.

Suppose $\theta$ is a cardinal with $\mbox{cof}(\theta)>\omega$, $\alpha$ is a
countable ordinal and $\beta>\alpha\cdot 2$. Then $\rm
DG^{\beta}_{\theta,\alpha}$ detects membership in $\mathscr{K}_{\theta}$. ∎

###  4.3. The models $\Phi(A)$

We let $\eta$ denote the order type of the rationals. Suppose
$A\subseteq\omega_{1}$ is non empty. Let

$\Phi(A)=A\times([0,1)\cap\mathbb{Q})\cup(\omega_{1}\setminus
A)\times((0,1)\cap\mathbb{Q}).$

We consider the structure $(\Phi(A),<_{\rm lex})$, where $<_{\rm lex}$ is the
lexicographical ordering. It is well known that $\Phi(A)\cong\Phi(B)$ iff
$A\Delta B$ is non-stationary (see e.g. [12]).

######  Proposition 4.6.

Let $\alpha$ and $\beta$ be ordinals with $\alpha$ countable and
$\beta>\alpha\cdot 3$. Then $\Phi(A)\cong\Phi(B)$ iff Adam has a winning
strategyin $\rm DG^{\beta}_{\aleph_{1},\alpha}(\Phi(A),\Phi(B))$.

###### Proof.

We only have to prove the implication from right to left. Suppose $\Phi(A)$
and $\Phi(B)$ are not isomorphic. So the set $A\Delta B$ is stationary. We
describe a winning strategy for Adam in $\rm
DG^{\beta}_{\aleph_{1},\alpha}(\Phi(A),\Phi(B))$. Adam first forces Eve to
play an isomorphism between an uncountable subset of $\Phi(A)$ and a subset of
$\Phi(B)$. More precisely, Adam starts by setting $\beta_{0}=\alpha\cdot 3$
and plays $(\alpha\cdot 3,\Phi(A),\Phi(B))$. Eve assigns a height function
$h_{0}:\Phi(A)\cup\Phi(B)\to\alpha$ and plays a partial isomorphism between
$h_{0}^{-1}(0)\cap\Phi(A)$ and $h_{0}^{-1}(0)\cap\Phi(B)$. Let $\alpha_{0}$ be
the least such that $h_{0}^{-1}(\alpha_{0})$ is uncountable. In the next move
Adam plays $\beta_{1}=\alpha\cdot 2+\alpha_{0}$. Eve then plays some
$h_{1}:\Phi(A)\cup\Phi(B)\to\alpha$, which is lower than $h_{0}$, namely such
that, for all $x$,

  1. (1)

$h_{1}(x)\leq h_{0}(x)$,

  2. (2)

if $h_{0}(x)\neq 0$ then $h_{1}(x)<h_{0}(x)$.

Let $\alpha_{1}$ be the least such that $h_{1}^{-1}(\alpha_{1})\cap\Phi(A)$ is
uncountable. Note that if $\alpha_{0}\neq 0$ then $\alpha_{1}<\alpha_{0}$. In
this case Adam plays $\alpha_{1}$ as his next ordinal. He continues playing in
this way. After finitely many steps the ordinal $\alpha_{n}$ reaches $0$. The
ordinal $\beta_{n}$ is $\alpha\cdot 2$. At that stage Eve has played a partial
isomorphism $g_{n}:D\to R$, where $D$ is an uncountable subset of $\Phi(A)$
and $R$ is an uncountable subset of $\Phi(B)$. Let $\pi_{0}$ be the projection
to the first coordinate and let $C$ be the set of ordinals $\delta<\omega_{1}$
such that:

  1. (1)

if $g_{n}(x)=y$ then, $\pi_{0}(x)<\delta$ iff $\pi_{0}(y)<\delta$,

  2. (2)

$\delta$ is a limit point of $\\{\pi_{0}(x):x\in D\\}$ and $\\{\pi_{0}(y):y\in
R\\}$.

Then $C$ is a club in $\omega_{1}$. Since $A\Delta B$ is stationary, there is
$\delta\in C\cap A\Delta B$. For simplicity let us assume $\delta\in A$ and
$\delta\notin B$. Note that the set $D_{0}=\\{x\in D:\pi_{0}(x)<\delta\\}$ has
the supremum in $\Phi(A)$, namely $(\delta,0)$, while the set $R_{0}=\\{y\in
R:\pi_{0}(y)<\delta\\}$ does not have a supremum in $\Phi(B)$.

In the next block of moves Adam forces Eve to commit to the image of
$(\delta,0)$ in $\Phi(B)$. More precisely, Adam plays
$\beta_{n+1}=\alpha+h_{n}((\delta,0))$. Eve then plays some $h_{n+1}$ which is
lower than $h_{n}$. Adam plays $\beta_{n+2}=\alpha+h_{n+1}((\delta,0))$. He
continues like this until at some stage $m\geq n$, we have
$h_{m}((\delta,0))=0$. At this point we must have $(\delta,0)\in{\rm
dom}(g_{m})$. The ordinal $\beta_{m}$ then equals $\alpha$. Suppose
$g_{m}((\delta,0))=(\xi,q)$. Note that we must have $\xi\geq\delta$, for
otherwise $g_{m}$ could not be a partial isomorphism. Moreover, $(\xi,q)$ has
to be above all the elements of $R_{0}$. Since $R_{0}$ does not have a
supremum in $\Phi(B)$, Adam can find some element $y\in\Phi(B)$ which is above
all elements of $R_{0}$, but is also below $(\xi,q)$. In the final block of
moves Adam forces Eve to reveal the preimage of $y$. Namely, he starts this
block by playing $\beta_{m+1}=h_{m}(y)$. In the next move Eve plays the height
function $h_{m+1}$ which is lower than $h_{m}$. Adam plays
$\beta_{m+2}=h_{m+1}(y)$, etc. After finitely many steps we must have
$h_{k}(y)=0$, so there must be some $x\in{\rm dom}(g_{k})$ such that
$g_{k}(x)=y$. However, we would have $x<_{\rm lex}(\delta,0)$, so there is
some element $x^{\prime}\in D_{0}$ with $x<_{\rm lex}x^{\prime}$, but then
$g_{k}(x^{\prime})\in R_{0}$ and also $g_{k}(x^{\prime})>_{\rm lex}y$, which
means that at this stage the function $g_{k}$ played by Eve could not be a
partial isomorphism, so she loses the game.

∎

###  4.4. The irrationals vs. the reals

We consider the two structures $\mathbb{I}=\mathbb{R}\setminus\mathbb{Q}$ and
$\mathbb{R}$ and with the usual ordering.

######  Proposition 4.7.

Let $\alpha$ and $\beta$ be ordinals with $\alpha$ countable and
$\beta>\alpha\cdot 2$. Then Adamhas a winning strategy in $\rm
DG^{\beta}_{2^{\omega},\alpha}(\mathbb{I},\mathbb{R})$.

###### Proof.

For simplicity, we consider that $\mathbb{I}$ and $\mathbb{R}$ are disjoint,
and describe a winning strategy for Adam. He start by setting
$\beta_{0}=\alpha\cdot 2$ and playing $(\omega,\mathbb{I},\mathbb{R})$. Eve
then plays a height function $h_{0}:\mathbb{I}\cup\mathbb{R}\to\alpha$ and a
partial isomorphism from $h_{0}^{-1}(0)\cap\mathbb{I}$ to
$h_{0}^{-1}(0)\cap\mathbb{R}$. Since $\alpha$ is countable there is an ordinal
$\alpha_{0}<\alpha$ such that $h_{0}^{-1}(\alpha_{0})\cap\mathbb{I}$ is non
meager. In the next move Adam plays $\beta_{1}=\alpha+\alpha_{0}$. Eve plays a
lower height function $h_{1}$ and extends the partial isomorphism $g_{0}$ to
$g_{1}$. Again, there is $\alpha_{1}<\alpha_{0}$ such that
$h_{1}^{-1}(\alpha_{1})$ is non meager. Adam then plays
$\beta_{2}=\alpha+\alpha_{1}$. He continues like this until at some stage
$\alpha_{n}=0$. At that point the set $D={\rm dom}(g_{n})$ must be non meager,
and hence dense in some open interval $J$. Adam fixes a rational $q\in J$.
Consider the sets $R_{0}=g_{n}[D\cap(-\infty,q)]$ and
$R_{1}=g_{n}[D\cap(q,\infty)]$. Since, for every $x\in R_{0}$ and $y\in R_{1}$
we have $x<y$, there must be a real $r$ such that $x<r<y$, for every $x\in
R_{0}$ and $y\in R_{1}$. Adam then plays $\beta_{n+1}=h_{n}(r)$. Eve then
plays a lower height function $h_{n+1}$ and Adam responds by playing
$\beta_{n+2}=h_{n+1}(r)$. He continues in this way until we reach $m$ such
that $h_{m}(r)=0$. At that point the real $r$ must be in the range of $g_{m}$,
but its preimage could only be $q$, which is not in $\mathbb{I}$. In other
words, Eve cannot play $g_{m}$ which is a partial isomorphism, and so Adam
wins the game.

∎

###  4.5. The reals vs. the reals minus a point

We now present two models $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ such that,
for $\beta=\omega_{1}+1$ and $\theta=2^{\aleph_{0}}$, Eve has a winning
strategy in $\rm DG^{\beta}_{\theta,\alpha}(M_{0},M_{1})$ if $\alpha>\omega$
and Adam has a winning strategy if $\alpha=\omega$. Thus the models $M_{0}$
and $M_{1}$ are equivalent in our sense but not in Shelah’s sense. In [12] the
models $\mathfrak{M}_{0}=(\mathbb{R},<)$ and
$\mathfrak{M}_{1}=(\mathbb{R}\setminus\\{0\\},<)$ were considered and it was
observed that these are non-isomorphic but can be made isomorphic by adding a
Cohen-real. In particular, the models are partially isomorphic. We will
consider that the domains $M_{0}$ and $M_{1}$ of $\mathfrak{M}_{0}$ and
$\mathfrak{M}_{1}$ are disjoint. This can be easily achieved by identifying
$M_{0}$ with $\mathbb{R}\times\\{0\\}$ and $M_{1}$ with
$(\mathbb{R}\setminus\\{0\\})\times\\{1\\}$ and copying the ordering
accordingly.

######  Proposition 4.8.

Let $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ be the structures described
above. Let $\theta=2^{\aleph_{0}}$ and $\beta=\omega_{1}+1$. Then we have the
following.

  1. (1)

Eve has a winning strategy in $\rm
DG^{\beta}_{\theta,\omega+1}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

  2. (2)

Adam has a winning strategy in $\rm
DG^{\beta}_{\theta,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

###### Proof.

(1): We describe a winning strategy for Eve. We may assume that Adam starts by
letting $\beta_{0}=\omega_{1}$ and playing $(\beta_{0},M_{0},M_{1})$. Eve
responds by giving all elements of $M_{0}\cup M_{1}$ height $\omega$. Now Adam
plays $\beta_{1}<\beta_{0}=\omega_{1}$. If $\beta_{1}=0$, Eve gives all
elements height $1$, and wins the game immediately, as Adam cannot move any
more. Let us therefore assume $\beta_{1}\neq 0$. Now Eve has to give
$h(x)<\omega$ for each $x\in M_{0}\cup M_{1}$. Before defining the function
$h$ we make some preparations.

Let $\delta=\omega^{\beta_{1}}$, and et $L$ be $\delta\times(1+\omega^{*})$
with the lexicographical order. Let $(a_{\xi}:\xi<\delta)$ be a strictly
increasing continuous sequence of elements of $M_{0}$ such that
$\sup_{\xi}a_{\xi}=\infty$.

$a_{0}$$a_{1}$$a_{\xi}$ | $(\xi<\delta)$
---|---

Let $(b_{\xi}:\xi<\delta)$ be a strictly increasing sequence of length
$\delta$ of elements of $M_{1}$ converging to $0$, and $(c_{n}:n<\omega)$ a
strictly decreasing sequence of elements of $M_{1}$ converging to $0$. For
each $n$, let $(c^{n}_{\xi}:\xi<\delta)$ be a strictly increasing sequence of
length $\delta$ of elements of $M_{1}$ with $c^{n}_{0}=c_{n}$,
$\sup_{\xi}c^{n+1}_{\xi}=c_{n}$ and $\sup_{\xi}c^{0}_{\xi}=\infty$.

0
---
$\underbrace{\raisebox{2.0pt}{\line(1,0){10.0}}b_{0}\raisebox{2.0pt}{\line(1,0){10.0}}b_{1}\raisebox{2.0pt}{\line(1,0){10.0}}b_{\xi}\raisebox{2.0pt}{\line(1,0){25.0}}}_{(-\infty,0)}$
$\bullet$ $\underbrace{\raisebox{2.0pt}{\line(1,0){25.0}}}_{\ldots}$
$\underbrace{c^{n}_{0}\raisebox{2.0pt}{\line(1,0){10.0}}c^{n}_{1}\raisebox{2.0pt}{\line(1,0){25.0}}c^{n}_{\xi}\raisebox{2.0pt}{\line(1,0){25.0}}}_{[c_{n},c_{n-1})}$
$\underbrace{c^{1}_{0}\raisebox{2.0pt}{\line(1,0){10.0}}c^{1}_{1}\raisebox{2.0pt}{\line(1,0){25.0}}c^{1}_{\xi}\raisebox{2.0pt}{\line(1,0){25.0}}}_{[c_{1},c_{0})}$
$\underbrace{c^{0}_{0}\raisebox{2.0pt}{\line(1,0){10.0}}c^{0}_{1}\raisebox{2.0pt}{\line(1,0){25.0}}c^{0}_{\xi}\raisebox{2.0pt}{\line(1,0){10.0}}}_{[c_{0},\infty)}$

The points $a_{\xi}$ divide the linear order $M_{0}$ into disjoint intervals
$(-\infty,a_{0})$ and $[a_{\xi},a_{\xi+1})$. Let us enumerate these intervals
as $\\{I_{n}:n<\omega\\}$. The points $b_{\xi}$ and $c^{n}_{\xi}$ divide the
linear order $M_{1}$ into disjoint intervals $(-\infty,b_{0})$,
$[b_{n},b_{n+1})$ and $[c^{n}_{\xi},c^{n}_{\xi+1})$, for $\xi<\delta$ and
$n<\omega$. Let us enumerate these intervals as $\\{J_{n}:n<\omega\\}$. We let
$h(x)$ denote the unique $n$ such that $x\in I_{n}\cup J_{n}$. Eve plays this
function $h$ as the height function on this second round. The rest of the game
proceeds as follows: Adam plays a descending sequence of elements of
$\beta_{1}$. Eve decreases the heights of all elements of $M_{0}\cup M_{1}$ in
each step by one until they become zero. Whenever the height of an element $a$
becomes zero, Eve extends the partial isomorphism she gave in the previous
round so that $a$ is in the domain or in the range of the mapping. Each
interval $I_{n}$ corresponds in a canonical way to an element of $\delta$.
Respectively, each interval $J_{n}$ corresponds to an element of $L$. This
reduces the game $\rm
DG^{\beta_{0}}_{\theta,\omega+1}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ to the
game $\rm DG^{\beta_{0}}_{1,1}(\delta,L)$. In the latter game Eve has a
winning strategy by C. Karp [5, page 411]. This winning strategy translates
canonically to a winning strategy for Eve in the former game.

(2): This is similar to the proof of (2) in the next section. ∎

###  4.6. $\kappa^{\leq\omega}$ and $\kappa^{\leq\omega}\setminus\\{b\\}$

Fix a cardinal $\kappa$. Let $\mathfrak{M}_{0}$ be the tree
$\kappa^{\leq\omega}$, where $s\leq t$ iff $s$ is an initial segment of $t$.
Fix some $b\in\kappa^{\omega}$ and let $\mathfrak{M}_{1}$ be
$\kappa^{\leq\omega}\setminus\\{b\\}$ with the same ordering. We will again
consider that the universes of $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ are
disjoint.

######  Proposition 4.9.

Let $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ be the structures described
above. Let $\theta=\kappa^{\omega}$ and $\beta=\kappa+1$. Then we have the
following.

  1. (1)

Eve has a winning strategy in $\rm
DG^{\beta}_{\theta,\omega+1}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

  2. (2)

Adam has a winning strategy in $\rm
DG^{\beta}_{\theta,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

###### Proof.

(1): This is similar to the proof of (1) in Proposition 4.9.

(2): For any $s\in\kappa^{<\omega}$ let
$N(s)=\\{s^{\prime}\in\kappa^{\leq\omega}:s\leq s^{\prime}\\}$. We call $N(s)$
the cone of $s$. We put a topology on $\kappa^{\leq\omega}$ by letting all
elements of $\kappa^{<\omega}$ be isolated. If $f\in\kappa^{\omega}$ we let
the neighbourhoods of $f$ be the cones $N(f\restriction n)$, for $n<\omega$.
If $s,t\in\kappa^{\leq\omega}$, we write $s\wedge t$ for their meet i.e. the
largest common initial segment of $s$ and $t$. We also write $\Delta(s,t)$ for
the length of $s\wedge t$. Before we start let us observe that if
$(\gamma,A,B,g,h)$ is a winning position for Eve, and $\gamma\geq\omega$, then
$g$ must preserve the length of nodes, and if $s,t\in{\rm dom}(g)$ then

$\Delta(g(s),g(t))=\Delta(s,t).$

Suppose now that Eve has a winning strategy $\tau$ in $\rm
DG^{\beta}_{\theta,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. Adam challenge
$\tau$ as follows. He lets $\beta_{0}=\kappa^{+}$ and plays
$(\beta_{0},M_{0},M_{1})$ as his first move. In future moves he only has to
specify a decreasing sequence of ordinals below $\kappa^{+}$. Suppose $\tau$
responds by playing a position $(\beta_{0},M_{0},M_{1},g_{0},h_{0})$. Let
$A_{n}=h_{0}^{-1}(n)\cap M_{0}$ and $B_{n}=h_{0}^{-1}(n)$, for all $n$. Then
$g_{0}$ has to be a partial isomorphism between $A_{0}$ and $B_{0}$.

Observe that the missing branch $b$ cannot be in $\bar{B}_{0}$. Otherwise we
find a sequence $(b_{n})_{n}$ of nodes in $B_{0}$ converging to $b$ such that

$\Delta(b_{0},b_{1})<\Delta(b_{1},b_{2})<\Delta(b_{2},b_{3})<\ldots$

Let $a_{n}=g^{-1}(b_{n})$ and observe that the sequence $(a_{n})_{n}$ must be
convergent as well. Let $a$ be the limit, and let $n=h_{0}(a)$. Adam then
plays $b_{1}=\omega+n$ and in $n$ steps forces Eve to decide the image of $a$
in $M_{1}$, while ensuring that $\beta_{n+1}\geq\omega$. But then the only
possible value for $g_{n+1}(a)$ would be $b$, which is not in $M_{1}$, a
contradiction.

Let $s_{0}$ be the shortest initial segment of $b$ such that $N(s_{0})\cap
B_{0}=\emptyset$. Let $m_{0}$ be such that $s_{0}\in B_{m_{0}}$, i.e.
$m_{0}=h_{0}(s_{0})$. For each ordinal $\gamma$ with
$\omega<\gamma<\kappa^{+}$, there is a winning position for Eve of the form
$(\gamma,M_{0},M_{1},g_{1}^{\gamma},h_{1}^{\gamma})$ in which Eve is obliged
to decide the preimage of $s_{0}$ in $M_{0}$, i.e. such that $s_{0}\in{\rm
ran}(g_{1}^{\gamma})$. Indeed, for each $\gamma$, Adam can play $\gamma+m_{0}$
in the position $(\beta_{0},M_{0},M_{1},g_{0},h_{0})$ as his next move and
then keep decreasing this ordinal by $1$ until the height of $s_{0}$ reaches
$0$ at which point Eve is obliged to decide the preimage of $s_{0}$. Let
$t_{0}^{\gamma}$ be such that $g_{1}^{\gamma}(t_{0}^{\gamma})=s_{0}$. Let
$C^{\gamma}_{1}={\rm ran}(g^{\gamma}_{1})$. If $\gamma\geq\omega$, by a
similar argument as above we must have that $b\notin\bar{C}^{\gamma}_{1}$. Let
$s^{\gamma}_{1}$ be an initial segment of $b$ such that $N(s^{\gamma}_{1})\cap
C^{\gamma}_{1}=\emptyset$. Now, by the Pigeon Hole Principle there are fixed
node $t_{0},s_{1}\in\kappa^{<\omega}$ and an unbounded subset $X_{1}$ of
$\kappa^{+}$ such that $t_{0}^{\gamma}=t_{0}$, and $s^{\gamma}_{1}=s_{1}$, for
all $\gamma\in X_{1}$.

Let $m_{1}$ be such that $s_{1}\in B_{m_{1}}$, i.e. $m_{1}=h_{0}(s_{1})$. As
above, we argue that, for all $\gamma<\kappa^{+}$, there is a winning position
for Eve of the form $(\gamma,M_{0},M_{1},g_{2}^{\gamma},h_{2}^{\gamma})$ such
that $s_{1}\in{\mathop{{\rm ran}}}(g_{2}^{\gamma})$ and which extends a
position of the form
$(\gamma^{\prime},M_{0},M_{1},g_{1}^{\gamma^{\prime}},h_{1}^{\gamma^{\prime}})$,
for some $\gamma^{\prime}\in X_{1}$ with $\gamma<\gamma^{\prime}$. Namely,
Adam picks some $\gamma^{\prime}\in X_{1}$ with
$\gamma+m_{1}\leq\gamma^{\prime}$. Since
$(\gamma^{\prime},M_{0},M_{1},g_{1}^{\gamma^{\prime}},h_{1}^{\gamma^{\prime}})$
is a winning position for Eve so is
$(\gamma+m_{1},M_{0},M_{1},g_{1}^{\gamma^{\prime}},h_{1}^{\gamma^{\prime}})$.
Adam then plays $m_{1}$ moves from this position each time decreasing the
height of the position by $1$ until the height of $s_{1}$ reaches $0$ at which
point Eve is obliged to decide the preimage of $s_{1}$. Now, given such a
position $(\gamma,M_{0},M_{1},g_{2}^{\gamma},h_{2}^{\gamma})$ let
$t_{1}^{\gamma}$ be such that $g_{2}^{\gamma}(t_{1}^{\gamma})=s_{1}$. Let
$C^{\gamma}_{2}={\rm ran}(g^{\gamma}_{2})$. As before, if $\gamma\geq\omega$
we must have $b\notin\bar{C}^{\gamma}_{2}$. Let $s^{\gamma}_{2}$ be an initial
segment of $b$ such that $N(s^{\gamma}_{2})\cap C^{\gamma}_{2}=\emptyset$. By
the Pigeon Hole Principle again, there is an unbounded subset $X_{2}$ of
$\kappa^{+}$ and fixed nodes $t_{1},s_{2}\in\kappa^{<\omega}$ such that
$t_{1}^{\gamma}=t_{1}$, and $s^{\gamma}_{2}=s_{2}$, for all $\gamma\in X_{2}$.

By repeating this process we can find increasing sequences $(s_{n})_{n}$ and
$(t_{n})_{n}$ of nodes in $\kappa^{<\omega}$, unbounded subsets $X_{n}$ of
$\kappa^{+}$, and, for each $\gamma\in X_{n}$, a winning position for Eve
$p_{n}^{\gamma}=(\gamma,M_{0},M_{1},g^{\gamma}_{n},h^{\gamma}_{n})$ such that,
letting $C^{\gamma}_{n}={\rm ran}(g^{\gamma}_{n})$, for all $n$ we have:

  1. (1)

$N(s_{n})\cap C^{\gamma}_{n}=\emptyset$,

  2. (2)

$s_{n}$ are initial segments of $b$,

  3. (3)

if $\gamma\in X_{n+1}$ then $t_{n}\in{\rm dom}(g^{\gamma}_{n+1})$ and
$g^{\gamma}_{n+1}(t_{n})=s_{n}$,

  4. (4)

if $\gamma\in X_{n+1}$ there is $\gamma^{\prime}\in X_{n}$ such that
$\gamma<\gamma^{\prime}$ and $p_{n+1}^{\gamma}$ extends
$p_{n}^{\gamma^{\prime}}$.

Let $a=\bigcup_{n}t_{n}$ and let $k=h_{0}(a)$. Pick some $\gamma\in X_{k+1}$
with $\gamma\geq\omega$ and let $\gamma^{\prime}\in X_{k}$ be such that
$\gamma<\gamma^{\prime}$ and $p^{\gamma}_{k+1}$ extends
$p^{\gamma^{\prime}}_{k}$. Notice that $a\in{\rm
dom}(g^{\gamma^{\prime}}_{k})$. Since $t_{k}\leq a$ and
$g^{\gamma}_{k+1}(t_{k})=s_{k}$ we must have that $s_{k}\leq
g^{\gamma}_{k+1}(a)$. However, $g^{\gamma}_{k+1}$ extends
$g^{\gamma^{\prime}}_{k}$ and hence $s_{k}\leq g^{\gamma^{\prime}}_{k}(a)$,
which contradicts the fact that $N(s_{k})\cap
C^{\gamma^{\prime}}_{k}=\emptyset$. ∎

###  4.7. Prikry forcing and the game $\rm DG^{\beta}_{<\kappa,\alpha}$

Elementary equivalence in infinitary logic is closely related to isomorphism
in a forcing extension. This is particularly evident in the case of
$L_{\infty\omega}$ where elementary equivalence is equivalent to isomorphism
in _some_ forcing extension. For stronger infinitary logics we have to limit
ourselves to special classes of forcings and we do not in general get an
equivalence as in the case of $L_{\infty\omega}$ ([12]). Given two structures
$\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ in the same vocabulary, we write
$\rm DG^{\beta}_{<\kappa,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ for the
variation of the game $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in which the
two players play subsets of $M_{0}$ and $M_{1}$ of size $<\kappa$ instead of
subsets of size $\leq\theta$. We demonstrate below a connection between the
game $\rm DG^{\beta}_{<\kappa,\alpha}$ and Prikry-forcing, introduced in [13].

Let $\kappa$ be a measurable cardinal and let $\mathcal{U}$ be a normal
ultrafilter on $\kappa$. We recall the definition of Prikry forcing
$\mathbb{P}_{\mathcal{U}}$. Conditions in $\mathbb{P}_{\mathcal{U}}$ are pairs
$p=(s_{p},Y_{p})$, where $s_{p}$ is a finite increasing sequence of elements
of $\kappa$ and $Y_{p}$ is an element of $\mathcal{U}$ with
$\max(s_{p})<\min(Y_{p})$. We will simultaneously think of $s_{p}$ either as a
finite increasing sequence and as a finite set which is the range of the
sequence. We say that a condition $q$ extends $p$ and write $q\leq p$ if:

  1. (1)

$s_{p}$ is an initial segment of $s_{q}$,

  2. (2)

$Y_{q}\subseteq Y_{p}$,

  3. (3)

$s_{q}\setminus s_{p}\subseteq Y_{p}$.

We say that a condition $q$ is a pure extension of a condition $p$ if $q\leq
p$ and $s_{q}=s_{p}$. Given a generic filter $G$ we let
$g=\bigcup\\{s_{p}:p\in G\\}$. Then $g$ is a cofinal $\omega$-sequence in
$\kappa$. It is well known that $\mathbb{P}_{\mathcal{U}}$ has the
$\kappa^{+}$-c.c. and does not add new bounded subsets of $\kappa$. Moreover
if $p\in\mathbb{P}_{\mathcal{U}}$ and $\phi$ is a sentence in the forcing
language, there is a pure extension $q$ of $p$ which decides $\phi$ (see
[13]). We refer to this fact as the Prikry lemma.

######  Proposition 4.10.

Let $\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$ be two structures in the same
vocabulary $\tau$. Suppose $\mathcal{U}$ is a normal ultrafilter on a
measurable cardinal $\kappa$, $\alpha$ and $\beta$ are ordinals with
$\alpha<\kappa$. Suppose $G$ is a $V$-generic filter over
$\mathbb{P}_{\mathcal{U}}$.

  1. (1)

If Eve has a winning strategy in $\rm
DG^{\beta}_{<\kappa,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in $V[G]$,
then she has a winning strategy in $\rm
DG^{\beta}_{<\kappa,\omega+\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in $V$.

  2. (2)

If Eve has a winning strategy in $\rm
DG^{\beta}_{<\kappa,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in $V$ then
she has a winning strategy in $\rm
DG^{\beta}_{\kappa,\alpha+\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in
$V[G]$.

###### Proof.

(1) We assume for simplicity that $\tau$ has only relation symbols and that
the domains of the two structures, $M_{0}$ and $M_{1}$, are disjoint. Let us
first prove something a bit weaker. Namely, assume that the maximal condition
in $\mathbb{P}_{\mathcal{U}}$ forces that $\check{\mathfrak{M}_{0}}$ and
$\check{\mathfrak{M}_{1}}$ are isomorphic and let us show that Eve has a
winning strategy in $\rm
DG^{\beta}_{<\kappa,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in $V$. Fix a
$\mathbb{P}_{\mathcal{U}}$-name $\Gamma$ for the generic Prikry sequence and a
$\mathbb{P}_{\mathcal{U}}$-name $\pi$ for the isomorphism between
$\mathfrak{M}_{0}$ and $\mathfrak{M}_{1}$. For each $a\in M_{0}$ let
$N^{1}_{a}\in V$ be the set of possible values for $\pi(a)$ in $M_{1}$. By the
$\kappa^{+}$-c.c., $|N^{1}_{a}|\leq\kappa$. Let $f_{a}:N^{1}_{a}\to\kappa$ be
an injective function in $V$. Let $h(a)$ be a $\mathbb{P}_{\mathcal{U}}$-name
for the least integer $n$ such that $f_{a}(\pi(a))<\Gamma(n)$. Similarly, if
$b\in M_{1}$ we let $N^{0}_{b}$ denote the set of possible values for
$\pi^{-1}(b)$. Again by the $\kappa^{+}$-cc, $|N^{1}_{b}|\leq\kappa$. Let
$f_{b}:N^{1}_{b}\to\kappa$ be an injective function in $V$, and let $\rho(b)$
be a $\mathbb{P}_{\mathcal{U}}$-name for the least integer $n$ such that
$f_{a}(\pi^{-1}(b))<\Gamma(n)$. Thus the function $\rho$ maps $M_{0}\cup
M_{1}$ to $\mathbb{P}_{\mathcal{U}}$-names for integers. We now informally
describe a winning strategy for Eve in $\rm
DG^{\beta}_{<\kappa,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$. Along the way
Eve builds a decreasing sequence $(p_{n})_{n}$ of conditions in
$\mathbb{P}_{\mathcal{U}}$ such that $|s_{p_{n}}|=n+1$. To simplify notation
we will write $s_{n}$ for $s_{p_{n}}$ and $Y_{n}$ for $Y_{p_{n}}$.

Suppose the first move by Adam is $(\beta_{0},B^{0}_{0},B^{0}_{1})$, where
$\beta_{0}<\beta$, $B^{0}_{0}\in[M_{0}]^{<\kappa}$ and
$B^{0}_{1}\in[M_{1}]^{<\kappa}$. To begin Eve finds $X_{0}\in\mathcal{U}$ such
that $(\emptyset,X_{0})$ decides the values of $\rho(x)$, for $x\in
B^{0}_{0}\cup B^{0}_{1}$. She can do this by the Prikry lemma and the fact
that there $<\kappa$-many decisions to be made. This gives us a function
$\rho_{0}$ defined on $B^{0}_{0}\cup B^{0}_{1}$ taking integer values. Eve
then lets $\alpha_{0}=\min(X_{0})$ and finds $Y_{0}\subseteq
X_{0}\setminus\\{\alpha_{0}\\}$ with $Y_{0}\in U$ such that
$(\\{\alpha_{0}\\},Y_{0})$ decides the value of $\pi(a)$, for all $a\in
B^{0}_{0}$ such that $\rho_{0}(a)=0$, and similarly the value of
$\pi^{-1}(b)$, for all $b\in B^{0}_{1}$ such that $\rho_{0}(b)=0$. The reason
she can do that is that $(\\{\alpha_{0}\\},X_{0}\setminus\\{\alpha_{0}\\})$
forces that the value of $\pi(a)$ belongs to $f_{a}^{-1}[\alpha_{0}]$ which is
a subset of $N^{1}_{a}$ of size $<\kappa$. Similarly,
$(\\{\alpha_{0}\\},X_{0}\setminus\\{\alpha_{0}\\})$ forces that $\pi^{-1}(b)$
belongs to $f_{b}^{-1}[\alpha_{0}]$, which is a subset of $N_{b}^{0}$ of size
$<\kappa$. Thus she has $<\kappa$-many decisions to make. In this way she
obtains a partial isomorphism $g_{0}$ of size $<\kappa$ whose domain contains
$\rho_{0}^{-1}(0)\cap B^{0}_{0}$ and whose range contains
$\rho_{0}^{-1}(0)\cap B^{0}_{1}$. Let $A^{0}_{0}={\rm dom}(g_{0})\cup
B^{0}_{0}$ and $A^{0}_{1}={\rm ran}(g_{0})\cup B^{0}_{1}$. Eve then extends
$\rho_{0}$ to a function $h_{0}$ on $A^{0}_{0}\cup A^{0}_{1}$ by setting
$h_{0}(x)=0$, for all $x\in A^{0}_{0}\setminus B^{0}_{0}$ and all $x\in
A^{0}_{1}\setminus B^{0}_{1}$. Eve then plays as her first move
$(\beta_{0},A^{0}_{0},A^{0}_{1},g_{0},h_{0})$. She sets her first condition
$p_{0}$ to be $(\\{\alpha_{0}\\},Y_{0})$.

Suppose that at stage $n$ we are in position
$(\beta_{n},A^{n}_{0},A^{n}_{1},g_{n},h_{n})$ and Eve has fixed a condition
$p_{n}=(s_{n},Y_{n})$. Suppose that Adam then plays
$(\beta_{n+1},B^{n+1}_{0},B^{n+1}_{1})$, for some $\beta_{n+1}<\beta_{n}$,
$B^{n+1}_{0}\in[M_{0}]^{<\kappa}$, and $B^{n+1}_{1}\in[M_{1}]^{<\kappa}$. Eve
first finds $X_{n+1}\subseteq Y_{n}$ with $X_{n+1}\in U$ such that
$(s_{n},X_{n+1})$ decides the value of $\rho(x)$, for $x\in B^{n+1}_{0}\cup
B^{n+1}_{1}$. She can do this by the Prikry lemma and the fact that there are
$<\kappa$ decisions to be made. This gives us a functions $\rho_{n+1}$ on
$B^{n+1}_{0}\cup B^{n+1}_{1}$ with integer values. Eve lets
$\alpha_{n+1}=\min(X_{n+1})$ and finds $Y_{n+1}\subseteq
X_{n+1}\setminus\\{\alpha_{n+1}\\}$ with $Y_{n+1}\in\mathcal{U}$ such that
$(s_{n}\cup\\{\alpha_{n+1}\\},Y_{n+1})$ decides the values of $\pi(a)$, for
all $a\in A^{n}_{0}$ with $h_{n}(a)\leq 1$, and all $a\in B^{n+1}_{0}$ with
$\rho_{n+1}(a)\leq n+1$, as well as the values of $\pi^{-1}(b)$, for all $b\in
A^{n}_{1}$ with $h_{n}(b)\leq 1$, and all $b\in B^{n+1}_{1}$ with
$\rho_{n+1}(b)\leq n+1$. This gives us a new partial isomorphism $g_{n+1}$ of
size $<\kappa$ which extends $g_{n}$. Let $A^{n+1}_{0}=A^{n}_{0}\cup
B^{n+1}_{0}\cup{\rm dom}(g_{n+1})$ and $A^{n+1}_{1}=A^{n}_{0}\cup
B^{n+1}_{1}\cup{\rm ran}(g_{n+1})$. Eve defines the function $h_{n+1}$ on
$A^{n+1}_{0}\cup A^{n+1}_{1}$ as follows.

$h_{n+1}(x)=\begin{cases}0,&\text{if $x\in{\rm dom}(g_{n+1})\cup{\rm
ran}(g_{n+1})$,}\\\ h_{n}(x)\dot{-}1,&\text{if $x\in A^{n}_{0}\cup
A^{n}_{1}$,}\\\ \rho_{n+1}(x)\dot{-}(n+1),&\text{if $x\in(B^{n+1}_{0}\setminus
A^{n}_{0})\cup(B^{n+1}_{1}\setminus A^{n}_{1})$.}\end{cases}$

Here, for integers $x$ and $y$, we use

$x\dot{-}y=\max(x-y,0).$

Eve then plays $(\beta_{n+1},A^{n+1}_{0},A^{n+1}_{1},g_{n+1},h_{n+1})$ and
sets $p_{n+1}=(s_{n}\cup\\{\alpha_{n+1}\\},Y_{n+1})$. It is clear now that by
playing in this way Eve wins the game $\rm
DG^{\beta}_{<\kappa,\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$.

We now return to the original problem. We will play the game $\rm
DG^{\beta}_{<\kappa,\omega+\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in $V$
and we will refer to it as the $V$-game. We will play the game $\rm
DG^{\beta}_{<\kappa,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in $V[G]$ and
will refer to it as the $V[G]$-game. Let $\sigma$ be a
$\mathbb{P}_{\mathcal{U}}$-name which is forced by the maximal condition to be
a winning strategy for Eve in the $V[G]$-game. We sketch how to derive a
winning strategy for Eve in the $V$-game. Along the way Eve will build a
decreasing sequence $(p_{n})_{n}$ of conditions in $\mathbb{P}_{\mathcal{U}}$.
As above we will write $p_{n}=(s_{n},Y_{n})$. We will ensure that $|s_{n}|=n$,
for all $n$.

Suppose Adam starts the $V$-game by playing some
$(\beta_{0},B^{0}_{0},B^{0}_{1})$, with $\beta_{0}<\beta$,
$B^{0}_{0}\in[M_{0}]^{<\kappa}$ and $B^{0}_{1}\in[M_{1}]^{<\kappa}$. Eve
considers the same move in the $V[G]$-game. Let
$(\check{\beta}_{0},\dot{A}^{0}_{0},\dot{A}^{0}_{1},\dot{g_{0}},\dot{h}_{0})$
be a name for the reply of $\sigma$ in this game. Since $\alpha<\kappa$ and
$B^{0}_{0}\cup B^{0}_{1}$ has size $<\kappa$, Eve can find a set
$Y_{0}\in\mathcal{U}$ such that $(\emptyset,Y_{0})$ decides the value of
$\dot{h}_{0}(x)$, for all $x\in B^{0}_{0}\cup B^{0}_{1}$. This gives us a
function $h^{\prime}_{0}:B^{0}_{0}\cup B^{0}_{1}\to\alpha$. Eve then defines
$h^{*}_{0}$ on $B^{0}_{0}\cup B^{0}_{1}$ by:

$h^{*}_{0}(x)=\omega+h^{\prime}_{0}(x).$

In the $V$-game Eve replies by playing
$(\beta_{0},B^{0},B^{0}_{1},\emptyset,h^{*}_{0})$. She also sets
$p_{0}=(\emptyset,Y_{0})$. Suppose now Adam plays
$(\beta_{1},B^{1}_{0},B^{1}_{1})$ in the $V$-game. We may assume that
$B^{0}_{0}\subseteq B^{1}_{0}$ and $B^{0}_{1}\subseteq B^{1}_{1}$. and let
$(\check{\beta}_{1},\dot{A}^{1}_{0},\dot{A}^{1}_{1},\dot{g_{1}},\dot{h}_{1})$
be a name for the reply of $\sigma$ to this move of Adam in the $V[G]$-game.
We first find $X_{1}\subseteq Y_{0}$ with $X_{1}\in\mathcal{U}$ such that
$(\emptyset,X_{1})$ decides the value of $\dot{h}_{1}(x)$, for all $x\in
B^{1}_{0}\cup B^{1}_{1}$. Let the resulting function be $h^{\prime}_{1}$. For
each $a\in B^{1}_{0}$ with $h^{\prime}_{1}(a)=0$ let $N^{1}_{a}$ be the set of
possible values of $\dot{g}_{1}(a)$. Then by the $\kappa^{+}$-cc of
$\mathbb{P}_{\mathcal{U}}$, $|N^{1}_{a}|\leq\kappa$. Fix an injective function
$f_{a}:N^{1}_{a}\to\kappa$, for all such $a$. Let $\rho_{1}(a)$ be the
$\mathbb{P}_{\mathcal{U}}$-name for the least integer $n$ such that
$f_{a}(\dot{g}_{1}(a))<\Gamma(n)$. Similarly, for each $b\in B^{1}_{1}$ such
that $h^{\prime}_{1}(b)=0$ let $N^{0}_{b}$ be the set of possible values of
$\dot{g}_{1}^{-1}(b)$. Then $|N^{0}_{b}|\leq\kappa$ as well. Fix an injective
function $f_{b}:N^{0}_{b}\to\kappa$, for all such $b$ and let $\rho_{1}(b)$ be
a $\mathbb{P}_{\mathcal{U}}$-name for the least integer $n$ such that
$f_{b}(\dot{g}^{-1}_{1}(b))<\Gamma(n)$. By shrinking the set $X_{1}$ we may
assume that $(\emptyset,X_{0})$ decides the value of $\rho_{1}(x)$, for all
$x\in B^{1}_{0}\cup B^{1}_{1}$ such that $h^{\prime}_{1}(x)=0$. Let us call
this value $r_{1}(x)$. Let $\alpha_{0}=\min(X_{1})$. We can now find
$Y_{1}\subseteq X_{1}\setminus\\{\alpha_{0}\\}$ with $Y_{1}\in\mathcal{U}$
such that $(\\{\alpha_{0}\\},Y_{1})$ decides the value of $\dot{g}_{1}(a)$,
for all $a\in B^{1}_{0}$ such that $h^{\prime}_{1}(a)=0$ and $r_{1}(a)=0$, and
similarly decides the value of $\dot{g}^{-1}_{1}(b)$, for all $b\in B^{1}_{1}$
such that $h^{\prime}_{1}(b)=0$ and $r_{1}(b)=0$. This is because there are
$<\kappa$-many possible values, so we can apply the Prikry lemma. This gives
us a partial isomorphism $g^{*}_{1}$. Let $A^{1}_{0}=B^{1}_{0}\cup{\rm
dom}(g^{*}_{1})$ and $A_{1}^{1}=B^{1}_{1}\cup{\rm ran}(g^{*}_{1})$. Define the
function $h^{*}_{1}$ on $A^{1}_{0}\cup A^{1}_{1}$ by:

$h^{*}_{1}(x)=\begin{cases}0,&\text{ if $x\in{\rm dom}(g^{*}_{1})\cup{\rm
ran}(g^{*}_{1})$,}\\\ r_{1}(x),&\text{ if $x\in B^{1}_{0}\cup B^{1}_{1}$ and
$h^{\prime}_{1}(x)=0$,}\\\ \omega+h^{\prime}_{1}(x),&\text{ if $x\in
B^{1}_{0}\cup B^{1}_{1}$ and $h^{\prime}_{1}(x)>0$.}\end{cases}$

Now, in the $V$-game Eve plays
$(\beta_{1},A^{1}_{0},A^{1}_{1},g^{*}_{1},h^{*}_{1})$ and she sets
$p_{1}=(\\{\alpha_{0}\\},Y_{1})$. It should now be clear how to define a
winning strategy for Eve in the $V$-game by using the construction from the
first part of the proof.

(2): We now consider $\rm
DG^{\beta}_{<\kappa,\alpha}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in $V$ and
call it the $V$-game, and we consider $\rm
DG^{\beta}_{\kappa,\alpha+\omega}(\mathfrak{M}_{0},\mathfrak{M}_{1})$ in
$V[G]$ and call it the $V[G]$-game. In $V[G]$, let $(\gamma_{n})_{n}$ be the
Prikry generic sequence. Thus $(\gamma_{n})_{n}$ is an increasing sequence
cofinal in $\kappa$. Since $\mathbb{P}_{\mathcal{U}}$ has the $\kappa^{+}$-cc,
every set in $[M_{0}]^{\leq\kappa}$ is covered by a set of size $\kappa$ which
belongs to $V$, and similary for sets in $[M_{1}]^{\leq\kappa}$. We can
therefore assume that in the $V[G]$-game Adam plays only sets of size
$\leq\kappa$ which are in $V$. For each $N\in V$ of size $\kappa$, fix an
injective function $f_{N}:N\to\kappa$ which is in $V$. In $V[G]$ We define
$\rho_{N}:N\to\omega$ by letting $\rho_{N}(x)$ be the least integer $n$ such
that $f_{N}(x)<\gamma_{n}$. For each integer $n$, let

$N(n)=\\{x\in N:\rho_{N}(x)<\gamma_{n}\\}.$

Note that $N(n)\in V$ and has size $<\kappa$. Now, fix a winning strategy
$\sigma$ for Eve in the $V$-game. We describe a winning strategy for Eve in
the $V[G]$-game. Suppose Adam starts by playing
$(\beta_{0},C^{0}_{0},C^{0}_{1})$, for some $\beta_{0}<\beta$, and
$C^{0}_{0}\in[M_{0}]^{\leq\kappa}$ and $C^{0}_{1}\in[M_{1}]^{\leq\kappa}$. We
may assume that $C^{0}_{0}$ and $C^{0}_{1}$ are in $V$. Let
$C_{0}=C^{0}_{0}\cup C^{0}_{1}$. Eve defines the function
$h^{*}_{0}:C_{0}\to\alpha+\omega$ by letting, for all $x$,

$h^{*}_{0}(x)=\omega+\rho_{C_{0}}(x).$

Eve then plays $(\beta_{0},C^{0}_{0},C^{0}_{1},\emptyset,h^{*}_{0})$ as a
reply to Adam’s move in the $V[G]$-game. Suppose now Adam plays some
$(\beta_{1},C^{1}_{0},C^{1}_{1})$, with $\beta_{1}<\beta_{0}$, and
$C^{1}_{0}\in[M_{0}]^{\leq\kappa}$ and $C^{1}_{1}\in[M_{1}]^{\leq\kappa}$. We
may assume that $C^{1}_{0}$ and $C^{1}_{1}$ are in $V$, and
$C^{0}_{0}\subseteq C^{1}_{0}$ and $C^{0}_{1}\subseteq C^{1}_{1}$. Let
$C_{1}=C^{1}_{0}\cup C^{1}_{1}$. Let $B^{0}_{0}=C^{0}_{0}(0)$ and
$B^{0}_{1}=C^{0}_{1}(0)$. Eve goes to the $V$-game and lets Adam play
$(\beta_{1},B^{0}_{0},B^{0}_{1})$ as his first move in this game. Let the
answer of the strategy $\sigma$ be
$(\beta_{1},A^{0}_{0},A^{0}_{1},g_{0},h_{0})$. Let $A_{0}=A^{0}_{0}\cup
A^{0}_{1}$. Eve then sets $D^{1}_{0}=A^{0}_{0}\cup C^{1}_{0}$ and
$D^{1}_{1}=A^{0}_{1}\cup C^{1}_{1}$. Let $D_{1}=D^{1}_{0}\cup D^{1}_{1}$. She
then defines a function $h^{*}_{1}:D_{1}\to\alpha+\omega$ as follows:

$h^{*}_{1}(x)=\begin{cases}h_{0}(x),&\text{ if $x\in A_{0}$,}\\\
\alpha+\rho_{C_{0}}(x)-1,&\text{ if $x\in C_{0}\setminus A_{0}$,}\\\
\alpha+\rho_{C_{1}}(x),&\text{ if $x\in C_{1}\setminus(A_{0}\cup
C_{0})$.}\end{cases}$

Let $g^{*}_{1}=g_{0}$. In the $V[G]$ Eve plays
$(\beta_{1},D^{1}_{0},D^{1}_{1},g^{*}_{1},h^{*}_{1})$ as her reply to Adam’s
previous move.

In the $n$-move we have a position
$(\beta_{n},D^{n}_{0},D^{n}_{1},g^{*}_{n},h^{*}_{n})$ in the $V[G]$-game and a
corresponding position $(\beta_{n},A^{n-1}_{0},A^{n-1}_{1},g_{n-1},h_{n-1})$
in the $V$-game. We have that

$A^{n-1}_{0}=\\{x\in D^{n}_{0}:h^{*}_{n}(x)<\alpha\\},$

and similarly for $A^{n-1}_{1}$. We have that $g^{*}_{n}=g_{n-1}$. If we let
$A_{n-1}=A^{n-1}_{0}\cup A^{n-1}_{1}$ we have $h_{n-1}=h^{*}_{n}\restriction
A_{n-1}$. Moreover, ${h_{n}^{*}}^{-1}(\alpha+m)$ has size $<\kappa$, for every
integer $m$. Suppose Adam then plays some
$(\beta_{n+1},C^{n+1}_{0},C^{n+1}_{1})$ in the $V[G]$-game. Without loss of
generality $C^{n}_{0}\subseteq C^{n+1}_{0}$ and $C^{n}_{1}\subseteq
C^{n+1}_{1}$. Eve takes the elements of $D^{n}_{0}$ whose current height is
$\alpha$ and calls the resulting set $B^{n}_{0}$. She defines similarly
$B^{n}_{1}$. She then lets Adam play $(\beta_{n+1},B^{n}_{0},B^{n}_{1})$ in
the corresponding position of the $V$-game. Let the response of $\sigma$ be
$(\beta_{n+1},A^{n}_{0},A^{n}_{1},g_{n},h_{n})$. Back in the $V[G]$-game she
lets $D^{n+1}_{0}=D^{n}_{0}\cup C^{n+1}_{0}$ and $D^{n+1}_{1}=D^{n}_{1}\cup
C^{n+1}_{1}$. She has to define the height function $h^{*}_{n+1}$ on
$D_{n+1}=D^{n+1}_{0}\cup D^{n+1}_{1}$. To elements $x$ of $A_{n}=A^{n}_{0}\cup
A^{n}_{1}$ she assign height $h_{n}(x)$. She lowers the heights of the
elements of $C_{n}\setminus A_{n}$ by $1$. To the elements $x$ of
$C_{n+1}\setminus(A_{n}\cup C_{n})$ she assigns heights
$\alpha+\rho_{C_{n+1}}(x)$. This gives the height function $h^{*}_{n+1}$. She
lets $g^{*}_{n+1}=g_{n}$ and plays
$(\beta_{n+1},D^{n+1}_{0},D^{n+1}_{1},g^{*}_{n+1},h^{*}_{n+1})$ in the
$V[G]$-game. This describes a winning strategy for Eve in the $V[G]$-game. ∎

###  4.8. $\oplus_{n}\Phi$ and $\Phi$

Suppose $\theta$ is a cardinal and $\Phi$ is a $\theta^{+}$ saturated linear
ordering. Let $\oplus_{n}\Phi$ denote the sum of $\omega$ many copies of
$\Phi$, i.e. $\omega\times\Phi$ with the lexicographical ordering.

######  Proposition 4.11.

Eve has a winning strategy in $\rm DG_{\theta,\omega}(\oplus_{n}\Phi,\Phi)$.

###### Proof.

We may consider that $\oplus_{n}\Phi$ and $\Phi$ are disjoint. This can be
easily achieved by replacing $\Phi$ by $\\{x\\}\times\Phi$, for some
$x\notin\omega$. For an integer $n$, let $\Phi_{n}$ denote the $n$-th copy of
$\Phi$, i.e. $\\{n\\}\times\Phi$, and let $\Phi[n]$ denote the sum of the
first $n$ copies of $\Phi$, i.e. $n\times\Phi$. Note that $\Phi[n]$ is
$\theta^{+}$-saturated, for all $n>0$. For a subset $X$ of $\oplus_{n}\Phi$ we
let $X(n)$ denote $X\cap\Phi_{n}$ and $X[n]=X\cap\Phi[n]$.

We now describe a winning strategy for Eve in $\rm
DG_{\theta,\omega}(\oplus_{n}\Phi,\Phi)$. Suppose Adam starts by playing
$(B^{0}_{0},B^{0}_{1})$ with $B_{0}\in[\oplus_{n}\Phi]^{\leq\theta}$ and
$B_{1}\in[\Phi]^{\leq\theta}$. Eve finds a partial isomorphism $g_{0}$ of size
$\leq\theta$ from $\Phi[1]$ to $\Phi$ such that $B^{0}_{0}[1]\subseteq{\rm
dom}(g_{0})$ and $B^{0}_{1}\subseteq{\rm ran}(g_{0})$. She can do that since
$\Phi[1]$ and $\Phi$ are both $\theta^{+}$-saturated. Let
$A^{0}_{0}=B^{0}_{0}\cup{\rm dom}(g_{0})$ and $A^{0}_{1}={\rm ran}(g_{0})$.
Let $h_{0}:A^{0}_{0}\cup A^{0}_{1}\to\omega$ be defined by:

$h_{0}(x)=\begin{cases}0,&\text{ if $x\in{\rm dom}(g_{0})\cup{\rm
ran}(g_{0})$,}\\\ n,&\text{ if $x\in B^{0}_{0}(n)\setminus{\rm
dom}(g_{0})$.}\end{cases}$

She then plays $(A^{0}_{0},A^{1}_{0},g_{0})$. Suppose in the next move Adam
plays some $(B^{1}_{0},B^{1}_{1})$. We may assume that $B^{0}_{0}\subseteq
B^{1}_{0}$ and $B^{0}_{1}\subseteq B^{1}_{1}$. Eve then extends $g_{0}$ to a
partial isomorphism $g_{1}$ of size $\leq\theta$ from $\Phi[2]$ to $\Phi$ such
that $B^{1}_{0}[2]\subseteq{\rm dom}(g_{1})$ and $B^{1}_{1}\subseteq{\rm
ran}(g_{1})$. Let $A^{1}_{0}=B^{1}_{0}\cup{\rm dom}(g_{1})$ and
$A^{1}_{1}={\rm ran}(g_{1})$. Let $h_{1}:A^{1}_{0}\cup A^{1}_{1}\to\omega$ be
defined by:

$h_{1}(x)=\begin{cases}0,&\text{ if $x\in{\rm dom}(g_{1})\cup{\rm
ran}(g_{1})$,}\\\ n-1,&\text{ if $x\in B^{0}_{0}(n)\setminus{\rm dom}(g_{0})$,
for $n>1$.}\end{cases}$

It should be clear that by continuing in this way Eve wins the game $\rm
DG_{\theta,\omega}(\oplus_{n}\Phi,\Phi)$. ∎

######  Corollary 4.12.

The property of having countable cofinality for a linear order cannot be
detected by the game $\rm DG_{\theta,\omega}$. ∎

##  5\. A class of infinitary logics

Let $\theta$ be a cardinal, and $\alpha$ and $\beta$ ordinals. Recall that for
two structures $\mathfrak{M}$ and $\mathfrak{N}$ in the same vocabulary, we
write $E^{\beta}_{\theta,\alpha}(\mathfrak{M},\mathfrak{N})$ if Eve has a
winning strategy in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M},\mathfrak{N})$. This relation is
reflexive and symmetric by definition, but we do not know if it is transitive.
Therefore, we make the following definition.

######  Definition 5.1.

Let $\theta$ be a cardinal and $\alpha$ and $\beta$ ordinals. We let
$\equiv^{\beta}_{\theta,\alpha}$ be the transitive closure of the relation
$E^{\beta}_{\theta,\alpha}$.

######  Remark 5.2.

Note that if $\beta^{\prime}\geq\beta$, $\theta^{\prime}\geq\theta$ and
$\alpha^{\prime}\leq\alpha$ then
$\equiv^{\beta^{\prime}}_{\theta^{\prime},\alpha^{\prime}}$ refines
$\equiv^{\beta}_{\theta,\alpha}$.

######  Definition 5.3.

Suppose $\kappa$ is a cardinal and $\alpha$ is an ordinal. For any signature
$\tau$ we define the following.

  1. (1)

An $\mathscr{L}^{1}_{\kappa,\alpha}$-sentence is a class of
$\tau_{0}$-structures closed under $\equiv^{\beta}_{\theta,\alpha}$, for some
cardinal $\theta<\kappa$, a vocabulary $\tau_{\phi}\in[\tau]^{\leq\theta}$,
and an ordinal $\beta<\kappa$.

  2. (2)

If $\phi$ is a $\tau$-sentence we let $\theta_{\phi}$ be the least $\theta$ as
above and let $\beta_{\phi}$ be the least ordinal for which $\phi$ is closed
under $\equiv^{\beta}_{\theta_{\phi},\alpha}$.

  3. (3)

For a $\tau$-structure $\mathfrak{M}$ and
$\phi\in\mathscr{L}^{1}_{\kappa,\alpha}$, we let:

$\mathfrak{M}\models\phi\hskip 8.53581pt\mbox{ if and only if }\hskip
8.53581pt\mathfrak{M}\restriction\tau_{\phi}\in\phi.$

######  Proposition 5.4.

Let $\kappa$ be an uncountable cardinal and $\alpha$ an ordinal with
$0<\alpha<\kappa$. The logic $\mathscr{L}^{1}_{\kappa,\alpha}$ is closed under
atomic sentences, negation, conjunction, and particularization.

###### Proof.

(1) (Atom property) Assume $\phi\in\mathscr{L}_{\omega,\omega}[\tau]$. We may
assume that $\tau$ is finite. We need to find
$\psi\in\mathscr{L}^{1}_{\kappa,\alpha}$, i.e. a model class closed under
$\equiv^{\beta}_{\theta,\alpha}$, for some cardinal $\theta<\kappa$ and
ordinal $\beta<\kappa$, such that, for every $\tau$-structure $\mathfrak{M}$,

$\mathfrak{M}\models\phi\hskip 14.22636pt\mbox{$\Longleftrightarrow$}\hskip
14.22636pt\mathfrak{M}\restriction\tau_{\psi}\in\psi.$

We let $\psi$ be the class of models satisfying $\phi$. In particular,
$\tau_{\psi}=\tau$. Note that $\psi$ is closed under the relation
$\equiv^{\beta}_{\omega,\alpha}$, for any $\alpha<\beta<\kappa$.

(2) (Negation) Let $\tau$ be a vocabulary and
$\phi\in\mathscr{L}^{1}_{\kappa,\alpha}$. Then $\neg\phi$ can be taken to be
the complement of $\phi$.

(3) (Conjunction) Suppose $\tau$ is a vocabulary and
$\phi_{0},\phi_{1}\in\mathscr{L}^{1}_{\kappa,\alpha}[\tau]$. We need to find
an $\mathscr{L}^{1}_{\kappa,\alpha}[\tau]$ sentence $\psi$ such that

${\rm Mod}^{\tau}_{\mathscr{L}^{1}_{\kappa,\alpha}}(\psi)={\rm
Mod}^{\tau}_{\mathscr{L}^{1}_{\kappa,\alpha}}(\phi_{0})\cap{\rm
Mod}^{\tau}_{\mathscr{L}^{1}_{\kappa,\alpha}}(\phi_{1}).$

Let $\psi$ be the class of $\tau_{\psi_{0}}\cup\tau_{\psi_{1}}$-structures
$\mathfrak{M}$ such that $\mathfrak{M}\restriction\tau_{\psi_{0}}\in\phi_{0}$
and $\mathfrak{M}\restriction\tau_{\psi_{1}}\in\psi_{1}$. Let
$\theta=\max\\{\theta_{\psi_{0}},\theta_{\psi_{1}}\\}$ and let
$\beta=\max\\{\beta_{\phi_{0}},\beta_{\psi_{1}}\\}$. Note that $\psi$ is
closed under $\equiv^{\beta}_{\theta,\alpha}$. Hence
$\psi\in\mathscr{L}^{1}_{\kappa,\alpha}[\tau]$, and is as required.

(4) (Particularization property) Let $\tau$ be a vocabulary and $c$ a new
constant symbol. Suppose $\phi$ is an
$\mathscr{L}^{1}_{\kappa,\alpha}[\tau\cup\\{c\\}]$-sentence. Let

$\psi=\\{\mathfrak{M}\in{\rm Str}[\tau]\ :\exists
a\,(\mathfrak{M},a)\in\phi\\}.$

Let $\theta=\theta_{\phi}$ and $\beta=\beta_{\phi}+\alpha+1$. Let us check
that $\psi$ is closed under $\equiv^{\beta}_{\theta,\alpha}$. First of all, if
this class is empty, then it is an $\mathscr{L}^{1}_{\kappa,\alpha}$-sentence.
Suppose now $\mathfrak{M}\in\psi$ and suppose $\mathfrak{N}$ is another
$\tau$-structure such that Eve has a winning strategy $\sigma$ in $\rm
DG^{\beta}_{\theta,\alpha}(\mathfrak{M},\mathfrak{N})$. We need to show that
$\mathfrak{N}\in\psi$. We describe a partial play in ${\rm
DG}^{\beta}_{\theta,\alpha}(\mathfrak{M},\mathfrak{N})$ in which Eve uses
$\sigma$. Let $a\in M$ be such that $(\mathfrak{M},a)\in\phi$. Adam starts by
letting $\beta_{0}=\beta_{\phi}+\alpha$ and playing
$(\beta_{0},\\{a\\},\emptyset)$. Eve follows her strategy $\sigma$ and assigns
some height $\alpha_{0}<\alpha$ to $a$. Adam then sets
$\beta_{1}=\beta_{\phi}+\alpha_{0}$. In finitely many steps the height
$\alpha_{n}$ assigned to $a$ by Eve must reach $0$ while
$\beta_{n}\geq\beta_{\phi}$. At this stage Eve must map $a$ to some element of
$N$. Since Eve can follow $\sigma$ from this position on and win the game
${\rm DG}^{\beta_{\phi}}_{\theta,\alpha}((\mathfrak{M},a),(\mathfrak{N},b))$
it follows that
$(\mathfrak{M},a)\equiv^{\beta_{\phi}}_{\theta,\alpha}(\mathfrak{N},b)$. ∎

######  Proposition 5.5.

Let $\kappa$ be an uncountable cardinal and $\alpha$ an ordinal with
$0<\alpha<\kappa$. The logic $\mathscr{L}^{1}_{\kappa,\alpha}$ has the atomic
substitution property.

###### Proof.

Suppose that $\tau$ and $\sigma$ are vocabularies. Let $U\in\sigma$ be a
binary relation. Suppose for every constant symbol $c\in\tau$, we have a unary
function symbol $K_{c}\in\sigma$, for every $n$-ary relation symbol
$R\in\tau$, we have an $n+1$-ary relation symbol $K_{R}\in\sigma$, and for
every $n$-ary function symbol $f\in\tau$, we have an $n+1$-ary function symbol
$K_{f}\in\sigma$. Finally, let $d\in\sigma$ be a constant symbol. Now, let
$\mathfrak{A}$ be a $\sigma$-structure and let $a=d^{\mathfrak{A}}$. Let

$U_{a}^{\mathfrak{A}}=\\{b\in A:U^{\mathfrak{A}}(b,a)\\}.$

If $R\in\tau$ is an $n$-ary relation symbol we can define an $n$-ary relation
$R^{\mathfrak{U}_{a}^{\mathfrak{A}}}$ on $U_{a}^{\mathfrak{A}}$ by letting

$R^{\mathfrak{U}^{\mathfrak{A}_{a}}}(b_{0},\ldots,b_{n-1})\hskip
14.22636pt\mbox{iff}\hskip
14.22636ptK_{R}^{\mathfrak{A}}(b_{0},\ldots,b_{n-1},a).$

If $c\in\tau$ is a constant symbol, we
$c^{\mathfrak{U}^{\mathfrak{A}}_{a}}=K_{c}^{\mathfrak{A}}(a)$. If $f\in\tau$
is an $n$-ary function symbol, we can define an $n$-ary function
$f^{\mathfrak{U}^{\mathfrak{A}}_{a}}$ by letting
$f^{\mathfrak{B}_{a}}(\bar{b})=K_{f}^{\mathfrak{A}}(\bar{b},a)$, for all
$\bar{b}\in A^{n}$. If $U_{a}^{\mathfrak{A}}$ is closed under these
interpretation of the symbols of $\tau$ we obtain a $\tau$-structure
$\mathfrak{U}^{\mathfrak{A}}_{a}$. Suppose $\phi$ is a $\tau$-sentence $\phi$.
We need to find a $\sigma$-sentence $\psi$ such that

$\mathfrak{A}\models_{\mathscr{L}^{1}_{\kappa,\alpha}}\psi\hskip
14.22636pt\mbox{iff \hskip 14.22636pt $\mathfrak{U}^{\mathfrak{A}}_{a}$ is a
$\tau$-closed and
}\mathfrak{U}^{\mathfrak{A}}_{a}\models_{\mathscr{L}^{1}_{\kappa,\alpha}}\phi.$

We simply let:

$\psi=\\{\mathfrak{A}\in{\rm
Str}[\sigma]:\mathfrak{U}_{d^{\mathfrak{A}}}\mbox{ is $\tau$-closed and
}\mathfrak{U}^{\mathfrak{A}}_{d^{\mathfrak{A}}}\in\phi\\}.$

In order to show that $\psi\in\mathscr{L}^{1}_{\kappa,\alpha}$ it suffices to
find a cardinal $\theta<\kappa$ and an ordinal $\beta<\kappa$ such that $\psi$
is closed under $\equiv^{\beta}_{\theta,\alpha}$.

Let $\theta=\theta_{\phi}$ and $\beta=\beta_{\phi}+\alpha+1$. Assume that
$\mathfrak{M}$ and $\mathfrak{N}$ are two $\sigma$-structures,
$\mathfrak{M}\in\psi$, and Eve has a winning strategy in ${\rm
DG}^{\beta}_{\kappa,\alpha}(\mathfrak{M},\mathfrak{N})$. We have to show that
$\mathfrak{N}\in\psi$. Let $a=d^{\mathfrak{M}}$ and $b=d^{\mathfrak{N}}$.

First we show that $U_{a}^{\mathfrak{M}}$ is $\tau$-closed if and only if
$U_{b}^{\mathfrak{N}}$ is $\tau$-closed. Assume towards contradiction that
$U_{a}^{\mathfrak{M}}$ is $\tau$-closed, but $U_{b}^{\mathfrak{N}}$ is not
$\tau$-closed. Let $B$ be a finite subset of $U_{b}^{\mathfrak{N}}$ whose
$\tau$-closure is not contained in $U_{b}^{\mathfrak{N}}$. In the first move
Adam sets $\beta_{0}=\beta_{\phi}+\alpha$ and plays $(\beta_{0},\emptyset,B)$.
Let us say that Eve follows her winning strategy and plays
$(\beta_{0},A^{0}_{0},A^{0}_{1},g_{0},h_{0})$. Let
$\alpha_{0}=\max\\{h_{0}(x):x\in B\\}$. Adam then sets
$\beta_{1}=\beta_{\phi}+\alpha_{0}$, and plays
$(\beta_{1},\emptyset,\emptyset)$. At stage $n$ Eve plays
$(\beta_{n},A^{n}_{0},A^{n}_{1},g_{n},h_{n})$. Let
$\alpha_{n}=\max\\{h_{n}(x):x\in B\\}$ Adam sets
$\beta_{n+1}=\beta_{\phi}+\alpha_{n}$ and plays
$(\beta_{n+1},\emptyset,\emptyset)$ as his next move. At some point the
ordinal $\alpha_{n}$ reaches $0$ and then Eve is obliged to have
$B\subseteq{\rm ran}(g_{n})$. Since $a$ and $b$ are interpretations of $d$ in
$\mathfrak{M}$ and $\mathfrak{N}$ we must have $a\in{\rm dom}(g_{n})$ and
$b\in{\rm ran}(g_{n})$. But then $g_{n}$ cannot be a partial isomorphism, a
contradiction.

In case $U_{a}^{\mathfrak{M}}$ and $U_{b}^{\mathfrak{N}}$ are both
$\tau$-closed, it suffices to show that Eve has a winning strategy in the game

${\rm
DG}^{\beta_{\phi}}_{\theta,\alpha}(\mathfrak{U}^{\mathfrak{M}}_{a},\mathfrak{U}^{\mathfrak{N}}_{b}).$

But this is clear; if Adam plays inside $U_{a}^{\mathfrak{M}}\cup
U_{b}^{\mathfrak{N}}$ then Eve’s winning strategy in the game ${\rm
DG}^{\beta}_{\theta,\alpha}(\mathfrak{M},\mathfrak{N})$ restricted to
$U_{a}^{\mathfrak{M}}\cup U_{b}^{\mathfrak{N}}$ gives rise to a winning
strategy for Eve in this game as well. This shows that $\psi$ is an
$\mathscr{L}^{1}_{\kappa,\alpha}$-sentence, and therefore that
$\mathscr{L}^{1}_{\kappa,\alpha}$ has the atomic substitution property. ∎

The way we have defined the logic $\mathscr{L}^{1}_{\kappa,\alpha}$, given a
vocabulary $\tau$ each $\tau$-sentence is a proper class. In order to remedy
this situation we show that each $\tau$-sentence has a model of bounded
cardinality. This is done as in [14] by using the results of Karp on the usual
infinitary logic $\mathscr{L}_{\gamma,\gamma}$ (see [2, Chapter 3]).

######  Definition 5.6.

Let $\theta$ be a cardinal and $\mathfrak{M}$ and $\mathfrak{N}$ two
structures in the same vocabulary $\tau$ of cardinality $\leq\theta$. We
define a sequence
$\\{\mathcal{I}^{\alpha}_{\theta}(\mathfrak{M},\mathfrak{N}):\alpha\in{\rm
ORD}\\}$ of families of partial isomorphisms from $\mathfrak{M}$ to
$\mathfrak{N}$ as follows.

  * •

Let ${\mathcal{I}}^{0}_{\theta}(\mathfrak{M},\mathfrak{N})$ be the family of
all partial isomorphisms from $\mathfrak{M}$ to $\mathfrak{N}$ of size at most
$\theta$.

  * •

Suppose ${\mathcal{I}}^{\alpha}_{\theta}(\mathfrak{M},\mathfrak{N})$ has been
defined for all $\alpha<\beta$. We say that a partial isomorphism $f$ of size
at most $\theta$ is in
${\mathcal{I}}^{\beta}_{\theta}(\mathfrak{M},\mathfrak{N})$ if for every
$A\in[M]^{\leq\theta}\cup[N]^{\leq\theta}$ and every $\alpha<\beta$ there is
$g\in{\mathcal{I}}^{\alpha}_{\theta}(\mathfrak{M},\mathfrak{N})$ which extends
$f$ and covers $A$.

Here $g$ covers $A$ means that if $A\in[M]^{\leq\theta}$ then $A\subseteq{\rm
dom}(g)$ and if $A\in[N]^{\leq\theta}$ then $A\subseteq{\rm ran}(g)$. If
${\mathcal{I}}^{\beta}_{\theta}(\mathfrak{M},\mathfrak{N})$ is non-empty we
say that $\mathfrak{M}$ and $\mathfrak{N}$ are $\theta$-back and forth
equivalent up to $\beta$ and write

$\mathfrak{M}\equiv^{\beta}_{\theta}\mathfrak{N}.$

Suppose now that $\theta$ is a cardinal and that $\mathfrak{M}$ is a
$\tau$-structure, for some vocabulary $\tau$ of cardinality at most $\theta$.
Observe that if $\beta$ is an ordinal and
$f\in{\mathcal{I}}^{\beta}_{\theta}(\mathfrak{M},\mathfrak{M})$, and
$g\subseteq f$ is a partial isomorphism then
$g\in{\mathcal{I}}^{\beta}_{\theta}(\mathfrak{M},\mathfrak{M})$. Moreover, if
$f,g\in{\mathcal{I}}^{\beta}_{\theta}(\mathfrak{M},\mathfrak{M})$ with ${\rm
ran}(f)\subseteq{\rm dom}(g)$ then $g\circ
f\in{\mathcal{I}}^{\beta}_{\theta}(\mathfrak{M},\mathfrak{M})$. Given two
sequence $\bar{a}=(a_{i})_{i<\theta}$ and $\bar{b}=(b_{i})_{i<\theta}$ of
elements of $M$ we write

$\bar{a}\sim_{\beta}\bar{b}$

if there is $f\in{\mathcal{I}}^{\beta}_{\theta}(\mathfrak{M},\mathfrak{M})$
such that $f(a_{i})=b_{i}$, for all $i<\theta$. It follows that $\sim_{\beta}$
is an equivalence relation. We now want to estimate the number of
$\sim_{\beta}$-equivalence classes. Consider first the case $\beta=0$. Note
that if $\bar{a}$ and $\bar{b}$ are two sequences of length $\theta$, then
$\bar{a}\sim_{0}\bar{b}$ iff the map $a_{i}\mapsto b_{i}$ extends to a partial
isomorphism. Let ${\rm tp}_{0}(\bar{a})$ denote the isomorphism type of the
sequence $\bar{a}$. Then $\bar{a}\sim_{0}\bar{b}$ iff ${\rm
tp}_{0}(\bar{a})={\rm tp}_{0}(\bar{b})$. Since the vocabulary $\tau$ has
cardinality at most $\theta$, the cardinality of the set of
$\sim_{0}$-equivalence classes is at most $2^{\theta}$.

Now, if $\bar{a},\bar{d}\in M^{\theta}$ and $f:\theta\to\theta$ is such that
$a_{i}=d_{f(i)}$, for all $i<\theta$, we write
$\bar{a}\sqsubseteq_{f}\bar{d}$. Suppose we have defined ${\rm
tp}_{\alpha}(\bar{a})$, for all $\alpha<\beta$ and all $\bar{a}\in
M^{\theta}$. Given $\bar{a}\in M^{\theta}$ we let

${\rm tp}_{\beta}(\bar{a})=\\{({\rm
tp}_{\alpha}(\bar{d}),f):\alpha<\beta,\bar{d}\in
M^{\theta},f\in\theta^{\theta},\mbox{ and }\bar{a}\sqsubseteq_{f}\bar{d}\\}.$

It should be clear that if ${\rm tp}_{\beta}(\bar{a})={\rm
tp}_{\beta}(\bar{b})$ then $\bar{a}\sim_{\beta}\bar{b}$, so it suffices to
estimate the number of $\beta$-types of $\theta$-sequences of elements of $M$.
Let $T_{\beta}$ be the set of $\beta$-types of $\theta$-sequences in $M$ and
let $\lambda_{\beta}$ be its cardinality. Then by the above analysis we have
that

$\lambda_{\beta}\leq\prod_{\alpha<\beta}\exp({\lambda_{\alpha}\times
2^{\theta}}).$

From this we conclude that $\lambda_{\beta}\leq\beth_{\beta+1}(\theta)$. We
now have the following.

######  Theorem 5.7 (Karp, [2]).

Let $\theta$ be an infinite cardinal and $\beta$ and ordinal. Suppose
$\mathfrak{M}$ is a structure in a vocabulary $\tau$ of cardinality at most
$\theta$. Then there is a substructure $\mathfrak{N}$ of $\mathfrak{M}$ of
cardinality at most $\beth_{\beta+1}(\theta)$ such that
$\mathfrak{M}\equiv^{\beta}_{\theta}\mathfrak{N}$.

###### Proof.

Let $\theta$ be a sufficiently large regular cardinal. Pick $H\prec H(\theta)$
of cardinality $\beth_{\beta+1}$ and closed under $\theta$-sequences such that
$\tau,\mathfrak{M}\in H$ and $T_{\beta}\subseteq H$. Let $N=M\cap H$ and let
$\mathfrak{N}$ be the substructure of $\mathfrak{M}$ with universe $N$. It is
straightforward to see that $\mathfrak{M}\equiv^{\beta}_{\theta}\mathfrak{N}$.
∎

Let us now observe that if $\theta$ is a cardinal, $\beta$ an ordinal, and
$\mathfrak{M}$ and $\mathfrak{N}$ are two structures in the same vocabulary of
size at most $\theta$, then

$\mathfrak{M}\equiv^{2\cdot\beta}_{\theta}\mathfrak{N}\Longrightarrow\mathfrak{M}\equiv^{\beta}_{\theta,1}\mathfrak{N}.$

The reason we need $2\cdot\beta$ in the first equivalence is that in the game
$\rm DG^{\beta}_{\theta,1}(\mathfrak{M},\mathfrak{N})$ Adam is allowed to play
sets of size $\leq\theta$ in both models at the same time, whereas if
$f\in\mathcal{I}^{\beta+1}_{\theta}(\mathfrak{M},\mathfrak{N})$ then for every
$A$ which is either in $[M]^{\leq\theta}$ or $[N]^{\leq\theta}$ there is
$g\in\mathcal{I}^{\beta}_{\theta}(\mathfrak{M},\mathfrak{N})$ extending $f$
which covers $A$.

Now, the upshot is that every $\equiv^{\beta}_{\theta,1}$-equivalence class of
models in a fixed vocabulary $\tau$ of size at most $\theta$ has an element
which is of cardinality at most $\beth_{2\cdot\beta+1}(\theta)$. It follows
that if $\kappa$ is a cardinal and $\alpha<\kappa$ then the logic
$\mathscr{L}^{1}_{\kappa,\alpha}$ is small. Strictly speaking we should
redefine the collection of $\mathscr{L}^{1}_{\kappa,\alpha}[\tau]$ sentences,
for a vocabulary $\tau$, and the satisfaction relation as follows. A
$\tau$-sentence is a class of models in some vocabulary
$\tau_{\phi}\in[\tau]^{\leq\theta}$ closed under
$\equiv^{\beta}_{\theta,\alpha}$ and consisting of models with universe a
subset of $\beth_{2\cdot\beta}(\theta)$, for some cardinal $\theta<\kappa$ and
ordinal $\beta<\kappa$. If $\mathfrak{M}$ is a $\tau$-structure and $\phi$ is
a $\tau$-sentence we let:

$\mathfrak{M}\models_{\mathscr{L}^{1}_{\kappa,\alpha}}\phi\hskip
8.53581pt\mbox{ if there is a structure $\mathfrak{N}\in\phi$ such that
}\hskip