Elementare Unterstruktur

Der Begriff elementare Unterstruktur (oder elementare Substruktur) entstammt der Modelltheorie, einem Gebiet der mathematischen Logik.^[1]

Eine Struktur ${\displaystyle {\mathfrak {B}}}$ ist elementare Unterstruktur der Struktur ${\displaystyle {\mathfrak {A}}}$, wenn sie Unterstruktur im algebraischen Sinn ist und für ihre Elemente in beiden Strukturen die gleichen Aussagen gelten.

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

Präzisierung

${\displaystyle {\mathfrak {A}}}$ soll eine beliebige Struktur sein und ${\displaystyle {\mathcal {L}}_{\mathfrak {A}}}$ die Sprache, die die entsprechenden Funktions-, Relations- und Konstantensymbole zur Signatur von ${\displaystyle {\mathfrak {A}}}$ enthält und ${\displaystyle {\mathfrak {B}}}$ eine Struktur mit gleicher Signatur.

Dann ist die Aussage „${\displaystyle {\mathfrak {B}}}$ ist eine elementare Unterstruktur von ${\displaystyle {\mathfrak {A}}}$“ durch folgende beiden Bedingungen definiert:

• für die Trägermengen gilt ${\displaystyle B\subseteq A}$.
• Für jede Formel ${\displaystyle \varphi \in {\mathcal {L}}_{\mathfrak {A}}}$ mit freien Variablen ${\displaystyle x_{1},\dots ,x_{n}}$ und jede Belegung dieser Variablen mit Elementen ${\displaystyle b_{1},\dots ,b_{n}\in B}$ gilt: ${\displaystyle {\mathfrak {A}}\models \varphi (b_{1},\dots ,b_{n})\Longleftrightarrow {\mathfrak {B}}\models \varphi (b_{1},\dots ,b_{n})}$

Man kann die zweite Bedingung auch so ausdrücken:

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

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

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

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

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 ${\displaystyle {\mathfrak {A}}}$ eine beliebige (unendliche) Struktur und ${\displaystyle {\mathcal {L}}_{A}}$ die zugehörige Sprache, dann gibt es für alle Kardinalitäten ${\displaystyle \kappa }$ mit ${\displaystyle \operatorname {card} ({{\mathcal {L}}_{A}})\leq \kappa \leq \operatorname {card} (A)}$ eine elementare Substruktur ${\displaystyle {\mathfrak {B\prec A}}}$ mit ${\displaystyle \operatorname {card} (B)=\kappa }$
  • („aufwärts“) Für alle ${\displaystyle \kappa \geq \max(\operatorname {card} ({{\mathcal {L}}_{A}},\operatorname {card} (B))}$ gibt es eine elementare Erweiterung ${\displaystyle {\mathfrak {B\succ A}}}$.

→ Hauptartikel: Satz von Löwenheim-Skolem

• Ist ${\displaystyle \operatorname {card} (A)}$ endlich, dann hat ${\displaystyle {\mathfrak {A}}}$ 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 ${\displaystyle {\mathfrak {B\prec A}}}$ prüfen kann. Zum Nachweis von ${\displaystyle {\mathfrak {B\prec A}}}$ muss man zeigen, dass jede in ${\displaystyle {\mathfrak {A}}}$ für Elemente aus ${\displaystyle B}$ geltende Formel auch schon in ${\displaystyle {\mathfrak {B}}}$ 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 ${\displaystyle A}$ zu Elementen aus ${\displaystyle B}$ gibt, muss es ja nicht schon in der kleineren Menge ${\displaystyle B}$ geben, wie auch die unten angegebenen Beispiele zeigen. Der Tarski-Vaught-Test sagt aus, dass das auch schon alles ist, worauf man achten muss:^[2]

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

• Für alle natürlichen Zahlen ${\displaystyle n}$ und alle Formeln ${\displaystyle \varphi =\varphi (v_{0},\ldots ,v_{n})}$ mit freien Variablen in ${\displaystyle v_{0},\ldots ,v_{n}}$ und alle ${\displaystyle n}$-Tupel ${\displaystyle (b_{1},\ldots ,b_{n})\in B^{n}}$ gilt: Wenn ${\displaystyle {\mathfrak {A}}\models \exists x\varphi (x,b_{1},\ldots ,b_{n})}$, dann gibt es ein ${\displaystyle b\in B}$ mit ${\displaystyle {\mathfrak {A}}\models \varphi (b,b_{1},\ldots ,b_{n})}$.

Beispiele

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

Einzelnachweise

1. 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
2. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Satz 8.3.2

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