Elementare Unterstruktur

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

Eine Struktur $𝔅$ ist elementare Unterstruktur der Struktur $𝔄$, wenn sie Unterstruktur im algebraischen Sinn ist und für ihre Elemente in beiden Strukturen die gleichen Aussagen gelten.

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

Präzisierung

$𝔄$ soll eine beliebige Struktur sein und ${ℒ}_{𝔄}$ die Sprache, die die entsprechenden Funktions-, Relations- und Konstantensymbole zur Signatur von $𝔄$ enthält und $𝔅$ eine Struktur mit gleicher Signatur.

Dann ist die Aussage „$𝔅$ ist eine elementare Unterstruktur von $𝔄$“ durch folgende beiden Bedingungen definiert:

• für die Trägermengen gilt $B\subseteq A$.
• Für jede Formel $\phi \in {ℒ}_{𝔄}$ mit freien Variablen $x_1,\dots ,x_n$ und jede Belegung dieser Variablen mit Elementen $b_1,\dots ,b_n\in B$ gilt: $𝔄\models \phi (b_1,\dots ,b_n)⟺𝔅\models \phi (b_1,\dots ,b_n)$

Man kann die zweite Bedingung auch so ausdrücken:

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

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

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

Eine Theorie $𝒯$ heißt modellvollständig, wenn für zwei Modelle von $𝒯$ gilt: aus $𝔅\mathfrak{\subseteq }𝔄$ folgt $𝔅\mathfrak{\prec }𝔄$.

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 $𝔄$ eine beliebige (unendliche) Struktur und ${ℒ}_A$ die zugehörige Sprache, dann gibt es für alle Kardinalitäten $\kappa$ mit $\mathrm{card}({ℒ}_A)\le \kappa \le \mathrm{card}(A)$ eine elementare Substruktur $𝔅\mathfrak{\prec }𝔄$ mit $\mathrm{card}(B)=\kappa$
  • („aufwärts“) Für alle $\kappa \ge \max (\mathrm{card}({ℒ}_A,\mathrm{card}(B))$ gibt es eine elementare Erweiterung $𝔅\mathfrak{\succ }𝔄$.

Vorlage:Hauptartikel

• Ist $\mathrm{card}(A)$ endlich, dann hat $𝔄$ 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{\prec }𝔄$ prüfen kann. Zum Nachweis von $𝔅\mathfrak{\prec }𝔄$ muss man zeigen, dass jede in $𝔄$ für Elemente aus $B$ geltende Formel auch schon in $𝔅$ 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{\prec }𝔄$ genau dann, wenn $𝔅\subset 𝔄$, das heißt $𝔅$ ist Unterstruktur von $𝔄$, und es gilt

• Für alle natürlichen Zahlen $n$ und alle Formeln $\phi =\phi (v_0,\dots ,v_n)$ mit freien Variablen in $v_0,\dots ,v_n$ und alle $n$-Tupel $(b_1,\dots ,b_n)\in B^n$ gilt: Wenn $𝔄\models \mathrm{\exists }x\phi (x,b_1,\dots ,b_n)$, dann gibt es ein $b\in B$ mit $𝔄\models \phi (b,b_1,\dots ,b_n)$.

Beispiele

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

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