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^S_I 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.

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.

Die Isomorphieklasse von ist stets in der elementaren Äquivalenzklasse enthalten, denn isomorphe Strukturen erfüllen dieselben Sätze . 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 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.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Elementare Äquivalenz aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung