Elementary equivalence

Two structures M and N of the same signature σ are elementarily equivalent if every first-order sentence (formula without free variables) over σ is true in M if and only if it is true in N, i.e. if M and N have the same complete first-order theory. If M and N are elementarily equivalent, one writes M ≡ N.

A first-order theory is complete if and only if any two of its models are elementarily equivalent.

For example, consider the language with one binary relation symbol '<'. The model R of real numbers with its usual order and the model Q of rational numbers with its usual order are elementarily equivalent, since they both interpret '<' as an unbounded dense linear ordering. This is sufficient to ensure elementary equivalence, because the theory of unbounded dense linear orderings is complete, as can be shown by the Łoś–Vaught test.

More generally, any first-order theory with an infinite model has non-isomorphic, elementarily equivalent models, which can be obtained via the Löwenheim–Skolem theorem. Thus, for example, there are non-standard models of Peano arithmetic, which contain other objects than just the numbers 0, 1, 2, etc., and yet are elementarily equivalent to the standard model.

N is an elementary substructure or elementary submodel of M if N and M are structures of the same signature σ such that for all first-order σ-formulas φ(x₁, …, x_n) with free variables x₁, …, x_n, and all elements a₁, …, a_n of N, φ(a₁, …, a_n) holds in N if and only if it holds in M: $${\displaystyle N\models \varphi (a_{1},\dots ,a_{n}){\text{ if and only if }}M\models \varphi (a_{1},\dots ,a_{n}).}$$

This definition first appears in Tarski, Vaught (1957).^[1] It follows that N is a substructure of M.

If N is a substructure of M, then both N and M can be interpreted as structures in the signature σ_N consisting of σ together with a new constant symbol for every element of N. Then N is an elementary substructure of M if and only if N is a substructure of M and N and M are elementarily equivalent as σ_N-structures.

If N is an elementary substructure of M, one writes N ${\displaystyle \preceq }$ M and says that M is an elementary extension of N: M ${\displaystyle \succeq }$ N.

The downward Löwenheim–Skolem theorem gives a countable elementary substructure for any infinite first-order structure in at most countable signature; the upward Löwenheim–Skolem theorem gives elementary extensions of any infinite first-order structure of arbitrarily large cardinality.

The Tarski–Vaught test (or Tarski–Vaught criterion) is a necessary and sufficient condition for a substructure N of a structure M to be an elementary substructure. It can be useful for constructing an elementary substructure of a large structure.

Let M be a structure of signature σ and N a substructure of M. Then N is an elementary substructure of M if and only if for every first-order formula φ(x, y₁, …, y_n) over σ and all elements b₁, …, b_n from N, if M ${\displaystyle \models }$ ${\displaystyle \exists }$x φ(x, b₁, …, b_n), then there is an element a in N such that M ${\displaystyle \models }$ φ(a, b₁, …, b_n).

An elementary embedding of a structure N into a structure M of the same signature σ is a map h: N → M such that for every first-order σ-formula φ(x₁, …, x_n) and all elements a₁, …, a_n of N,

N ${\displaystyle \models }$ φ(a₁, …, a_n) if and only if M ${\displaystyle \models }$ φ(h(a₁), …, h(a_n)).

Every elementary embedding is a strong homomorphism, and it induces an isomorphism between N and an elementary substructure of M.

Elementary embeddings are the most important maps in model theory. In set theory, elementary embeddings whose domain is V (the universe of set theory) play an important role in the theory of large cardinals (see also Critical point).