Elementare Unterstruktur

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Tarski-Vaught-Test)
Zur Navigation springen Zur Suche springen

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

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 (oder ; oft wird auch und geschrieben).

Präzisierung[Bearbeiten | Quelltext bearbeiten]

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 .
  • Für jede Formel mit freien Variablen und jede Belegung dieser Variablen mit Elementen gilt:

Man kann die zweite Bedingung auch so ausdrücken:

  • Erweitert man die Sprache um eine Konstantenmenge , dann gilt für die erweiterten Strukturen (wenn jeweils die Konstante durch belegt wird), d. h. die erweiterten Strukturen sind elementar äquivalent.

Ist ein Monomorphismus, d. h. ein injektiver starker Homomorphismus, dessen Bild eine elementare Unterstruktur von ist, dann nennt man eine elementare Einbettung.

Die Ausdrucksweise „Es gibt eine elementare Erweiterung von “ wird auch verwendet, wenn es eine Struktur und eine elementare Einbettung gibt.

Eine Theorie heißt modellvollständig, wenn für zwei Modelle von gilt: aus folgt .

Aussagen über elementare Substrukturen[Bearbeiten | Quelltext bearbeiten]

  • 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 die zugehörige Sprache, dann gibt es für alle Kardinalitäten mit eine elementare Substruktur mit
    • („aufwärts“) Für alle gibt es eine elementare Erweiterung .
  • Ist endlich, dann hat keine echten elementaren Unterstrukturen.

Tarski-Vaught-Test[Bearbeiten | Quelltext bearbeiten]

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 prüfen kann. Zum Nachweis von muss man zeigen, dass jede in für Elemente aus 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 zu Elementen aus gibt, muss es ja nicht schon in der kleineren Menge 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 genau dann, wenn , das heißt ist Unterstruktur von , und es gilt

  • Für alle natürlichen Zahlen und alle Formeln mit freien Variablen in und alle -Tupel gilt: Wenn , dann gibt es ein mit .

Beispiele[Bearbeiten | Quelltext bearbeiten]

  • Betrachtet man und als reine Ordnungsstrukturen, dann gilt . Elementare Unterstrukturen müssen schon aus Kardinalitätsgründen nicht isomorph zur Ausgangsstruktur sein.
  • Andererseits ist aber , wenn man beide als Ringe betrachtet. . Es kann also von der betrachteten Signatur abhängen, ob gilt oder nicht.
  • Bezeichnet die Struktur der geraden Zahlen (als reine Ordnungsstruktur), dann ist . Dies zeigt, dass eine isomorphe Unterstruktur nicht elementare Unterstruktur sein muss.
  • 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.)

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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[Bearbeiten | Quelltext bearbeiten]

  • 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