Discrete Linear Orderings and Fraïssé Games

V.Boutchkova

23 June 1999

Abstract Fraïssé games are used to prove some axiomatizations of the order types (ω, <) ⊕ (ω, <), ({0, …, m − 1}, <), (ω · m, <), (ω · m + q, <) and (ω^{m}, <).

We consider structures of the signature ((2),∅,0). The language L that belongs to this signature has two binary relation symbols, ⊏ and =, and does not have function symbols nor individual constants.

We consider formulas θ(x_{0} … x_{k−1}) in L, where all the free variables of θ are among x_{0} … x_{k−1}, that we abbreviate by \overrightarrow{x}. For every x we define two mappings L_{x} and R_{x} between such formulas in a way that the formulas L_{x}(θ) and R_{x}(θ) have free variables among x, x_{0} … x_{k−1}. Sometimes we use a second notation:

θ^{⊏x}(x, \overrightarrow{x}) ≡ L_{x}(θ(\overrightarrow{x})), and θ^{x⊏}(x, \overrightarrow{x}) ≡ R_{x}(θ(\overrightarrow{x})).

If 𝔄 = (A, <) is a structure of the given signature, for each element b ∈ A we define A^{<b} to be the set {a ∈ A | a < b}, and 𝔄^{<b} to be the structure (A^{<b}, <) where the relation < is restricted to the set A^{<b}. We want to have the following property:

𝔄 ⊧ θ^{⊏x}[b, a_{0} … a_{k−1}] if and only if 𝔄^{<b} ⊧ θ[a_{0} … a_{k−1}],

for all b ∈ A and for all a_{0} … a_{k−1} ∈ A^{<b}. And we want the analogous property for the mapping R_{x}, i.e. if A^{>b} = {a ∈ A | b < a} and 𝔄^{>b} = (A^{>b}, <), then 𝔄 ⊧ θ^{x⊏}[b, a_{0} … a_{k−1}] if and only if 𝔄_{b} ⊧ θ[a_{0} … a_{k−1}], where b ∈ A and a_{0} … a_{k−1} ∈ A^{>b}.

Definition We define the mappings L_{x} and R_{x} by induction on the formula θ :

• If θ is a basic formula or the negation of a basic formula, then L(x, θ) ≡ R(x, θ) ≡ θ.

• If θ(\overrightarrow{x}) is the formula θ_{1}(\overrightarrow{x}) ∧ θ_{2}(\overrightarrow{x}), then

L(x, θ) ≡ L(x, θ_{1}) ∧ L(x, θ_{2}), R(x, θ) ≡ R(x, θ_{1}) ∧ R(x, θ_{2}).

We define in the same way the image of the disjunction: θ(\overrightarrow{x}) is the formula θ_{1}(\overrightarrow{x}) ∨ θ_{2}(\overrightarrow{x}).

• If θ(\overrightarrow{x}) is the formula ∃y φ(y, \overrightarrow{x}), then

L(x, θ(\overrightarrow{x})) ≡ ∃y(y ⊏ x ∧ L(x, φ(y, \overrightarrow{x})) ), R(x, θ(\overrightarrow{x})) ≡ ∃y(x ⊏ y ∧ R(x, φ(y, \overrightarrow{x})) ).

• If θ(\overrightarrow{x}) is the formula ∀y φ(y, \overrightarrow{x}), then

L(x, θ(\overrightarrow{x})) ≡ ∀y(y ⊏ x → L(x, φ(y, \overrightarrow{x})) ), R(x, θ(\overrightarrow{x})) ≡ ∀y(x ⊏ y → R(x, φ(y, \overrightarrow{x})) ).

Remark: The bounding of the quantifiers in the formula does not change its quantifier depth: QD(L_{x}(θ)) = QD(θ) = QD(R_{x}(θ)).

1 The order type (ω, <) ⊕ (ω, <)

The first goal is to find an axiomatization of the structure (ℕ, <) ⊕ (ℕ, <). We define the following sentence:

φ ≡ ∀x_{0}(¬(x_{0} ⊏ x_{0})) ∧  (irreflexibility) ∀x_{0}∀x_{1}∀x_{2}(x_{0} ⊏ x_{1} ⊏ x_{2} → x_{0} ⊏ x_{2}) ∧  (transitivity) ∀x_{0}∀x_{1}(x_{0} ⊏ x_{1} ∨ x_{0} = x_{1} ∨ x_{1} ⊏ x_{0}) ∧  (linearity) ∀x_{0}∃x_{1}(x_{0} ⊏ x_{1} ∧ ¬∃x_{2}(x_{0} ⊏ x_{2} ⊏ x_{1})) ∧  (immediate successor)

∃x_{0}∃x_{1} ( \begin{matrix}x_{0} ⊏ x_{1} ∧ ¬∃x_{2}(x_{2} ⊏ x_{0}) ∧ \\ ∀x_{2} ( \begin{matrix}¬(x_{0} = x_{2}) ∧ ¬(x_{1} = x_{2}) ⟷ \\ ∃x_{3}(x_{3} ⊏ x_{2} ∧ ¬∃x_{4}(x_{3} ⊏ x_{4} ⊏ x_{2})) \end{matrix} ) \end{matrix} )

Definition: Let 𝔄 = (A, <) be a structure with signature ((2),∅,0). We define distance between two elements of this structure as follows: for all a, b ∈ A, such that a < b, d(a, b) = 1+ the number of elements between a

and b, i.e. | \begin{matrix}d(a, b) = 1 + ∥\{c ∈ A | a < c < b\}∥ & , for a < b \\ d(a, a) = 0 \end{matrix}

Notation:

ψ(x_{0}, x_{1}) ≡ ( \begin{matrix}x_{0} ⊏ x_{1} ∧ ¬∃x_{2}(x_{2} ⊏ x_{0}) ∧ \\ ∀x_{2} ( \begin{matrix}¬(x_{0} = x_{2}) ∧ ¬(x_{1} = x_{2}) ⟷ \\ ∃x_{3}(x_{3} ⊏ x_{2} ∧ ¬∃x_{4}(x_{3} ⊏ x_{4} ⊏ x_{2})) \end{matrix} ) \end{matrix} ) .

If 𝔄 ⊧ φ then 𝔄 ⊧ ∃x_{0}∃x_{1}ψ(x_{0}, x_{1}) and therefore there exist exactly two elements (we will denote them by 0_{0}^{𝔄} and 0_{1}^{𝔄}) such that 𝔄 ⊧ ψ[0_{0}^{𝔄}, 0_{1}^{𝔄}].

Lemma

Let 𝔄 = (A, <_{A}) and 𝔅 = (B, <_{B}) be models of φ. Let f ∈ LI_{0}(𝔄, 𝔅) be a local isomorphism from 𝔄 to 𝔅. Let us denote a^{(0)} :=

