Winning Strategies and σ-closed Sets of Partial Isomorphisms

Jouko Väänänen & Boban Veličković

Let I_{κ} be the set of all partial isomorphisms of cardinality < κ between two first order structures A and B of the same vocabulary. X ⊆ I has the κ-back-and-forth property if for all λ < κ and for all p ∈ X: ∀a ∈ ^{λ}A∃b ∈ ^{λ}B (p ∪ {⟨a(i), b(i)⟩ : i < λ} ∈ X) and ∀b ∈ ^{λ}B∃a ∈ ^{λ}A(p ∪ {⟨a(i), b(i)⟩ : i < λ} ∈ X). X is σ-closed, if whenever p_{0} ⊆ p_{1} ⊆ ... are in X, also ⋃_{n<ω} p_{n} ∈ X. Let I_{ℵ_{1}}^{∗} be the largest X ⊆ I with the ℵ_{1}-back-and-forth property. If I_{ℵ_{1}}^{∗} ≠ ∅, then A ≡_{∞ℵ_{1}} B. The following theorem is a special case of a more general result:

Theorem 1 The following conditions are equivalent:

(1) The Nonempty Player has a winning strategy in the Banach-Mazur game on ⟨I_{ℵ_{1}}^{∗}, ⊆⟩.

(2) I_{ℵ_{1}}^{∗} contains a σ-closed dense subset.

Another measure of the largeness of I_{λ}^{∗} is the Ehrenfeucht-Fraïssé-game.

Theorem 2 Suppose A and B have cardinality ≤ λ = κ^{+}. Then the following conditions are equivalent:

(3) Player II has a winning strategy in the Ehrenfeucht-Fraïssé-game of length ω_{1} between A and B, players playing ≤ κ elements at a time.

(4) I_{λ}^{∗} has a σ-closed subset with the λ-back-and-forth property.

The condition (4) was introduced by Dickmann in 1975. It implies isomorphism among structures of cardinality ≤ ℵ_{1}. It is an open problem, whether (4) is transitive for all A and B.

Corollary 3 (4) is transitive among structures of cardinality ≤ λ = κ^{+}.

Addresses Jouko Väänänen : Department of Mathematics, University of Helsinki, Helsinki, Finland

Boban Veličković: UFR de Mathèmatiques, Universitè de Paris 7, Paris, France