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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ B \prec A }} prüfen kann. Zum Nachweis von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ B \prec A }} muss man zeigen, dass jede in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ A }} für Elemente aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} geltende Formel auch schon in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} zu Elementen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} gibt, muss es ja nicht schon in der kleineren Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Tarski-Vaught-Test: Es gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ B \prec A }} genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ B } \subset \mathfrak{ A }} , das heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ B }} ist Unterstruktur von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ A }} , und es gilt

• Für alle natürlichen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} und alle Formeln Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi = \varphi(v_0,\ldots, v_n)} mit freien Variablen in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_0,\ldots, v_n} und alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Tupel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (b_1,\ldots, b_n) \in B^n} gilt: Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ A } \models \exists x \varphi (x,b_1,\ldots, b_n)} , dann gibt es ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b \in B} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ A } \models \varphi (b,b_1,\ldots, b_n)} .

Beispiele

• Betrachtet man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Q} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R} als reine Ordnungsstrukturen, dann gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Q \prec \R} . Elementare Unterstrukturen müssen schon aus Kardinalitätsgründen nicht isomorph zur Ausgangsstruktur sein.
• Andererseits ist aber Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Q \not\prec \R} , wenn man beide als Ringe betrachtet. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[ \R \models \ \exists x: x^2 = 2 \right]} . Es kann also von der betrachteten Signatur abhängen, ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{ B \prec A}} gilt oder nicht.
• Bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2\Z} die Struktur der geraden Zahlen (als reine Ordnungsstruktur), dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2\Z \not\prec \Z} . Dies zeigt, dass eine isomorphe Unterstruktur nicht elementare Unterstruktur sein muss. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[ \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R} . (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