Logic and Proof MT24, Ehrenfeucht-Fraïssé games

The definition is by induction on $k$.

• $k = 0$: $(\mathcal A, \pmb a) \sim _ 0 (\mathcal B, \pmb b)$ iff for any atomic $\sigma$-formula $\varphi$ with free variables among $x _ 1, \ldots, x _ m$, $\mathcal A \models \varphi(\pmb a)$ iff $\mathcal B \models \varphi (\pmb b)$.
• $k > 0$: $(\mathcal A, \pmb a) \sim _ {k+1} (\mathcal B, \pmb b)$ iff:
  • for all $a’ \in A$, there exists $b’ \in B$ such that $(\mathcal A, \pmb a \parallel a’) \sim _ k (\mathcal B, \pmb b \parallel b’)$, and
  • for all $b’ \in B$, there exists $a’ \in A$ such that $(\mathcal A, \pmb a \parallel a’) \sim _ k (\mathcal B, \pmb b \parallel b’)$.

It is a game between two players:

• Spoiler, who aims to show that $\mathcal A$ and $\mathcal B$ are different
• Duplicator, who aims to show that $\mathcal A$ and $\mathcal B$ are not that different

The game consists of $k$ rounds. In each round $1 \le i \le k$, Spoiler picks an element $a \in A$ or $b \in B$ and Duplicator responds with an element of the other structure.

After $k$ rounds, this produces tuples $\pmb a’ \in A^k$ and $\pmb b’ \in B^k$ of elements chosen by each player.

Duplicator wins if for all atomic formulas $\varphi(x _ 1, \ldots, x _ {m+k})$,

\[\mathcal A \models \varphi(\pmb a \parallel \pmb a') \text{ iff } \mathcal B \models \varphi(\pmb b \parallel \pmb b')\]

A function that takes a configuration of the game $\big((\mathcal A, \pmb a), (\mathcal B, \pmb b)\big)$ and a move of Spoiler, and outputs a response.

The set of $\sigma$-formulas in free variables $x _ 1, \ldots, x _ m$ that have maximum quantifier depth $k$.

For all formulas $\varphi \in \text{FO} _ {k, m}^\sigma$ (first-order formulas of depth $k$ with $m$ free variables), $\mathcal A \models \varphi(\pmb a)$ iff $\mathcal B \models \varphi(\pmb b)$.

• $(\mathcal A, \pmb a) \sim _ k (\mathcal B, \pmb b)$

iff

• Duplicator has a winning strategy in $G _ k\big((\mathcal A, \pmb a), (\mathcal B, \pmb b)\big)$.

Suppose:

• $\sigma$ is a signature
• $\mathcal A$ is a $\sigma$-structure
• $\mathcal B$ is a $\sigma$-structure
• $\pmb a, \pmb b$ are $m$-tuples
• $k, m \in \mathbb N _ {\ge 0}$

Then:

• $(\mathcal A, \pmb a) \equiv _ k (\mathcal B, \pmb b)$ (agree on all first-order formulas with quantifier depth $k$)

iff

• $(\mathcal A, \pmb a) \sim _ k (\mathcal B, \pmb b)$ (“inductively similar”, equivalent to Duplicator having a winning strategy in corresponding Ehrenfeucht-Fraïssé game).

Induct on the quantifier depth $k$.

Base case: $k = 0$. In this case, every formula in $\text{FO} _ {k, m}^\sigma$ is a boolean combination of atomic formulas in the free variables $x _ 1, \ldots, x _ m$, of which there are only finitely many.

Inductive step: $k > 0$.

Note that every formula in $\text{FO} _ {k+1, m}^\sigma$ is a boolean combination of formulas of the form

\[\exists x _ {m+1} \varphi\]

where $\varphi \in \text{FO} _ {k, m+1}^\sigma$. But then by the induction hypothesis, there are only finitely many choices of $\varphi$ up to logical equivalence.

Since $\varphi \equiv \varphi’$ implies $\exists x _ {m+1} \varphi \equiv \exists x _ {m+1} \varphi’$, the result follows.

This follows straightforwardly from the definitions. Recall that $(\mathcal A, \pmb a) \sim _ k (\mathcal B, \pmb b)$ is defined inductively via:

• $k = 0$: $(\mathcal A, \pmb a) \sim _ 0 (\mathcal B, \pmb b)$ iff for any atomic $\sigma$-formula $\varphi$ with free variables among $x _ 1, \ldots, x _ m$, $\mathcal A \models \varphi(\pmb a)$ iff $\mathcal B \models \varphi (\pmb b)$.
• $k > 0$: $(\mathcal A, \pmb a) \sim _ {k+1} (\mathcal B, \pmb b)$ iff:
  • for all $a’ \in A$, there exists $b’ \in B$ such that $(\mathcal A, \pmb a \parallel a’) \sim _ k (\mathcal B, \pmb b \parallel b’)$, and
  • for all $b’ \in B$, there exists $a’ \in A$ such that $(\mathcal A, \pmb a \parallel a’) \sim _ k (\mathcal B, \pmb b \parallel b’)$.

The characterisations are equivalent when $k = 0$. Then note:

• Duplicator has a winning strategy in $G _ {k+1}((\mathcal A, \pmb a), (\mathcal B, \pmb b))$, iff
• For every move of Spoiler, Duplicator has a winning strategy in $G _ {k}((\mathcal A, \pmb a), (\mathcal B, \pmb b))$, iff
• $(\mathcal A, \pmb a) \sim _ {k+1} (\mathcal B, \pmb b)$

Recall the definitions:

$(\mathcal A, \pmb a) \equiv _ k (\mathcal B, \pmb b)$ means that for all formulas $\varphi \in \text{FO} _ {k, m}^\sigma$, $\mathcal A \models \varphi(\pmb a)$ iff $\mathcal B \models \varphi(\pmb b)$.

and

$(\mathcal A, \pmb a) \sim _ k (\mathcal B, \pmb b)$ is defined inductively, like so:

• $k = 0$: $(\mathcal A, \pmb a) \sim _ 0 (\mathcal B, \pmb b)$ iff for any atomic $\sigma$-formula $\varphi$ with free variables among $x _ 1, \ldots, x _ m$, $\mathcal A \models \varphi(\pmb a)$ iff $\mathcal B \models \varphi (\pmb b)$.
• $k > 0$: $(\mathcal A, \pmb a) \sim _ {k+1} (\mathcal B, \pmb b)$ iff:
  • for all $a’ \in A$, there exists $b’ \in B$ such that $(\mathcal A, \pmb a \parallel a’) \sim _ k (\mathcal B, \pmb b \parallel b’)$, and
  • for all $b’ \in B$, there exists $a’ \in A$ such that $(\mathcal A, \pmb a \parallel a’) \sim _ k (\mathcal B, \pmb b \parallel b’)$.

We proceed by induction on $k$.

Base case $k = 0$: This is trivial, since $\sim _ 0$ and $\equiv _ 0$ have the same definition.

Inductive step $k > 0$:

---

For the forward direction, suppose that $(\mathcal A, \pmb a) \equiv _ {k+1} (\mathcal B, \pmb b)$, we aim to show that $(\mathcal A, \pmb a) \sim _ {k+1} (\mathcal B, \pmb b)$.

To do this, pick some $a’ \in A$. The definition requires us to find some $b’ \in B$ such that

\[(\mathcal A, \pmb a \parallel a') \sim _ k (\mathcal B, \pmb b \parallel b')\]

Let

• $\psi _ 1, \psi _ 2, \ldots, \psi _ {\ell _ 1} \in \text{FO}^\sigma _ {k, m+1}$ be an enumeration of all formulas up to logical equivalence that are satisfied by $(\mathcal A, \pmb a \parallel a’)$
• $\psi _ 1’, \psi _ 2’, \ldots, \psi _ {\ell _ 2}’ \in \text{FO}^\sigma _ {k, m+1}$ be an enumeration of all formulas up to logical equivalence that are not satisfied by $(\mathcal A, \pmb a \parallel a’)$.

Define

