Theorie (Logik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Definition[Bearbeiten]

Eine Menge von Aussagen T heißt deduktiv abgeschlossen, wenn für alle Aussagen \phi aus

T \vdash \phi

schon folgt, dass

\phi \in T.

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

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

Eine Menge von Aussagen ist eine Axiomenmenge für eine Theorie, wenn der deduktive Abschluss dieser Aussagen die Theorie ist.

Wenn M eine Struktur ist, so ist \mathrm{Th}(M)=\{\phi|M \Vdash \phi\} eine Theorie, da diese Menge deduktiv abgeschlossen ist.

Eigenschaften[Bearbeiten]

Allgemein[Bearbeiten]

  • 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 „\phi \wedge \neg \phi “ 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.

Modelltheorie[Bearbeiten]

  • 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 der deduktive Abschluss einer Menge von Formeln ist, die ohne Quantoren gebildet wurde.
  • Eine Theorie ist kategorisch in einer Kardinalzahl \kappa, wenn sie bis auf Isomorphie nur ein Modell der Mächtigkeit \kappa hat.
  • Eine vollständige Theorie T heißt klein oder schmal, wenn für alle n \ S_n(T) abzählbar ist. (S_n(T) ist die Menge alle vollständigen Typen in n Variablen.)

Sätze[Bearbeiten]

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.

Beispiele[Bearbeiten]

Die Theorie der natürlichen Zahlen[Bearbeiten]

Die Theorie der natürlichen Zahlen ist über der Sprache (0,S,\cdot,+) formuliert, die Axiome formalisieren folgende Aussagen:

  • Null ist kein Wert der (Nachfolgerfunktion) S.
  • Die Nachfolgerfunktion ist injektiv
  • Für alle n ist n+0=n
  • Für alle n ist n+1=Sn
  • Für alle n ist n+(Sm)=S(n+m)
  • Für alle n ist n \cdot 0 = 0
  • Für alle n ist n \cdot Sm = (n \cdot m) + n

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

  • \phi(0,\vec y) \land \forall x ( \phi(x,\vec y)\rightarrow\phi(x+1,\vec y)) \rightarrow \forall x \phi(x,\vec y)
(\vec y steht für y_1,...,y_k)

Die Theorie der natürlichen Zahlen ist unvollständig. Es gibt keine konsistente rekursiv aufzählbare Erweiterung der natürlichen Zahlen. Dies ist die Aussage des Unvollständigkeitssatzes.

Die Theorie der dichten linearen Ordnung ohne Endpunkte[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. (x < y) \vee (x = y) \vee (y < x) (Trichotomie)
  2. (x < y) \rightarrow \neg (y < x) (Antisymmetrie)
  3. (x < y) \wedge (y < z) \rightarrow (x < z) (Transitivität)
  4. \exists y,z: ( x < y, z < x ) (Offenheit)
  5. x < y \rightarrow \exists z(x < z \wedge z < y) (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 \omega-kategorisch, aber nicht kategorisch in überabzählbaren Kardinalzahlen: Ist \kappa eine überabzählbare Kardinalzahl, so hat diese Theorie 2^{\kappa} nicht-isomorphe Modelle der Mächtigkeit \kappa.
  • 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]

  • Sie ist vollständig.
  • Sie hat ein Primmodell.
  • Sie ist \omega-kategorisch, aber nicht kategorisch in einer überabzählbaren Kardinalzahl.
  • Sie hat Quantorenelemination.

Einzelnachweise[Bearbeiten]

  1. Chang, Chen C., Keisler, H.Jerome: Model Theory. Amsterdam [u.a.], North-Holland, 1998, S. 12

Literatur[Bearbeiten]

  • 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.