\{ \begin{matrix}min\{a_{i} | a_{i} ∈ Dom(f)\} & , if f ≠ ∅ \\ 0_{0}^{𝔄} & , otherwise \end{matrix}

and

a^{(1)} := \{ \begin{matrix}min\{a_{i} | a_{i} ∈ Dom(f) & 0_{1}^{𝔄} ≤_{A} a_{i}\} & , if ∃a ∈ Dom(f)(0_{1}^{𝔄} ≤_{A} a) \\ 0_{1}^{𝔄} & , otherwise \end{matrix}

Then for every natural number p ≥ 2,

f ∈ LI_{p}(𝔄, 𝔅) if and only if

( \begin{matrix}∀n ≤ 2^{(p−1)} ∀a_{i}, a_{j} ∈ Dom(f) \\ (d(a_{i}, a_{j}) = n ⇔ d(f(a_{i}), f(a_{j})) = n) \\ & \\ ∀n ≤ 2^{(p−1)} + p − 2 \\ (a^{(0)} ∈ Dom(f) ⇒ (d(0_{0}^{𝔄}, a^{(0)}) = n ⇔ d(0_{0}^{𝔅}, f(a^{(0)})) = n)) \\ & \\ ∀n ≤ 2^{(p−1)} + p − 4 \\ (a^{(1)} ∈ Dom(f) ⇒ (d(0_{1}^{𝔄}, a^{(1)}) = n ⇔ d(0_{1}^{𝔅}, f(a^{(1)})) = n)) \end{matrix} )

The three conjuncts of the right side formalize the following three properies:

• ”to preserve distances less than or equal to2^{p−1}”,

• ”to preserve the distances to the first element 0_{0}, which are less than or equal to 2^{(p−1)} + p − 2” and

• ”to preserve the distances to the second zero 0_{1}, which are less than or equal to 2^{(p−1)} + p − 4”.

We will need the direction (⇐) only.

Proof: Induction on p.

p = 2.

(⇒) f ∈ LI_{2}(𝔄, 𝔅)

• It is easy to verify that d(a_{i}, a_{j}) = d(f(a_{i}), f(a_{j})) when one of these distances is ≤ 2.

• If a^{(0)} ∈ Dom(f) and one of d(0_{0}^{𝔄}, a^{(0)}) and d(0_{0}^{𝔅}, f(a^{(0)})) is ≤ 2, it is easy to verify that they are equal.

• If a^{(1)} ∈ Dom(f), it is easy to verify that a^{(1)} = 0_{1}^{𝔄} if and only if f(a^{(1)}) = 0_{1}^{𝔅} : Assume for example that a^{(1)} = 0_{1}^{𝔄} and d(0_{1}^{𝔅}, f(a^{(1)}) ≠ 0. We have two cases: If 0_{1}^{𝔅} < f(0_{1}^{𝔄}), then for b ∈ B - the predecessor of f(0_{1}^{𝔄}), there exists a ∈ A, such that f ∪ {(a, b)} ∈ LI_{1}(𝔄, 𝔅) and therefore a < 0_{1}^{𝔄}. Then for S_{a} ∈ A - the successor of a, that is between a and 0_{1}^{𝔄}, there exists c ∈ B, such that f ∪ {(a, b)} ∪ {(S_{a}, c)} ∈ LI_{0}(𝔄, 𝔅) and therefore c is between b and its successor f(0_{1}^{𝔄}), which is a contradiction. In the case f(0_{1}^{𝔄}) < 0_{1}^{𝔅} we take the predecessor of f(0_{1}^{𝔄}). In the other direction the proof is similar.

(⇐) The local isomorphism f preserves the distances for p = 2. We can prove f ∈ LI_{2}(𝔄, 𝔅). using the fact that f ∈ LI_{1}(𝔄, 𝔅) if and only if both ∀n ≤ 1 (d(a_{i}, a_{j}) = n ⇔ d(f(a_{i}), f(a_{j})) = n) and f(a) = 0_{0}^{𝔅} ⇔ a = 0_{0}^{𝔄}, where a_{i}, a_{j}, a ∈ Dom(f). The interesting case is when we choose a ∈ A, such that 0_{0}^{𝔄} < a < a^{(0)} and d(a, a^{(0)}) > 1. Then we have to find b ∈ B, such that 0_{0}^{𝔅} < b and d(b, f(a^{(0)}) > 1. This is possible, because otherwise d(0_{0}^{𝔅}, f(a^{(0)})) ≤ 2, which is a contradiction, since d(0_{0}^{𝔄}, a^{(0)}) > 2.

IH - assume it is true for some p ≥ 2. We have to prove it for p + 1.

(⇒) Let f ∈ LI_{p+1}(𝔄, 𝔅).

1. Suppose d(a_{i}, a_{j}) = n ≤ 2^{p} for some a_{i}, a_{j} ∈ Dom(f) and n > 0, the case n = 0 is easy.

Take an element c of A, such that d(a_{i}, c) = [\frac{n}{2}]. Then d(c, a_{j}) =

[\frac{n − 1}{2}] + 1. There exists e ∈ B, such that f ∪ \{(c, e)\} ∈ LI_{p}(𝔄, 𝔅).

Therefore f(a_{i}) ≤ e ≤ f(a_{j}). Since [\frac{n}{2}] ≤ 2^{(p−1)} and [\frac{n − 1}{2}] + 1 ≤

2^{(p−1)}+1, from the IH it follows that d(f(a_{i}), e) = d(a_{i}, c) and d(e, f(a_{j})) = d(c, a_{j}) and therefore d(f(a_{i}), f(a_{j})) = d(f(a_{i}), e) + d(e, f(a_{j})) = n. In the other direction the proof is similar.

2. Suppose a^{(0)} ∈ Dom(f) and d(0_{0}^{𝔄}, a^{(0)}) ≤ 2^{(p+1)−1} + (p + 1) − 2 = 2^{p} + p − 1. We have two subcases:

• d(0_{0}^{𝔄}, a^{(0)}) < 2^{p} + p − 1. Now we can choose c ∈ A, such that d(c, a^{(0)}) ≤ 2^{(p−1)} and d(0_{0}^{𝔄}, c) ≤ 2^{(p−1)} +p−2. There exists e ∈ B, such that f ∪{(c, e)} ∈ LI_{p}(𝔄, 𝔅). From IH it follows that d(0_{0}^{𝔄}, c) = d(0_{0}^{𝔅}, e) and d(c, a^{(0)}) = d(e, f(a^{(0)})) and therefore d(0_{0}^{𝔄}, a^{(0)}) = d(0_{0}^{𝔅}, f(a^{(0)})).

• d(0_{0}^{𝔄}, a^{(0)}) = 2^{p} + p − 1. Assume that d(0_{0}^{𝔄}, a^{(0)}) ≠ d(0_{0}^{𝔅}, f(a^{(0)})). Then d(0_{0}^{𝔅}, f(a^{(0)})) > 2^{p} + p − 1. Now we can choose e ∈ B, such that d(0_{0}^{𝔅}, e) > 2^{(p−1)} + p − 2 and d(e, f(a^{(0)})) > 2^{(p−1)}. But there exists c ∈ A, such that f ∪ {(c, e)} ∈ LI_{p}(𝔄, 𝔅) and from IH it follows that d(0_{0}^{𝔄}, c) > 2^{(p−1)} + p − 2 and d(c, a^{(0)}) > 2^{(p−1)}. Then d(0_{0}^{𝔄}, (a^{(0)}) > 2^{p} + p − 1, which is a contradiction.

3. Suppose a^{(1)} ∈ Dom(f) and d(0_{1}^{𝔄}, a^{(1)}) ≤ 2^{(p+1)−1} + (p + 1) − 4 = 2^{p} + p − 3. The proof is similar.

(⇐) Suppose that for the local isomorphism f the distance conditions for p + 1 hold. From IH it follows that f ∈ LI_{p}(𝔄, 𝔅). We have to prove that f ∈ LI_{p+1}(𝔄, 𝔅). Take for example a ∈ A. We have the following cases:

• a ∈ Dom(f).

Therefore there exists b ∈ B, b = f(a), such that f ∪ {(a, b)} = f ∈ LI_{p}(𝔄, 𝔅).

• a′ < a < a′′, for some a′, a′′ ∈ Dom(f), s.t. between them there are no elements from Dom(f).

– d(a′, a) ≤ 2^{(p−1)} and d(a, a′) ≤ 2^{(p−1)}.

Then d(a′, a′′) ≤ 2^{p} and we can choose b ∈ B, such that d(f(a′), b) = d(a′, a) and d(b, f(a′′)) = d(a, a′′). From IH it follows that f ∈ LI_{p+1}(𝔄, 𝔅).

– d(a′, a) ≤ 2^{(p−1)} and d(a, a′′) > 2^{(p−1)}.

We can choose b ∈ B, such that d(f(a′), b) = d(a′, a). If d(b, f(a′′)) ≤ 2^{(p−1)}, then d(f(a′), f(a′′)) ≤ 2^{p}, which is a contradiction.

– d(a′, a) > 2^{(p−1)} and d(a, a′′) ≤ 2^{(p−1)}.

This case is similar to the previous, except that it is possible a′ ≤ 0_{1}^{𝔄} ≤ a. Then d(0_{1}^{𝔅}) ≥ 2^{(p−1)} and we can choose b ∈ B, such that d(b, f(a′′)) = d(a, a′′). If d(0_{1}^{𝔄}, a) ≤ 2^{(p−1)} + p − 4, then d(0_{1}^{𝔄}, a′′) ≤ 2^{p} + p − 4 < 2^{p} + p − 3 and therefore (IH) d(0_{1}^{𝔄}, a′′) = d(0_{1}^{𝔅}, f(a′′)), then d(0_{1}^{𝔄}, a) = d(0_{1}^{𝔄}, b) and f ∈ LI_{p+1}(𝔄, 𝔅).

– d(a′, a) > 2^{(p−1)} and d(a, a′′) > 2^{(p−1)}. Analogous.

• 0_{0}^{𝔄} < a < a^{(0)}. Analogous.

• max{a_{i} | a_{i} ∈ Dom(f)} < a. This case is easy.

Notation: By (ω · 2, <′) we denote the structure (ℕ, <) ⊕ (ℕ, <) with domain ω · 2 = ℕ ∪ {x′ | x ∈ ℕ} and the following relation: for all x, y ∈ ℕ, such that x < y,

x <′ y and x′ <′ y′ and x <′ x′.

Theorem: (ℕ, <) ⊕ (ℕ, <) is a prime model of φ.

Proof: Let 𝔄 = (A, <_{A}) be a model of φ. Define a function f from ω · 2 to A, as follows: f(0) := 0_{0}^{𝔄}, f(0′) := 0_{1}^{𝔄} and for each x > 0 in ℕ, f(x + 1) := the <_{A}-successor of f(x) and f((x + 1)′) := the <_{A}-successor of f(x′). From the Lemma it follows that every finite subset of f belongs to every LI_{p}((ω·2, <′ ), 𝔄), and therefore f is an elementary embedding from (N, <′) into 𝔄.

□

From the last theorem it follows that for every model 𝔄 of φ, for every sentence ψ, if (ℕ, <)⊕(ℕ, <) ⊧ ψ then 𝔄 ⊧ ψ, and therefore φ is an axiom for the structure (ℕ, <) ⊕ (ℕ, <).

2 Finite structures 𝔄_{m} = ({0, …, m − 1}, <)

Consider structures 𝔄_{m} = (A_{m}, <), where A_{m} = {0, …, m − 1}. We want to prove that for all m, n ≥ 1 and for all p ≥ 0,

𝔄_{m} ≡_{p} 𝔄_{n} if and only if ((m = n) or (m ≠ n and 2^{p} − 2 < min(m, n) )).

Proof: (⇒) We want to prove that if m < n and 2^{p} − 2 ≥ m, then 𝔄_{m} ≢_{p} 𝔄_{n}, finding sentence φ_{m}, with QD(φ_{m}) ≤ p and such that 𝔄_{n} ⊧ φ_{m}, but 𝔄_{m} |̸= φ_{m}.

We can easily define sentences DiffEl_{m}, such that 𝔄_{m} ⊧ ¬DiffEl_{m} and 𝔄_{n} ⊧ DiffEl_{m} for all n > m, (DiffEl_{m} says ’there exist at least m + 1 different elements in the structure’):

| \begin{matrix}DiffEl_{0} ≡ ∃x_{0}(x_{0} = x_{0}) \\ DiffEl_{m+1} ≡ ∃x_{0} … ∃x_{m+1}(x_{0} ⊏ x_{1} ∧ x_{1} ⊏ x_{2} ∧ … ∧ x_{m} ⊏ x_{m+1}), \end{matrix}

but QD(DiffEl_{m}) = m + 1. It suffices to find sentences φ_{m}, such that:

(a) QD(φ_{m}) = μp[2^{p} − 2 ≥ m]; and (b) 𝔄_{n} ⊧ φ_{m} ↔ DiffEl_{m}, for all n.

Now define φ_{m} by induction on m as follows: φ_{0} ≡ ψ_{0} ≡ ∃x_{0}(x_{0} = x_{0}) and φ_{1} ≡ ψ_{1} ≡ ∃x_{0}∃x_{1}(x_{0} ⊏ x_{1}), and for m ≥ 0,

φ_{m+2} ≡ ∃x(φ_{[ \frac{m}{2} ]}^{⊏x}(x) ∧ φ_{[ \frac{m+1}{2} ]}^{⊏x}(x)), i.e.

| \begin{matrix}φ_{2k+2} ≡ ∃x(φ_{k}^{⊏x}(x) ∧ φ_{k}^{x⊏}(x)) \\ φ_{2k+3} ≡ ∃x(φ_{k}^{⊏x}(x) ∧ φ_{k+1}^{x⊏}(x)) \end{matrix}

It is easy to check (b), i.e. 𝔄_{n} ⊧ φ_{m} ↔ DiffEl_{m}, for all n. We prove (a), i.e. QD(φ_{m}) = μp[2^{p} − 2 ≥ m], by induction on m :

• for m = 0 and m = 1, QD(φ_{0}) = 1 = μp[2^{p} − 2 ≥ 0] and QD(φ_{1}) = 2 = μp[2^{p} − 2 ≥ 1].

• IH for smaller than m ≥ 2.

Remark:

QD(φ_{m}) ≤ QD(φ_{m+1}).

1. m = 2k + 2. Let p := QD(φ_{2k+2}) and q := QD(φ_{k}). Then p = q + 1. From IH it follows that 2^{q} − 2 ≥ k and therefore 2^{q} ≥ k + 2, then 2^{p} = 2^{q+1} ≥ 2k + 2 + 2 = m + 2, i.e. 2^{p} ≥ m + 2. It remains to prove that p is the least, i.e. p = μt[2^{t} − 2 ≥ m]. Assume there is smaller p′ s.t. 2^{p′} ≥ m + 2. Then p′ ≤ q and therefore 2^{q} ≥ m + 2 = 2k + 4, then 2^{q−1} − 2 ≥ k, but from IH (for k < m) q is the least such that 2^{q} − 2 ≥ k, contradiction.

2. m = 2k + 3. Let p := QD(φ_{2k+3}) and q := QD(φ_{k+1}). Then p = q + 1. From IH it follows that 2^{q} − 2 ≥ k + 1, i.e 2^{q} ≥ k + 3, then 2^{p} = 2^{q+1} ≥ 2k + 6 = m + 3, then 2^{p} ≥ m + 2. Assume there is smaller p′ s.t. 2^{p′} ≥ m + 2. Again p′ ≤ q and therefore 2^{q} ≥ m + 2 = 2k + 5, then 2^{q} ≥ 2k + 6, then 2^{q−1} ≥ k + 3, i.e. 2^{q−1} − 2 ≥ k + 1, but from IH (for k + 1 < m) it follows that q is the least with this property, which is a contradiction.

Therefore if m ≠ n and 2^{p} − 2 ≥ min(m, n) then 𝔄_{m} ≢_{p} 𝔄_{n}.

(⇐) We want to prove that if m < n and 2^{p} ≤ 1 + m, then 𝔄_{m} ≡_{p} 𝔄_{n}, which is equivalent to ∅ ∈ LI_{p}(𝔄_{m}, 𝔄_{n}). By induction on m ≥ 1.

• m = 1.

Since 2^{p} ≤ 2, 0 ≤ p ≤ 1 and then 𝔄_{1} ≡_{p} 𝔄_{n}, for n > 1.

• m > 1. IH for smaller than m.

We have to prove that:

– for all a ∈ A_{m} there is b ∈ A_{n}, such that {(a, b)} ∈ LI_{p−1}(𝔄_{m}, 𝔄_{n});

– for all b ∈ A_{n} there is a ∈ A_{m}, such that {(a, b)} ∈ LI_{p−1}(𝔄_{m}, 𝔄_{n}).

For the first we consider different cases for a :

1. for 0 ≤ a ≤ \frac{m − 1}{2}, take b = a.

{(a, a)} ∈ LI_{p−1}(𝔄_{m}, 𝔄_{n}) if and only if ∅ ∈ LI_{p−1}(𝔄_{m−a−1}, 𝔄_{n−a−1}), which follows from 2^{p−1} ≤ m − a, (from IH for m − a − 1 < m). Assume 2^{p−1} > m − a.

Since 2^{p} ≤ m + 1, 2^{p−1} ≤ \frac{m + 1}{2} = \frac{m}{2} + \frac{1}{2}. Then \frac{m + 1}{a} > m − a.

Therefore m + 1 > 2m − 2a, then 2a > m − 1, then a > \frac{m − 1}{2}, which is a contradiction.

2. for \frac{m − 1}{2} ≤ a ≤ m − 1, take b = a + n − m,

i.e. such that the distances d(a, m − 1) = d(b, n − 1), b ∈ A_{n}, since 0 ≤ a + n − m ≤ n − 1. Again {(a, b)} ∈ LI_{p−1}(𝔄_{m}, 𝔄_{n}) if and only if ∅ ∈ LI_{p−1}(𝔄_{a}, 𝔄_{b}), which follows from 2^{p−1} ≤ a + 1, (from IH for a < m).

Assume 2^{p−1} > a + 1, then 2^{p} > 2a + 2. Since a ≥ \frac{m − 1}{2}, 2a ≥ m − 1. Therefore 2^{p} > m − 1 + 2 = m + 1, which is a contradiction.

In order to prove the second, we consider cases for b :

1. for 0 ≤ b ≤ \frac{m − 1}{2}, take a = b.

The proof is the same as in the case for a.

2. for n − 1 − \frac{m − 1}{2} ≤ b ≤ n − 1, take a = b + m − n,

i.e. such that d(a, m − 1) = d(b, n − 1). Then \frac{m − 1}{2} ≤ a ≤ m − 1 and the proof is the same as in the case for a.

3. for \frac{m − 1}{2} < b < n − 1 − \frac{m − 1}{2}, take a = [\frac{m − 1}{2}] ∈ A_{m}. Then

m − 2 ≤ 2a ≤ m − 1, a < b and m − a − 1 ≤ n − b − 1, m ≤ 2b ≤ 2n − m − 1. Therefore {(a, b)} ∈ LI_{p−1}(𝔄_{m}, 𝔄_{n}) if and only if

∅ ∈ LI_{p−1}(𝔄_{a}, 𝔄_{b}) and ∅ ∈ LI_{p−1}(𝔄_{m−a−1}, 𝔄_{n−b−1}),

which follows from (2^{p−1} ≤ a + 1 and 2^{p−1} ≤ m − a), since IH for a + 1 < m and IH for m − a − 1 < m. Assume 2^{p−1} > a + 1. Then 2^{p} > 2a + 2 >= m. But 2^{p} ≤ m + 1, then m + 1 ≥ 2^{p} > m.

Then 2^{p} = m + 1 and [\frac{m − 1}{2}] = \frac{m − 1}{2}, then 2a = m − 1, therefore

2^{p} > 2a + 2 = m + 1, which is a contradiction. Assume 2^{p−1} > m − 1. Then 2^{p} > 2m − 2a ≥ 2m − m + 1 = m + 1, i.e. 2^{p} > m + 1, but 2^{p} ≤ m + 1, which is a contradiction. Therefore (2^{p−1} ≤ a + 1 and 2^{p−1} ≤ m − a).

□

3 The order types 𝔅_{m} = (ω · m, <)

Consider structures 𝔅_{m} = (B_{m}, <) with m ≥ 1 and B_{m} = ω · m = {k_{i} | k ∈ ℕ & 0 ≤ i ≤ m − 1} and k_{i} < l_{j} ⇔ (i < j or i = j & k < l). We want to prove that for all m, n ≥ 1 and for all p ≥ 0,

𝔅_{m} ≡_{p} 𝔅_{n} if and only if ((m = n) or (m ≠ n and 2^{p−2} ≤ min(m, n) )).

Proof: (⇒) We want to prove that if m < n and 2^{p−2} > m, then 𝔅_{m} ≢_{p} 𝔅_{n}, finding sentence ψ_{m}, with QD(ψ_{m}) ≤ p and such that 𝔅_{n} ⊧ ψ_{m}, but 𝔅_{m} |̸= φ_{m}. Define a formula W ip(x) with QD(W ip) = 2, which says that the element x does not have immediate predecessor, but has a predecessor, as follows:

W ip(x) ≡ ∃y(y ⊏ x) ∧ ∀y(y ⊏ x → ∃z(y ⊏ z ∧ z ⊏ x)).

Again we can define sentences DiffW ipEl_{m}, for m ≥ 1, such that 𝔅_{m} ⊧ ¬DiffW ipEl_{m} and 𝔅_{n} ⊧ DiffW ipEl_{m} for all n > m, (DiffW ipEl_{m} says ”there exist at least m different W ip-elements”):

DiffW ipEl_{m} ≡ ∃x_{0} … ∃x_{m−1}(W ip(x_{0}) ∧ … ∧ W ip(x_{m−1}) ∧ x_{0} ⊏ … ⊏ x_{m−1}).

QD(DiffW ipEl_{m}) = m+2. It suffices to find sentences ψ_{m}, such that (a) QD(ψ_{m}) = μp[2^{p−2} − 1 ≥ m] and (b) 𝔅_{n} ⊧ ψ_{m} ↔ DiffW ipEl_{m}, for all n.

We define ψ_{m} by induction on m ≥ 1,

| \begin{matrix}ψ_{1} ≡ ∃x_{0}W ip(x_{0}), & QD(ψ_{1}) = 3 \\ ψ_{2} ≡ ∃x_{0}∃x_{1}(x_{0} ⊏ x_{1} ∧ W ip(x_{0}) ∧ W ip(x_{1})), & QD(ψ_{2}) = 4. \end{matrix}

for m > 1, φ_{m+1} ≡ ∃(W ip(x) ∧ ψ_{[ \frac{m}{2} ]}^{⊏x} ∧ ψ_{[ \frac{m+1}{2} ]}^{⊏x}), i.e.

| \begin{matrix}ψ_{2k+1} ≡ ∃x(W ip(x) ∧ ψ_{k}^{⊏x}(x) ∧ ψ_{k}^{x⊏}(x)) \\ ψ_{2k+2} ≡ ∃x(W ip(x) ∧ ψ_{k}^{⊏x}(x) ∧ ψ_{k+1}^{x⊏}(x)) \end{matrix} for k ≥ 1.

It is easy to check (b), i.e. 𝔅_{n} ⊧ ψ_{m} ↔ DiffW ipEl_{m}, for all n. We prove (a), i.e. QD(ψ_{m}) = μp[2^{p−2} − 1 ≥ m], by induction on m :

• m = 1 μp[2^{p−2} − 1 ≥ 1] = μp[2^{p−2} ≥ 2] = μp[p − 2 ≥ 1] = 3 = QD(ψ_{1}).

• m = 2 μp[2^{p−2} − 1 ≥ 2] = μp[2^{p−2} ≥ 3] = μp[p − 2 ≥ 2] = 4 = QD(ψ_{2}).

• m > 2. IH for smaller than m.

Since the function f(p) = μp[2^{p−2} ≥ m] is monotone, we have:

1. m = 2k + 1, for k ≥ 1.

QD(ψ_{2k+1}) = 1 + QD(ψ_{k}) =^{IH} 1 + μq[2^{q−2} − 1 ≥ k] = 1 + μq[2^{q−2} ≥

k + 1] = μp[2^{p−3} ≥ k + 1] = μp[2^{p−2} ≥ 2k + 2] = μp[2^{p−2} > 2k + 1] = μp[2^{p−2} ≥ 2k + 1].

2. m = 2k + 2, for k ≥ 1.

QD(ψ_{2k+2}) = 1+QD(ψ_{k+1}) =^{IH} 1+μq[2^{q−2} −1 ≥ k +1] = 1+μq[2^{q−2} ≥

k + 2] = μp[2^{p−3} ≥ k + 2] = μp[2^{p−2} ≥ 2k + 4] = μp[2^{p−2} > 2k + 3] = μp[2^{p−2} ≥ 2k + 3] = μp[2^{p−2} ≥ m + 1].

Therefore if n ≠ m and 2^{p−2} > m, then 𝔅_{m} ≢_{p} 𝔅_{n}.

(⇐) We want to prove that if m < n and 2^{p−2} ≤ m, then 𝔅_{m} ≡_{p} 𝔅_{n}, which is equivalent to ∅ ∈ LI_{p}(𝔅_{m}, 𝔅_{n}). By induction on m ≥ 1.

• m = 1.

Since 2^{p−2} ≤ 1, 0 ≤ p ≤ 2 and then 𝔅_{1} ≡_{p} 𝔅_{n}, for n > 1.

• m > 1. IH for smaller than m. Let 2^{p−2} ≤ m. We have to prove that:

– for all a ∈ ω · m there is b ∈ ω · n, such that {(a, b)} ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n});

– for all b ∈ ω · m there is a ∈ ω · n, such that {(a, b)} ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n}).

First we prove that for the wip-elements, 0_{i}^{𝔅_{m}} and 0_{j}^{𝔅_{n}}, with 0 < i ≤ m − 1 and 0 < j ≤ n − 1, i.e. those elements for which 𝔅_{m} ⊧ W ip[0_{i}^{𝔅_{m}}]. Using that, the winning strategy for the second player in p moves, for the other elements of ω · m and ω · n can be expressed, since: {(0_{0}^{𝔅_{m}}, 0_{0}^{𝔅_{n}})} ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n}) if and only if ∅ ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n}); And for a ∈ 𝔅_{m}, such that 0_{i}^{𝔅_{m}} ≤ a < 0_{i+1}^{𝔅_{m}} and b ∈ 𝔅_{n}, such that 0_{j}^{𝔅_{n}} ≤ a < 0_{j+1}^{𝔅_{n}} and d(0_{i}^{𝔅_{m}}, a) = d(0_{j}^{𝔅_{n}}, b), {(a, b)} ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n}) if and only if {(0_{i}^{𝔅_{m}}, 0_{j}^{𝔅_{n}})} ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n}).

