Editing Elementary equivalence

{{Short description|Concept in model theory}}
{{Inline citations|date=February 2023}}
In [[model theory]], a branch of [[mathematical logic]], two [[Structure (mathematical logic)|structure]]s ''M'' and ''N'' of the same [[Signature (mathematical logic)|signature]] ''σ'' are called '''elementarily equivalent''' if they satisfy the same [[First-order logic|first-order]] [[Sentence (mathematical logic)|''σ''-sentence]]s.

If ''N'' is a [[Substructure (mathematics)|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>,&nbsp;…,&nbsp;''a''<sub>''n''</sub>) with parameters ''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>''n''</sub> from ''N'' is true in ''N'' if and only if it is true in&nbsp;''M''.
If ''N'' is an elementary substructure of ''M'', then ''M'' is called an '''elementary extension''' of&nbsp;''N''. An [[embedding#Universal algebra and model theory|embedding]] ''h'':&nbsp;''N''&nbsp;→&nbsp;''M'' is called an '''elementary embedding''' of ''N'' into ''M'' if ''h''(''N'') is an elementary substructure of&nbsp;''M''.

A substructure ''N'' of ''M'' is elementary if and only if it passes the '''Tarski–Vaught test''': every first-order formula ''φ''(''x'',&nbsp;''b''<sub>1</sub>,&nbsp;…,&nbsp;''b''<sub>''n''</sub>) with parameters in ''N'' that has a solution in ''M'' also has a solution in&nbsp;''N'' when evaluated in&nbsp;''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&nbsp;''σ'' are '''elementarily equivalent''' if every first-order sentence (formula without free variables) over&nbsp;''σ'' is true in ''M'' if and only if it is true in ''N'', i.e. if ''M'' and ''N'' have the same [[complete theory|complete]] first-order theory.
If ''M'' and ''N'' are elementarily equivalent, one writes ''M''&nbsp;≡&nbsp;''N''.

A first-order [[theory (mathematical logic)|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 [[Dense order|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 model of arithmetic|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.

==Elementary substructures and elementary extensions==

''N'' is an '''elementary substructure''' or '''elementary submodel''' of ''M'' if ''N'' and ''M'' are structures of the same [[Signature (mathematical logic)|signature]]&nbsp;''σ'' such that for all first-order ''σ''-formulas ''φ''(''x''<sub>1</sub>,&nbsp;…,&nbsp;''x''<sub>''n''</sub>) with free variables ''x''<sub>1</sub>,&nbsp;…,&nbsp;''x''<sub>''n''</sub>, and all elements ''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>n</sub> of&nbsp;''N'', ''φ''(''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>n</sub>) holds in ''N'' if and only if it holds in ''M'':
<math display="block">N \models \varphi(a_1, \dots, a_n) \text{ if and only if } M \models \varphi(a_1, \dots, a_n).</math>

This definition first appears in Tarski, Vaught (1957).<ref>E. C. Milner, [https://www.sciencedirect.com/science/article/pii/0012365X9590789N The use of elementary substructures in combinatorics] (1993). Appearing in ''Discrete Mathematics'', vol. 136, issues 1--3, 1994, pp.243--252.</ref> 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&nbsp;''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'' <math>\preceq</math> ''M'' and says that ''M'' is an '''elementary extension''' of ''N'': ''M'' <math>\succeq</math> ''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'',&nbsp;''y''<sub>1</sub>,&nbsp;…,&nbsp;''y''<sub>''n''</sub>) over ''σ'' and all elements ''b''<sub>1</sub>,&nbsp;…,&nbsp;''b''<sub>''n''</sub> from ''N'', if ''M'' <math>\models</math> {{exist}}''x''&nbsp;''φ''(''x'',&nbsp;''b''<sub>1</sub>,&nbsp;…,&nbsp;''b''<sub>''n''</sub>), then there is an element ''a'' in ''N'' such that ''M'' <math>\models</math> ''φ''(''a'',&nbsp;''b''<sub>1</sub>,&nbsp;…,&nbsp;''b''<sub>''n''</sub>).

==Elementary embeddings==

An '''elementary embedding''' of a structure ''N'' into a structure ''M'' of the same signature ''σ'' is a map ''h'':&nbsp;''N''&nbsp;→&nbsp;''M'' such that for every first-order ''σ''-formula ''φ''(''x''<sub>1</sub>,&nbsp;…,&nbsp;''x''<sub>''n''</sub>) and all elements ''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>n</sub> of&nbsp;''N'', 
:''N'' <math>\models</math> ''φ''(''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>''n''</sub>) if and only if ''M'' <math>\models</math> ''φ''(''h''(''a''<sub>1</sub>),&nbsp;…,&nbsp;''h''(''a''<sub>''n''</sub>)).
Every elementary embedding is a [[Structure (mathematical logic)#Homomorphisms|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 (set theory)|Critical point]]).

==References==

{{reflist}}

* {{Citation| last1=Chang | first1=Chen Chung | last2=Keisler | first2=H. Jerome | author1-link=Chen Chung Chang | author2-link=Howard Jerome Keisler | title=Model Theory | orig-year=1973 | publisher=Elsevier | edition=3rd | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-88054-3 | year=1990}}.
* {{Citation| last1=Hodges | first1=Wilfrid | author1-link=Wilfrid Hodges | title=A shorter model theory | publisher= [[Cambridge University Press]]| location=Cambridge | isbn=978-0-521-58713-6 | year=1997}}.
* {{Citation|last=Monk |first=J. Donald |title=Mathematical Logic |series=Graduate Texts in Mathematics |publisher=Springer Verlag |location=New York • Heidelberg • Berlin |year=1976 |isbn=0-387-90170-1 |url-access=registration |url=https://archive.org/details/mathematicallogi00jdon}}

{{Mathematical logic}}
{{DEFAULTSORT:Elementary Equivalence}}

[[Category:Equivalence (mathematics)]]
[[Category:Mathematical logic]]
[[Category:Model theory]]