Modelltheorie

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Racine carrée bleue.svg
Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen.

Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion! (Artikel eintragen)

Die Modelltheorie ist ein Teilgebiet der mathematischen Logik. Inhalt der Modelltheorie sind die Beziehungen zwischen den rein formalen Ausdrücken einer Sprache (syntaktische Ebene) und deren Bedeutung (semantische Ebene). Diese Beziehung wird über sogenannte Interpretationen und eine als Erfüllungsrelation bezeichnete mathematische Relation hergestellt.

Ganz allgemein gesprochen beschäftigt sich die Modelltheorie mit der Konstruktion und der Klassifikation von allen (möglichen) Strukturen und Klassen von Strukturen, im Besonderen mit solchen Strukturen, die axiomatisierbaren Sprachen oder Theorien entsprechen. Dabei geht es u. a. um die Aufgabe, Modelle für ein vorgegebenes Axiomensystem zu konstruieren -- oft geht es um Modelle mit zusätzlichen Eigenschaften, die im Axiomensystem aber nicht spezifiziert werden können, z. B. die Kardinalität des Modells. Weiterhin beschäftigt sich die Modelltheorie mit der Äquivalenz von Modellen, etwa der Frage, ob in ihnen die gleichen Aussagen gelten, und der Frage, wie viele (nichtisomorphe) Modelle eines Axiomensystems es gibt.

Grundbegriffe der Modelltheorie[Bearbeiten | Quelltext bearbeiten]

Ein Modell im Sinn der Modelltheorie ist eine mit einer gewissen Struktur versehene Menge (Universum, Individuenbereich, Trägermenge oder Domäne genannt), auf die eine Menge von Aussagen zutrifft.

Dass die Trägermenge eine Struktur habe, bedeutet, dass gewisse Relationen auf definiert sind, also Teilmengen kartesischer Produkte . Das Tupel aus Universum und den Relationen heißt Struktur. Eine Struktur heißt Modell einer Aussage, falls die Aussage als eine Aussage über die Struktur interpretierbar ist und dort erfüllt wird.

Beispiel. Zu den einfachsten Strukturen zählen Graphen. Ein Graph ist ein Tupel mit . Das Universum wäre hier und die (in diesem Fall einzige) Relation wäre . Um eine Aussage wie „Julian und Chelsea sind Freunde“ in zu interpretieren, könnte man (in diesem Fall müsste man, da es keine andere Relation gibt) als Freundschaftsrelation interpretieren; Julian und Chelsea müssten mit Individuen aus dem Universum indentifiziert werden. Falls dann , wäre die Aussage in der Struktur erfüllt und wäre ein Modell für die Aussage. Falls aber leer wäre, gäbe es keine Möglichkeit, so zu wählen, dass sie Freunde sind, und die Aussage wäre in dieser Struktur nicht erfüllt.

Allgemeiner wird nicht nur eine Aussage, sondern eine Menge von Aussagen in einer Sprache betrachtet. Die Modelltheorie beschäftigt sich mit der Frage, welche Modelle jede Aussage der Menge erfüllen bzw. ob die Menge überhaupt ein Modell hat.

Signatur[Bearbeiten | Quelltext bearbeiten]

Eine Signatur ist eine Menge von Relationensymbolen über eine gegebene Menge und eine Funktion, die jedem Relationsymbol eine Stelligkeit zuordnet und angibt, ob die Relation eine Funktion ist. Ist die Relation linkstotal und rechtseindeutig, spricht man von Funktionen. Elemente einstelliger Relationen heißen Konstante.

Struktur[Bearbeiten | Quelltext bearbeiten]

Sei eine Signatur. Eine -Struktur ist ein Tupel bestehend aus:

  • einer nichtleeren Menge , dem Universum,
  • einer k-stelligen Relation für jedes k-stellige Relationssymbol ,
  • einer k-stelligen Funktion für jedes k-stellige Funktionssymbol ,
  • einem Element für jedes Konstantensymbol .

