In model theory, a branch of mathematical logic, two structures M and N of the same signature ÃÂ are called elementarily equivalent if they satisfy the same first-order ÃÂ-sentences.
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 ÃÂ(a<sub>1</sub>, â¦, a<sub>n</sub>) with parameters a<sub>1</sub>, â¦, a<sub>n</sub> 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, b<sub>1</sub>, â¦, b<sub>n</sub>) 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.
Elementary embeddings are used in the study of large cardinals, including rank-into-rank.
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<sub>1</sub>, â¦, x<sub>n</sub>) with free variables x<sub>1</sub>, â¦, x<sub>n</sub>, and all elements a<sub>1</sub>, â¦, a<sub>n</sub> of N, ÃÂ(a<sub>1</sub>, â¦, a<sub>n</sub>) holds in N if and only if it holds in M:
This definition first appears in Tarski, Vaught (1957). 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 ÃÂ<sub>N</sub> 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 ÃÂ<sub>N</sub>-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, y<sub>1</sub>, â¦, y<sub>n</sub>) over àand all elements b<sub>1</sub>, â¦, b<sub>n</sub> from N, if M x ÃÂ(x, b<sub>1</sub>, â¦, b<sub>n</sub>), then there is an element a in N such that M ÃÂ(a, b<sub>1</sub>, â¦, b<sub>n</sub>).
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<sub>1</sub>, â¦, x<sub>n</sub>) and all elements a<sub>1</sub>, â¦, a<sub>n</sub> of 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).