Elementary Equivalence

Origin. Tarski's notion of arithmetical equivalence (1936) and its development with Vaught (1957); Fraïssé's back-and-forth characterization (1954) and Ehrenfeucht's game formulation (1961), which made the relation checkable. Same first-order theory. Indistinguishable by FOL. Ehrenfeucht-Fraïssé games. Foundation for model comparison.

Models. Structures satisfy same sentences. Isomorphism implies, not converse. Game characterization. Back-and-forth systems.

Formalism.

Definition: M ≡ N iff for all φ ∈ FOL: M ⊨ φ iff N ⊨ φ. Same first-order theory.

Isomorphism implies: M ≅ N → M ≡ N Isomorphic structures equivalent. Converse fails!

Counterexample: (ℚ, <) ≡ (ℝ, <) Both dense linear orders without endpoints. Not isomorphic (cardinality).

Ehrenfeucht-Fraïssé games: EF_n(M, N): n-round game. Spoiler picks element in one structure. Duplicator responds in other. Duplicator wins if partial isomorphism.

Game theorem: M ≡ N iff Duplicator wins EF_n for all n. Finite approximations.

n-equivalence: M ≡_n N: same sentences up to quantifier rank n. Duplicator wins n rounds. Finer classification.

Back-and-forth: Set of partial isomorphisms. Forth: extend in M. Back: extend in N. Existence implies equivalence.

Types: tp(a/M) = {φ(x) : M ⊨ φ(a)} Type of element. Realized types match in equivalent structures.

Symbols.

Symbol	Unicode	Name	Meaning
κ	U+03BA	Kappa	Cardinal in the Łoś–Vaught test
φ	U+03C6	Phi	Metavariable over first-order sentences
ℚ	U+211A	Double-struck Q	The rationals, in (ℚ, <)
ℝ	U+211D	Double-struck R	The reals, in (ℝ, <)
→	U+2192	Rightwards arrow	Implication: M ≅ N → M ≡ N
∈	U+2208	Element of	Membership, as in φ ∈ FOL
≅	U+2245	Isomorphism	Same structure; strictly stronger than ≡
≡	U+2261	Elementary equivalence	Same first-order theory
≥	U+2265	Greater than or equal	Cardinality bound in the Łoś–Vaught test
⊨	U+22A8	Satisfaction	M ⊨ φ
≡_n	—	n-equivalence	Same sentences of quantifier rank at most n
EF_n	—	Ehrenfeucht–Fraïssé game	The n-round game on two structures
M, N	—	Structures	The two structures being compared
<	—	Linear order	The order of (ℚ, <) and (ℝ, <)
tp(a/M)	—	Type	The formulas satisfied by a in M
Th(M)	—	Theory of M	The set of sentences true in M
FOL	—	First-order logic	The language over which ≡ is defined

Metatheory. Elementary equivalence is sameness of complete theory, so the ≡-classes of structures in a fixed signature stand in bijection with the complete consistent theories of that signature. Fraïssé (1954) and Ehrenfeucht (1961) reduced the relation to games over a finite relational signature: M ≡ N iff Duplicator wins EF_n for every n, which works because only finitely many sentences of quantifier rank n exist up to logical equivalence. On finite structures in a finite relational signature ≡ collapses into ≅, since each such structure is described up to isomorphism by a single sentence, so all the content of the relation is in the infinite case. The Łoś–Vaught test supplies equivalence in bulk: a theory with no finite models that is categorical in some κ at least the size of its language is complete, hence all its models are elementarily equivalent — which is how (ℚ, <) ≡ (ℝ, <) is proved. The exact converse to the failure of ≅ is Keisler–Shelah: M ≡ N iff M and N have isomorphic ultrapowers, proved by Keisler (1961) under GCH and by Shelah (1971) in ZFC.

Applies to. Model comparison. Decidability proofs. Database query equivalence. Descriptive complexity.

Limitations. Elementary equivalence fixes the first-order theory and nothing beyond it. Löwenheim–Skolem gives every structure with an infinite model elementarily equivalent companions in every cardinality at least that of the language, so cardinality, Dedekind completeness, and well-foundedness are all invisible across ≡: (ℚ, <) ≡ (ℝ, <) is the textbook case, and the nonstandard models of arithmetic are the same phenomenon. The relation is not effective — the complete theory of the natural numbers is not arithmetical, by Tarski's undefinability theorem, so there is no arithmetical test for elementary equivalence to the standard model. The game characterization is not a free substitute: it presupposes a finite relational signature, and it demands a separate winning strategy for each n rather than one argument. Nor does second-order logic close the gap absolutely — Ajtai (1979) showed that whether second-order equivalence implies isomorphism for countable structures is independent of ZFC.