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 $L_I^S$ die Sprache der Prädikatenlogik erster Stufe mit der Symbolmenge S. Zwei S-Strukturen $\mathcal A$ und $\mathcal B$ heißen elementar äquivalent, wenn

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

für alle Sätze, das heißt Ausdrücke ohne freie Variable, $\varphi \in L_I^S$, wobei das Zeichen $\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 $\{\varphi;\, \varphi \mbox{ Satz in } L_I^S, \mathcal{A} \vDash \varphi\}$ als die Theorie von $\mathcal A$, so kann man auch formulieren, dass elementar äquivalente Strukturen dieselbe Theorie haben.

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

Die Isomorphieklasse $\{\mathcal{B};\, \mathcal{B} \cong \mathcal{A}\}$ von $\mathcal A$ ist stets in der elementaren Äquivalenzklasse enthalten, denn isomorphe Strukturen erfüllen dieselben Sätze ^[3]. Ist $\mathcal A$ unendlich, so ist diese Inklusion echt; man kann zum Beispiel zeigen, dass die geordneten Mengen $(\R,<)$ und $(\Q,<)$, die schon aus Mächtigkeitsgründen nicht isomorph sein können, elementar äquivalent sind (die Sprache ist hier $L_I^{\{<\}}$). Letzteres zeigt man leicht mit dem Satz von Fraïssé, der bei endlicher Symbolmenge eine rein algebraische Charakterisierung der elementaren Äquivalenz darstellt, ohne einen Bezug auf die Prädikatenlogik zu nehmen.

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