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:

$\forall \phi \colon T\vdash \phi \rightarrow \phi \in 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 $\mathrm {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:

$\mathrm {Th} (M)=\{\phi \mid M\vDash \phi \}$.

Wenn $M$ eine Struktur ist, so ist $\mathrm {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 „$\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

• 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 $\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

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

Arithmetik

Die Theorie der Arithmetik der natürlichen Zahlen (oft kurz auch nur: Arithmetik) $\mathrm {Th} ({\cal {N}})$ enthält alle Aussagen, die für die Struktur ${\cal {N}}=(\mathbb {N} ,0,s,\cdot ,+)$ gelten. Hierbei ist

$\mathbb {N}$ die Menge der natürlichen Zahlen,

$0\in \mathbb {N}$ die Null,

$+:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ die Additionsfunktion,

$\cdot :\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ die Multiplikationsfunktion und

$s:\mathbb {N} \to \mathbb {N}$ die Nachfolgefunktion.

Die Aussagen sind in der Sprache der Prädikatenlogik der ersten Stufe mit der Signatur $(0,S,\cdot ,+)$ formuliert, wobei $0$ das Symbol für die Null, $S$ das Symbol für die Nachfolgefunktion, $\cdot$ 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 ${\cal {N}}$ für die Theorie auch abzählbare Nicht-Standard-Modelle ${\cal {N'}}$ für $\mathrm {Th} ({\cal {N}})$.

Peano-Arithmetik

→ Hauptartikel: 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\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 (Sx,{\vec {y}}))\rightarrow \forall x\phi (x,{\vec {y}})$

(${\vec {y}}$ steht für $y_{1},...,y_{k}$)

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

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)$ (Asymmetrie)
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)

• Die Theorie der algebraisch abgeschlossenen Körper ohne Angabe der Charakteristik ist modellvollständig, aber nicht vollständig.
• Für die Theorie der algebraisch abgeschlossenen Körper mit einer Angabe der Charakteristik gilt:

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

Literatur

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