Elementare Unterstruktur

Der Begriff elementare Unterstruktur (oder elementare Substruktur) entstammt der Modelltheorie, einem Gebiet der mathematischen Logik.<ref> Der Begriff wurde von A. Tarski und R. L. Vaught eingeführt in ihrer Arbeit: A. Tarski, R. L. Vaught: Arithmetical Extensions of Relational Systems; in: Compositio Math., vol 13 (1956/58), Seite 81–102</ref>

Eine Struktur <math>\mathfrak B</math> ist elementare Unterstruktur der Struktur <math>\mathfrak A</math>, wenn sie Unterstruktur im algebraischen Sinn ist und für ihre Elemente in beiden Strukturen die gleichen Aussagen gelten.

Man sagt dann auch: <math>\mathfrak A</math> ist elementare Erweiterung von <math>\mathfrak B</math> und verwendet als mathematische Symbolschreibweise <math> \mathfrak{ B \prec A}</math> (oder <math> \mathfrak{ A \succ B} </math>; oft wird auch <math> \mathfrak{ B \preccurlyeq A }</math> und <math> \mathfrak{ A \succcurlyeq B}</math> geschrieben).

Präzisierung

<math>\mathfrak A</math> soll eine beliebige Struktur sein und <math>\mathcal L_{\mathfrak A}</math> die Sprache, die die entsprechenden Funktions-, Relations- und Konstantensymbole zur Signatur von <math>\mathfrak A</math> enthält und <math>\mathfrak B</math> eine Struktur mit gleicher Signatur.

Dann ist die Aussage „<math>\mathfrak B</math> ist eine elementare Unterstruktur von <math>\mathfrak A</math>“ durch folgende beiden Bedingungen definiert:

für die Trägermengen gilt <math>B \subseteq A</math>.
Für jede Formel <math>\varphi \in \mathcal L_{\mathfrak A}</math> mit freien Variablen <math>x_1, \dots, x_n</math> und jede Belegung dieser Variablen mit Elementen <math> b_1, \dots, b_n \in B</math> gilt: <math>{\mathfrak A} \models \varphi (b_1, \dots, b_n) \Longleftrightarrow {\mathfrak B} \models \varphi (b_1, \dots, b_n) </math>

Man kann die zweite Bedingung auch so ausdrücken:

Erweitert man die Sprache <math>\mathcal L_{\mathfrak A}</math> um eine Konstantenmenge <math> \left\{\dot{a}| a \in A\right\}</math>, dann gilt <math>\mathfrak{ A \equiv B}</math> für die erweiterten Strukturen (wenn jeweils die Konstante <math>\dot{a}</math> durch <math>a\,</math> belegt wird), d. h. die erweiterten Strukturen sind elementar äquivalent.

Ist <math>\Phi: \mathfrak {B \hookrightarrow A} </math> ein Monomorphismus, d. h. ein injektiver starker Homomorphismus, dessen Bild <math>\mathfrak{ \widehat {B}}</math> eine elementare Unterstruktur von <math> \mathfrak A </math> ist, dann nennt man <math>\Phi </math> eine elementare Einbettung.

Die Ausdrucksweise „Es gibt eine elementare Erweiterung von <math>\mathfrak A</math>“ wird auch verwendet, wenn es eine Struktur <math> \mathfrak B </math> und eine elementare Einbettung <math> \mathfrak{ A \to B} </math> gibt.

Eine Theorie <math>\mathcal T</math> heißt modellvollständig, wenn für zwei Modelle von <math>\mathcal T</math> gilt: aus <math> \mathfrak {B \subseteq A} </math> folgt <math> \mathfrak {B \prec A} </math>.

Aussagen über elementare Substrukturen

Auf Alfred Tarski gehen folgende Versionen des Satzes von Löwenheim-Skolem zurück, die auch als Sätze von Löwenheim-Skolem-Tarski bezeichnet werden (mit ZFC):
- („abwärts“) Ist <math>\mathfrak A</math> eine beliebige (unendliche) Struktur und <math>\mathcal L_A</math> die zugehörige Sprache, dann gibt es für alle Kardinalitäten <math>\kappa</math> mit <math> \operatorname{card} ({\mathcal L_A}) \le \kappa \le \operatorname{card}(A) </math> eine elementare Substruktur <math>\mathfrak{ B \prec A} </math> mit <math> \operatorname{card}(B) = \kappa </math>
- („aufwärts“) Für alle <math> \kappa \ge \max( \operatorname{card} ({\mathcal L_A},\operatorname{card}(B)) </math> gibt es eine elementare Erweiterung <math>\mathfrak{ B \succ A} </math>.

{{#if: Satz von Löwenheim-Skolem|{{#ifexist:Satz von Löwenheim-Skolem||{{#if: |{{#ifexist:{{{2}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{2}}}{{#if: ||{{{titel2}}}}}]]{{#if: |{{#ifexist:{{{3}}}| und [[{{{3}}}{{#if: ||{{{titel3}}}}}]]|}}|}}

|{{#if: |{{#ifexist:{{{3}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{3}}}{{#if: ||{{{titel3}}}}}]]

|}}|}}|}}|}}|}}|Einbindungsfehler: Die Vorlage Hauptartikel benötigt immer mindestens ein Argument.}}

Ist <math>\operatorname{card} (A) </math> endlich, dann hat <math>\mathfrak A</math> keine echten elementaren Unterstrukturen.

Tarski-Vaught-Test

Der Tarski-Vaught-Test, benannt nach Alfred Tarski und Robert Vaught, gibt ein Kriterium an, wie man in der Prädikatenlogik erster Stufe die Beziehung <math> \mathfrak{ B \prec A }</math> prüfen kann. Zum Nachweis von <math> \mathfrak{ B \prec A }</math> muss man zeigen, dass jede in <math> \mathfrak{ A }</math> für Elemente aus <math>B</math> geltende Formel auch schon in <math> \mathfrak{ B }</math> gilt. Ein Blick auf die induktive Konstruktion der Formeln zeigt, dass hier am ehesten die Existenzaussagen zu einem Scheitern führen, denn das, was es in <math>A</math> zu Elementen aus <math>B</math> gibt, muss es ja nicht schon in der kleineren Menge <math>B</math> geben, wie auch die unten angegebenen Beispiele zeigen. Der Tarski-Vaught-Test sagt aus, dass das auch schon alles ist, worauf man achten muss:<ref>Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Satz 8.3.2</ref>

Tarski-Vaught-Test: Es gilt <math> \mathfrak{ B \prec A }</math> genau dann, wenn <math> \mathfrak{ B } \subset \mathfrak{ A }</math>, das heißt <math>\mathfrak{ B }</math> ist Unterstruktur von <math> \mathfrak{ A }</math>, und es gilt

Für alle natürlichen Zahlen <math>n</math> und alle Formeln <math>\varphi = \varphi(v_0,\ldots, v_n)</math> mit freien Variablen in <math>v_0,\ldots, v_n</math> und alle <math>n</math>-Tupel <math>(b_1,\ldots, b_n) \in B^n</math> gilt: Wenn <math>\mathfrak{ A } \models \exists x \varphi (x,b_1,\ldots, b_n)</math>, dann gibt es ein <math>b \in B</math> mit <math>\mathfrak{ A } \models \varphi (b,b_1,\ldots, b_n)</math>.

Beispiele

Betrachtet man <math> \Q</math> und <math> \R</math> als reine Ordnungsstrukturen, dann gilt <math> \Q \prec \R</math>. Elementare Unterstrukturen müssen schon aus Kardinalitätsgründen nicht isomorph zur Ausgangsstruktur sein.
Andererseits ist aber <math> \Q \not\prec \R</math>, wenn man beide als Ringe betrachtet. <math>\left[ \R \models \ \exists x: x^2 = 2 \right]</math>. Es kann also von der betrachteten Signatur abhängen, ob <math> \mathfrak{ B \prec A}</math> gilt oder nicht.
Bezeichnet <math>2\Z</math> die Struktur der geraden Zahlen (als reine Ordnungsstruktur), dann ist <math>2\Z \not\prec \Z</math>. Dies zeigt, dass eine isomorphe Unterstruktur nicht elementare Unterstruktur sein muss. <math>\left[ \Z \models \ \exists x: \left(0 < x \land x < 2\right) \right]</math>
Die Theorie der algebraisch abgeschlossenen Körper ist modellvollständig, obwohl sie nicht vollständig ist!
In der Nonstandardanalysis ist die Struktur der hyperreellen Zahlen eine elementare Erweiterung von <math>\R</math>. (Sowohl die Theorie der reell-abgeschlossenen Körper als auch die Theorie der reell-abgeschlossenen geordneten Körper sind modellvollständig.)

Einzelnachweise

Quellen

Lexikon der Mathematik, Spektrum Akademischer Verlag, 2003, (CD-Rom Ausgabe), Art. "elementare Erweiterung einer L-Struktur"

Chang, Chen C., Keisler, H. Jerome, Model Theory, Amsterdam [u. a.], North-Holland (1998); Kap. 3