So first we consider different cases for a = 0_{i}^{𝔅_{m}} ∈ 𝔅_{m}, for which we take b = 0_{j}^{𝔅_{n}} ∈ 𝔅_{n}, as follows:

1. For 1 ≤ i ≤ [\frac{m − 1}{2}] , take j = i. We have 1 ≤ 2i ≤ m − 1 and b = 0_{i}^{𝔅_{n}}.

Therefore {(a, b)} ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n}) if and only if ∅ ∈ LI_{p−1}(𝔅_{m−i}, 𝔅_{n−i}), which follows from 2^{p−3} ≤ m − i, since IH for m − i < m.

Assume 2^{p−3} > m − i, i.e. m − i + 1 ≤ 2^{p−3} ≤ \frac{m}{2}, then 2m − 2i + 2 ≤ m,

then m + 2 ≤ 2i ≤ m − 1, which is a contradiction.

2. For [\frac{m − 1}{2}] < i ≤ m − 1, take j = n − m + i.

We have m ≤ 2i and b = 0_{n−m+i}^{𝔅_{n}}. Therefore {(a, b)} ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n}) if and only if ∅ ∈ LI_{p−1}(𝔅_{i}, 𝔅_{j}), which follows from 2^{p−3} ≤ i, since IH for i < m. Assume 2^{p−3} > i, i.e. i + 1 ≤ 2^{p−3}, but 2^{p−2} ≤ m. Then 2i + 2 ≤ 2^{p−2} ≤ m, i.e. m + 2 ≤ m, contradiction.

