Theorie (Logik)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In der mathematischen Logik ist eine Theorie (der Prädikatenlogik erster Stufe) eine Menge von Aussagen über einer Signatur.

Eine Menge von Aussagen heißt deduktiv abgeschlossen, wenn alle Aussagen, die daraus abgeleitet werden können, schon zu gehören. Als Formel:

Wenn eine Sprache ist, so ist eine Theorie eine deduktiv abgeschlossene Menge von Aussagen über dieser Sprache.

(Bemerkung: Die Definitionen sind in der Literatur nicht einheitlich. Zum Teil wird nicht verlangt, dass eine Theorie deduktiv abgeschlossen ist.)[1]

Eine Menge von Aussagen ist ein Axiomensystem für eine Theorie, wenn diese Theorie der deduktive Abschluss des Axiomensystems ist.

Theorie einer Struktur

[Bearbeiten | Quelltext bearbeiten]

Die Theorie einer Struktur wird notiert als . Sie enthält alle Sätze, die für gelten, das heißt, für die ein Modell ist. Als Formel:

.[2]

Wenn eine Struktur ist, so ist deduktiv abgeschlossen.

  • Die Mächtigkeit einer Theorie ist ihre Mächtigkeit als Menge, mindestens aber abzählbar.
  • Eine Theorie ist konsistent, wenn sie nicht jeden Satz enthält. (Das ist dazu äquivalent, dass sie keinen Satz der Form „“ enthält.)
  • Die Theorie ist vollständig, wenn sie für jede Aussage entweder sie oder ihre Negation enthält.
  • Die Theorie ist endlich axiomatisierbar, wenn sie der deduktive Abschluss einer endlichen Menge von Aussagen ist.
  • Eine Theorie ist modellvollständig, wenn sich daraus, dass ein Modell in dem anderen liegt, dieses dann auch elementar in dem anderen liegt.
  • Eine Theorie hat Quantorenelimination, wenn sie der deduktive Abschluss einer Menge von Formeln ist, die ohne Quantoren gebildet wurde.
  • Eine Theorie ist kategorisch in einer Kardinalzahl , wenn sie bis auf Isomorphie nur ein Modell der Mächtigkeit hat.
  • Eine vollständige Theorie heißt klein oder schmal, wenn für alle abzählbar ist. ( ist die Menge alle vollständigen Typen in Variablen.)

Wichtige Sätze über Theorien sind:

Der Gödelsche Vollständigkeitssatz:

  • Jede konsistente Theorie hat ein Modell.

Der Satz von Löwenheim-Skolem:

  • Wenn eine Theorie ein Modell in einer unendlichen Kardinalzahl hat, so hat sie auch eines in jeder Kardinalzahl größer oder gleich ihrer Mächtigkeit.

Der Satz von Morley:

  • Ist eine abzählbare Theorie in einer überabzählbaren Kardinalzahl kategorisch, so in jeder.

Die Theorie der Arithmetik der natürlichen Zahlen (oft kurz auch nur: Arithmetik) enthält alle Aussagen, die für die Struktur gelten.[3] Hierbei ist

die Menge der natürlichen Zahlen,
die Null,
die Additionsfunktion,
die Multiplikationsfunktion und
die Nachfolgefunktion.

Die Aussagen sind in der Sprache der Prädikatenlogik der ersten Stufe mit der Signatur formuliert, wobei das Symbol für die Null, das Symbol für die Nachfolgefunktion, das Symbol für die Multiplikation und das Symbol für die Addition ist. Nach dem Satz von Skolem gibt es neben dem Standard-Modell für die Theorie auch abzählbare Nicht-Standard-Modelle für .[4]

Peano-Arithmetik

[Bearbeiten | Quelltext bearbeiten]

Die Peano-Arithmetik ist die Theorie der Aussagen, die aus den folgenden noch zu formalisierenden Axiomen über der Symbolmenge der Sprache der Arithmetik folgen:

  • Null ist kein Wert der (Nachfolgerfunktion) S.
  • Die Nachfolgerfunktion ist injektiv
  • Für alle ist
  • Für alle ist
  • Für alle ist
  • Für alle ist

Zusätzlich ist noch für jede Formel die Induktionsformel mit ein Axiom:

( steht für )

Die Peano-Arithmetik ist eine echte Teilmenge der Arithmetik. In anderen Worten: die Peano-Arithmetik ist unvollständig, es gibt Aussagen in der Arithmetik die nicht aus den Axiomen der Peano-Arithmetik folgen. Die Arithmetik lässt sich nicht rekursiv aufzählen. Dies ist die Aussage des Unvollständigkeitssatzes.

Die Theorie der dichten linearen Ordnung ohne Endpunkte

[Bearbeiten | Quelltext bearbeiten]

Die Theorie der dichten linearen Ordnung ohne Endpunkte ist die Theorie von den rationalen Zahlen mit der Ordnungsrelation „<“. Die Axiome lauten im Einzelnen:

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

Sie hat unter anderem 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.

Die Theorie der algebraisch abgeschlossenen Körper (in der Charakteristik p oder 0)

[Bearbeiten | Quelltext bearbeiten]
  • Sie ist vollständig.
  • Sie hat ein Primmodell.
  • Sie ist -kategorisch, aber nicht kategorisch in einer überabzählbaren Kardinalzahl.
  • Sie hat Quantorenelimination.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Chang, Chen C., Keisler, H.Jerome: Model Theory. Amsterdam [u. a.], North-Holland, 1998, S. 12
  2. Heinz-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas. Einführung in die mathematische Logik. 6. überarbeitete und erweiterte Auflage. Springer Spektrum, 2018. doi:10.1007/978-3-662-58029-5. Seite 99
  3. Heinz-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas. Einführung in die mathematische Logik. 6. überarbeitete und erweiterte Auflage. Springer Spektrum, 2018. doi:10.1007/978-3-662-58029-5. Seiten 52 und 101
  4. Heinz-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas. Einführung in die mathematische Logik. 6. überarbeitete und erweiterte Auflage. Springer Spektrum, 2018. doi:10.1007/978-3-662-58029-5. Seite 101
  • H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5
  • Wilfrid Hodges: Model theory. Cambridge University Press, 1993, ISBN 0-521-30442-3.
  • Chang, Chen C., Keisler, H.Jerome: Model Theory. Amsterdam [u. a.], North-Holland, 1998.
  • Prestel, Alexander: Einführung in die Mathematische Logik und Modelltheorie. Vieweg, Braunschweig 1986. (Vieweg-Studium; 60: Aufbaukurs Mathematik), ISBN 3-528-07260-1. 286 S.
  • Philipp Rothmaler: Einführung in die Modelltheorie. Spektrum Akademischer Verlag, 1995, ISBN 978-3-86025-461-5.