Theorie (Logik)

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

Definition

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

∀ϕ:(T⊢ϕ⇒ϕ∈T).

Wenn L 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.)

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

Theorie einer Struktur

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

Th⁡(M)={ϕ∣M⊨ϕ}.

Wenn M eine Struktur ist, so ist Th⁡(M) deduktiv abgeschlossen.

Eigenschaften

Allgemein

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

Modelltheorie

  • Eine Theorie ist modellvollständig, wenn daraus, dass ein Modell im anderen liegt, auch folgt, dass dieses dann elementar im 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 T heißt klein oder schmal, wenn Sn(T) für alle n abzählbar ist. (Sn(T) ist die Menge aller vollständigen Typen in n Variablen.)

Sätze

Wichtige Sätze über Theorien sind:

Der Gödelsche Vollständigkeitssatz:

Der Satz von Löwenheim-Skolem:

Der Satz von Morley:

Beispiele

Arithmetik

Die Theorie der Arithmetik der natürlichen Zahlen (oft kurz auch nur: Arithmetik) Th⁡(𝒩) enthält alle Aussagen, die für die Struktur 𝒩=(ℕ,0,s,+,⋅) gelten. Hierbei sind

ℕ die Menge der natürlichen Zahlen,
0∈ℕ die Null,
+:ℕ×ℕ→ℕ die Additionsfunktion,
⋅:ℕ×ℕ→ℕ die Multiplikationsfunktion und
s:ℕ→ℕ die Nachfolgerfunktion.

Die Aussagen sind in der Sprache der Prädikatenlogik der ersten Stufe mit der Signatur (0,S,+,⋅) formuliert, wobei 0 das Symbol für die Null, S das Symbol für die Nachfolgerfunktion, + das Symbol für die Addition und ⋅ das Symbol für die Multiplikation ist. Nach dem Satz von Skolem gibt es neben dem Standardmodell 𝒩 für die Theorie auch abzählbare Nichtstandardmodelle 𝒩′ für Th⁡(𝒩).

Peano-Arithmetik

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 n ist n+0=n.
  • Für alle n ist n+(Sm)=S(n+m).
  • Für alle n ist n⋅0=0.
  • Für alle n ist n⋅Sm=(n⋅m)+n.

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

  • ϕ(0,y→)∧∀x(ϕ(x,y→)→ϕ(Sx,y→))→∀xϕ(x,y→)
(y→ steht für y1,…,yk.)

Die Peano-Arithmetik ist eine echte Teilmenge der Arithmetik. Mit 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

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)∨(x=y)∨(y<x) (Trichotomie)
  2. (x<y)→¬(y<x) (Asymmetrie)
  3. (x<y)∧(y<z)→(x<z) (Transitivität)
  4. ∃y∃z:(x<y∧z<x) (Offenheit)
  5. x<y→∃z:(x<z∧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 (siehe 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 also κ eine überabzählbare Kardinalzahl, so hat diese Theorie 2κ 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)

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