Editing Elementary equivalence (section)

==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.