Interpretation[Bearbeiten | Quelltext bearbeiten]

Sei eine Sprache mit Variablen, Eigennamen, Termen und Prädikaten. Eine Interpretation von in einer Struktur ist eine Zuordnung

  • der Variablen auf das Universum von ,
  • der Individuennamen auf auf die Konstanten von ,
  • der Terme auf die Funktionen von ,
  • der Prädikate auf die übrigen Relationen von ,

die jeweils in vorkommen.

Eine Interpretation ist also möglich, falls die Sprache zur Signatur passt. Durch die Interpretation wird zu einer Aussage über die Struktur .

Modell[Bearbeiten | Quelltext bearbeiten]

Sei eine beliebige Sprache und eine Teilmenge der Sprache. Eine Struktur heißt Modell von , falls es eine Interpretation gibt, sodass jedes Element aus einer Aussage entspricht, die in der Struktur erfüllt ist.

Modelltheoretische Folgerung[Bearbeiten | Quelltext bearbeiten]

Die Modelltheorie beschäftigt sich damit, welche Modelle es für Aussagenmengen in einer gegebenen Sprache gibt. Umgekehrt kann man die Frage stellen, welche Aussagen einer Sprache in einem Modell wahr sind.

Man sagt, eine Aussage folge modelltheoretisch aus einer Aussage , falls jedes Modell von auch ein Modell für ist. Symbolisch: .

Die Folgerungsrelation wird dann auf beliebige Aussagemengen erweitert: Eine Aussagenmenge folgt modelltheoretisch aus einer Aussagenmenge , falls jedes Modell von ein Modell für ist. Symbolisch: .

Unter der Theorie eines Modells versteht man die Menge aller Aussagen, die in ihm gelten. Jede Theorie eines Modells ist vollständig, das heißt, zu jeder Aussage ist entweder oder .

Zur Geschichte der Modelltheorie[Bearbeiten | Quelltext bearbeiten]

Die Ursprünge der Modelltheorie finden sich in der Algebra des 19. Jahrhunderts, so wie sie im umfangreichen Werk von Ernst Schöder: Vorlesungen über die Algebra der Logik (1890-1905) dargestellt wird. Zentral war der Individuenbereich (damals auch Denkbereich genannt), auf den man einen algebraisch Ausdruck anwandte. Aber der Begriff blieb undefiniert. Diese Tradition setzte sich selbst bei logisch-axiomatisch veranlagten Mathematikern wie Ernst Zermelo fort, der bei der Axiomatisierung der Mengenlehre den Begriff Individuenbereich ebenfalls ohne Definition lässt, obwohl seine Axiomatisierung auf dem Begriff gründete. Selsbt Albert Thoralf Skolem, der einige Begriffe Zermelos zu präzisieren sucht, verwendete den Begriff ohne weitere Erklärung.

Der wohl erste Versuch einer Formalisierung findet sich bei Rudolf Carnap. Aber die moderne Modelltheorie weicht in wichtigen Punkten von seiner Auffassung ab. Er bezog Modelle (wie damals üblich) auf Axiomensysteme und nicht auf Aussagenmengen, sodass ein Axiomensystem schon dann ein Modell hatte, wenn die Axiome des Systems erfüllt sind. Das ist aus wichtigen Gründen in der modernen Auffassung nicht mehr notwendig. Carnap verstand unter einem Modell für die axiomatischen Grundzeichen eines gegebenen Axiomensystems bezüglich eines gegebenen Individuenbereichs Folgendes: eine Bewertung für diese Zeichen derart, dass sowohl der Bereich wie auch die Bewertung ohne Gebrauch deskriptiver Konstanten angegeben wird. Ein Modell für die Grundzeichen heißt ein Modell für ein Axiomensystem, wenn es alle Axiome erfüllt, d. h. wahr macht.[1]

