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 die Sprache der Prädikatenlogik erster Stufe mit der Symbolmenge . Zwei -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 hat offenbar die charakteristischen Eigenschaften einer Ä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, 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 und 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 sind äquivalent:[4]

  • Alle zu elementar äquivalenten Modelle sind isomorph zu .
  • ist endlich.

Siehe auch

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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.