Now consider cases for b = 0_{j}^{𝔅_{n}} ∈ 𝔅_{n}, for which we take a = 0_{i}^{𝔅_{m}} ∈ 𝔅_{m}, as follows (the proof for the first two cases is the same):

1. For 1 ≤ j ≤ [\frac{m − 1}{2}] , take i = j.

2. For [\frac{m − 1}{2}] + n − m < j ≤ n − 1, take i = j − n + m.

3. For [\frac{m − 1}{2}] + 1 ≤ j ≤ n − m + [\frac{m − 1}{2}] , take i = [\frac{m − 1}{2}] + 1.

Then we have m + 1 ≤ 2j ≤ 2n − m − 2 and m ≤ 2i ≤ m + 1. {(a, b)} ∈ LI_{p−1}(𝔅_{m}, 𝔅_{n}) if and only if

(∅ ∈ LI_{p−1}(𝔅_{i}, 𝔅_{j}) and ∅ ∈ LI_{p−1}(𝔅_{m−i}, 𝔅_{n−j})).

Since j < n − m + [\frac{m − 1}{2}] + 1, j < n + i − m. Then m − i < n − j. We

have i ≤ j. It suffices to prove (2^{p−3} ≤ i and 2^{p−3} ≤ m − i), since from IH for i < m and m − i < m it will follow that ∅ ∈ LI_{p−1}(𝔅_{m−i}, 𝔅_{n−j}). Assume 2^{p−3} > i, then 2^{p−2} ≥ 2i + 2 ≥ m + 2, but 2^{p−2} ≤ m, then m ≥ m + 2, contradiction. Assume 2^{p−3} > m − i. Then 2^{p−2} ≥ 2m − 2i + 2 ≥ m + 1. But 2^{p−2} ≤ m, then m ≥ m + 1, contradiction.

□

4 The order types ℭ_{m,q} = (ω · m + q, <)

Consider structures ℭ_{m,q} = (C_{m,q}, <), where for m ≥ 1 and q ≥ 0, C_{m,q} = ω · m + q, and ω · m + q = (ω · m) ∪ {ω · m, ω · m + 1, … ω · m + (q − 1)}. The elements of a structure ℭ_{m,q} will be denoted k_{i}^{ℭ_{m,q}} for k_{i}^{ℭ_{m,q}} ∈ ω · m, i.e. 0 ≤ i ≤ m − 1, and k^{ℭ_{m,q}} for ω · m + k. Therefore k_{i}^{ℭ_{m,q}} < l_{j}^{ℭ_{m,q}} ⇔ (i < j or i = j & k < l), and k_{i}^{ℭ_{m,q}} < k^{ℭ_{m,q}}, for all k^{ℭ_{m,q}} and all k_{i}^{ℭ_{m,q}} ∈ ω · m.

Having two structures ℭ_{m,q} and ℭ_{n,r}, we want to find for which p, ℭ_{m,q} ≡_{p} ℭ_{n,r}.

4.1. First consider the case m = n and q < r. We want to prove

ℭ_{m,q} ≡_{p} ℭ_{m,r} ⇔ (q = 0 and p ≤ 1) or (q > 0 and 2^{p} < q + 5).

