Elementare Äquivalenz

Die elementare Äquivalenz ist ein Begriff aus der Modelltheorie, einem Teilgebiet der mathematischen Logik. Vereinfacht ausgedrückt heißen zwei Strukturen elementar äquivalent, wenn sie dieselben Sätze erfüllen, wie 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.