\[\varphi := \bigwedge^{\ell _ 1} _ {i = 1} \psi _ i \land \bigwedge^{\ell _ 2} _ {i = 1} \lnot \psi _ i'\]

Then $\mathcal A \models (\exists x _ {m+1} \varphi)(\pmb a)$ (just take $x _ {m+1}$ to be $a’$). Since $(\exists x _ {m+1} \varphi) \in \text{FO} _ {k+1, m}$, we have that $\mathcal B \models \varphi (\pmb b \parallel b’)$ by the assumption. By the definition of $\varphi$ we therefore have

\[(\mathcal A, \pmb a \parallel a') \equiv _ k (\mathcal B, \pmb b \parallel b')\]

since otherwise $\mathcal A$ and $\mathcal B$ would disagree on one of the conjuncts in $\varphi$. But then by the inductive hypothesis,

\[(\mathcal A, \pmb a \parallel a') \sim _ k (\mathcal B, \pmb b \parallel b')\]

and thus

\[(\mathcal A, \pmb a) \sim _ {k+1} (\mathcal B, \pmb b)\]

as required. The definition of $\sim _ {k+1}$ also requires we show that for all $b’ \in B$ there exists $a’ \in A$ with $(\mathcal A, \pmb a \parallel a’) \sim _ k (\mathcal B, \pmb b \parallel b’)$, but this is immediate since the above argument is symmetric.

---

For the backward direction, suppose that $(\mathcal A, \pmb a) \sim _ {k+1} (\mathcal B, \pmb b)$ and we aim to show that $(\mathcal A, \pmb a) \equiv _ {k+1} (\mathcal B, \pmb b)$.

Consider some formula $(\exists x _ {m+1} \varphi) \in \text{FO} _ {k+1, m}^\sigma$, and suppose that

\[\mathcal A \models (\exists x _ {m+1} \varphi)(\pmb a)\]

Then there exists $a’ \in A$ such that

\[\mathcal A \models \varphi(\pmb a \parallel a')\]

Since by assumption $(\mathcal A, \pmb a) \sim _ {k+1} (\mathcal B, \pmb b)$, there exists $b’$ such that

\[(\mathcal A, \pmb a \parallel a') \sim _ k (\mathcal B, \pmb b \parallel b')\]

By the inductive hypothesis, it follows that

\[(\mathcal A, \pmb a \parallel a') \equiv _ k (\mathcal B, \pmb b \parallel b')\]

which implies that

\[\mathcal B \models \varphi(\pmb b \parallel b')\]

Hence $B \models (\exists x _ {m+1} \varphi)(\pmb b)$. Since every formula in $\text{FO} _ {k+1,m}^\sigma$ is a boolean combination of formulas $\exists x _ {m+1} \varphi$ for $\varphi \in \text{FO} _ {k, m+1}^\sigma$, we conclude that $(\mathcal A, \pmb a) \equiv _ {k+1} (\mathcal B, \pmb b)$. The definition of $\equiv _ {k+1}$ also requires us to show that $\mathcal B \models \varphi(\pmb b)$ implies $\mathcal A \models \varphi(\pmb a)$, but again this is immediate from symmetry.

For each $k$, we exhibit two structures $\mathcal A$ and $\mathcal B$ over $\sigma$ where:

• $\mathcal A$ has an odd number of elements,
• $\mathcal B$ has an even number of elements, and
• Duplicator wins the corresponding $k$-round EF game

By the EF theorem, this implies that $\mathcal A$ and $\mathcal B$ agree on all formulas of quantifier depth $k$. Since any first-order formula expressing that a finite linear order has even cardinality must have a finite quantifier depth, it follows that no first-order formula can express this property.

---

Fix some $k$.

Exhibit two structures: Pick any such $\mathcal A$ and $\mathcal B$ where $ \vert A \vert , \vert B \vert \ge 2^k - 1$.

State the invariant Duplicator maintains: Duplicator should ensure that after round $\ell = 0, 1, \ldots, k$, the tuples

• $\pmb a = (a _ {-1}, a _ 0, \ldots, a _ \ell)$
• $\pmb b = (b _ {-1}, b _ 0, \ldots, b _ \ell)$

satisfy the following conditions:

1. $a _ i < a _ j$ iff $b _ i < b _ j$ for all $1 \le i, j \le \ell$
2. $d(a _ i, a _ j) < 2^{k-\ell} - 1$ implies $d(a _ i, a _ j) = d(b _ i, b _ j)$
3. $d(a _ i, a _ j) \ge 2^{k-\ell} - 1$ implies $d(b _ i, b _ j) \ge 2^{k-\ell} - 1$

where $a _ {-1} = \min A$, $a _ 0 = \max A$ and $b _ {-1} = \min B$, $b _ 0 = \max B$ are not moves played in the game and only serve to express the invariant and where $d$ is the distance between two elements.

Explain how duplicator can maintain the invariant: Todo.

@important~

For each $k$, we exhibit two graphs $G _ 1$ and $G _ 2$ over $\sigma$ where:

• $G _ 1$ is connected,
• $G _ 2$ is not connected, and
• Duplicator wins the corresponding $k$-round EF game

By the EF theorem, this implies that $\mathcal A$ and $\mathcal B$ agree on all formulas of quantifier depth $k$. Since any first-order formula expressing that a graph is connected must have a finite quantifier depth, it follows that no first-order formula can express this property.

---

Notation:

• Let $B^G _ d(u$ be the subgraph consisting of the set of vertices at distance at most $d$ to $u$
• Let $B^G _ d(u _ 1, \ldots, u _ s)$ be subgraph consisting of the set of vertices at distance at most $d$ from some $u _ i$
• Let $G \cong H$ denote a graph isomorphism from $G$ to $H$.

---

Exhibit two structures:

• Let $\mathcal A$ consist of a single cycle of length $4 \cdot 3^k + 4$
• Let $\mathcal B$ consist of two disjoint cycles of lengths $2 \cdot 3^k + 2$

State the invariant Duplicator maintains: Duplicator should maintain the invariant that after $\ell$ rounds there is a graph isomorphism

\[f : \bigcup^\ell _ {i = 1} B^\mathcal A _ {3^{k-\ell} } (a _ i) \to \bigcup^\ell _ {i = 1} B^\mathcal B _ {3^{k-\ell} } (b _ i)\]

with $f(a _ i) = b _ i$ for $i = 1, \ldots, \ell$ where $(\pmb a, \pmb b) \in A^\ell \times B^\ell$ is the sequence of moves played in the first $\ell$ rounds.

Explain how duplicator can maintain the invariant: Without loss of generality, we may consider the case where Spoiler moves in $\mathcal A$ and Duplicator responds in $\mathcal B$.

If Spoiler chooses $a \in A$ at distance at most $2 \cdot 3^{k-\ell-1}$ from some element of $\pmb a$, then Duplicator responds by playing $f(a)$, which maintains the invariant since $f$ restricts to a graph isomorphism from $\bigcup^{\ell + 1} _ {i = 1} B^{\mathcal A} _ {3^{k - \ell - 1} }(a _ i)$ to $\bigcup^{\ell + 1} _ {i = 1} B^\mathcal B _ {3^{k - \ell - 1} }(b _ i)$.

If Spoiler plays $a \in A$ at a distance strictly greater than $2 \cdot 3^{k - \ell - 1}$ to any element of $\pmb a$, then Duplicator can play $b \in B$ at distance greater than $2 \cdot 3^{k - \ell - 1}$ from any element of $\pmb b$, and we can construct the required isomorphism

\[f : \bigcup^{\ell+1} _ {i = 1} B^\mathcal A _ {3^{k-\ell-1} } (a _ i) \to \bigcup^{\ell+1} _ {i = 1} B^\mathcal B _ {3^{k-\ell-1} } (b _ i)\]

by gluing together an isomorphism from $B^\mathcal A _ {3^{k - \ell - 1} }(a)$ to $B^\mathcal B _ {3^{k - \ell - 1} }(b)$ (since all balls of this radius in $\mathcal A$ and $\mathcal B$ are isomorphic), and the restriction of $f$ to an isomorphism from $\bigcup^\ell _ {i = 1} B^{\mathcal A} _ {3^{k - \ell - 1} }(a _ i)$ to $\bigcup^\ell _ {i = 1} B^{\mathcal B} _ {3^{k - \ell - 1} }(a _ i)$.

---

Note that there is a simpler argument by appealing to the compactness theorem for first-order logic.

@important~