Proof: (⇒) We will need the following formulas:

Gst(x) ≡ ∀y(y = x ∨ y ⊏ x), ”x is the greatest element”; QD(Gst) = 1.

W ip^{∗}(x) ≡ ∀y(y ⊏ x → ∃z(y ⊏ z ⊏ x)), ”x has no immediate predecessor”; QD(W ip^{∗}) = 2.

T ail(x) ≡ ∀y(x ⊑ y → ¬W ip^{∗}(y)), ”all the elements greater than or equal to x have immediate predecessor”; QD(T ail) = 3.

DiffEl_{q}, defined in Section 2, ”there are at least q + 1 different elements”; we have defined formulas φ_{q}, such that 𝔄_{t} ⊧ φ_{q} ↔ DiffEl_{q}, for all t, and QD(φ_{q}) = μp[2^{p} ≥ q + 2]. But still ℭ_{s,t} ⊧ φ_{q} ↔ DiffEl_{q}, for all s and t, so here we may assume that

QD(DiffEl_{q}) = μp[2^{p} ≥ q + 2].

We define formulas Ψ_{q} by induction on q as follows:

|||||||| Ψ_{0} ≡ ∃xGst(x),  QD(Ψ_{0}) = 2,

Ψ_{q} ≡ ∀x(W ip^{∗}(x) → DiffEl_{q−1}^{x⊏}(x)),  for 1 ≤ q ≤ 3, QD(Ψ_{q}) = 3,
Ψ_{q} ≡ ∃x(Ψ_{[ \frac{q}{2} ]−2}^{⊏x}(x) ∧ DiffEl_{[ \frac{q+1}{2} ]}^{x⊏}(x) ∧ T ail(x)), for q > 3.

For these formulas we can prove the following properties:

(i) QD(Ψ_{q}) = μp[2^{p} ≥ q + 5], for q > 0.

(ii) ℭ_{m,q} |̸= Ψ_{q}, but for all s and all t > q, ℭ_{s,t} ⊧ Ψ_{q}.

(i) The proof is by induction on q, using [\frac{q}{2}] + [\frac{q+1}{2}] = q.

• 1 ≤ q ≤ 3; QD(Ψ_{q}) = 3 and μp[2^{p} ≥ q + 5] = 3 for 1 ≤ q ≤ 3;

• q > 3; IH for t < q, i.e. for all t, such that 0 < t < q, QD(Ψ_{t}) = μp[2^{p} ≥ t + 5]. Therefore QD(Ψ_{q}) = 1 + max\{QD(Ψ_{[ \frac{q}{2} ]−2}), QD(DiffEl_{[ \frac{q+1}{2} ]}), QD(T ail)\}. For q > 3, 0 ≤ [\frac{q}{2}] − 2 < q. Therefore (for q = 4 we cannot apply the IH, but the following equalities are still valid)

QD(Ψ_{q}) = 1 + max\{μp[2^{p} ≥ [\frac{q}{2}] + 3], μp[2^{p} ≥ [\frac{q+1}{2}] + 2], 3\} = = 1 + μp[2^{p} ≥ [\frac{q}{2}] + 3] = μp[2^{p−1} ≥ [\frac{q}{2}] + 3] =

= μp[2^{p} ≥ 2 · [\frac{q}{2}] + 6] = μp[2^{p} ≥ 2[\frac{q}{2}] + 5] =
= μp[2^{p} ≥ q + 5].

(ii) The proof is by induction on q.

(⇐) The case q = 0 and p ≤ 1 is easy to check. If q > 0 and 2^{p} ≤ q + 4 we have to prove that ∅ ∈ LI_{p}(ℭ_{m,q}, ℭ_{m,r}), i.e. there is a winning strategy for the second player for a game with p moves. The proof is by induction on q.

• q = 1, Therefore p ≤ 2. It is easy to check that ∅ ∈ LI_{p}(ℭ_{m,q}, ℭ_{m,r}).

• q > 1, IH for t < q, i.e. for all t, such that 0 < t < q, if 2^{p} < t + 5, then ∅ ∈ LI_{p}(ℭ_{m,t}, ℭ_{n,r}), where m = n and t < r. Let 2^{p} ≤ q + 4. We shall prove

(a) ∀a ∈ C_{m,q}∃b ∈ C_{m,r} s.t. {(a, b)} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}); and

(b) ∀b ∈ C_{m,r}∃a ∈ C_{m,q} s.t. {(a, b)} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}).

The cases a = k_{i}^{ℭ_{m,q}} where 0 ≤ i ≤ m − 1, and b = k_{i}^{ℭ_{m,r}} where 0 ≤ i ≤ m − 1 for (a) and (b) resp. (the first player chooses element from the part ω · m and the second player answers with the same element from the other structure) are trivial, since {(k_{i}^{ℭ_{m,q}}, k_{i}^{ℭ_{m,q}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}) if and only if ∅ ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}).

Consider the case when the first player chooses element ω ·m+i from the tail, i.e. an element a from the set {0^{ℭ_{m,q}} … (q − 1)^{ℭ_{m,q}}} or b from {0^{ℭ_{m,r}} … (r − 1)^{ℭ_{m,r}}}.

