- 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
die Sprache der Prädikatenlogik erster Stufe mit der Symbolmenge S. Zwei S-Strukturen
und
heißen elementar äquivalent, wenn
genau dann, wenn
für alle Sätze, das heißt Ausdrücke ohne freie Variable,
, wobei das Zeichen
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
als die Theorie von
, so kann man auch formulieren, dass elementar äquivalente Strukturen dieselbe Theorie haben.
Elementare Äquivalenz ist offenbar eine Äquivalenzrelation und man schreibt
, wenn die Strukturen
und
elementar äquivalent sind. Die elementare Äquivalenzklasse
ist Δ-elementar, denn sie wird durch die Satzmenge der Theorie von
charakterisiert[2].
Die Isomorphieklasse
von
ist stets in der elementaren Äquivalenzklasse enthalten, denn isomorphe Strukturen erfüllen dieselben Sätze [3]. Ist
unendlich, so ist diese Inklusion echt; man kann zum Beispiel zeigen, dass die geordneten Mengen
und
, die schon aus Mächtigkeitsgründen nicht isomorph sein können, elementar äquivalent sind (die Sprache ist hier
). 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
- ↑ 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
- ↑ 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
- ↑ René Cori, Daniel Lascar: Mathematical Logic: Propositional calculus, Boolean algebras, predicate calculus, Oxford University Press (2000), ISBN 0198500483, Satz 3.74
Wikimedia Foundation.