Elementare Äquivalenz

Die elementare Äquivalenz i​st ein Begriff a​us der Modelltheorie, e​inem Teilgebiet d​er mathematischen Logik. Vereinfacht ausgedrückt heißen z​wei Strukturen elementar äquivalent, w​enn sie dieselben Sätze erfüllen, w​ie im Folgenden präzisiert wird.

Es sei ${\displaystyle L_{I}^{S}}$ die Sprache der Prädikatenlogik erster Stufe mit der Symbolmenge ${\displaystyle S}$. Zwei ${\displaystyle S}$-Strukturen ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ heißen elementar äquivalent, wenn

${\displaystyle {\mathcal {A}}\vDash \varphi }$ genau dann, wenn ${\displaystyle {\mathcal {B}}\vDash \varphi }$

für alle Sätze, das heißt Ausdrücke ohne freie Variable, ${\displaystyle \varphi \in L_{I}^{S}}$, wobei das Zeichen ${\displaystyle \vDash }$ für „erfüllt“ bzw. „ist Modell von“ steht.[1]

Elementar äquivalente Strukturen lassen sich also nicht durch Sätze der Prädikatenlogik erster Stufe unterscheiden. Bezeichnet man die Gesamtheit ${\displaystyle \{\varphi$ ;\,\varphi {\mbox{ Satz in }}L_{I}^{S},{\mathcal {A}}\vDash \varphi \}} als die Theorie von ${\displaystyle {\mathcal {A}}}$, so kann man auch formulieren, dass elementar äquivalente Strukturen dieselbe Theorie haben.

Elementare Äquivalenz hat offenbar die charakteristischen Eigenschaften einer Äquivalenzrelation, und man schreibt ${\displaystyle {\mathcal {A}}\equiv {\mathcal {B}}}$, wenn die Strukturen ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ elementar äquivalent sind. Die elementare Äquivalenzklasse ${\displaystyle \{{\mathcal {B}};\,{\mathcal {B}}\equiv {\mathcal {A}}\}}$ ist ${\displaystyle \Delta }$-elementar, denn sie wird durch die Satzmenge der Theorie von ${\displaystyle {\mathcal {A}}}$ charakterisiert.[2]

Die Isomorphieklasse ${\displaystyle \{{\mathcal {B}};\,{\mathcal {B}}\cong {\mathcal {A}}\}}$ von ${\displaystyle {\mathcal {A}}}$ ist stets in der elementaren Äquivalenzklasse enthalten, denn isomorphe Strukturen erfüllen dieselben Sätze.[3] Ist ${\displaystyle {\mathcal {A}}}$ unendlich, so ist diese Inklusion echt, denn nach dem Satz von Löwenheim-Skolem gibt es Modelle unterschiedlicher Mächtigkeit, die daher nicht isomorph sein können. So sind z. B. die geordneten Mengen ${\displaystyle (\mathbb {R} ,<)}$ und ${\displaystyle (\mathbb {Q} ,<)}$ elementar äquivalent, was man leicht mit dem Satz von Fraïssé zeigen kann, der bei endlicher Symbolmenge eine rein algebraische Charakterisierung der elementaren Äquivalenz darstellt, ohne einen Bezug auf die Prädikatenlogik zu nehmen. Das Auseinanderfallen der Begriffe Isomorphie und elementare Äquivalenz charakterisiert die endlichen Modelle, denn für ein Modell ${\displaystyle {\mathcal {A}}}$ sind äquivalent:[4]

• Alle zu ${\displaystyle {\mathcal {A}}}$ elementar äquivalenten Modelle sind isomorph zu ${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle {\mathcal {A}}}$ ist endlich.

Siehe auch

• Elementare Unterstruktur

Einzelnachweise

1. Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg/Berlin/Oxford 1996, ISBN 3-8274-0130-5, Kap VI, Definition 4.1
2. Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg/Berlin/Oxford 1996, ISBN 3-8274-0130-5, Kap VI, Lemma 4.2
3. René Cori, Daniel Lascar: Mathematical Logic: Propositional calculus, Boolean algebras, predicate calculus, Oxford University Press (2000), ISBN 0198500483, Satz 3.74
4. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Satz 8.1.1