– For a = k^{ℭ_{m,q}} such that 0 ≤ k ≤ [\frac{q}{2}] − 2, take b = k^{ℭ_{m,r}} ∈ C_{m,r}.

Then we have {(a, b)} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}) if and only if

{(k^{ℭ_{m,q}}, k^{ℭ_{m,r}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}) iff ∅ ∈ LI_{p−1}(𝔄_{q−k−1}, 𝔄_{r−k−1}), where 𝔄_{l} denote the finite structures ({0, …, l − 1}, <), defined in Section 2. We have proved that ∅ ∈ LI_{p−1}(𝔄_{q−k−1}, 𝔄_{r−k−1}) iff 2^{p−1} ≤ 1 + (q − k − 1), i.e. iff 2^{p−1} ≤ q − k. Since 0 ≤ k ≤ [\frac{q}{2}] − 2 and 2^{p} ≤ q + 4, we have 2k ≤ q − 4, then 2q − 2k ≥ q + 4 ≥ 2^{p}, therefore 2^{p−1} ≤ q − k.

For b = l^{ℭ_{m,r}}, such that 0 ≤ l ≤ [\frac{q}{2}] − 2, take a = l^{ℭ_{m,q}}, and we have proved {(l^{ℭ_{m,q}}, l^{ℭ_{m,r}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}).

– In the cases where the distance between the chosen element and the end of the structure (the greatest element) is less than or equal to [\frac{q+1}{2}], the second player chooses and element having the same distance to the greatest element.

For a = k^{ℭ_{m,q}}, such that [\frac{q}{2}] − 1 ≤ k ≤ q − 1, take b = l^{ℭ_{m,q}}, such that l = r − q + k. Therefore {(a, b)} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}) if and only if {(k^{ℭ_{m,q}}, l^{ℭ_{m,r}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}) if and only if (∅ ∈ LI_{p−1}(ℭ_{m,k}, ℭ_{m,l}) and ∅ ∈ LI_{p−1}(𝔄_{q−k−1}, 𝔄_{r−l−1})) iff ∅ ∈ LI_{p−1}(ℭ_{m,k}, ℭ_{m,l}), since q − k − 1 = r − l − 1. Since [\frac{q}{2}] − 1 ≤ k ≤ q − 1 and 2^{p} ≤ q + 4, we have 2k ≥ q − 3, i.e. 2[\frac{q}{2}] ≥ q − 1, then 2^{p} ≤ q + 4 ≤ 2k + 7, i.e. 2^{p} ≤ 2k + 6, then 2^{p−1} ≤ k + 3 < k + 4. Then from the IH it follows that ∅ ∈ LI_{p−1}(ℭ_{m,k}, ℭ_{m,l}).

For b = l^{ℭ_{m,r}}, such that r − [\frac{q+1}{2}] − 1 ≤ l ≤ r − 1, take a = k^{ℭ_{m,q}}, where k = l − r + q. Therefore [\frac{q}{2}] − 1 ≤ k ≤ q − 1, and we have already proved that {(k^{ℭ_{m,q}}, l^{ℭ_{m,r}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}).

– For b = l^{ℭ_{m,r}}, such that [\frac{q}{2}] − 1 ≤ l ≤ r − [\frac{q+1}{2}] − 2, take a = k^{ℭ_{m,q}}, where k = [\frac{q+1}{2}] − 2. Therefore {(a, b)} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}) if and only if {(k^{ℭ_{m,q}}, l^{ℭ_{m,r}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}) if and only if (∅ ∈ LI_{p−1}(ℭ_{m,k}, ℭ_{m,l}) and ∅ ∈ LI_{p−1}(𝔄_{q−k−1}, 𝔄_{r−l−1})) iff (2^{p−1} ≤ k +4 and 2^{p−1} ≤ q −k), by IH and the result in Section 2, since k < l and q − k − 1 < r − l − 1.

1) 2^{p−1} ≤ q − k = [\frac{q}{2}] + 2 if and only if 2^{p} ≤ 2[\frac{q}{2}] + 4 iff 2^{p} ≤ q + 4, the latter is our assumption.

2) Since 2^{p} ≤ q+4, we have 2^{p} ≤ 2[\frac{q+1}{2}]+4, therefore 2^{p−1} ≤ [\frac{q+1}{2}]+2 ≤ k + 4. Therefore {(a, b)} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,r}).

This is the end of the proof for the first case, where m = n and q < r.

□

4.2. Now consider the case m ≤ n and q = r. We want to prove

ℭ_{m,q} ≡_{p} ℭ_{n,q} ⇔ (2^{p−2} ≤ m + 1 & (q ≤ 3 ⇔ 2^{p−2} ≤ m)).

Proof:

(⇒) Let ℭ_{m,q} ≡_{p} ℭ_{n,q}, for m < n, and assume that m + 1 < 2^{p−2} and (m < 2^{p−1} if q ≤ 3). In order to get a contradiction we need to find formulas Φ_{m,q}, such that QD(Φ_{m,q}) ≤ p and ℭ_{m,q} |̸= Φ_{m,q}, but ℭ_{n,q} ⊧ Φ_{m,q}.

We have defined sentences DiffW ipEl_{m} (see Section 3), such that 𝔅_{n} ⊧ ψ_{m} ↔ DiffW ipEl_{m}, for all n, for some sentences ψ_{m} with QD(ψ_{m}) = μp[2^{p−2} ≥ m + 1]. But still ℭ_{s,q} ⊧ ψ_{m} ↔ DiffW ipEl_{m}, for all s ≥ 1, and we may assume that QD(DiffW ipEl_{m}) = μp[2^{p−2} ≥ m + 1].

Define DiffW ipEl_{m,q}^{∗} ≡ DiffW ipEl_{m+1}, ”there are at least m + 1 different W ipelements”. Therefore:

(a) QD(DiffW ipEl_{m,q}^{∗}) = μp[2^{p−2} ≥ m + 2]; and

(b) ℭ_{m,q} |̸= DiffW ipEl_{m,q}^{∗} and ℭ_{n,q} ⊧ DiffW ipEl_{m,q}^{∗}, since m < n.

In Section 2 we defined sentences DiffEl_{q} ”there are at least q + 1 different elements” and we may assume that QD(DiffEl_{q}) = μp[2^{p} ≥ q+2], since they are still equivalent to formulas with this quantifier depth in the structures ℭ_{s,q}, for all s ≥ 1 and q. Now define sentences χ_{m,q}, that are equivalent to ∃x_{0} … ∃x_{m−1}(W ip(x_{0}) ∧ … ∧ W ip(x_{m−1}) ∧ DiffEl_{q−1}^{x_{m−1}⊏}(x_{m−1})) in any ℭ_{s,t}, i.e. saying ”there are at least m different W ip-elements and at least q different elements after the last”, as follows:

χ_{m,0} ≡ DiffW ipEl_{m−1},
χ_{1,q} ≡ ∃x(W ip(x) ∧ DiffEl_{q−1}^{x⊏}(x_{0})), for q > 0,
χ_{m+1,q} ≡ ∃x(W ip(x) ∧ DiffW ipEl_{[ \frac{m}{2} ]}^{⊏x}(x) ∧ χ_{[ \frac{m+1}{2} ],q}^{x⊏}(x)), for q > 0,