Der Durchbruch zum modernen Verständnis kam durch Alfred Tarski, der die Semantik eines Axiomensystems von seiner Syntax trennte. Dadurch konnte der Fall eintreten, dass Strukturen jedes Axiom erfüllen, aber das Axiomensystem dennoch kein Modell hat, nämlich dann, wenn das Kalkül des Systems inkorrekt ist. Diese Trennung von Syntax und Semantik führte zur Unterscheidung der modelltheoretischen Folgerung auf semantischer Ebene und der [[[Ableitung_(Logik)|logischen Ableitung]] auf syntaktischer Ebene, die heute den status der Modelltheorie als eigenständige Theorie begründet.

Zur Bedeutung von Modellen[Bearbeiten | Quelltext bearbeiten]

  • Eine Axiomenmenge lässt sich oft einfacher als Theorie eines Modells angeben als in einer aufzählenden Form.
  • Die Existenz eines Modells beweist, dass sich die Axiome nicht widersprechen, sie sind also konsistent. Eine Logik hat die Eigenschaft der Vollständigkeit, falls umgekehrt jede konsistente Aussagenmenge ein Modell hat (dies gilt für die Prädikatenlogik erster Stufe, siehe weiter unten).
  • Existieren sowohl Modelle mit einer gewissen Eigenschaft als auch solche, die diese Eigenschaft nicht haben, so ist damit die logische Unabhängigkeit der Eigenschaft von den Axiomen bewiesen, d. h., diese Eigenschaft folgt nicht aus den Axiomen und lässt sich auch nicht auf Grundlage der Axiome widerlegen.

Beispiele für Modelle[Bearbeiten | Quelltext bearbeiten]

Dichte Ordnungen[Bearbeiten | Quelltext bearbeiten]

Die geordnete Menge der rationalen Zahlen ist ein Modell für die Axiome der dichten offenen strengen Totalordnungen:

  1. (Trichotomie)
  2. (Antisymmetrie)
  3. (Transitivität)
  4. (Offenheit)
  5. (Dichtheit)

Die geordnete Menge der reellen Zahlen und alle Teilmengen der reellen Zahlen, die die rationalen Zahlen enthalten, sind Modelle. Die Theorie der dichten offenen strengen Totalordnungen ist ein Standardbeispiel in der Modelltheorie. Sie hat u. a. folgende Eigenschaften:

  • Sie ist endlich axiomatisierbar, hat aber keine endlichen Modelle.
  • Sie ist vollständig und modellvollständig.
  • Alle abzählbaren Modelle sind isomorph (zum Beweis), in überabzählbaren Kardinalzahlen gibt es nicht isomorphe Modelle. In der Sprache der Modelltheorie heißt das: Sie ist -kategorisch, aber nicht kategorisch in überabzählbaren Kardinalzahlen: Ist eine überabzählbare Kardinalzahl, so hat diese Theorie nicht-isomorphe Modelle der Mächtigkeit .
  • Sie ist der (eindeutig bestimmte) Modellbegleiter der Theorie der linearen Ordnung.
  • Sie besitzt mit den rationalen Zahlen ein Primmodell. (Das ist ein Modell, das in jedes andere Modell elementar eingebettet werden kann.)
  • Jedes Modell ist atomar.
  • Sie hat Quantorenelimination.
  • Sie ist nicht stabil.

Einelementige Universen[Bearbeiten | Quelltext bearbeiten]

Das einelementige Universum, das nur die Konstante c enthält, ist ein Modell für das Axiom über der Signatur .

Ein Beispiel für zweielementige Modelle[Bearbeiten | Quelltext bearbeiten]

Wie kann ein Modell für die folgende Menge von Aussagen über aussehen? ( sei eine Konstante, sei eine zweistellige Relation)

Die erste Aussage bestimmt, dass das Universum maximal zwei Elemente enthält, die zweite und dritte Aussage zusammen gelten nur, wenn es zwei Elemente enthält. Es gibt bis auf Isomorphie nur zwei Modelle (wobei wir das Universum zugrunde legen):

und

Das Modell

ist isomorph zu . (Es gibt eine Isomorphie, die auf abbildet und auf .)

Nichterfüllbare Axiome[Bearbeiten | Quelltext bearbeiten]

Die Aussagenmenge

ist nicht erfüllbar, das heißt, sie hat kein Modell.

Wichtige Sätze der Modelltheorie[Bearbeiten | Quelltext bearbeiten]

Es konnten Kriterien gefunden werden, die die Existenz von Modellen garantieren.

  • So besagt etwa der Gödelsche Vollständigkeitssatz, dass jede syntaktisch konsistente Theorie (also jede Menge von geschlossenen Formeln, aus der kein logischer Widerspruch herleitbar ist) ein Modell hat.
  • Der Kompaktheitssatz besagt, dass ein (unendliches) Axiomensystem genau dann ein Modell hat, falls jedes endliche Teilsystem ein Modell hat.
  • Der Satz von Löwenheim-Skolem sagt darüber hinaus aus, dass jede Theorie (in einer abzählbaren Sprache der Prädikatenlogik), die überhaupt ein unendliches Modell hat, auch ein Modell jeder unendlichen Kardinalität hat.

Endliche Modelltheorie[Bearbeiten | Quelltext bearbeiten]

Die Endliche Modelltheorie ist ein Teilbereich der Modelltheorie, der auf die Eigenschaften logischer Sprachen (wie etwa der Prädikatenlogik) sowie auf endliche Strukturen wie etwa endliche Gruppen, Graphen und die meisten Maschinenmodelle fokussiert ist. Ein Schwerpunkt liegt dabei insbesondere in den Beziehungen zwischen logischen Sprachen und der Berechenbarkeitstheorie. Weiterhin bestehen enge Bezüge zur diskreten Mathematik, zur Komplexitätstheorie und zur Theorie der Datenbanken.

Typische Fragen in der endlichen Modelltheorie sind, zu welchen Kardinalitäten sich für ein gegebenes Axiomensystem Modelle schaffen lassen. So ist diese Frage für die Körperaxiome vollständig geklärt: Primzahlen und Primzahlpotenzen sind die alleinigen Kardinalitäten endlicher Modelle. Diese Menge natürlicher Zahlen heißt dann Spektrum der Körperaxiome.

Es ist bisher ungeklärt, ob das Komplement eines Spektrums stets wieder ein Spektrum ist: Gesucht ist also eine Axiomenmenge dergestalt, dass alle endlichen Modelle eine Kardinalität im Komplement des Spektrums besitzen. Diese Frage hängt auch mit dem P-NP-Problem aus der Komplexitätstheorie zusammen.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • C. C. Chang, H. J. Keisler: Model Theory, Studies in Logic and the Foundations of Mathematics, Band 73, Elsevier Science 1990, ISBN 0-444-88054-2
  • David Marker: Model Theory: an introduction, Springer Verlag New York 2002, ISBN 9780387987606
  • Alexander Prestel: Einführung in die Mathematische Logik und Modelltheorie. Vieweg, Braunschweig 1986. (Vieweg-Studium; 60: Aufbaukurs Mathematik). ISBN 3-528-07260-1
  • Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5
  • Wolfram Schwabhäuser: Modelltheorie I BI Hochschultaschenbücher Band 813, Bibliographisches Institut Mannheim 1971
  • Wolfram Schwabhäuser: Modelltheorie II BI Hochschultaschenbücher Band 815, Bibliographisches Institut Mannheim 1972
  • Herbert Stachowiak: Allgemeine Modelltheorie, Springer Verlag, Wien, New York 1973, ISBN 3-211-81106-0

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Carnap, Rudolf: Einführung in die symbolische Logik. Springer, Wien, New York, 3. Aufl. 1968, S. 174