Elementary equivalence

The elementary equivalence is a term from the model theory , a branch of mathematical logic . In simple terms, two structures are called elementarily equivalent if they satisfy the same theorems, as will be specified in the following.

Let it be the language of first order predicate logic with the symbol set . Two - structures and are called elementarily equivalent if ${\displaystyle L_{I}^{S}}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

${\displaystyle {\mathcal {A}}\vDash \varphi }$ exactly when ${\displaystyle {\mathcal {B}}\vDash \varphi }$

for all sentences, i.e. expressions without free variables, where the symbol stands for “fulfilled” or “is model of”. ${\displaystyle \varphi \in L_{I}^{S}}$ ${\displaystyle \vDash }$

Elementary equivalent structures cannot be differentiated by sentences of the first-order predicate logic. If the entirety is called the theory of , one can also formulate that elementary equivalent structures have the same theory. ${\displaystyle \{\varphi ;\,\varphi {\mbox{ Satz in }}L_{I}^{S},{\mathcal {A}}\vDash \varphi \}}$ ${\displaystyle {\mathcal {A}}}$

Elementary equivalence obviously has the characteristic properties of an equivalence relation , and one writes when the structures and are elementary equivalent. The elementary equivalence class is -elementary , because it is characterized by the set of sentences of the theory of . ${\displaystyle {\mathcal {A}}\equiv {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle \{{\mathcal {B}};\,{\mathcal {B}}\equiv {\mathcal {A}}\}}$ ${\displaystyle \Delta }$ ${\displaystyle {\mathcal {A}}}$

The isomorphism class of is always contained in the elementary equivalence class, because isomorphic structures satisfy the same theorems. If infinite, this inclusion is real, because according to the Löwenheim-Skolem theorem there are models of different thicknesses, which therefore cannot be isomorphic. So are z. B. the ordered sets and elementary equivalent, which can easily be shown with Fraïssé's theorem , which represents a purely algebraic characterization of the elementary equivalence for a finite set of symbols without referring to the predicate logic. The divergence of the terms isomorphism and elementary equivalence characterizes the finite models, because for a model the following are equivalent: ${\displaystyle \{{\mathcal {B}};\,{\mathcal {B}}\cong {\mathcal {A}}\}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle (\mathbb {R} ,<)}$ ${\displaystyle (\mathbb {Q} ,<)}$ ${\displaystyle {\mathcal {A}}}$

• All models which are equivalent to elementary are isomorphic to . ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$
• ${\displaystyle {\mathcal {A}}}$ is finite.

See also

• Elementary substructure

Individual evidence

1. ^ Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic. Spectrum Academic Publishing House, Heidelberg / Berlin / Oxford 1996, ISBN 3-8274-0130-5 , Chapter VI, Definition 4.1
2. ^ Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Introduction to mathematical logic. Spektrum Akademischer Verlag, Heidelberg / Berlin / Oxford 1996, ISBN 3-8274-0130-5 , Chapter VI, Lemma 4.2
3. ^ René Cori, Daniel Lascar: Mathematical Logic: Propositional calculus, Boolean algebras, predicate calculus , Oxford University Press (2000), ISBN 0198500483 , Theorem 3.74
4. ↑ Philipp Rothmaler: Introduction to model theory , Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , sentence 8.1.1