If N is a substructure of M, one often needs a stronger condition. In this case N is called an elementary substructure of M if every first-order ?-formula ?(a1, ..., an) with parameters a1, ..., an from N is true in N if and only if it is true in M. If N is an elementary substructure of M, then M is called an elementary extension of N. An embedding h: N -> M is called an elementary embedding of N into M if h(N) is an elementary substructure of M.
A substructure N of M is elementary if and only if it passes the Tarski-Vaught test: every first-order formula ?(x, b1, ..., bn) with parameters in N that has a solution in M also has a solution in N when evaluated in M. One can prove that two structures are elementarily equivalent with the Ehrenfeucht-Fraïssé games.
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 of M if N and M are structures of the same signature ? such that for all first-order ?-formulas ?(x1, ..., xn) with free variables x1, ..., xn, and all elements a1, ..., an of N, ?(a1, ..., an) holds in N if and only if it holds in M:
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 M and says that M is an elementary extension of N: M 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, y1, ..., yn) over ? and all elements b1, ..., bn from N, if M x ?(x, b1, ..., bn), then there is an element a in N such that M ?(a, b1, ..., bn).
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 ?(x1, ..., xn) and all elements a1, ..., an of N,
Every elementary embedding is a strong homomorphism, and its image is an elementary substructure.
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).