Elementare Unterstruktur
# Elementare Unterstruktur

Der Begriff elementare Unterstruktur (oder elementare Substruktur) entstammt der Modelltheorie, einem Gebiet der mathematischen Logik.
Eine Struktur ${\mathfrak {B}}$ ist elementare Unterstruktur der Struktur ${\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: ${\mathfrak {A}}$ ist elementare Erweiterung von ${\mathfrak {B}}$ und verwendet als mathematische Symbolschreibweise ${\mathfrak {B\prec A}}$ (oder ${\mathfrak {A\succ B}}$; oft wird auch ${\mathfrak {B\preccurlyeq A}}$ und ${\mathfrak {A\succcurlyeq B}}$ geschrieben).

## Präzisierung

${\mathfrak {A}}$ soll eine beliebige Struktur sein und ${\mathcal {L}}_{\mathfrak {A}}$ die Sprache, die die entsprechenden Funktions-, Relations- und Konstantensymbole zur Signatur von ${\mathfrak {A}}$ enthält und ${\mathfrak {B}}$ eine Struktur mit gleicher Signatur.
Dann ist die Aussage „${\mathfrak {B}}$ ist eine elementare Unterstruktur von ${\mathfrak {A}}$“ durch folgende beiden Bedingungen definiert:
* für die Trägermengen gilt $B\subseteq A$.
* Für jede Formel $\varphi \in {\mathcal {L}}_{\mathfrak {A}}$ mit freien Variablen $x_{1},\dots ,x_{n}$ und jede Belegung dieser Variablen mit Elementen $b_{1},\dots ,b_{n}\in B$ gilt: ${\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 ${\mathcal {L}}_{\mathfrak {A}}$ um eine Konstantenmenge $\left\{{\dot {a}}|a\in A\right\}$, dann gilt ${\mathfrak {A\equiv B}}$ für die erweiterten Strukturen (wenn jeweils die Konstante ${\dot {a}}$ durch $a\,$ belegt wird), d. h. die erweiterten Strukturen sind elementar äquivalent.
Ist $\Phi :{\mathfrak {B\hookrightarrow A}}$ ein Monomorphismus, d. h. ein injektiver starker Homomorphismus, dessen Bild ${\mathfrak {\widehat {B}}}$ eine elementare Unterstruktur von ${\mathfrak {A}}$ ist, dann nennt man $\Phi$ eine elementare Einbettung.
Die Ausdrucksweise „Es gibt eine elementare Erweiterung von ${\mathfrak {A}}$“ wird auch verwendet, wenn es eine Struktur ${\mathfrak {B}}$ und eine elementare Einbettung ${\mathfrak {A\to B}}$ gibt.
Eine Theorie ${\mathcal {T}}$ heißt modellvollständig, wenn für zwei Modelle von ${\mathcal {T}}$ gilt: aus ${\mathfrak {B\subseteq A}}$ folgt ${\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 ${\mathfrak {A}}$ eine beliebige (unendliche) Struktur und ${\mathcal {L}}_{A}$ die zugehörige Sprache, dann gibt es für alle Kardinalitäten $\kappa$ mit $\operatorname {card} ({{\mathcal {L}}_{A}})\leq \kappa \leq \operatorname {card} (A)$ eine elementare Substruktur ${\mathfrak {B\prec A}}$ mit $\operatorname {card} (B)=\kappa$
** („aufwärts“) Für alle $\kappa \geq \max(\operatorname {card} ({{\mathcal {L}}_{A}},\operatorname {card} (B))$ gibt es eine elementare Erweiterung ${\mathfrak {B\succ A}}$.
    → Hauptartikel: Satz von Löwenheim-Skolem
* Ist $\operatorname {card} (A)$ endlich, dann hat ${\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 ${\mathfrak {B\prec A}}$ prüfen kann. Zum Nachweis von ${\mathfrak {B\prec A}}$ muss man zeigen, dass jede in ${\mathfrak {A}}$ für Elemente aus $B$ geltende Formel auch schon in ${\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 $A$ zu Elementen aus $B$ gibt, muss es ja nicht schon in der kleineren Menge $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:
Tarski-Vaught-Test: Es gilt ${\mathfrak {B\prec A}}$ genau dann, wenn ${\mathfrak {B}}\subset {\mathfrak {A}}$, das heißt ${\mathfrak {B}}$ ist Unterstruktur von ${\mathfrak {A}}$, und es gilt
* Für alle natürlichen Zahlen $n$ und alle Formeln $\varphi =\varphi (v_{0},\ldots ,v_{n})$ mit freien Variablen in $v_{0},\ldots ,v_{n}$ und alle $n$-Tupel $(b_{1},\ldots ,b_{n})\in B^{n}$ gilt: Wenn ${\mathfrak {A}}\models \exists x\varphi (x,b_{1},\ldots ,b_{n})$, dann gibt es ein $b\in B$ mit ${\mathfrak {A}}\models \varphi (b,b_{1},\ldots ,b_{n})$.

## Beispiele

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