where the formula W ip is defined in Section 3 and QD(W ip) = 2. Therefore

(c) QD(χ_{m,q}) = μp[2^{p−2} ≥ m + 1], for q ≤ 3; and

(d) ℭ_{m,q} |̸= χ_{m,q} and ℭ_{n,q} ⊧ χ_{m,q}, since m < n.

The property (c) can be proved by induction on m :

• m = 1, QD(χ_{1,q}) = 1 + max(2, μp[2^{p} ≥ q + 1]) = 3, for q ≤ 3.

• IH for m ≥ 1. Therefore QD(χ_{m+1,q}) = 1+max\{2, μp[2^{p−2} ≥ [\frac{m}{2}]+1], QD(χ_{[ \frac{m+1}{2} ],q})\} = 1+max(μp[2^{p−2} ≥ [\frac{m}{2}] + 1], μp[2^{p−2} ≥ [\frac{m+1}{2}] + 1]) = 1 + μp[2^{p−2} ≥ [\frac{m+1}{2}] + 1] = μp[2^{p−3} ≥ [\frac{m+1}{2}] + 1] = μp[2^{p−2} ≥], since 2^{p−2} ≥ 2[\frac{m+1}{2}] + 2 ⇔ 2^{p−2} ≥ m + 2.

Define Φ_{m,q} as follows: | \begin{matrix}Φ_{m,q} ≡ χ_{m,q}, & for q ≤ 3; \\ Φ_{m,q} ≡ DiffW ipEl_{m,q}^{∗}, & for q > 3. \end{matrix} Therefore for

q ≤ 3, QD(Φ_{m,q}) = μp[2^{p−2} ≥ m+1] and for q > 3, QD(Φ_{m,q}) = μp[2^{p−2} ≥ m+2], i.e.QD(Φ_{m,q} ≤ p, and ℭ_{m,q} |̸= Φ_{m,q}, but ℭ_{n,q} ⊧ Φ_{m,q}, which is a contradiction.

(⇒)Let 2^{p−2} ≤ m + 1 & (q ≤ 3 ⇔ 2^{p−2} ≤ m). We want to prove that ℭ_{m,q} ≡_{p} ℭ_{n,q}.

If 2^{p−2} ≤ m, then (see Section 3) for any q the second player has a winning strategy for a game with p moves (for the elements from the tail chooses the correspondent elements from the tail of the other structure, and for the elements from ω · m use the winning strategy, described in Section 3).

Therefore it suffices to consider the case 2^{p−2} = m+1 and q ≥ 4, using induction on m. We may assume that m = 2k + 1.

It is easy to verify the statement for m = 1, where p = 3. Let m > 1 and assume (IH) the claim is true for smaller than m. We have to

prove that for every a ∈ C_{m,q} there is b ∈ C_{n,q}, (and for every b ∈ C_{n,q} there is a ∈ C_{m,q}), such that {(a, b)} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{n,q}). Consider the cases for the W ip-elements (the others are analogous), i.e. the first player chooses an element a = 0_{i}^{ℭ_{m,q}} (or b = 0_{j}^{ℭ_{n,q}}), then the second player chooses an element b = 0_{j}^{ℭ_{n,q}} (resp. a = 0_{i}^{ℭ_{m,q}}), depending on i :

• 1 ≤ j ≤ [\frac{m−1}{2}] + 1, i.e. 1 ≤ j ≤ k + 1.

Take i = j. Therefore {(0_{i}^{ℭ_{m,q}}, 0_{i}^{ℭ_{n,q}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{n,q}) if and only if ∅ ∈ LI_{p−1}(ℭ_{m−i,q}, ℭ_{n−i,q}), which follows by the IH, if 2^{p−3} ≤ m − i + 1. Assume 2^{p−3} ≥ m − i + 2, then 2^{p−2} = m + 1 ≥ 2m − 2i + 4, then 2i ≥ m + 3, then [\frac{m−1}{2}] = k, therefore 2i ≥ 2k+4, but i ≤ [\frac{m−1}{2}]+1 = k+1, contradiction.

• n − [\frac{m}{2}] + 1 ≤ j ≤ n − 1, i.e. n − k + 1 ≤ j ≤ n − 1, then [\frac{m−1}{2}] ≤ i ≤ m − 1, i.e. k ≤ i ≤ 2k. Take i = m − n + j. Then {(0_{i}^{ℭ_{m,q}}, 0_{i}^{ℭ_{n,q}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{n,q}) if and only if ∅ ∈ LI_{p−1}(𝔅_{i}, 𝔅_{j}), iff 2^{p−3} ≤ i, since i < j (see Section 3). The case where the first player chooses [\frac{m−1}{2}] ≤ i ≤ m − 1, is the same if the second takes j = n − m + i.

• [\frac{m−1}{2} + 2 ≤ j ≤ n − [\frac{m}{2}]], i.e. k + 2 ≤ j ≤ n − k.

Take i = [𝔪 − 12]+1, i.e. i = k+1. Therefore {(0_{i}^{ℭ_{m,q}}, 0_{i}^{ℭ_{n,q}})} ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{n,q}) if and only if (left part) ∅ ∈ LI_{p−1}(𝔅_{i}, 𝔅_{j}) and (right part) ∅ ∈ LI_{p−1}(ℭ_{m,q}, ℭ_{m,q}) if and only if 2^{p−3} ≤ i and 2^{p−3} ≤ m − i + 1, which is easy to check: 2^{p−3} ≤ i iff 2^{p−3} ≤ k+1 iff 2k+2 = 2^{p−2} ≤ 2k+2; and 2^{p−3} ≤ m−i+1 = k+1 iff 2^{p−2} ≤ 2k + 2.

□

We have solved the problem ω · m + q ≡_{p} ω · n + r for the cases where q = r or m = n. It remains the case where m ≠ n and q ≠ r, which we do not consider here.

5 The order types 𝔑_{m} = (ω^{m}, <)

Consider structures 𝔑_{m} = (ω^{m}, <), where ω^{m} = {(x_{0}, …, x_{m−1}) | x_{0}, …, x_{m−1} ∈ ℕ}. We want to find for which p, (ω^{m}, < ) ≡_{p} (ω^{n}, <)?

Here we prove only that for m < n,

If (ω^{m}, <) ≡_{p} (ω^{n}, <) then p ≤ 2m.

Proof: Define formulas D_{m} by induction as follows:

| \begin{matrix}D_{0}(x) & ≡ x = x \\ D_{m+1}(x) & ≡ ∃y(y ⊏ x ∧ D_{m}(y))∧ \\ & ∀y(y ⊏ x ∧ D_{m}(y) → ∃z(y ⊏ z ⊏ x ∧ D_{m}(z))). \end{matrix}

Define φ_{m} ≡ ∃xD_{m}(x). One can prove by induction that QD(D_{m}) = 2m and

(a) QD(φ_{m}) = 2m + 1, and

(b) (ω^{m}, <) |̸= φ_{m}, but (ω^{n}, <) ⊧ φ_{m}, since n > m. If we assume that ω^{m} ≡_{p} ω^{n} and p ≥ 2m + 1, then QD(φ_{m}) ≤ p, which is a contradiction.

The other direction, i.e. the question whether for all m < n and p ≤ 2m, (ω^{m}, <) ≡_{p} (ω^{n}, <) remains unsolved. However 2m seems to be very large upper bound. □