Elementary equivalence
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 1 , …, a n ) with parameters a 1 , …, a n 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 1 , …, b n ) 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.
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 1 , …, a n ) with parameters a 1 , …, a n 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 1 , …, b n ) 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.
Elementarily equivalent structures
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 ' 1 , …, x n ) with free variables x 1 , …, x n , and all elements a 1 , …, a n of N, φ(a 1 , …, a n ) holds in N if and only if it holds in M: 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). 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 \preceq M and says that M is an elementary extension of N: M \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.
Tarski–Vaught test
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 1 , …, y n ) over σ and all elements b 1 , …, b n from N, if M \models x φ(x, b 1 , …, b n ), then there is an element a in N such that M \models φ(a, b 1 , …, b n ).
Elementary embeddings
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 1 , …, x n ) and all elements a 1 , …, a n of N, N \models φ(a 1 , …, a n ) if and only if M \models φ(h(a 1 ), …, 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).
References
. .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1344446394 under CC BY-SA 4.0; modifications have been made.