Elementare Äquivalenz - Elementary equivalence

In der Modelltheorie , einem Zweig der mathematischen Logik , werden zwei Strukturen M und N derselben Signatur σ als elementar äquivalent bezeichnet, wenn sie dieselben σ- Sätze erster Ordnung erfüllen .

Wenn N eine Unterstruktur von M ist , braucht man oft eine stärkere Bedingung. In diesem Fall heißt N eine elementare Substruktur von M, wenn jede σ- Formel φ erster Ordnung ( a ₁ ,…,  a _n ) mit den Parametern a ₁ ,…,  a _n von N genau dann in N wahr ist, wenn dies der Fall ist wahr in  M . Wenn N eine elementare Unterstruktur von M ist , wird M eine elementare Erweiterung von  N genannt . Eine Einbettung von h :  N  →  M wird als elementare Einbettung von N in M bezeichnet, wenn h ( N ) eine elementare Unterstruktur von  M ist .

Eine Unterstruktur N von M ist genau dann elementar, wenn sie den Tarski-Vaught-Test besteht : Jede Formel erster Ordnung φ ( x ,  b ₁ ,…,  b _n ) mit Parametern in N , die eine Lösung in M hat , hat auch eine Lösung in  N , wenn sie in ausgewertet  M . Man kann beweisen, dass zwei Strukturen den Ehrenfeucht-Fraïssé-Spielen elementar gleichwertig sind .

Elementar äquivalente Strukturen

Zwei Strukturen M und N derselben Signatur  σ sind elementar äquivalent, wenn jeder Satz erster Ordnung (Formel ohne freie Variablen) über  σ genau dann in M wahr ist, wenn er in N wahr ist , dh wenn M und N gleich vollständig sind Theorie erster Ordnung. Wenn M und N elementar äquivalent sind, schreibt ein M  ≡  N .

Eine Theorie erster Ordnung ist genau dann vollständig, wenn zwei ihrer Modelle elementar äquivalent sind.

Betrachten Sie beispielsweise die Sprache mit einem binären Beziehungssymbol '<'. Das Modell R der reellen Zahlen mit der üblichen Ordnung und das Modell Q der rationalen Zahlen mit der üblichen Ordnung ist elementar gleichwertig, da sie beide interpretieren ‚<‘ als unbeschränkt dichten lineare Ordnung . Dies reicht aus, um die elementare Äquivalenz sicherzustellen, da die Theorie der unbegrenzten dichten linearen Ordnungen vollständig ist, wie der Łoś-Vaught-Test zeigen kann .

Allgemeiner gesagt hat jede Theorie erster Ordnung mit einem unendlichen Modell nicht-isomorphe, elementar äquivalente Modelle, die über den Löwenheim-Skolem-Satz erhalten werden können . So gibt es beispielsweise nicht standardmäßige Modelle der Peano-Arithmetik , die andere Objekte als nur die Zahlen 0, 1, 2 usw. enthalten und dennoch elementar dem Standardmodell entsprechen.

Elementare Unterstrukturen und elementare Erweiterungen

N ist eine elementare Unterstruktur von M, wenn N und M Strukturen derselben Signatur   σ sind, so dass für alle σ- Formeln erster Ordnung φ ( x ₁ ,…,  x _n ) mit freien Variablen x ₁ ,…,  x _n und Alle Elemente a ₁ ,…,  a _n von  N , φ ( a ₁ ,…,  a _n ) gelten genau dann in N, wenn es in M gilt :

N φ ( a ₁ ,…,  a _n ) iff M φ ( a ₁ ,…,  a _n ). ${\ displaystyle \ models}$ ${\ displaystyle \ models}$

Daraus folgt, dass N eine Unterstruktur von M ist .

Wenn N eine Unterstruktur von M ist , können sowohl N als auch M als Strukturen in der Signatur σ _N interpretiert werden, die aus σ zusammen mit einem neuen konstanten Symbol für jedes Element von  N besteht . Dann ist N genau dann eine elementare Unterstruktur von M, wenn N eine Unterstruktur von M ist und N und M elementar äquivalent zu σ _N- Strukturen sind.

Wenn N eine elementare Unterstruktur von M ist , schreibt man N M und sagt, dass M eine elementare Erweiterung von N : M N ist . ${\ displaystyle \ preceq}$ ${\ displaystyle \ succeq}$

Das abwärts gerichtete Löwenheim-Skolem-Theorem liefert eine zählbare elementare Unterstruktur für jede unendliche Struktur erster Ordnung in höchstens zählbarer Signatur; Der Löwenheim-Skolem-Satz nach oben liefert elementare Erweiterungen jeder unendlichen Struktur erster Ordnung mit beliebig großer Kardinalität.

Tarski-Vaught-Test

Der Tarski-Vaught-Test (oder das Tarski-Vaught-Kriterium ) ist eine notwendige und ausreichende Bedingung dafür, dass eine Unterstruktur N einer Struktur M eine elementare Unterstruktur ist. Es kann nützlich sein, um eine elementare Unterstruktur einer großen Struktur zu konstruieren.

Lassen M eine Struktur der Unterschrift sein σ und N eine Unterkonstruktion aus M . Dann ist N genau dann eine elementare Unterstruktur von M, wenn für jede Formel erster Ordnung φ ( x ,  y ₁ ,…,  y _n ) über σ und alle Elemente b ₁ ,…,  b _n von N , wenn M x φ ( x ,  b ₁ ,…,  b _n ), dann gibt es ein Element a in N, so dass M φ ( a ,  b ₁ ,…,  b _n ). ${\ displaystyle \ models}$ ${\ displaystyle \ existiert}$  ${\ displaystyle \ models}$

Elementare Einbettungen

Eine elementare Einbettung einer Struktur N in eine Struktur M derselben Signatur σ ist eine Abbildung h :  N  →  M, so dass für jede σ- Formel erster Ordnung φ ( x ₁ ,…,  x _n ) und alle Elemente a ₁ , …,  Ein _n von  N ,

N φ ( a ₁ ,…,  a _n ) genau dann, wenn M φ ( h ( a ₁ ),…,  h ( a _n )). ${\ displaystyle \ models}$ ${\ displaystyle \ models}$

Jede elementare Einbettung ist ein starker Homomorphismus , und ihr Bild ist eine elementare Substruktur.

Elementare Einbettungen sind die wichtigsten Karten in der Modelltheorie. In der Mengenlehre spielen elementare Einbettungen, deren Domäne V ist (das Universum der Mengenlehre), eine wichtige Rolle in der Theorie der großen Kardinäle (siehe auch Kritischer Punkt ).

Verweise

• Chang, Chen Chung ; Keisler, H. Jerome (1990) [1973], Modelltheorie , Studien in Logik und Grundlagen der Mathematik (3. Aufl.), Elsevier, ISBN   978-0-444-88054-3 .
• Hodges, Wilfrid (1997), Eine kürzere Modelltheorie , Cambridge: Cambridge University Press , ISBN   978-0-521-58713-6 .
• Monk, J. Donald (1976), Mathematische Logik , Diplomtexte in Mathematik, New York • Heidelberg • Berlin: Springer Verlag, ISBN   0-387-90170-1