Vorlesung über Mathematische Logik^{1}

Martin Ziegler

Freiburg

SS 1997, SS 2000, WS 2003, SS 2007

1Version 7.10 (22.7.2008) Subversion: 69, 2008-07-22

Inhaltsverzeichnis

1 Prädikatenkalkül 3 1 Strukturen und Formeln . . . . . . . . . . . . . . . . . . . . . . . 3 2 Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Allgemeingültige Formeln . . . . . . . . . . . . . . . . . . . . . . 13 4 Der Gödelsche Vollständigkeitssatz . . . . . . . . . . . . . . . . . 16 5 Der Sequenzenkalkül . . . . . . . . . . . . . . . . . . . . . . . . . 25 6 Der Herbrandsche Satz und automatisches Beweisen . . . . . . . 30

2 Mengenlehre 38 7 Die Axiome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 8 Die natürlichen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . 46 9 Ordinalzahlen und Kardinalzahlen . . . . . . . . . . . . . . . . . 50 10 Metamathematik von ZFC . . . . . . . . . . . . . . . . . . . . . . 56

3 Rekursionstheorie 60 11 Registermaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . 60 12 Primitiv rekursive Funktionen und Gödelisierung . . . . . . . . . 66 13 Rekursiv aufzählbare Mengen . . . . . . . . . . . . . . . . . . . . 72 14 Gödelnummern von Formeln . . . . . . . . . . . . . . . . . . . . . 74 15 Ein anderer Aufbau der rekursiven Funktionen . . . . . . . . . . 76

4 Arithmetik 78 16 Definierbare Relationen . . . . . . . . . . . . . . . . . . . . . . . 78 17 Das System Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 18 Peanoarithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

19 Der Zweite Gödelsche Unvollständigkeitssatz . . . . . . . . . . . 91 Literaturverzeichnis 96 Index 97 Änderungen 102

Kapitel 1

Prädikatenkalkül

1 Strukturen und Formeln

Eine Struktur ist eine nicht–leere Menge mit ausgezeichneten Elementen, Operationen und Relationen. Zum Beispiel

ein Ring:  (R, 0, 1, +, −, ·)
eine Gruppe:  (G, e, ∘,^{−1})
die reellen Zahlen  (ℝ, 0, 1, +, −, · , <)
die natürlichen Zahlen 𝔑 = (ℕ, 0, S, +, · , <)

(S ist die Nachfolgeroperation x ↦ x + 1 .)

In diesen Beispielen sind die Relationen zweistellig und die Operationen ein– oder zweistellig. Im Allgemeinen sind beliebige positive Stelligkeiten erlaubt. Nicht alle Gegenstände der Mathematik sind Strukturen. Zum Beispiel ist die Klasse aller Gruppen mit der Isomorphie als zweistelliger Relation keine Struktur, weil der Grundbereich — die Klasse aller Gruppen — zu groß ist. Eine topologischer Raum ist keine Struktur, auf ihm ist vielmehr eine Menge von (offenen) Teilmengen ausgezeichnet.

Werden wir etwas präziser:

Definition Eine Struktur ist ein Paar 𝔄 = (A, J), wobei A eine nicht–leere Menge und J eine Familie von Elementen aus A und Operationen und Relationen auf A ist.

Die Struktur 𝔔 = (ℚ, 0, 1, +, −, ·) des Körpers der rationalen Zahlen müssen wir jetzt schreiben als (ℚ, (Z_{i})_{i<5}), wobei Z_{0} = 0, Z_{1} = 1, Z_{2} = +, Z_{3} = −, Z_{4} = ·. Wenn eine Frage, wie „ist (ℚ, 0, 1, ·, −, +) ein Körper“ sinnvoll sein soll, muß man festlegen, welche Operation die Addition und welche die Multiplikation sein soll. Der Ausgangspunkt ist also eine Sprache:

Definition Eine Sprache ist eine Menge von Konstantenzeichen^{1}, Funktionszeichen und Relationszeichen. Funktionszeichen und Relationszeichen haben eine (positive) Stelligkeit.

1Konstantenzeichen nennen wir auch einfach Konstanten.

Gelegentlich nennt man Relationszeichen, aber auch Relationen, Prädikate.

Eine Liste von Beispielen:

L_{∅} = ∅  Die leere Sprache
L_{R} = \{\underline{0}, \underline{1}, +, −, ·\} Die Ring–Sprache.
L_{G} = \{\underline{e}, ∘,^{−1}\}  Die Gruppen–Sprache.
L_{O} = {<}  Die Ordnungs–Sprache.
L_{AK} = L_{R} ∪ L_{O}  Die Angeordnete–Körper–Sprache.
L_{N} = \{\underline{0}, S, +, ·, <\} Die Sprache der natürlichen Zahlen.
L_{Me} = {ϵ}  Die Mengenlehre-Sprache.

Dabei sind

Konstanten:  \underline{0}, \underline{1}, \underline{e}
einstellige Funktionszeichen: −, ^{−1}, S
zweistellige Funktionszeichen: +, ·, ∘
zweistellige Relationszeichen: <, ϵ .

Definition Sei L eine Sprache. Eine L–Struktur ist ein Paar

𝔄 = (A, (Z^{𝔄})_{Z∈L}),

wobei

A  eine nicht–leere Menge (die Grundmenge von 𝔄 ) ist,
Z^{𝔄} ∈ A,  wenn Z eine Konstante ist,
Z^{𝔄} : A^{n} ⟶ A, wenn Z ein n–stelliges Funktionszeichen ist und
Z^{𝔄} ⊂ A^{n},  wenn Z ein n–stelliges Relationszeichen ist.

Definition Zwei L–Strukturen 𝔄 und 𝔅 heißen isomorph, 𝔄 ≅ 𝔅, wenn es einen Isomorphismus F : 𝔄 ⟶ 𝔅 gibt, eine Bijektion F : A ⟶ B, die mit den Interpretationen der Zeichen aus L kommutiert:

F (Z^{𝔄})  = Z^{𝔅}  (Z eine Konstante aus L)

F (Z^{𝔄}(a_{1}, …, a_{n})) = Z^{𝔅}(F (a_{1}), …, F (a_{n})) (Z ein n–stelliges Funktionszeichen aus L, a_{1}, …, a_{n} ∈ A)

R^{𝔄}(a_{1}, …, a_{n}) ⇔ R^{𝔅}(F (a_{1}), …, F (a_{n})) (Z ein n–stelliges Relationszeichen aus L, a_{1}, …, a_{n} ∈ A)

Das Inverse eines Isomorphismus und die Verknüpfung von zwei Isomorphismen ist wieder ein Isomorphismus. Daraus folgt, daß ≅ eine Äquivalenzrelation ist.

Wir fixieren ein Folge von Variablen v_{0}, v_{1}, . . ..

Definition Ein L–Term ist eine Zeichenfolge, die nach den folgenden Regeln gebildet ist:

T1 Jede Variable ist ein L–Term.

T2 Jede Konstante aus L ist ein L–Term.

T3 Wenn f ein n–stelliges Funktionszeichen aus L ist und wenn t_{1}, …, t_{n} L– Terme sind, dann ist auch ft_{1} … t_{n} ein L–Term.

Um Terme besser lesbar zu machen, schreiben wir häufig f(t_{1}, …, t_{n}) statt ft_{1} … t_{n}. Wenn f einstellig ist, auch t_{1}f, wenn f zweistellig ist, auch t_{1}ft_{2}. Zum Beispiel steht (x + y) · (z + w) für · + xy + zw und (x ∘ y)^{−1} für ^{−1} ∘ xy.

Das folgende Lemma zeigt, weshalb wir auf Klammern verzichten können. Übrigens würde der Gebrauch von Klammern den Beweis nicht einfacher machen.

Lemma 1.1 (Eindeutige Lesbarkeit von Termen) Für jeden L–Term t tritt genau einer der folgenden drei Fälle ein:

1. t ist eine Variable,

2. t ist eine Konstante,

3. t = ft_{1} … t_{n}, wobei f ein n–stelliges Funktionszeichen und t_{1}, …, t_{n} L– Terme sind.

Im letzten Fall sind f und t_{1}, …, t_{n} eindeutig bestimmt.

Beweis: Daß genau einer der drei Fälle eintritt ist klar. Zu zeigen ist die Eindeutigkeit der t_{i}. Wenn t = es_{1} … s_{m} für ein m–stelliges Funktionszeichen e und Terme s_{i}, ist klar, daß e = f und m = n. Daß s_{i} = t_{i}, folgt aus dem nächsten Hilfssatz.^{2} □

Hilfssatz Kein L–Term ist echtes Anfangsstück eines anderen L–Terms.

Beweis: Sei s Anfangsstück von t. Wir zeigen s = t durch Induktion über die Länge von t. Wenn t eine Variable oder eine Konstante ist, ist die Behauptung klar. Sonst ist s = fs_{1} … s_{n} und t = ft_{1} … t_{n} für ein n–stelliges Funktionszeichen f. Wenn s ≠ t, gibt es einen kleinsten Index i mit s_{i} ≠ t_{i}. s_{i} ist dann echtes Anfangsstück von t_{i}, oder umgekehrt, was nach Induktionsvoraussetzung unmöglich ist. □

L–Formeln sind Zeichenreihen, die aus den Zeichen aus L, den Klammern ( und ) als Hilfszeichen und den folgenden logischen Zeichen gebildet ist:

2Oder vielmehr aus seinem Beweis.

Variable  v_{0}, v_{1}, …
Gleichheitszeichen =^{.}
Junktoren  ¬ (Negation), ∧ (Konjunktion)
Existenzquantor  ∃

Man liest =^{.} als „gleich“, ¬ als „nicht“, ∧ als „und“ und ∃ als „es gibt ein“.

Definition Eine L–Formel ist

F1 t_{1} =^{.} t_{2} , wenn t_{1}, t_{2} L–Terme sind,

F2 Rt_{1} …, t_{n}  , wenn R ein n–stelliges Relationszeichen aus L und t_{1}, …, t_{n} L–Terme sind,

F3 ¬ ψ , wenn ψ eine L–Formel ist,

F4 (ψ_{1} ∧ ψ_{2}) ,wenn ψ_{1} und ψ_{2} L–Formeln sind,

F5 ∃x ψ ,wenn ψ eine L–Formel und x eine Variable ist.

Formeln der Form F1 und F2 heißen Primformeln^{3}.

Wir verwenden folgende Abkürzungen:

(ψ_{1} ∨ ψ_{2}) = ¬ (¬ ψ_{1} ∧ ¬ ψ_{2})
(ψ_{1} → ψ_{2}) = ¬ (ψ_{1} ∧ ¬ ψ_{2})
(ψ_{1} ↔ ψ_{2}) = ((ψ_{1} → ψ_{2}) ∧ (ψ_{2} → ψ_{1}))
∀x ψ = ¬ ∃x¬ ψ
(ψ_{0} ∧ ⋯ ∧ ψ_{n}) = \underbrace{(… (}_{n -mal} ψ_{0} ∧ ψ_{1}) ∧ … ψ_{n})
(ψ_{0} ∨ ⋯ ∨ ψ_{n}) = \underbrace{(… (}_{n -mal} ψ_{0} ∨ ψ_{1}) ∨ … ψ_{n})

Die Disjunktion ∨ liest man als „oder“, die Implikation → als „impliziert“, die Äquivalenz ↔ als „genau dann , wenn“ und den Allquantor ∀ als „für alle“.

Statt Rt_{1}t_{2} schreiben wir auch t_{1}Rt_{2} und statt ∃x_{1} … ∃x_{n} schreiben wir ∃x_{1} … x_{n} (ebenso für ∀). Zur besseren Lesbarkeit der Formeln gebrauchen wir überflüssige Klammern. Wir lassen auch Klammern weg und lesen die Formeln gemäß der Bindungsstärke der logischen Zeichen:

Höchste Bindungsstärke:  ¬ ∃ ∀
∧
∨
Niedrigste Bindungsstärke:  → ↔

Zum Beispiel steht ¬ ϕ ∧ ψ → χ für

((¬ ϕ ∧ ψ) → χ) = ¬ ((¬ ϕ ∧ ψ) ∧ ¬ χ).

3Man nennt Primformeln auch atomar.

Als Beispiel schreiben wir in L_{R} die Körperaxiome auf. Beachte, daß das erste Axiom zum Beispiel voll ausgeschrieben

¬ ∃v_{0}¬ ¬ ∃v_{1}¬ + v_{0}v_{1} =^{.} +v_{1}v_{0}

ist. x, y, z stehen für die Variablen v_{0}, v_{1}, v_{2}. \underline{Die Körperaxiome}.

1. ∀x, y x + y =^{.} y + x

2. ∀x x + \underline{0} =^{.} x

3. ∀x x + (−x) =^{.} \underline{0}

4. ∀x, y, z (x + y) + z =^{.} x + (y + z)

5. ∀x, y x · y =^{.} y · x

6. ∀x x · \underline{1} =^{.} x

7. ∀x, y, z (x · y) · z =^{.} x · (y · z)

8. ∀x, y, z x · (y + z) =^{.} (x · y) + (x · z)

9. ∀x (¬ x =^{.} \underline{0} → ∃y x · y =^{.} \underline{1})

10. ¬ \underline{0} =^{.} \underline{1}

Die ersten acht Axiome drücken aus, daß ein Körper insbesondere ein kommutativer Ring mit Einselement ist. Die ersten vier Axiome sagen, daß einem Ring eine additive geschriebene abelsche Gruppe zugrunde liegt. Lemma 1.2 Für jede L–Formel ϕ tritt genau einer der folgenden Fälle ein.

1. ϕ = t_{1} =^{.} t_{2} für L–Terme t_{1}, t_{2}

2. ϕ = Rt_{1} … t_{n}  für ein n–stelliges Relationszeichen R aus L und L–Terme t_{1}, …, t_{n}

3. ϕ = ¬ ψ für eine L–Formel ψ

4. ϕ = (ψ_{1} ∧ ψ_{2}) für L–Formeln ψ_{1} und ψ_{2}

5. ϕ = ∃x ψ für eine L–Formel ψ und eine Variable x

In jedem der Fälle sind die Terme t_{i}, das Relationszeichen R, die Formeln ψ, ψ_{1}, ψ_{2} und die Variable x jeweils eindeutig bestimmt.

Beweis: Daß genau einer der fünf Fälle auftritt ist klar. Sie treten ein je nachdem, ob das erste Zeichen von ϕ eine Variable, Konstante oder Funktionszeichen ist (Fall 1) oder ein Relationszeichen (Fall 2) oder ein Negationszeichen (Fall 3) oder eine aufgehende Klammer (Fall 4) oder ein Existenzquantor (Fall 5). Wir müssen noch in die Eindeutigkeit der Zerlegung in jedem Fall zeigen:

Fall 1: Klar, weil in ϕ nur ein Gleichheitszeichen vorkommt.

Fall 2: R ist als das erste Zeichen von ϕ eindeutig bestimmt. Die Eindeutigkeit der t_{i} folgt aus dem Hilfssatz im Beweis von 1.1.

Fall 3: Klar.

Fall 5: Klar.

Fall 4: Wenn (ψ_{1} ∧ψ_{2}) = (ψ′_{1} ∧ψ′_{2}), ist ψ_{1} Anfangsstück von ψ′_{1} oder umgekehrt. Aus dem nächsten Hilfsatz folgt ψ_{1} = ψ′_{1} und also auch ψ_{2} = ψ′_{2}. □

Hilfssatz Keine L–Formel ist echtes Anfangsstück einer anderen L–Formel.

Beweis: ϕ und ϕ′ seien L–Formeln und ϕ ein echtes Anfangsstück von ϕ′. Wir zeigen durch Induktion über die Länge von ϕ′, daß das unmöglich ist. Es ist klar, daß für ϕ und ϕ′ derselbe Fall auftritt. Wir gehen alle fünf Fälle durch: Wenn ϕ = t_{1} =^{.} t_{2} und ϕ′ = t′_{1} =^{.} t′_{2}, ist t_{2} ein echtes Anfangsstück von t′_{2}, was nach dem Hilfssatz im Beweis von 1.1 nicht geht. Wenn ϕ = Rt_{1} … t_{n} und ϕ′ = Rt′_{1} … t′_{n}, gibt es ein kleinstes i mit t_{i} ≠ t′_{i}. t_{i} ist dann ein echtes Anfangsstück von t′_{i} oder umgekehrt: unmöglich. Wenn ϕ = ¬ ψ und ϕ′ = ¬ ψ′, ist ψ echtes Anfangsstück von ψ′, das ist unmöglich nach Induktionsannahme. ϕ = ∃xψ ist aus demselben Grund unmöglich. Wenn ϕ = (ψ_{1} ∧ ψ_{2}) und ϕ′ = (ψ′_{1} ∧ ψ′_{2}), ist ψ_{1} echtes Anfangsstück von ψ′_{1} oder umgekehrt. □

2 Semantik

Ein L-Term t hat einen Wert in einer L–Struktur, wenn man die Variablen von t durch Elemente von A belegt.

Definition Sei 𝔄 eine L–Struktur. Eine Belegung ist eine Funktion

β : {v_{0}, v_{1} …} ⟶ A

von der Menge der Variablen in die Grundmenge von 𝔄.

Diese Belegung der Variablen läßt sich auf alle Terme fortsetzen. Die folgende rekursive Definition ist sinnvoll wegen 1.1.

Definition Für L–Terme t, L–Strukturen 𝔄 und Belegungen β definieren wir t^{𝔄}[β] durch

(1)  v_{i}^{𝔄}[β] = β(v_{i})
(2)  c^{𝔄}[β] = c^{𝔄}
(3)  ft_{1} … t_{n}^{𝔄}[β] = f^{𝔄}(t_{1}^{𝔄}[β], …, t_{n}^{𝔄}[β]).

Sei 𝔔 der Körper der rationalen Zahlen und t = ·v_{0}+v_{1}v_{2}. Wenn β(v_{i}) = i+2, ist t^{𝔔}[β] = 2(3 + 4) = 14.

Das folgende Lemma ist klar.

Lemma 2.1 Wenn die Belegungen β und γ auf den Variablen, die in t vorkommen übereinstimmen, ist t^{𝔄}[β] = t^{𝔄}[γ]. □

Wenn wir einen Term in der Form t(x_{1}, …, x_{n}) schreiben, meinen wir:

1. daß die x_{i} paarweise verschiedene Variable sind,

2. daß in t nur Variable aus {x_{1}, …, x_{n}} vorkommen.

Wenn dann a_{1}, …, a_{n} Elemente der Struktur 𝔄 sind, ist wegen 2.1 t^{𝔄}[a_{1}, …, a_{n}] durch t^{𝔄}[β] für eine Belegung β mit β(x_{i}) = a_{i} wohldefiniert.

Die folgende rekursive Definition der Semantik ist sinnvoll, wegen 1.2.

Definition Sei 𝔄 eine L–Struktur. Wir definieren für Belegungen β und L– Formeln ϕ die Relation

𝔄 ⊧ ϕ[β]

— ϕ trifft in 𝔄 auf β zu— durch Rekursion über den Aufbau von ϕ:

(1)  𝔄 ⊧ t_{1} =^{.} t_{2} [β] ⇔ t_{1}^{𝔄}[β] = t_{2}^{𝔄}[β]
(2)  𝔄 ⊧ Rt_{1} … t_{n} [β] ⇔ R^{𝔄}(t_{1}^{𝔄}[β], …, t_{n}^{𝔄}[β])

(3)  𝔄 ⊧ ¬ ψ [β] ⇔ 𝔄 |̸= ψ [β]
(4)  𝔄 ⊧ (ψ_{1} ∧ ψ_{2}) [β] ⇔ 𝔄 ⊧ ψ_{1} [β] und 𝔄 ⊧ ψ_{2} [β]
(5)  𝔄 ⊧ ∃xψ [β] ⇔ es gibt ein a ∈ A mit 𝔄 ⊧ ψ [β \frac{a}{x}].

Dabei ist β \frac{a}{x}(y) = \{ \begin{matrix}β(y) , wenn & y ≠ x \\ a , wenn & y = x. \end{matrix}

Es ist klar, daß unsere Abkürzungen die intendierte Interpretation haben. Also, daß z.B.

𝔄 ⊧ (ψ_{1} → ψ_{2})[β] ⟺ wenn 𝔄 ⊧ ψ_{1}[β], dann 𝔄 ⊧ ψ_{2}[β].

Ob ϕ in 𝔄 auf β zutrifft, hängt nur von den freien Variablen von ϕ ab.

Definition Die Variable x kommt frei in der Formel ϕ vor, wenn sie an einer Stelle vorkommt, die nicht im Wirkungsbereich eines Quantors ∃x liegt. Präzis definiert durch Rekursion nach dem Aufbau von ϕ:

(1)  x frei in t_{1} =^{.} t_{2} ⇔ x kommt in t_{1} oder in t_{2} vor.
(2)  x frei in Rt_{1} … t_{n} ⇔ x kommt in einem der t_{i} vor.
(3)  x frei in ¬ ψ ⇔ x frei in ψ
(4)  x frei in (ψ_{1} ∧ ψ_{2}) ⇔ x frei in ψ_{1} oder x frei in ψ_{2}
(5)  x frei in ∃y ψ ⇔ x ≠ y und x frei in ψ

Zum Beispiel kommt in ∀v_{0}(∃v_{1}R(v_{0}, v_{1}) ∧ P (v_{1})) die Variable v_{0} nicht frei vor. v_{1} kommt gebunden und frei vor.

Satz 2.2 Wenn β und γ an allen Variablen, die frei in ϕ vorkommen, übereinstimmen, ist

𝔄 ⊧ ϕ[β] ⇔ 𝔄 ⊧ ϕ[γ].

Beweis: durch Induktion über den Aufbau von ϕ: Wenn ϕ eine Primformel ist, folgt die Behauptung aus 2.1. Wenn ϕ eine Negation oder eine Konjunktion ist, ist der Induktionsschritt einfach. Sei also ϕ = ∃xψ. Wenn 𝔄 ⊧ ϕ[β], gibt es ein a mit 𝔄 ⊧ ψ[β \frac{a}{x}]. Außer x hat ψ die gleichen freien Variablen wie ϕ. Also ist nach Induktionsvoraussetzung 𝔄 ⊧ ψ[γ \frac{a}{x}]. Daraus folgt 𝔄 ⊧ ϕ[γ]. □

Wenn wir eine Formel in der Form ϕ(x_{1}, …, x_{n}) schreiben, meinen wir:

1. daß die x_{i} paarweise verschiedene Variable sind,

2. daß in ϕ nur Variable aus {x_{1}, …, x_{n}} frei vorkommen.

Wenn dann a_{1}, …, a_{n} Elemente der Struktur 𝔄 sind, ist wegen 2.2 𝔄 ⊧ ϕ[a_{1}, …, a_{n}] durch 𝔄 ⊧ ϕ[β] für eine Belegung β mit β(x_{i}) = a_{i} wohldefiniert.

Definition Eine Aussage ϕ ist eine Formel ohne freie Variable. Wir schreiben 𝔄 ⊧ ϕ, wenn 𝔄 ⊧ ϕ[β] für ein (alle) β. Sprechweisen:

• ϕ gilt in 𝔄.

• ϕ ist wahr in 𝔄.

• 𝔄 ist Modell von ϕ.

Zwei L–Strukturen 𝔄 und 𝔅 heißen elementar äquivalent, 𝔄 ≡ 𝔅, wenn in ihnen die gleichen Aussagen gelten. Übung Isomorphe Strukturen sind elementar äquivalent.

Sei x eine Variable und s ein Term. t\frac{s}{x} entsteht aus t durch Ersetzen aller Vorkommen von x durch s. ϕ\frac{s}{x} entsteht aus ϕ durch Ersetzen aller freien Vorkommen von x durch s. Man sieht leicht, daß t\frac{s}{x} wieder ein Term und ϕ\frac{s}{x} eine Formel ist.

Die rekursive Definition von ϕ\frac{s}{x} ist

(1)  (t_{1} =^{.} t_{2})\frac{s}{x} = t_{1} \frac{s}{x} =^{.} t_{2} \frac{s}{x}
(2)  (Rt_{1} … t_{n})\frac{s}{x} = Rt_{1} \frac{s}{x} … t_{n} \frac{s}{x}
(3)  (¬ ψ)\frac{s}{x} = ¬ (ψ \frac{s}{x})
(4)  (ψ_{1} ∧ ψ_{2})\frac{s}{x} = (ψ_{1} \frac{s}{x} ∧ ψ_{2} \frac{s}{x})
(5)  (∃yψ)\frac{s}{x} = ∃y(ψ \frac{s}{x}), wenn x ≠ y
= ∃yψ, wenn x = y.

Definition x heißt frei für s in ϕ, wenn kein freies Vorkommen von x in ϕ im Wirkungsbereich eines Quantors ist, der eine Variable von s bindet.

Rekursive Definition: x ist frei für s in ϕ, wenn x nicht frei in ϕ ist oder wenn x frei in ϕ ist und einer der folgenden Fälle zutrifft

(1)  ϕ = t_{1} =^{.} t_{n}
(2)  ϕ = Rt_{1} … t_{n}
(3)  ϕ = ¬ ψ und x frei für s in ψ
(4)  ϕ = (ψ_{1} ∧ ψ_{2}) und x frei für s in ψ_{1} und ψ_{2},
(5)  ϕ = ∃yψ, x frei für s in ψ und y kommt nicht in s vor.

Lemma 2.3 (Substitutionslemma) Sei x eine Variable, s ein Term und β eine Belegung mit Werten in der Struktur 𝔄.

1. Für jeden Term t ist

(t\frac{s}{x})^{𝔄}[β] = t^{𝔄}[β \frac{s^{𝔄}[β]}{x}].

2. Für jede Formel ϕ ist

𝔄 ⊧ ϕ\frac{s}{x}[β] ⟺ 𝔄 ⊧ ϕ[β \frac{s^{𝔄}[β]}{x}],

falls x frei für s in ϕ.

Beweis:

1. Induktion über den Aufbau von t: Wenn t = x, sind beide Seiten der behaupteten Gleichung gleich s^{𝔄}[β]. Wenn t eine Variable verschieden von x ist, sind beide Seiten β(t). Wenn t eine Konstante ist, steht t^{𝔄} links und rechts. Wenn t ein zusammengesetzter Term ft_{1} … t_{n} ist, schließen wir induktiv:

(t\frac{s}{x})^{𝔄}[β] = f^{𝔄}((t_{1} \frac{s}{x})^{𝔄}[β] …) = f^{𝔄}(t_{1}^{𝔄}[β \frac{s^{𝔄}[β]}{x}] …) = t^{𝔄}[β \frac{s^{𝔄}[β]}{x}].

2. Wenn x nicht frei in ϕ vorkommt, ist ϕ\frac{s}{x} = ϕ und die Behauptung folgt aus 2.2. Wir nehmen also an, daß x frei in ϕ vorkommt und schließen durch Induktion über den Aufbau von ϕ: Wenn ϕ eine Primformel ist, folgt die Behauptung aus dem ersten Teil. Wenn ϕ eine Negation oder eine Konjunktion ist, ist der Induktionsschritt trivial. Sei schließlich ϕ = ∃yψ. Dann ist y verschieden von x und kommt, weil x frei für s in ϕ ist, in s nicht vor. Für b = s^{𝔄}[β] haben wir dann

𝔄 ⊧ ϕ\frac{s}{x}[β] ⇔ 𝔄 ⊧ ψ \frac{s}{x}[β \frac{a}{y}]  für ein a
⇔ 𝔄 ⊧ ψ[β \frac{a}{y} \frac{s^{𝔄}[β \frac{a}{y}]}{x}] für ein a (Induktionsvoraussetzung)
⇔ 𝔄 ⊧ ψ[β \frac{a}{y} \frac{b}{x}]  für ein a (weil b = s^{𝔄}[β \frac{a}{y}])
⇔ 𝔄 ⊧ ψ[β \frac{b}{x} \frac{a}{y}]  für ein a (weil x ≠ y)
⇔ 𝔄 ⊧ ϕ[β \frac{b}{x}].
□

Sei t = t(x_{1}, …, x_{n}), ϕ = ϕ(x_{1}, …, x_{n}) und s = s(x_{1}, …, x_{n}). Dann kann man das Substitutionslemma schreiben als

t(s, x_{2}, …, x_{n})^{𝔄}[a_{1}, …, a_{n}] = t^{𝔄}[s^{𝔄}[a_{1}, …, a_{n}], a_{2}, …, a_{n}]

und

𝔄 ⊧ ϕ(s, x_{2}, …, x_{n})[a_{1}, …, a_{n}] ⟺ 𝔄 ⊧ ϕ[s^{𝔄}[a_{1}, …, a_{n}], a_{2}, …, a_{n}].

Sei ϕ(x) = ∀y y ∘ y =^{.} x und s = y. Sei 𝔄 eine L_{G}–Struktur und β irgendeine Belegung. Dann bedeutet 𝔄 ⊧ ϕ\frac{s}{x}[β], daß alle Elemente von 𝔄 idempotent sind.

𝔄 ⊧ ϕ[β \frac{s^{𝔄}[β]}{x}] bedeutet, daß alle Quadrate gleich β(y) sind. Auf die Voraussetzung, daß x frei für s in ϕ, kann man also in 2.3 nicht verzichten.

3 Allgemeingültige Formeln

Definition Eine L–Formel ϕ heißt allgemeingültig, wenn sie für alle^{4} Belegungen β in allen L–Strukturen gilt. Wir schreiben dafür

⊧ ϕ.

ϕ(x_{1}, …, x_{n}) ist genau dann allgemeingültig, wenn die Aussage ∀x_{1} … x_{n}ϕ(x_{1}, …, x_{n}) allgemeingültig ist.

Lemma 3.1 Sei ϕ eine L–Formel und K eine Erweiterung von L. Dann ist ϕ als L–Formel genau dann allgemeingültig, wenn ϕ als K–Formel allgemeingültig ist.

Beweis: Wir können annehmen, daß ϕ eine Aussage ist. Wenn 𝔄 = (A, (Z^{𝔄})_{Z∈K}) eine K-Struktur ist, in der ϕ falsch ist, ist ϕ auch falsch in der Einschränkung 𝔄 ↾ L = (A, (Z^{𝔄})_{Z∈L}) auf L. Wenn ϕ in der L-Struktur 𝔅 falsch ist, wählen wir eine Expansion von 𝔅 zu einer K–Struktur 𝔄, für die also 𝔄 ↾ L = 𝔅. (Das ist möglich, weil B nicht leer ist.) Dann ist ϕ auch in 𝔄 falsch. □

Formeln wie zum Beispiel ϕ ∨ ¬ ϕ oder ϕ ∧ (ϕ → ψ) → ψ sind allgemeingültig, weil sie in einer Struktur immer wahr sind, welchen Wahrheitswert die Teilformeln ϕ und ψ auch haben. Formeln dieser Art heißen Tautologien. Um zu einer präzisen Definition zu kommen, führen wir Aussagenlogik ein. Aussagenlogische Formeln bauen sich aus Aussagenvariablen (aus einem Vorrat M von Aussagenvariablen) mit ¬ und ∧ auf. ∨, → und ↔ werden wie früher als Abkürzungen verstanden. Eine Belegung ist eine Abbildung μ : M ⟶ {W, F} in die Menge der Wahrheitswerte. μ setzt sich auf die Menge aller Formeln gemäß μ(¬ f) = ¬ (μ(f)) und μ(f ∧ g) = μ(f) ∧ μ(g) fort, wobei ¬ und ∧ auf der Menge der Wahrheitswerte durch die Wahrheitstafeln

∧ W F W W F F F F  und  \begin{matrix}¬ \\ W & F \\ F & W \end{matrix}

definiert sind. Eine aussagenlogische Formel, die bei allen Belegungen den Wahrheitswert W bekommt, heißt allgemeingültig. Zum Beispiel sind für Variable p und q die Formeln (p ∨ ¬ p) und (p ∧ (p → q) → q) allgemeingültig.

Wenn wir die Variablen p_{i} einer aussagenlogischen Formel f = f(p_{1} …, p_{n}) durch L–Formeln ϕ_{i} ersetzen erhalten wir eine L–Formel f(ϕ_{1}, …, ϕ_{n}).

Definition Eine Tautologie entsteht aus einer allgemeingültigen aussagenlogischen Formel durch Ersetzen der Variablen durch L–Formeln.

Tautologien sind zum Beispiel ϕ ∨ ¬ ϕ und ϕ ∧ (ϕ → ψ) → ψ.

4Weil das leere Universum nicht zugelassen ist, besitzt jede Struktur eine Belegung.

Lemma 3.2 Tautologien sind allgemeingültig.

Beweis: Wenn man die L–Formeln in die aussagenlogische Formel f = f(p_{1}, …, p_{n}) einsetzt, ergibt sich für alle Belegungen β:

𝔄 ⊧ f(ϕ_{1}, …, ϕ_{n})[β] ⟺ μ(f) = W,

wobei μ(p_{i}) = W ⇔ 𝔄 ⊧ ϕ_{i}[β]. □

Lemma 3.3 (Axiome der Gleichheit) Die folgenden L–Aussagen sind allgemeingültig.

(1)  Reflexivität ∀x x =^{.} x
(2)  Symmetrie ∀x, y x =^{.} y → y =^{.} x
(3)  Transitivität ∀x, y, z x =^{.} y ∧ y =^{.} z → x =^{.} z

∀x_{1}, …, x_{n}, y_{1}, … y_{n} x_{1} =^{.} y_{1} ∧ … ∧ x_{n} =^{.} y_{n} (4)

⟶ fx_{1} … x_{n} =^{.} fy_{1} … y_{n}

∀x_{1}, …, x_{n}, y_{1}, … y_{n} x_{1} =^{.} y_{1} ∧ … ∧ x_{n} =^{.} y_{n} (5)

⟶ (Rx_{1} … x_{n} ↔ Ry_{1} … y_{n})

Dabei sind die f n–stellige Funktionszeichen und die R n–stellige Relationszeichen aus L.

Beweis: Klar. □

Die Gleichheitsaxiome drücken aus, daß = eine Kongruenzrelation^{5} ist.

Lemma 3.4 (∃–Quantorenaxiome) ϕ sei eine L–Formel, t ein L–Term und x frei für t in ϕ. Dann ist

ϕ\frac{t}{x} ⟶ ∃xϕ

allgemeingültig.

Beweis: Sei β eine Belegung mit Werten in 𝔄. Dann folgt aus 2.3

𝔄 ⊧ ϕ\frac{t}{x}[β] ⟹ 𝔄 ⊧ ϕ[β \frac{t^{𝔄}[β]}{x}] ⟹ 𝔄 ⊧ ∃xϕ[β].

□

Daß die Voraussetzung, daß x frei für t in ϕ, notwendig ist, zeigt folgendes Beispiel: Sei ϕ = ∀y y =^{.} x und t = y . ∀y y =^{.} y → ∃x∀y x =^{.} y ist nicht allgemeingültig.

5Eine Kongruenzrelation E auf 𝔄 ist eine Äquivalenzrelation für die a_{1}Eb_{1}, …, a_{n}Eb_{n} impliziert, daß f^{𝔄}(a_{1} … a_{n})Ef^{𝔄}(b_{1}, …, b_{n}), R^{𝔄}(a_{1}, …, a_{n}) ⇔ R^{𝔄}(b_{1}, …, b_{n}).

Lemma 3.5 (Modus Ponens) Wenn ϕ und (ϕ → ψ) allgemeingültig sind, dann auch ψ.

Beweis: Klar. □

Lemma 3.6 (∃–Einführung) Wenn x nicht frei in ψ vorkommt, dann ist mit ϕ → ψ auch ∃xϕ → ψ allgemeingültig.^{6}

Beweis: Wenn 𝔄 ⊧ ∃xϕ[β], gibt es ein a ∈ A mit 𝔄 ⊧ ϕ[β \frac{a}{x}]. Ist ϕ → ψ allgemeingültig, so gilt auch 𝔄 ⊧ ψ[β \frac{a}{x}]. Aus 2.2 folgt dann 𝔄 ⊧ ψ[β]. □

6Man spricht von Existenzeinführung.

4 Der Gödelsche Vollständigkeitssatz

Definition (Der Hilbertkalkül) L sei eine Sprache. Eine L–Formel ist beweisbar, wenn sie

B1 eine Tautologie ist,

B2 ein Gleichheitsaxiom ist,

B3 ein ∃–Quantorenaxiom ist,

B4 sich mit Hilfe der Modus Ponens Regel aus zwei beweisbaren L–Formeln ergibt,

B5 oder wenn sie sich mit der Regel der ∃–Einführung aus einer beweisbaren L–Formel ergibt.

Wir schreiben:

⊢_{L} ϕ

Das Ziel dieses Abschnitts ist es, den Gödelschen Vollständigkeitssatz zu beweisen.

Satz 4.1 (Gödelscher Vollständigkeitssatz) Ein Formel ist genau dann allgemeingültig, wenn sie beweisbar ist:

⊧ ϕ ⟺ ⊢_{L} ϕ

Es folgt, daß ⊢_{L} ϕ von der Sprachumgebung unabhängig ist (vgl. 3.1). Wir verwenden darum später die Notation

⊢ ϕ.

Die eine Richtung ist leicht zu zeigen: Die Menge der allgemeingültigen Sätze hat wegen 3.2, 3.3, 3.4, 3.5 und 3.6 die Eigenschaften B1–B5. Also sind alle beweisbaren Sätze allgemeingültig.

Der Beweis der Umkehrung macht den Rest des Kapitels aus.

Zuerst ergänzen wir Axiome und Regeln durch abgeleitete Axiome und Regeln.

\begin{matrix}Lemma 4.2 \\ 1. \end{matrix} (Aussagenlogik) Wenn ϕ_{1},…,ϕ_{n} beweisbar sind und (ϕ_{1} ∧…∧ϕ_{n}) → ψ eine Tautologie ist, ist auch ψ beweisbar.

2. (∀–Quantorenaxiome) Wenn x frei für t in ϕ, ist

⊢_{L} ∀xϕ → ϕ\frac{t}{x}.

3. (∀–Einführung) Wenn x nicht frei in ϕ ist, dann folgt aus der Beweisbarkeit von ϕ → ψ die Beweisbarkeit von ϕ → ∀xψ. Insbesondere folgt aus der Beweisbarkeit von ψ die Beweisbarkeit von ∀xψ.

Beweis:

1. Die Behauptung gilt auch, wenn wir nur annehmen, daß (ϕ_{1} ∧ … ∧ ϕ_{n}) → ψ beweisbar ist. Man sieht leicht, daß

((ϕ_{1} ∧ … ∧ ϕ_{n}) → ψ) → (ϕ_{1} → (ϕ_{2} → (⋯ (ϕ_{n} → ψ) ⋯)))

eine Tautologie ist. Modus Ponens ergibt also die Beweisbarkeit von

ϕ_{1} → (ϕ_{2} → (⋯ (ϕ_{n} → ψ) ⋯)).

Nach n–maliger Anwendung von Modus Ponens sehen wir, daß ⊢_{L} ψ.

2. ¬ ϕ\frac{t}{x} → ∃x¬ ϕ ist ein ∃–Quantorenaxiom.

(¬ ϕ\frac{t}{x} → ∃x¬ ϕ) → (¬ ∃x¬ ϕ → ϕ\frac{t}{x})

ist eine Tautologie (entstanden aus der allgemeingültigen Formel (¬ p → q) → (¬ q → p)). Mit Modus Ponens ergibt sich ⊢_{L} ¬ ∃x¬ ϕ → ϕ\frac{t}{x}.

3. Wenn ⊢_{L} ϕ → ψ, folgt mit einer Anwendung von 4.2.1, daß ⊢_{L} ¬ ψ → ¬ ϕ. ∃–Einführung ergibt ⊢_{L} ∃x¬ ψ → ¬ ϕ und mit Aussagenlogik ⊢_{L} ϕ → ¬ ∃x¬ ψ. Um den letzten Teil der Behauptung zu zeigen, nehmen wir an, daß ψ beweisbar ist. Wir nehmen uns dann eine Tautologie ϕ, die x nicht frei enthält. Aussagenlogik ergibt die Beweisbarkeit von ϕ → ψ, woraus die Beweisbarkeit von ϕ → ∀xψ folgt. Mit Modus Ponens ergibt sich ⊢_{L} ∀xψ. □

Das Lemma erleichtert das Führen von Beweisen sehr. Wir geben als Beispiel einen Beweis^{7} der allgemeingültigen Aussage ∃x∀yRxy → ∀y∃xRxy:

(1)  ∀yRxy → Rxy  ∀–Quantorenaxiom
(2)  Rxy → ∃xRxy  ∃–Quantorenaxiom
(3)  ∀yRxy → ∃xRxy  aus (1) und (2) mit Aussagenlogik
(4)  ∀yRxy → ∀y∃xRxy aus (3) mit ∀–Einführung
(5)  ∃x∀yRxy → ∀y∃xRxy aus (4) mit ∃–Einführung

Das nächste Lemma zeigt, daß wir uns beim Beweis von 4.1 auf Aussagen beschränken können.

Lemma 4.3 Sei ϕ(x_{1}, …, x_{n}) eine L–Formel, C eine Menge von neuen Konstanten und c_{1}, …, c_{n} eine Folge von paarweise verschiedenen Elementen von C. Dann ist

⊢_{L∪C} ϕ(c_{1}, …, c_{n}) ⟺ ⊢_{L} ϕ(x_{1}, …, x_{n}).

Beweis: Ein L–Beweis von ψ ist eine Folge von L–Formeln, die entweder Axiome sind oder mit den beiden Regeln aus früheren Formeln folgen, und die bei ψ endet.

7Eigentlich geben wir nur einen Beweis der Beweisbarkeit.

Sei nun B(c_{1}, …, c_{n}) ein L ∪ C–Beweis von ϕ(c_{1}, …, c_{n}). (Wir können annehmen, daß alle neuen Konstanten, die im Beweis vorkommen, in der Liste c_{1}, …, c_{n} aufgeführt sind.) Wenn wir überall im Beweis die Konstanten c_{i} durch Variable y_{i} ersetzen, die sonst im Beweis nicht vorkommen, erhalten wir einen L–Beweis B(y_{1}, …, y_{n}) von ϕ(y_{1}, …, y_{n}). ∀–Einführung ergibt (n–mal angewendet) ∀y_{1} … y_{n} ϕ(y_{1}, …, y_{n}). Zusammen mit dem ∀–Quantorenaxiom 4.2.2 ∀y_{1} … y_{n} ϕ(y_{1}, …, y_{n}) → ϕ(x_{1}, …, x_{n}) und Modus Ponens ergibt sich ⊢_{L} ϕ(x_{1}, …, x_{n}).

Wenn umgekehrt ⊢_{L} ϕ(x_{1}, …, x_{n}), liefert ∀–Einführung

⊢_{L} ∀x_{1} … x_{n} ϕ(x_{1}, …, x_{n}),

woraus ⊢_{L∪C} ϕ(c_{1}, …, c_{n}) folgt. □

Eine L–Theorie ist eine Menge von L–Aussagen. Eine L–Theorie T heißt widerspruchsfrei oder konsistent, wenn man nicht Aussagen ϕ_{1}, …, ϕ_{n} aus T finden kann, die sich widersprechen, das heißt, für die ⊢_{L} ¬ (ϕ_{1} ∧ … ∧ ϕ_{n}). (Man beachte, daß es wegen 4.2.1 auf die Klammerung und Reihenfolge der ϕ_{i} nicht ankommt.) Eine Aussage ϕ ist genau dann nicht beweisbar, wenn {¬ ϕ} widerspruchsfrei ist. Denn man hat ⊢ ϕ ⇒⊢ ¬ ¬ ϕ und ⊢ ¬ (¬ ϕ∧…∧¬ ϕ) ⇒⊢ ϕ. Ein Modell von T ist eine L–Struktur, in der alle Aussagen aus T gelten. 4.1 folgt also aus dem nächsten Satz, der, weil T auch unendlich sein kann, noch eine wesentliche Verstärkung darstellt.

Sei T eine widerspruchsfreie L–Theorie. Aus dem letzten Lemma folgt, daß T auch als L ∪ C–Theorie widerspruchsfrei ist. Der nächste Satz hat sogar zur Folge, daß, für jede Erweiterung K von L, T als K–Theorie widerspruchsfrei ist,

Satz 4.4 Eine Theorie hat genau dann ein Modell, wenn sie widerspruchsfrei ist.

Beweis: Eine Theorie, die ein Modell hat, muß natürlich widerspruchsfrei sein.

Für die Umkehrung müssen wir zu einer widerspruchsfreien L–Theorie T ein Modell konstruieren. Wir tun das, indem wir T zuerst zu einer Theorie T^{∗} erweitern, die aussieht wie das vollständige Diagramm einer L–Struktur 𝔄: Wir indizieren die Elemente von A mit neuen Konstanten aus einer Menge C

A = {a_{c} | c ∈ C}.

Das vollständige Diagramm ist dann die Menge aller L∪C–Aussagen, die in der L ∪ C-Struktur 𝔄^{∗} = (𝔄, a_{c})_{c∈C} gelten. Man sieht sofort, daß das vollständige Diagramm eine vollständige Henkintheorie ist, im Sinn der folgenden Definition:

Definition 1. Eine L ∪ C–Theorie T^{+} heißt Henkintheorie mit Konstantenmenge C, wenn es zu jeder L ∪ C–Formel ϕ(x) eine Konstante c ∈ C mit

(∃xϕ(x) → ϕ(c)) ∈ T^{+}

gibt.

2. Eine K–Theorie T^{∗} ist vollständig, wenn sie widerspruchsfrei ist und wenn

ϕ ∈ T^{∗} oder ¬ ϕ ∈ T^{∗}

für jede K–Aussage ϕ.^{8}

Wir werden zuerst zeigen, daß T in einer vollständigen Henkintheorie T^{∗} enthalten ist. Dann beweisen wir, daß T^{∗} das vollständige Diagramm eines Modells ist (das dadurch im wesentlichen eindeutig bestimmt ist.)

\underline{Schritt 1} T ist in einer widerspruchsfreien Henkintheorie T^{+} enthalten. Beweis: Sei ϕ(x) eine L–Formel und c eine neue Konstante. Dann ist T ∪ {(∃xϕ(x) → ϕ(c))} widerspruchsfrei. Denn wenn für eine L–Aussage ψ

⊢_{L∪{c}} ¬ (ψ ∧ (∃xϕ(x) → ϕ(c))),

so folgt (mit Aussagenlogik) ⊢_{L∪{c}} ¬ ∃xϕ(x) → ¬ ψ und ⊢_{L∪{c}} ϕ(c) → ¬ ψ. Aus 4.3 folgt ⊢_{L} ¬ ∃xϕ(x) → ¬ ψ und ⊢_{L} ϕ(x) → ¬ ψ. Das letztere hat aber nach der ∃–Einführungsregel ⊢_{L} ∃xϕ(x) → ¬ ψ zur Folge und insgesamt ergibt sich (mit Aussagenlogik) ⊢_{L} ¬ ψ. Daraus ergibt sich: Wenn T widerspruchsfrei ist, dann kann es keine ψ_{1} … ψ_{n} ∈ T mit ⊢_{L∪{c}} ¬ (ψ_{1} ∧ … ∧ (∃xϕ(x) → ϕ(c))) geben. Daraus folgt (induktiv), daß, wenn wir für jede L–Formel ϕ(x) eine eigene Konstante c_{ϕ} einführen, die Theorie T_{1} = T ∪ {∃xϕ(x) → ϕ(c_{ϕ}) | ϕ(x) L–Formel} widerspruchsfrei ist (als L ∪ C_{1}–Theorie, wobei C_{1} = {c_{ϕ} | ϕ(x) L–Formel}). Jetzt führen wir für jede L ∪ C_{1}–Formel eine neue Konstante ein und erhalten eine L ∪ C_{1} ∪ C_{2}–Theorie T_{2}. Wenn wir so fortfahren ist T = ⋃_{i∈ℕ} T_{i} eine widerspruchsfreie Henkintheorie T^{+} mit Konstantenmenge C = ⋃_{i∈ℕ} C_{i}.

\underline{Schritt 2} Jede widerspruchsfreie K–Theorie T^{+} läßt sich zu einer vollständigen K–Theorie T^{∗} erweitern. Beweis: Sei ϕ eine K-Aussage. Wenn weder T^{+} ∪ {ϕ} noch T^{+} ∪ {¬ ϕ} widerspruchsfrei wären, gäbe es Aussagen ψ_{i} und χ_{j} aus T^{+}, für die

⊢_{K} ψ_{1} ∧ … ∧ ψ_{n} → ϕ und ⊢_{K} χ_{1} ∧ … ∧ χ_{m} → ¬ ϕ.

Mit Aussagenlogik ergäbe sich

⊢_{K} ¬ (ψ_{1} ∧ … ∧ ψ_{n} ∧ χ_{1} ∧ … ∧ χ_{m}),

und T^{+} wäre nicht widerspruchsfrei.

Es ist also immer T^{+}∪{ϕ} oder T^{+}∪{¬ ϕ} widerspruchsfrei. Wenn K höchstens abzählbar ist, können wir T^{∗} auf einfache Weise gewinnen: Wir zählen die Menge aller K–Aussagen als ϕ_{0}, ϕ_{1} … auf und nehmen der Reihe nach jeweils ϕ_{i} oder ¬ ϕ_{i} hinzu. Wenn K überabzählbar ist, verwenden wir Zorns Lemma: Weil die Vereinigung jeder Kette von widerspruchsfreien K–Theorien widerspruchsfrei ist, gibt eine maximale widerspruchsfreie K–Theorie T^{∗}, die T^{+} enthält. Dann ist T^{∗} ∪ {ϕ} genau dann widerspruchsfrei, wenn ϕ ∈ T^{∗}, und T^{∗} ist vollständig. Damit ist die Behauptung bewiesen.

8Die offizielle Definition der Vollständigkeit auf Seite 75 ist schwächer.

Wir schreiben T^{+} ⊢_{K} ϕ, (ϕ ist aus T^{+} ableitbar), wenn es ψ_{1}, …, ψ_{n} ∈ T^{+} gibt mit

⊢_{K} ψ_{1} ∧ … ∧ ψ_{n} → ϕ.

Wir vermerken, daß eine vollständige Theorie T^{∗} deduktiv abgeschlossen ist. Das heißt, daß für alle K–Aussagen ϕ

T^{∗} ⊢_{K} ϕ ⇔ ϕ ∈ T^{∗}.

\underline{Schritt 3} Eine vollständige Henkintheorie T^{∗} hat ein Modell aus Konstanten. Das heißt ein Modell 𝔄^{∗} = (𝔄, a_{c})_{c∈C} mit A = {a_{c} | c ∈ C}. 𝔄^{∗} ist bis auf Isomorphie eindeutig bestimmt.

Beweis der Eindeutigkeit: Sei 𝔅^{∗} = (𝔅, b_{c})_{c∈C} ein zweites Modell aus Konstanten. Weil T^{∗} vollständig ist, ist T^{∗} das vollständige Diagramm von 𝔄^{∗}. Es ist also für alle L ∪ C–Aussagen ϕ

𝔄^{∗} ⊧ ϕ ⇔ ϕ ∈ T^{∗} ⇔ 𝔅^{∗} ⊧ ϕ.

Weil daher

a_{c} = a_{d} ⇔ 𝔄^{∗} ⊧ c =^{.} d ⇔ 𝔅^{∗} ⊧ c =^{.} d ⇔ b_{c} = b_{d},

liefert f(a_{c}) = b_{c} eine Bijektion zwischen A und B. f respektiert die Interpretation der Konstanten aus C nach Konstruktion. Daß die Relationen respektiert werden, folgt aus

R^{𝔄}(a_{c_{1}}, …, a_{c_{n}}) ⇔ 𝔄^{∗} ⊧ R(c_{1}, …, c_{n}) ⇔ 𝔅^{∗} ⊧ R(c_{1}, …, c_{n})
⇔ R^{𝔅}(b_{c_{1}}, …, b_{c_{n}}).

Ebenso schließt man, daß für Funktionszeichen und Konstanten f ∈ L

f^{𝔄}(a_{c_{1}}, …, a_{c_{n}}) = a_{c_{0}} ⇔ f^{𝔅}(b_{c_{1}}, …, b_{c_{n}}) = b_{c_{0}}.

Beweis der Existenz: Um 𝔄^{∗} zu konstruieren, müssen wir Elemente a_{c}, (c ∈ C), finden mit

a_{c} = a_{d} ⇔ c =^{.} d ∈ T^{∗}. (1)

Das ist genau dann möglich, wenn die Relation

c ∼ d ⇔ c =^{.} d ∈ T^{∗}

eine Äquivalenzrelation ist. Dann können wir nämlich für a_{c} die Äquivalenzklasse von c nehmen. Nun folgt aber aus dem ersten Gleichheitsaxiom und dem ∀– Quantorenaxiom, daß ⊢_{L∪C} c =^{.} c und, weil T^{∗} deduktiv abgeschlossen ist, c =^{.} c ∈ T^{∗}. ∼ ist also reflexiv. Aus dem gleichen Grund ist (c =^{.} d ∧ d =^{.} e → c =^{.} e) ∈ T^{∗}. Wenn nun c =^{.} d ∈ T^{∗} und d =^{.} e ∈ T^{∗}, folgt, wegen der deduktiven Abgeschlossenheit, c =^{.} e ∈ T^{∗}. Damit ist ∼ transitiv. Ebenso folgt die Symmetrie aus dem dritten Gleichheitsaxiom.

Wir setzen A = {a_{c} | c ∈ C}.

Jetzt müssen wir für jedes Relationszeichen R ∈ L eine Relation R^{𝔄} auf A finden, sodaß

R^{𝔄}(a_{c_{1}}, …, a_{c_{n}}) ⇔ R(c_{1}, …, c_{n}) ∈ T^{∗}. (2)

Wir können (2) als Definition nehmen, wenn wir zeigen können, daß

a_{c_{1}} = a_{d_{1}}, …, a_{c_{n}} = a_{d_{n}}, R(c_{1}, …, c_{n}) ⇒ R(d_{1}, …, d_{n}) ∈ T^{∗}.

Das folgt aber aus dem fünften Gleichheitsaxiom und der deduktiven Abgeschlossenheit von T^{∗}. Sei f ein n–stelliges Funktionszeichen oder eine Konstante (dann setzen wir n = 0) aus L. Wir müssen eine Operation f^{𝔄} auf A so definieren, daß

f^{𝔄}(a_{c_{1}}, …, a_{c_{n}}) = a_{c_{0}} ⇔ f(c_{1}, …, c_{n}) =^{.} c_{0} ∈ T^{∗}. (3)

Dazu müssen wir erstens für alle c_{1}, …, c_{n} ein c_{0} finden, für das die rechte Seite von (3) gilt. Aus ⊢_{L∪C} f(c_{1}, …, c_{n}) =^{.} f(c_{1}, …, c_{n}) folgt aber mit dem ∃–Quantorenaxiom ⊢_{L∪C} ∃x f(c_{1}, …, c_{n}) =^{.} x. Weil T^{∗} eine Henkintheorie ist,

gibt es ein c_{0} ∈ C mit (∃x f(c_{1}, …, c_{n}) =^{.} x → f(c_{1}, …, c_{n}) =^{.} c_{0}) ∈ T^{∗}. Aus

der deduktiven Abgeschlossenheit folgt die rechte Seite von (3).

Zweitens müssen wir zeigen, daß a_{c_{0}} durch die rechte Seite von (3) eindeutig bestimmt ist und nur von den a_{c_{1}}, …, a_{c_{n}} abhängt. Das heißt, daß c_{0} =^{.} d_{0} zu

T^{∗} gehört, wenn c_{1} =^{.} d_{1}, …, c_{n} =^{.} d_{n}, f(c_{1}, …, c_{n}) =^{.} c_{0} und f(d_{1}, …, d_{n}) =^{.} d_{0}

zu T^{∗} gehören. Das folgt aber aus den Gleichheitsaxiomen und der deduktiven Abgeschlossenheit von T^{∗}.

Konstante Terme (das heißt, Terme ohne Variable) werden in 𝔄^{∗} so ausgerechnet, wie es T^{∗} sagt:

t^{𝔄^{∗}} = a_{c} ⇔ t =^{.} c ∈ T^{∗} (4)

Wir zeigen das durch Induktion über den Aufbau von t: Wenn t eine Konstante aus C ist, folgt die Behauptung aus (1). Wenn t = ft_{1} … t_{n}, und t_{i}^{𝔄^{∗}} = a_{c_{i}}, sind nach Induktionsvoraussetzung die Gleichungen t_{i} =^{.} c_{i} in T^{∗}. Aus dem vierten Gleichheitsaxiom folgt, daß

t =^{.} c ∈ T^{∗} ⇔ fc_{1} … c_{n} =^{.} c ∈ T^{∗}.

Andererseits ist

t^{𝔄^{∗}} = a_{c} ⇔ f^{𝔄^{∗}}(a_{c_{1}}, …, a_{c_{n}}) = a_{c} ⇔ fc_{1} … c_{n} =^{.} c ∈ T^{∗}.

Schließlich beweisen wir durch Induktion über den Aufbau der Aussage ϕ, daß

𝔄^{∗} ⊧ ϕ ⇔ ϕ ∈ T^{∗}.

1. Fall: ϕ = t_{1} =^{.} t_{2}

Sei t_{i}^{𝔄^{∗}} = a_{c_{i}}. Dann ist nach (4) t_{i} =^{.} c_{i} ∈ T^{∗} für i = 1, 2 und daher

𝔄^{∗} ⊧ ϕ ⇔ a_{c_{1}} = a_{c_{2}} ⇔ c_{1} =^{.} c_{2} ∈ T^{∗} ⇔ t_{1} =^{.} t_{2} ∈ T^{∗}.

2. Fall: ϕ = Rt_{1} …, t_{n} Sei t_{i}^{𝔄^{∗}} = a_{c_{i}}. Dann ist nach (4) t_{i} =^{.} c_{i} ∈ T^{∗} für i = 1, …, n und

𝔄^{∗} ⊧ ϕ ⇔ Rc_{1} … c_{n} ∈ T^{∗} ⇔ ϕ ∈ T^{∗}.

Die letzte Äquivalenz folgt aus dem fünften Gleichheitsaxiom.

3. Fall ϕ = ¬ ψ Weil T^{∗} vollständig ist, gilt

𝔄^{∗} ⊧ ϕ ⇔ 𝔄^{∗} |̸= ψ ⇔ ψ ∉ T^{∗} ⇔ ϕ ∈ T^{∗}.

4. Fall ϕ = (ψ_{1} ∧ ψ_{2}) Aus der deduktiven Abgeschlossenheit von T^{∗} folgt:

𝔄^{∗} ⊧ ϕ ⇔ 𝔄^{∗} ⊧ ψ_{i} (i = 1, 2) ⇔ ψ_{i} ∈ T^{∗} (i = 1, 2) ⇔ ϕ ∈ T^{∗}.

5. Fall ϕ = ∃x ψ Aus der deduktiven Abgeschlossenheit von T^{∗} folgt ∃x ψ ∈ T^{∗}, wenn ψ(c) ∈ T^{∗} für ein c ∈ C. Wenn umgekehrt ∃x ψ ∈ T^{∗}, und ∃x ψ → ψ(c) ∈ T^{∗} folgt ψ(c) ∈ T^{∗}. Also haben wir 𝔄^{∗} ⊧ ϕ ⇔ 𝔄^{∗} ⊧ ψ[a_{c}] für ein c ∈ C ⇔ 𝔄^{∗} ⊧ ψ(c) für ein c ∈ C

⇔ ψ(c) ∈ T^{∗} für ein c ∈ C ⇔ ϕ ∈ T^{∗}.

Damit ist 4.4 bewiesen. □

Definition Sei T eine L–Theorie und ϕ eine L–Aussage.

1. ϕ ist in T beweisbar,

T ⊢ ϕ,

wenn es Axiome ψ_{1}, …, ψ_{n} aus T gibt für die ψ_{1} ∧ ⋯ ∧ ψ_{n} → ϕ beweisbar ist.

2. ϕ folgt logisch aus T,

T ⊧ ϕ,

wenn ϕ in allen Modellen von T gilt Folgerung 4.5

T ⊢ ϕ  ⇔  T ⊧ ϕ

Beweis: ϕ ist in T genau dann nicht beweisbar, wenn T ∪ {¬ ϕ} widerspruchsfrei ist. Andererseits folgt ϕ genau dann nicht logisch aus T, wenn T ∪ {¬ ϕ} ein Modell hat. □

Folgerung 4.6 (Kompaktheitssatz) Eine Theorie hat genau dann ein Modell, wenn jede endliche Teilmenge ein Modell hat.

Den Kompaktheitssatz könnte man den ersten Hauptsatz der Modelltheorie nennen. Der zweite Hauptsatz wäre der Satz von Löwenheim-Skolem.

Folgerung 4.7 (Löwenheim-Skolem) Wenn eine Theorie mit höchstens abzählbarer Sprache eine Modell hat, hat sie ein höchstens abzählbares Modell.

Beweis: Im Beweis von 4.4 wurde die Sprache durch eine Konstantenmenge C erweitert. Zu jeder L–Formel wurde eine Konstante eingeführt und dieser Prozeß abzählbar oft wiederholt. Wenn L höchstens abzählbar ist, ist also auch C höchstens abzählbar. Das im Beweis konstruierte Modell hat aber höchstens so viele Elemente wie C. □

Am Schluß dieses Abschnitts bemerken wir noch, daß man sich in vielen Fällen auf Formeln ohne Gleichheitszeichen zurückziehen kann. Sei T eine L– Theorie und E ein neues zweistelliges Relationszeichen. Wir bezeichnen mit

• T (=^{.} /E) die L ∪ {E}–Theorie, die aus T entsteht, indem man in den Axiomen alle Teilformeln t_{1} =^{.} t_{2} durch Et_{1}t_{2} ersetzt,

• Kong_{L} Axiome, die ausdrücken, daß E eine Kongruenzrelation ist.

Dann gilt:

Lemma 4.8 T ist genau dann konsistent, wenn T (=^{.}/E) ∪ Kong_{L} konsistent ist.

Beweis: Ein Modell von T wird ein Modell von T (=^{.}/E) ∪ Kong_{L}, wenn man E durch die Gleichheit interpretiert. Sei umgekehrt (𝔄, E^{𝔄}) ein Modell von T (=^{.}/E) ∪ Kong_{L}. Dann ist E eine Kongruenzrelation auf 𝔄. Definiere die L–Struktur 𝔅 auf der Grundmenge A/E^{𝔄} durch

c^{𝔅} = c^{𝔄}E
f^{𝔅}(a_{1}E, …, a_{n}E) = f^{𝔄}(a_{1}, …, a_{n})E
R^{𝔅}(a_{1}E, …, a_{n}E) ⇔ R^{𝔄}(a_{1}, …, a_{n})

𝔅 ist ein Modell von T. □

Bemerkung Der Beweis von 4.1 zeigt, daß eine allgemeingültige Formel ohne Gleichheitszeichen einen Beweis hat, in dem keine Gleichheitszeichen vorkommen.

5 Der Sequenzenkalkül

Der von Gentzen aufgestellte Sequenzenkalkül hat gegenüber dem Hilbertschen Kalkül Vorteile

1. Axiome und Regeln entsprechen den Regeln des Formelaufbaus.

2. Die Beweise sind näher am natürlichen Schließen.

3. Der Beweis des Vollständigkeitssatzes ist einfach.

4. Die Beweise lassen sich analysieren.

aber den Nachteil, daß man Sequenzen (und nicht Formeln) herleitet.

Sei L eine Sprache und C eine abzählbare Menge von neuen Konstanten. Eine Sequenz ist ein Paar

Δ ≻ Γ

von endlichen Mengen von L ∪ C–Aussagen. Eine Sequenz Δ ≻ Γ gilt in der L ∪ C–Struktur 𝔄^{∗}, wenn in 𝔄^{∗} eine der Aussagen aus Δ falsch ist oder eine der Aussagen aus Γ wahr. {δ_{1}, …, δ_{m}} ≻ {γ_{1}, …, γ_{n}} hat also die Bedeutung

(δ_{1} ∧ … ∧ δ_{m}) ⟶ (γ_{1} ∨ … ∨ γ_{n}).

Eine Sequenz ist allgemeingültig, wenn sie in allen L ∪ C–Strukturen gilt.

Wir beschreiben die Axiome und Regeln des Sequenzenkalküls in der Form

\frac{𝔖_{1}, …, 𝔖_{n}}{𝔖_{0}} mit der Bedeutung: Wenn die Sequenzen 𝔖_{1}, …, 𝔖_{n} ableitbar

sind, dann auch die Sequenz 𝔖_{0}. Wir lassen die Regeln für Gleichheit, Konstanten und Funktionszeichen weg, um die Darstellung zu vereinfachen.^{9}

Axiome  \overline{Δ ∪ \{ϕ\} ≻ Γ ∪ \{ϕ\}}
¬ –links–Regel \frac{Δ ≻ Γ ∪ \{ϕ\}}{Δ ∪ \{¬ ϕ\} ≻ Γ}
¬ –rechts–Regel \frac{Δ ∪ \{ϕ\} ≻ Γ}{Δ ≻ Γ ∪ \{¬ ϕ\}}
∧–links–Regeln \frac{Δ ∪ \{ϕ_{i}\} ≻ Γ}{Δ ∪ \{(ϕ_{1} ∧ ϕ_{2})\} ≻ Γ}  für i = 1, 2
∧–rechts–Regel \frac{Δ ≻ Γ ∪ \{ϕ_{1}\} , Δ ≻ Γ ∪ \{ϕ_{2}\}}{Δ ≻ Γ ∪ \{(ϕ_{1} ∧ ϕ_{2})\}}

∃–links–Regel

\frac{Δ ∪ \{ϕ(c)\} ≻ Γ}{Δ ∪ \{∃x ϕ(x)\} ≻ Γ}

wenn c nicht in Δ, Γ und ϕ vorkommt.

∃–rechts–Regel \frac{Δ ≻ Γ ∪ \{ϕ(c)\}}{Δ ≻ Γ ∪ \{∃x ϕ(x)\}}

Wenn man will, kann man in den Axiomen voraussetzen, daß ϕ eine Primformel ist.

9n ≥ 0-stellige Funktionen könnte man durch n+1 stellige Relationen ersetzen. Für Gleichheitszeichen siehe Lemma 4.8.

Satz 5.1 Eine Sequenz (ohne Gleichheit, Konstanten und Funktionszeichen aus L) ist genau dann allgemeingültig, wenn sie im Sequenzenkalkül ableitbar ist.

Beweis: Es ist klar, daß die Axiome des Kalküls allgemeingültig sind und daß die Regeln von allgemeingültigen Sequenzen wieder zu allgemeingültige Sequenzen führen: In den ¬ –Regeln und der ∧–rechts–Regel ist die Konklusion logisch äquivalent zu der (Konjunktion der) Hypothese(n). In den ∧–links–Regeln und in der ∃– rechts–Regel folgt die Konklusion (wegen 3.4) aus der Hypothese. Die ∃–links– Regel ist eine Form der ∃–Einführung.

Bevor wir die Umkehrung beweisen, zeigen wir noch wie die Allgemeingültigkeit der Formel ϕ = ∃x∀yRxy → ∀y∃xRxy im Sequenzenkalkül abgeleitet wird: (Wir lassen dabei auf beiden Seiten einer Sequenz Mengenklammern weg.)

Rcd ≻ Rcd  Axiom
Rcd ≻ ∃xRxd  ∃–rechts–Regel
≻ ¬ Rcd, ∃xRxd  ¬ –rechts–Regel
≻ ∃y¬ Rcy, ∃xRxd  ∃–rechts–Regel
¬ ∃xRxd ≻ ∃y¬ Rcy  ¬ –links–Regel
¬ ∃y¬ Rcy, ¬ ∃xRxd ≻  ¬ –links–Regel
¬ ∃y¬ Rcy, ∃y¬ ∃xRxy ≻  ∃–links–Regel
∃x¬ ∃y¬ Rxy, ∃y¬ ∃xRxy ≻  ∃–links–Regel
∃x¬ ∃y¬ Rxy ≻ ¬ ∃y¬ ∃xRxy  ¬ –rechts–Regel
∃x¬ ∃y¬ Rxy, ¬ ¬ ∃y¬ ∃xRxy ≻  ¬ –links–Regel
(∃x¬ ∃y¬ Rxy ∧ ¬ ¬ ∃y¬ ∃xRxy), ∃x¬ ∃y¬ Rxy ≻ ∧–links–Regel
(∃x¬ ∃y¬ Rxy ∧ ¬ ¬ ∃y¬ ∃xRxy) ≻  ∧–links–Regel
≻ ¬ (∃x¬ ∃y¬ Rxy ∧ ¬ ¬ ∃y¬ ∃xRxy)  ¬ –rechts–Regel

Die rechte Seite der letzten Sequenz ist ϕ.

Sei Δ ≻ Γ eine Sequenz, die nicht ableitbar ist. L sei eine endliche (oder abzählbare) Sprache, zu der diese Sequenz gehört. Wir konstruieren eine Folge Δ_{i} ≻ Γ_{i}, (i = 0, 1, 2 …) von nicht–ableitbaren Sequenzen. Dabei werden die Δ_{i} und die Γ_{i} zwei aufsteigende Folgen bilden, die bei Δ = Δ_{0} und bei Γ = Γ_{0} beginnen. Wir fixieren eine Aufzählung (ϵ_{i}, ϕ_{i}, c_{i}), in der jedes Tripel (ϵ, ϕ, c), bestehend aus ϵ ∈ {links, rechts}, einer L ∪ C–Formel ϕ_{i} und einer Konstanten c, unendlich oft vorkommt. Dann definieren wir die gesuchte Folge rekursiv. Sei Δ_{i} ≻ Γ_{i} schon konstruiert und nicht ableitbar:

1. Fall: ϕ_{i} = ¬ ψ ∈ Δ_{i} und ϵ_{i} = links. Dann ist wegen der ¬ –links–Regel die Sequenz Δ_{i+1} = Δ_{i} ≻ Γ_{i+1} = Γ_{i} ∪ {ψ} nicht ableitbar.

2. Fall: ϕ_{i} = ¬ ψ ∈ Γ_{i} und ϵ_{i} = rechts. Dann ist wegen der ¬ –rechts–Regel die Sequenz Δ_{i+1} = Δ_{i} ∪ {ψ} ≻ Γ_{i+1} = Γ_{i} nicht ableitbar.

3. Fall: ϕ = (ψ_{1} ∧ ψ_{2}) ∈ Δ_{i} und ϵ_{i} = links. Wir setzen Δ_{i+1} = Δ_{i} ∪ {ψ_{1}, ψ_{2}} und Γ_{i+1} = Γ_{i}. Durch Anwenden der beiden ∧–links–Regeln könnte man Δ_{i} ≻ Γ_{i} aus Δ_{i+1} ≻ Γ_{i+1} gewinnen. Also ist Δ_{i+1} ≻ Γ_{i+1} nicht ableitbar.

4. Fall: ϕ = (ψ_{1} ∧ ψ_{2}) ∈ Γ_{i} und ϵ_{i} = rechts. Wegen der ∧–rechts–Regel können nicht beide Sequenzen Δ_{i} ≻ Γ_{i}∪{ψ_{1}} und Δ_{i} ≻ Γ_{i}∪{ψ_{2}} ableitbar sein. Wir wählen j so daß Δ_{i+1} = Δ_{i} ≻ Γ_{i+1} = Γ_{i} ∪ {ψ_{j}} nicht ableitbar ist.

5. Fall: ϕ_{i} = ∃xψ(x) ∈ Δ_{i} und ϵ_{i} = links. Wähle ein c, daß in Δ_{i} und Γ_{i} nicht vorkommt. Dann ist wegen der ∃–links–Regel die Sequenz Δ_{i+1} = Δ_{i} ∪ {ψ(c)} ≻ Γ_{i+1} = Γ_{i} nicht ableitbar.

6. Fall: ϕ_{i} = ∃xψ(x) ∈ Γ_{i} und ϵ_{i} = rechts. Wir setzen dann Δ_{i+1} = Δ_{i} und Γ_{i+1} = Γ_{i} ∪ {ψ(c_{i})}. Die neue Sequenz ist nicht ableitbar wegen der ∃–rechts–Regel.

Wenn keiner dieser sechs Fälle auftritt, setzen wir Δ_{i+1} = Δ_{i} und Γ_{i+1} = Γ_{i}. Weil die Δ_{i} ≻ Γ_{i} keine Axiome sind, sind die Δ_{i} und die Γ_{i} disjunkt.

Die Mengen Δ^{∗} = ⋃_{i∈ℕ} Δ_{i} und Γ^{∗} = ⋃_{i∈ℕ} Γ_{i} haben offensichtlich die folgenden Eigenschaften

0. Δ^{∗} und Γ^{∗} sind disjunkt.

1. Wenn ¬ ψ ∈ Δ^{∗}, ist ψ ∈ Γ^{∗}.

2. Wenn ¬ ψ ∈ Γ^{∗}, ist ψ ∈ Δ^{∗}.

3. Wenn (ψ_{1} ∧ ψ_{2}) ∈ Δ^{∗}, gehören ψ_{1} und ψ_{2} zu Δ^{∗}.

4. Wenn (ψ_{1} ∧ ψ_{2}) ∈ Γ^{∗}, dann gehört ψ_{1} oder ψ_{2} zu Γ^{∗}.

5. Wenn ∃xψ(x) ∈ Δ^{∗}, gibt es ein c ∈ C mit ψ(c) ∈ Δ^{∗}.

6. Wenn ∃xψ(x) ∈ Γ^{∗}, ist ψ(c) ∈ Γ^{∗} für alle c ∈ C.

Sei nun A = {a_{c} | c ∈ C} eine Menge, die durch (a_{c})_{c∈C} injektiv aufgezählt ist (man kann z.B. a_{c} = c nehmen). Wir machen A zu einer L–Struktur 𝔄, indem wir die Relationszeichen R ∈ L durch R^{𝔄}(a_{c_{1}}, …, a_{c_{n}}) ⇔ R(c_{1}, …, c_{n}) ∈ Δ^{∗} interpretieren. 𝔄^{∗} = (𝔄, a_{c})_{c∈C} ist eine L ∪ C–Struktur, in der Δ ≻ Γ nicht gilt. Um das einzusehen, zeigen wir durch Induktion über den Aufbau von ϕ, daß ϕ ∈ Δ^{∗} ⇒ 𝔄^{∗} ⊧ ϕ und ϕ ∈ Γ^{∗} ⇒ 𝔄^{∗} |̸= ϕ:

0. Fall: ϕ = R(c_{1}, …, c_{n}).

Wenn R(c_{1}, …, c_{n}) ∈ Δ^{∗}, ist 𝔄^{∗} ⊧ R(c_{1}, …, c_{n}) nach Konstruktion. Wenn R(c_{1}, …, c_{n}) ∈ Γ^{∗}, ist nach Eigenschaft (0) R(c_{1}, …, c_{n}) ∉ Δ^{∗}, also 𝔄^{∗} |̸= R(c_{1}, …, c_{n}).

1. Fall: ϕ = ¬ ψ ∈ Δ^{∗}.

Dann ist nach Eigenschaft (1) ψ ∈ Γ^{∗}. Nach Induktionsvoraussetzung ist 𝔄^{∗} |̸= ψ. Also 𝔄^{∗} ⊧ ϕ.

2. Fall: ϕ = ¬ ψ ∈ Γ^{∗}.

Dann ist nach Eigenschaft (2) ψ ∈ Δ^{∗}. Die Induktionsvoraussetzung liefert 𝔄^{∗} ⊧ ψ. Also 𝔄^{∗} |̸= ϕ.

3. Fall: Wenn ϕ = (ψ_{1} ∧ ψ_{2}) ∈ Δ^{∗}, sind wegen (3) ψ_{1} und ψ_{2} in Δ^{∗}. Nach Induktionsvoraussetzung gelten ψ_{1} und ψ_{2} in 𝔄^{∗}, also gilt auch ϕ.

4. Fall: Aus ϕ = (ψ_{1} ∧ ψ_{2}) ∈ Γ^{∗} folgt aus (4), daß zum Beispiel ψ_{1} ∈ Γ^{∗}. Die Induktionsvoraussetzung liefert 𝔄^{∗} |̸= ψ_{1}, also 𝔄^{∗} |̸= ϕ.

5. Fall: Wenn ∃xψ(x) ∈ Δ^{∗}, gibt es wegen (5) ein c ∈ C mit ψ(c) ∈ Δ^{∗}. Dann ist 𝔄^{∗} ⊧ ψ(c) nach Induktionsvoraussetzung, also 𝔄^{∗} ⊧ ϕ.

6. Fall: ϕ = ∃xψ(x) ∈ Γ^{∗}.

Eigenschaft (6) sagt, daß alle ϕ(c) für c ∈ C zu Γ^{∗} gehören. Also gilt nach Induktionsvoraussetzung keines der ϕ(c) in 𝔄^{∗}. Weil A = {c^{𝔄^{∗}} | c ∈ C} ist 𝔄^{∗} |̸= ϕ.

□

Als ein Anwendungsbeispiel beweisen wir den Interpolationssatz. Allerdings nur für Aussagen ϕ_{i} ohne Gleichheit, Konstanten und Funktionszeichen. Man kann sich aber leicht überzeugen, daß der Satz in seiner Allgemeinheit leicht aus diesem Spezialfall folgt.

Satz 5.2 Sei ϕ_{1} eine L_{1}–Aussage und ϕ_{2} eine L_{2}–Aussage. Wenn

ϕ_{1} → ϕ_{2}

allgemeingültig ist, gibt es eine interpolierende L_{1} ∩ L_{2}–Aussage δ, für die

ϕ_{1} → δ und δ → ϕ_{2}

allgemeingültig sind.

Beweis: Wenn ϕ_{1} → ϕ_{2} allgemeingültig ist, ist die Sequenz ϕ_{1} ≻ ϕ_{2} ableitbar. Wir zeigen die Existenz von δ durch Induktion über die Länge des Beweises. Weil aber in einem Beweis von ϕ_{1} → ϕ_{2} Sequenzen vorkommen werden, in denen L_{1}–Aussagen auch rechts und L_{2}–Aussagen auch links stehen können, beweisen wir durch Induktion über die Beweislänge:

Wenn Δ_{i} und Γ_{i} endliche Mengen von L_{i} ∪ C–Aussagen sind und

Δ_{1} ∪ Δ_{2} ≻ Γ_{1} ∪ Γ_{2}

ableitbar ist, gibt es eine (L_{1} ∩ L_{2}) ∪ C–Aussage β, für die Δ_{1} ≻ Γ_{1} ∪ {β} und {β} ∪ Δ_{2} ≻ Γ_{2} allgemeingültig sind.

Daraus folgt dann die Behauptung. Denn wenn ϕ ≻ β(c_{1}, …, c_{n}) und β(c_{1}, …, c_{n}) ≻ ψ allgemeingültig sind, leistet δ = ∃x_{1} … x_{n} β(x_{1}, … x_{n}) das Verlangte.

Sei nun 𝔖 = Δ_{1} ∪ Δ_{2} ≻ Γ_{1} ∪ Γ_{2} ableitbar. Dann ist 𝔖 ein Axiom oder folgt nach einer der sechs Regeln aus Sequenzen mit kürzeren Ableitungen. Jeder dieser Fälle zerfällt in zwei Unterfälle, je nachdem, ob die Formel im Axiom zu Δ_{1} oder Δ_{2}, oder ob die in der Regel betrachtete Formel zu Δ_{1}∪Γ_{1} oder Δ_{2}∪Γ_{2} gehört. Wir brauchen aber immer nur den ersten dieser Fälle zu betrachten. Die Induktionsbehauptung impliziert nämlich die Allgemeingültigkeit von Δ_{2} ≻ Γ_{2} ∪ {¬ β} und {¬ β} ∪ Δ_{1} ≻ Γ_{1} und ist daher symmetrisch in L_{1} und L_{2}.

0. Fall: 𝔖 ist ein Axiom, weil es ein ϕ ∈ Δ_{1} mit ϕ ∈ Γ_{1} ∪ Γ_{2} gibt. Wenn ϕ ∈ Γ_{1} ist, können wir β = ¬ c =^{.} c setzen^{10}, und β = ϕ, wenn ϕ ∈ Γ_{2}.

1. Fall: Es ist Δ_{1} = Δ′_{1} ∪ {¬ ϕ} und 𝔖 folgt mit der ¬ –links–Regel aus Δ′_{1} ∪ Δ_{2} ≻ (Γ_{1} ∪ {ϕ}) ∪ Γ_{2}. Nach Induktionsvoraussetzung gibt es eine (L_{1} ∩L_{2})∪C–Formel β′, für die Δ′_{1} ≻ (Γ_{1} ∪{ϕ})∪{β′} und {β′}∪Δ_{2} ≻ Γ_{2} allgemeingültig sind. Wir setzen β = β′.

2. Fall: Es ist Γ_{1} = Γ′_{1} ∪ {¬ ϕ} und 𝔖 folgt mit der ¬ –rechts–Regel aus (Δ_{1} ∪ {ϕ}) ∪ Δ_{2} ≻ Γ′_{1} ∪ Γ_{2}. Wir wählen wieder β′, sodaß Δ_{1} ∪ {ϕ} ≻ (Γ′_{1}) ∪ {β′} und {β′} ∪ Δ_{2} ≻ Γ_{2} allgemeingültig sind, und setzen β = β′.

3. Fall: Es ist Δ_{1} = Δ′_{1} ∪ {ϕ_{1} ∧ ϕ_{2}} und für ein i = 1, 2 folgt 𝔖 mit der ∧– rechts–Regel aus (Δ′_{1} ∪{ϕ_{i}})∪Δ_{2} ≻ Γ_{1} ∪Γ_{2}. Wenn (Δ′_{1} ∪{ϕ_{i}}) ≻ Γ_{1} ∪{β′} und {β′} ∪ Δ_{2} ≻ Γ_{2} allgemeingültig sind, können wir β = β′ nehmen.

4. Fall: Es ist Γ_{1} = Γ′_{1} ∪ {ϕ_{1} ∧ ϕ_{2}} und 𝔖 folgt aus den beiden Sequenzen Δ_{1} ∪ Δ_{2} ≻ (Γ_{1} ∪ {ϕ_{i}}) ∪ Γ_{2} (i = 1, 2) mit der ∧–rechts–Regel. Wenn dann für i = 1, 2 Δ_{1} ≻ (Γ′_{1} ∪ {ϕ_{i}}) ∪ {β_{i}} und {β_{i}} ∪ Δ_{2} ≻ Γ_{2} allgemeingültig sind, setzen wir β = β_{1} ∨ β_{2}.

5. Fall: Es ist Δ_{1} = Δ′_{1} ∪ {∃x ϕ(x)} und 𝔖 folgt aus (Δ′_{1} ∪ {ϕ(c)}) ∪ Δ_{2} ≻ Γ_{1} ∪ Γ_{2} mit der ∃–links–Regel. c kommt also in 𝔖 nicht vor. Wenn nun für ein β(x), das c nicht enthält, die Sequenzen (Δ′_{1} ∪ {ϕ(c)}) ≻ Γ_{1} ∪ {β′(c)} und {β′(c)} ∪ Δ_{2} ≻ Γ_{2} allgemeingültig sind, setzen wir β = ∃x β′(x).

6. Fall: Es ist Γ_{1} = Γ′_{1} ∪ {∃x ϕ(x)} und 𝔖 folgt mit der ∃–rechts–Regel aus Δ_{1} ∪ Δ_{2} ≻ (Γ′_{1} ∪ {ϕ(c)}) ∪ Γ_{2}. Wenn Δ_{1} ≻ (Γ′_{1} ∪ {ϕ(c)}) ∪ {β′} und {β′} ∪ Δ_{2} ≻ Γ_{2} allgemeingültig sind, setzen wir β = β′.

□

10Statt ¬ c =^{.} c können wir irgendeine (L_{1} ∩ L_{2}) ∪ C–Aussage nehmen, deren Negation allgemeingültig ist.

6 Der Herbrandsche Satz und automatisches Beweisen

Definition Eine universelle Formel hat die Form

∀x_{1} … ∀x_{n}ψ,

wobei ψ eine quantorenfreie Formel ist. Existentielle Formeln beginnen mit Existenzquantoren.

Satz 6.1 (Skolem–Normalform) Zu jeder L–Aussage ϕ kann man eine Spracherweiterung L^{∗} und einen universellen L^{∗}–Satz ϕ^{∗} angeben, derart, daß ϕ in einer L–Struktur 𝔄 genau dann gilt, wenn sich 𝔄 zu einem Modell von ϕ^{∗} expandieren läßt. ϕ ist also genau dann erfüllbar, wenn ϕ^{∗} erfüllbar ist.

Beweis: Eine Formel ist in pränexer Normalform, wenn alle Quantoren am Anfang der Formel stehen, wenn also die Formel die Gestalt

Q_{1}x_{1}Q_{2}x_{2} … Q_{n}x_{n}ψ

hat, mit quantorenfreiem ψ und Q_{i} ∈ {∃, ∀}.

Man sieht leicht, daß sich in jeder Formel die Quantoren so nach vorn ziehen lassen, daß eine äquivalente Formel^{11} in pränexer Normalform entsteht. Man verwendet dabei die Umformungen

¬ ∃ ⇝ ∀¬
¬ ∀ ⇝ ∃¬
(ϕ ∧ ∃xψ) ⇝ ∃y (ϕ ∧ ψ \frac{x}{y})
(ϕ ∧ ∀xψ) ⇝ ∀y (ϕ ∧ ψ \frac{x}{y})

Die Variable y soll dabei in ϕ und ψ nicht vorkommen.

Wir können also annehmen, daß ϕ pränex ist. ϕ^{∗} konstruieren wir durch Rekursion über die Zahl der Quantorenwechsel von ϕ. Sei

ϕ = ∀x_{1} … ∀x_{m}∃y_{1} … ∃y_{n}χ(x_{1}, …, y_{n}),

wobei χ (höchstens) mit einem ∀–Quantor beginnt. Wir führen jetzt neue m– stellige Funktionszeichen f_{1}, …, f_{n} ein und sehen, daß ϕ genau in den Strukturen gilt, die sich zu einem Modell von

ϕ′ = ∀x_{1} … ∀x_{m} χ(x_{1}, …, x_{m}, f_{1}(x_{1}, …, x_{m}), …, f_{n}(x_{1}, …, x_{m}))

expandieren lassen.^{12}. ϕ′ hat zwei Quantorenwechsel weniger als ϕ. Jetzt verfahren wir mit ϕ′ ebenso und erhalten schließlich die Skolem–Normalform. □

11ϕ und ψ heißen äquivalent, wenn ϕ ↔ ψ allgemeingültig ist.

12Wenn m = 0, führen wir neue Konstanten ein.

Man nennt die neu eingeführten Funktionszeichen in L^{∗} Skolemfunktionen.

Beispiel: Sei

ϕ = ∀x (∃y R(x, y) ∧ ∀z ∃w S(x, z, w)).

Die pränexe Normalform ist (z.B.)

∀x ∃y ∀z ∃w (R(x, y) ∧ S(x, z, w)).

Der erste Umformungsschritt liefert

∀x, z ∃w (R(x, f(x)) ∧ S(x, z, w))

und der zweite

ϕ^{∗} = ∀x, z, w (R(x, f(x)) ∧ S(x, z, g(x, z)).

Folgerung 6.2 (Herbrand–Normalform) Zu jeder L–Aussage ϕ kann man eine Spracherweiterung L^{∗} und einen existentiellen L^{∗}–Satz ϕ_{∗} angeben, der genau dann allgemeingültig ist, wenn ϕ allgemeingültig ist.

Wichtig ist, daß man ϕ_{∗} explizit angeben kann. Die reine Existenz ist trivial. Man nimmt für ϕ_{∗} entweder ∃x x =^{.} x oder ∃x ¬ x =^{.} x, jenachdem ob ϕ erfüllbar ist oder nicht.

Beweis: ϕ ist genau dann allgemeingültig, wenn ¬ ϕ nicht erfüllbar ist. Man setzt also ϕ_{∗} = ¬ (¬ ϕ)^{∗}. □

Bemerkung Wir finden immer ein ϕ_{∗} ohne Gleichheitszeichen.

Beweis: Wegen Lemma 4.8 können wir annehmen, daß ϕ kein Gleichheitszeichen enthält. Im eben konstruierten ϕ^{∗} gibt es dann ebenfalls kein Gleichheitszeichen. □

Für die Allgemeingültigkeit existentieller Aussagen gibt es ein einfaches Kriterium.

Satz 6.3 (Satz von Herbrand) Sei

ϕ = ∃x_{1} … ∃x_{n}ψ(x_{1}, …, x_{n})

eine existentielle Aussage für eine Sprache L, die mindestens eine Konstante enthält. Dann ist ϕ genau dann allgemeingültig, wenn es konstante Terme

t_{1}^{1}, t_{2}^{1}, … t_{n}^{1} … t_{1}^{N}, t_{2}^{N}, … t_{n}^{N}

gibt, für die die quantorenfreie Aussage

⋁_{i=1}^{N} ψ(t^{i}) = ψ(t_{1}^{1}, t_{2}^{1}, … t_{n}^{1}) ∨ … ∨ ψ(t_{1}^{N}, t_{2}^{N}, … t_{n}^{N})

allgemeingültig ist.

Beweis: Weil ϕ aus ⋁_{i=1}^{N} ψ(t^{i}) folgt, ist ϕ allgemeingültig,wenn ⋁_{i=1}^{N} ψ(t^{i}) allgemeingültig ist. Nehmen wir umgekehrt an, an, daß ⋀_{i=1}^{N} ¬ ψ(t^{i}) für jede beliebige Wahl der t_{j}^{i} erfüllbar ist. Dann ist die Theorie

T = {¬ ψ(t_{1}, …, t_{n}) | t_{1}, …, t_{n} konstante Terme}

endlich erfüllbar. T hat nach dem Kompaktheitssatz ein Modell 𝔄. Sei A_{0} = {t^{𝔄} | t konstanter Term} die Menge der Elemente von A, die von konstanten Termen dargestellt werden. A_{0} ist nicht–leer und unter den auf 𝔄 definierten Operationen abgeschlossen. Wenn wir die Interpretation von L in 𝔄 auf A_{0} einschränken, erhalten wir also eine Unterstruktur 𝔄_{0}, in der ∀x_{1} … x_{n}¬ ψ(x_{1} … x_{n}) gilt und ϕ daher falsch ist. □

Beispiel: Wir betrachten die Aussage ϕ = ∃w∀x R(w, x) → ∀z∃y R(y, z). Eine pränexe Normalform ist ∀w∃x∀z∃y (¬ R(w, x) ∨ R(y, z)) und die Herbrand– Normalform ϕ_{∗} = ∃x∃y (¬ R(c, x) ∨ R(y, f(x)). Wenn wir x, y zum einen durch c, c und zu anderen durch f(c), c ersetzen, erhalten wir die allgemeingültige Disjunktion

(¬ R(c, c) ∨ R(c, f(c)) ∨ (¬ R(c, f(c)) ∨ R(c, f(f(c))).

Also ist ϕ_{∗} und daher auch ϕ allgemeingültig.

Wenn in ψ das Gleichheitszeichen nicht vorkommt, ist die Allgemeingültigkeit von ⋁_{i=1}^{N} ψ(t^{i}) ein reines Problem der Aussagenlogik. Eine quantorenfreie Aussage ϕ ohne Gleichheitszeichen ist genau dann allgemeingültig, wenn sie eine aussagenlogische Tautologie ist. Anders ausgedrückt: Man ersetzt jede in ϕ enthaltene Primformel R(s_{1}, …, s_{m}) durch eine Aussagenvariable p_{R(s_{1},...,s_{m})}. Die resultierende aussagenlogische Formel ist genau dann allgemeingültig, wenn ϕ allgemeingültig ist.

Es gibt drei Methoden, von einer aussagenlogischen Formel f festzustellen, ob sie allgemeingültig oder –dual– erfüllbar ist:

1. \underline{Wahrheitstafeln} Sei M die Menge aller in f vorkommenden Variablen und (μ_{i}) eine Liste aller Belegungen μ → {W, F}. Dann ist f genau dann erfüllbar, wenn man ein μ_{i} findet mit μ_{i}(f) = W.

2. \underline{Disjunktive Normalform} Man bringt f in disjunktive Normalform

⋁_{i=1}^{N} g_{i},

(wobei die g_{i} Konjunktionen von Variablen und negierten Variablen sind.). Dann ist f genau dann erfüllbar, wenn eines der g_{i} erfüllbar ist. g_{i} ist erfüllbar, wenn in g_{i} nicht eine Variable zusammen mir ihrer Negation vorkommt.

3. \underline{Konjunktive Normalform} Man bringt f in konjunktive Normalform

⋀_{i=1}^{N} c_{i},

wobei die c_{i} Disjunktionen von (negierten) Variablen sind, sogenannte Klauseln. Dann verwendet man die unten beschrieben Resolutionsmethode: Wir schließen die Menge C = {c_{i} | i = 1, …, N} der Klauseln unter Resolutionen ab. Wenn die leere Klausel (die leere Disjunktion) nicht in der resultierendem Menge C′ vorkommt, ist ϕ erfüllbar, sonst nicht.

Definition Nehmen wir an, daß in der Klausel c^{+} die Variable p positiv und in der Klausel c^{−} negativ vorkommt. Daß also bis auf die Reihenfolge c^{+} = p ∨ c_{0}^{+} und c^{−} = ¬ p ∨ c_{0}^{−}. Dann sagen wir, daß

c_{0}^{+} ∨ c_{0}^{−}

eine Resolution von c^{+} und c^{−} ist.

Die Resolution der beiden Klauseln p und ¬ p ist die (immer falsche) leere Klausel F.

Lemma 6.4 Sei C eine erfüllbare Menge von Klauseln und c eine Resolution von zwei Klauseln c^{+} und c^{−} aus C. Dann ist auch C ∪ {c} erfüllbar.

Beweis: Sei μ eine Belegung der Variablen, die alle Klauseln aus C wahr macht. Wenn μ(p) = W, ist μ(c^{+}) = W, sonst ist μ(c^{−}) = W. In beiden Fällen folgt μ(c) = W.

□

Satz 6.5 (Resolutionsmethode) Eine unter Resolutionen abgeschlossene Menge von Klauseln ist genau dann erfüllbar, wenn sie die leere Klausel nicht enthält.

Beweis: Sei p eine der in C vorkommenden Variablen. Sei C^{+} die Menge der c ∈ C, in denen ¬ p nicht als Konjunktionsglied vorkommt und C^{−} die Menge der c ∈ C, in denen p nicht vorkommt. Wir bilden C_{0}^{+} und C_{0}^{−}, indem wir p und ¬ p aus den Klauseln von C^{+} und C^{−} entfernen. Beide Mengen sind wieder unter Resolutionen abgeschlossen. Weil C nicht die leere Klausel enthält, kann nicht sowohl C^{+} die Klausel p als auch C^{−} die Klausel ¬ p enthalten. Also können nicht beide Mengen C_{0}^{+} und C_{0}^{−} die leere Klausel enthalten. Wenn wir unseren Beweis induktiv über die Zahl der vorkommenden Variablen führen, wissen wir, daß C_{0}^{+} oder C_{0}^{−} erfüllbar ist. Im ersten Fall belegen wir zusätzlich p mit dem Wert F, im zweiten Fall mit W und erhalten jedesmal ein Modell von C. Wir haben hier angenommen, daß C nur endlich viele Variable enthält. Was zu der intendierten Anwendung des Satzes paßt. Wenn C unendlich viele Variablen enthält verwenden wir den Kompaktheitssatz. □

Wenn man eine endliche Menge von Klauseln unter Resolutionen abschließt, erhält man im allgemeinen unendlich viele neue Klauseln, weil wir Klauseln, in denen eine Variable mehrere Male vorkommt, nicht ausgeschlossen haben. Wir nennen eine Klausel reduziert, wenn in ihr keine Variable doppelt vorkommt. Man erhält aus einer Menge von Klauseln eine äquivalente Menge von reduzierten Klauseln, indem man Klauseln, in denen eine Variable positiv und negativ vorkommt, wegläßt und in allen Klauseln doppelte Vorkommen von Variablen mit dem gleichen Vorzeichen streicht.

Eine Menge C von reduzierten Klauseln nennen wir reduziert abgeschlossen, wenn jede reduzierte Klausel, die aus der einer Resolution zweier Klauseln aus C durch Streichen doppelter Vorkommen von Variablen mit dem gleichen Vorzeichen entsteht, wieder zu C gehört. Man sieht nun leicht:

Bemerkung Sei C reduziert abgeschlossen. Wenn C die leere Klausel nicht enthält, enthält der Abschluß von C unter Resolutionen ebenfalls nicht die leere Klausel.

Beweis: C′ sei die Menge aller Klauseln in den Variablen von C, die eine Klausel aus C als Teilklausel enthalten oder in denen eine Variable positiv und negativ vorkommt. C′ ist unter Resolutionen abgeschlossen. □

Die Resolutionsmethode liefert dual eine Kriterium für die Allgemeingültigkeit von aussagenlogischen Formeln in disjunktiver Normalform: Sei C eine Menge von Konjunktionen von (eventuell negierten) Aussagenvariablen. Wir sagen, daß C unter Resolutionen abgeschlossen ist, wenn C mit zwei Konjunktionen p ∧ c^{+} und ¬ p ∧ c^{−} auch die Konjunktion c^{+} ∧ c^{−} enthält.

Folgerung 6.6 Die Menge C sei unter Resolutionen abgeschlossen. Dann ist ⋁ C genau dann allgemeingültig, wenn C die leere Konjunktion W enthält.

Wenn man den Satz von Herbrand (6.3) verwenden will, um die Allgemeingültigkeit einer Aussage ϕ = ∃x_{1} … ∃x_{n}ψ(x_{1}, …, x_{n}) ohne Gleichheitszeichen zu zeigen, bringt man ψ in disjunktive Normalform und wählt dann Terme t_{j}^{i}, für die man die letzte Folgerung auf ⋁_{i=1}^{N} ψ(t^{i}) anwenden kann. Die Terme wählt man so, daß genügend viele Formelpaare

R(s_{1}^{1}(x_{1}, …, x_{n}), …, s_{k}^{1}(x_{1}, …, x_{n}))

und

R(s_{1}^{2}(x_{1}, …, x_{n}), …, s_{k}^{2}(x_{1}, …, x_{n})),

in den Disjunktionsgliedern von ψ gleich werden, wenn man die x_{j} durch die t_{j}^{1} bzw. t_{j}^{2} ersetzt.

Man verwendet dazu die Unifikationsmethode. Seien

S^{1}(x_{1}, …, x_{n}) = (s_{1}^{1}(x_{1}, …, x_{n}), …, s_{k}^{1}(x_{1}, …, x_{n}))

und

S^{2}(x_{1}, …, x_{n}) = (s_{1}^{2}(x_{1}, …, x_{n}), …, s_{k}^{2}(x_{1}, …, x_{n}))

zwei gleichlange Folgen von Termen. Eine Termfolge T = (t_{1}, …, t_{n}) unifiziert S^{1} und S^{2}, wenn

S^{1}(t_{1}, …, t_{n}) = S^{2}(t_{1}, …, t_{n}).

Satz 6.7 (Unifikation) Wenn S^{1} und S^{2} unifizierbar sind, gibt es eine universelle unifizierende Termfolge U(y_{1}, …, y_{m}). Das heißt, daß eine Termfolge T genau dann S^{1} und S^{2} unifiziert, wenn es Terme t_{1}, …, t_{m} gibt, sodaß

T = U(t_{1}, …, t_{m}).

Man kann U durch ein einfaches Verfahren finden, das gleichzeitig entscheidet, ob S^{1} und S^{2} unifizierbar sind.

Beweis: Wir fassen das Paar S^{1}, S^{2} als eine Menge

S(x_{1}, …, x_{n}) = {s_{1}^{1} =^{.} s_{1}^{2}, …, s_{k}^{1} =^{.} s_{k}^{2}}

von Gleichungen auf. T unifiziert S, wenn alle Gleichungen aus S(T) allgemeingültig sind. Unser Unifikationsverfahren formt S in äquivalente Gleichungssysteme um. Dabei wenden wir, solange es geht, die folgenden Schritte A und B an.

\underline{Schritt A:} Wenn S eine Gleichung f^{1}(t_{1}^{1}, …, t_{l^{1}}^{1}) =^{.} f^{2}(t_{1}^{2}, …, t_{l^{2}}^{2}) enthält, gibt es zwei Möglichkeiten:

• Wenn f^{1} ≠ f^{2}, ist S nicht unifizierbar und das Verfahren bricht ab.

• Wenn f^{1} = f^{2} (und daher l^{1} = l^{2} = l), ersetzen wir die Gleichung durch die Gleichungen t_{1}^{1} =^{.} t_{1}^{2}, …, t_{l}^{1} =^{.} t_{l}^{2}.

\underline{Schritt B:} Wenn S eine Gleichung x_{i} =^{.} s enthält^{13}, gibt es drei Möglichkeiten:

• s = x_{i}. Dann streichen wir die Gleichung einfach.

• s ist ein zusammengesetzter Term, in dem x_{i} vorkommt. Dann ist S nicht unifizierbar und das Verfahren bricht ab.

• x_{i} kommt in s nicht vor. Dann ersetzen wir in allen anderen Gleichungen die Variable x_{i} durch s.

13Wir unterscheiden diese Gleichung nicht von s =^{.} x_{i}.

Wenn das Verfahren nicht mit dem Ergebnis, daß eine Unifikation unmöglich sei, abbricht, hat das Gleichungssystem – nach Umnumerierung der Variablen – die Form

x_{m} =^{.} u_{m}(x_{1}, …, x_{m−1}), …, x_{n} =^{.} u_{n}(x_{1}, …, x_{m−1})

für ein 1 ≤ m ≤ n + 1. Die gesuchte universelle unifizierende Termfolge ist dann

x_{1}, …, x_{m−1}, u_{m}, …, u_{n}.
□

Beispiel: Wir wollen die beiden Terme

k(x_{1}, x_{1}, x_{4}) und k(f(c, g(x_{2}, x_{3})), f(c, g(x_{3}, x_{2})), k(x_{3}, x_{2}, x_{1}))

unifizieren. Wir beginnen also mit der Gleichung

k(x_{1}, x_{1}, x_{4}) =^{.} k(f(c, g(x_{2}, x_{3}), f(c, g(x_{3}, x_{2})), k(x_{3}, x_{2}, x_{1})).

Schritt A:

x_{1} =^{.} f(c, g(x_{2}, x_{3}))
x_{1} =^{.} f(c, g(x_{3}, x_{2}))
x_{4} =^{.} k(x_{3}, x_{2}, x_{1})

Schritt B (ersetze x_{1} durch f(c, g(x_{2}, x_{3}))):

x_{1} =^{.} f(c, g(x_{2}, x_{3}))
f(c, g(x_{2}, x_{3})) =^{.} f(c, g(x_{3}, x_{2}))
x_{4} =^{.} k(x_{3}, x_{2}, f(c, g(x_{2}, x_{3})))

Schritt A:

x_{1} =^{.} f(c, g(x_{2}, x_{3}))
x_{2} =^{.} x_{3}
x_{3} =^{.} x_{2}
x_{4} =^{.} k(x_{3}, x_{2}, f(c, g(x_{2}, x_{3})))

Schritt B (ersetze x_{2} durch x_{3}):

x_{1} =^{.} f(c, g(x_{2}, x_{3}))
x_{2} =^{.} x_{3}
x_{4} =^{.} k(x_{3}, x_{3}, f(c, g(x_{3}, x_{3})))

Es ergibt sich die universelle Lösung

f(c, g(x_{3}, x_{3})), x_{3}, x_{3}, k(x_{3}, x_{3}, f(c, g(x_{3}, x_{3}))).

Folgerung 6.8 Sei ψ(x_{1}, …, x_{n}) eine quantorenfreie L–Formel ohne Gleichheitszeichen und N eine natürliche Zahl^{14}. Man kann effektiv entscheiden, ob es konstante Terme

t_{1}^{1}, t_{2}^{1}, … t_{n}^{1} … t_{1}^{N}, t_{2}^{N}, … t_{n}^{N}

gibt, für die

⋁_{i=1}^{N} ψ(t^{i}) = ψ(t_{1}^{1}, t_{2}^{1}, … t_{n}^{1}) ∨ … ∨ ψ(t_{1}^{N}, t_{2}^{N}, … t_{n}^{N})

allgemeingültig ist. □

14Der Fall N = 1 impliziert sofort die Folgerung für beliebiges N. Wir haben diese Fomulierung gewählt, wegen des Zusammenhangs mit Satz 6.3.

Mengenlehre

7 Die Axiome

Die Sprache der Mengenlehre ist L_{Me} = {ϵ}. Man liest „x ϵ y“ als x ist Element von y.

Die Axiome der Naiven Mengenlehre sind das Extensionalitätsaxiom: Zwei Mengen sind gleich, wenn sie die gleichen Elemente haben. Und das Schema der vollen Komprehension: Jede definierbare Klasse von Mengen ist die Klasse der Elemente einer Menge. In Formeln:

Axiom (Extensionalität)

∀x, y (∀z (z ϵ x ↔ z ϵ y) → x =^{.} y)

Axiom (Volle Komprehension) Für alle Formeln ϕ(x, y_{1}, …, y_{n})

∀y_{1} … y_{n}∃x∀z (z ϵ x ↔ ϕ(z, y_{1}, …, y_{n}))

(Um genau zu sein: Das Komprehensionsaxiom ist nicht ein einzelnes Axiom, sondern ein Axiomenschema)

Das volle Komprehensionsaxiom sagt, daß für jede Formel ϕ(z, y_{1}, …, y_{n}) und fixierte Parameter y_{1}, …, y_{n} die Klasse

{z | ϕ(z, y_{1}, …, y_{n})}

eine Menge ist.

Das System aller Mengen, wie wir sie uns vorstellen, scheint tatsächlich diese Axiome zu erfüllen. Es gilt aber die Russellsche Antinomie:

Satz 7.1 (Bertrand Russell) Die naive Mengenlehre ist inkonsistent.

Beweis:

Betrachte die Formel ϕ(x) = ¬ x ϵ x. Das Komprehensionsschema liefert dann das Axiom

∃x∀z (z ϵ x ↔ ¬ z ϵ z).

Wenn aber x eine Menge mit ∀z (z ϵ x ↔ ¬ z ϵ z) ist, also

x = {z | ¬ z ϵ z},

liefert die Einsetzung von x für z den Widerspruch x ϵ x ↔ ¬ x ϵ x. □

Es sind verschiedene Modifikationen der Mengenlehre vorgeschlagen worden (z.B. von Quine: New Foundation). Durchgesetzt hat sich

ZFC,

die nach ihren Erfindern Zermelo und Fränkel und nach „choice“, dem Auswahlaxiom benannt ist. Hier ist die Liste der Axiome, die wir im folgenden diskutieren:

• Extensionalität

• Aussonderung

• Paarmenge

• Vereinigung

• Potenzmenge

• Ersetzung

• Fundierung

• Unendlichkeit

• Auswahl

ZFC enthält natürlich das Extensionalitätsaxiom: Axiom (Extensionalität)

∀x, y (∀z (z ϵ x ↔ z ϵ y) → x =^{.} y)

Wir führen als „x ⊂ y“ als Abkürzung für die Formel ∀z (z ϵ x → z ϵ y) ein, gelesen als „x ist Teilmenge von y“. Das Extensionalitätsaxiom ist dann gleichbedeutend mit

∀x, y(x ⊂ y ∧ y ⊂ x) → x =^{.} y.

Dann folgen fünf Spezialfälle der vollen Komprehension.

Axiom (Aussonderung)

∀y_{0} … y_{n}∃x∀z (z ϵ x ↔ (z ϵ y_{0} ∧ ϕ(z, y_{1}, …, y_{n})))

Das Aussonderungsaxiom erlaubt es zum Beispiel den Durchschnitt

x ∩ y = {z ϵ x | z ϵ y}

und die Differenz

x \ y = {z ϵ x | ¬ z ϵ y}

von zwei Mengen zu bilden. Es ergibt sich auch die Existenz der leeren Menge.

∅ = {z | ¬ z =^{.} z}

Für eine beliebige Menge x ist nämlich ∅ = {z ϵ x | ¬ z =^{.} z}.

Die Russellsche Antinomie wird jetzt ein Theorem von ZFC: Bemerkung In ZFC ist beweisbar, daß die Klasse V aller Mengen keine Menge ist. Formal:

ZFC ⊢ ¬ ∃x∀z z ϵ x

Beweis: Sonst wäre nach dem Aussonderungsaxiom die Russellsche Klasse

{z | ¬ z ϵ z} = {z ∈ V | ¬ z ϵ z}

ebenfalls eine Menge, was sofort zu einem Widerspruch führt. □

Das Paarmengenaxiom Axiom (Paarmenge)

∀y_{1}, y_{2}∃x∀z z ϵ x ↔ (z =^{.} y_{1} ∨ z =^{.} y_{2})

besagt, daß

{x, y} = {z | z =^{.} x ∨ z =^{.} y}

eine Menge ist, die aus x und y gebildete Paarmenge. Definition Das geordnete Paar von zwei Mengen x und y ist die Menge

(x, y) = {{x}, {x, y}}.

(x, y) heißt Kuratowski Paar. Lemma 7.2 (ZFC)

ZFC ⊢ ∀x, y, x′, y′ (x, y) =^{.} (x′, y′) → x =^{.} x′ ∧ y =^{.} y′

□

Das Vereinigungsmengenaxiom ist

Axiom (Vereinigung)

∀y∃x∀z z ϵ x ↔ ∃w (z ϵ w ∧ w ϵ y).

Wir schreiben

⋃ y = {z | ∃w (z ϵ w ∧ w ϵ y)}.

⋃ y ist die Vereinigung der Elemente von y. Aus dem Paarmengenaxiom und dem Vereinigungsmengenaxiom folgt die Existenz der Vereinigung von zwei Mengen:

x ∪ y = ⋃{x, y}.

Man definiert rekursiv über n

{y_{1}, y_{2}, …, y_{n+1}} = {y_{1}, …, y_{n}} ∪ {y_{n+1}}.

Das Potenzmengenaxiom

Axiom (Potenzmenge)

∀y∃x∀z z ϵ x ↔ z ⊂ y

postuliert die Existenz der Potenzmenge

𝔓(y) = {z | z ⊂ y}.

Lemma 7.3 (ZFC) Aus den Axiomen von ZFC folgt für alle a und b die Existenz des direkten Produktes

a × b = {(x, y) | x ∈ a ∧ y ∈ b}.

Beweis: Wenn x ∈ a und y ∈ b, sind {x} und {x, y} Elemente von 𝔓(a ∪ b). Dann ist (x, y) = {{x}, {x, y}} ein Element von 𝔓(𝔓(a ∪ b)). Es folgt, daß {(x, y) | x ∈ a∧y ∈ b} eine definierbare Teilklasse von 𝔓(𝔓(a∪b)) ist. Also eine Menge nach dem Aussonderungsaxiom. □

Wir definieren Tripel durch

(x, y, z) = ((x, y), z)

und a × b × c = {(x, y, z) | x ∈ a, y ∈ b, z ∈ c}. Entsprechend Viertupel usw.

Eine Relation ist nun eine Menge von Paaren. Der Definitionsbereich von R ist

dom(R) = {x | ∃y (x, y) ∈ R},

der Bildbereich

Im(R) = {y | ∃x (x, y) ∈ R}.

Definitions– und Bildbereich sind Mengen, weil sie Teilklassen von ⋃ ⋃ R sind. Denn

{{x}, {x, y}} ∈ R ⇒ {x, y} ∈ ⋃ R ⇒ x, y ∈ ⋃ ⋃ R.

Eine Funktion f ist eine rechtseindeutige Relation^{1}:

∀x, y_{1}, y_{2} (x, y_{1}) ∈ f ∧ (x, y_{2}) ∈ f → y_{1} = y_{2}.

Man schreibt dann

f(x) = y (^{2})

für (x, y) ∈ f. Die Schreibweise

f : a → b

bedeutet dom(f) = a und Im(f) ⊂ b. Wenn wir b nicht spezifizieren wollen, schreiben wir f : a → V.

f ↾ c = f ∩ (c × b)

ist die Einschränkung von f auf c.

f[c] = {f(x) | x ∈ c}

ist der Bildbereich von f ↾ c.

Axiom (Ersetzung)

∀y, \overline{w}(∀u∃! z ϕ(u, z, \overline{w}) → ∃x∀z (z ϵ x ↔ ∃u(u ϵ y ∧ ϕ(u, z, \overline{w}))))

\overline{w} steht hier für ein Tupel von Variablen. ∃! ϕ(x), es gibt genau ein x …, steht

für ∃x(ϕ(x) ∧ ∀x′(ϕ(x′) → x =^{.} x′)).

Als ein Beispiel überlegen wir, wie wir ohne Verwendung des Potenzmengenaxioms die Existenz von a × b aus dem Ersetzungsaxiom schließen können: Wir halten zunächst x fest. Dann gilt offenbar

∀u∃! z z =^{.} (x, u).

Also gibt es eine Menge die genau aus den (x, u) mit u ∈ b besteht. Diese Menge ist natürlich {x} × b. Eine zweite Anwendung des Ersetzungsaxioms liefert die Existenz von c = {{x} × b | x ∈ a}. Schließlich ist a × b = ⋃ c.

Ein zweites Beispiel: Mit Hilfe des Ersetzungsaxiom sieht man leicht, daß die inverse Relation

R^{−1} = {(y, x) | (x, y) ∈ R}

eine Menge ist.

Eine Funktion f : a → b heißt surjektiv, wenn Im(f) = b,^{3}

1Wir identifizieren also eine Funktion mit ihrem Graphen.

2Wenn x ∉ dom(f), setzen wir f(x) = ∅.

injektiv, wenn f^{−1} eine Funktion ist,

bijektiv, wenn f injektiv und surjektiv ist.

\underline{Exkurs über definitorische Erweiterungen:} Die Einführung von neuen Relations– und Funktionszeichen

Sei T eine L–Theorie und ϕ(x_{1}, …, x_{n}) eine Formel. Wenn wir für ϕ ein neues (n–stelliges) Relationszeichen R einführen, erweitern wir L zu L′ = L∪{R} und T zu T′ = T ∪ {∀x_{1}, …, x_{n} R(x_{1}, …, x_{n}) ↔ ϕ(x_{1}, …, x_{n})}. Es ist klar, daß T′ sich nicht wesentlich von T unterscheidet. Erstens ist T′ eine konservative Erweiterung von T, das heißt, daß jede L–Aussage, die in T′ beweisbar ist, auch in T beweisbar ist. Zweitens ist jede L′–Formel zu einer L–Formel T′–beweisbar äquivalent.

Die Einführung neuer Funktionszeichen beschreiben wir in einem Satz.

Satz 7.4 Sei die Funktionalität von ϕ in T beweisbar, also

T ⊢ ∀x_{1}, …, x_{n}∃! x_{0}ϕ(x_{0}, …, x_{n}).

Sei f ein neues n–stelliges Funktionszeichen und L′ = L ∪ {f}. Dann ist die L′–Theorie

T′ = T ∪ {∀x_{1}, …, x_{n}ϕ(f(x_{1}, …, x_{n}), x_{1}, …, x_{n})}

eine konservative Erweiterung von T. Darüberhinaus gibt es zu jeder L′–Formel ψ eine L–Formel ψ^{∗} mit T′ ⊢ ψ ↔ ψ^{∗}.

Beweis: Ein T –Modell 𝔄 läßt sich (in genau einer Weise) zu einem T′–Modell expandieren, indem man f durch die Funktion interpretiert, die a_{1}, …, a_{n} das a_{0} zuordnet, für das 𝔄 ⊧ ϕ[a_{0}, …, a_{n}]. Daraus folgt, daß T′ eine konservative Erweiterung ist.

Die Übersetzung ψ^{∗} definiert man leicht rekursiv über den Aufbau von ψ. Etwas schwerer ist nur der Fall, daß ψ eine Primformel ist. Sei also zum Beispiel ψ = R(t_{1}, t_{2}). Wenn f zum Beispiel in t_{1} vorkommt, schreiben wir

t_{1} = s_{0}(f(s_{1}, …, s_{n}))

für L′–Terme s_{0}, …, s_{n} und setzen

ψ^{∗} = ∃x_{0}(ϕ(x_{0}, s_{1}, …, s_{n}) ∧ R(s_{0}(x_{0}), t_{2})^{∗}).
□

Satz 7.4 ist auch sinnvoll für n = 0. Wir führen dann allerdings kein Funktionszeichen sondern eine neue Konstante ein.

3Surjektivität und Bijektivität sind nicht Eigenschaften von f allein, sondern Eigenschaften des Paares f, b.

Definition Eine Erweiterung einer Theorie durch definierte Relationszeichen, Funktionszeichen und Konstanten heißt definitorische Erweiterung.

Man kann leicht zeigen, daß konservative Erweiterungen T′, für die jede L′– Formel zu einer L–Formel T′–beweisbar äquivalent ist, definitorisch sind.

\underline{Beispiele}:

Relationszeichen: x ⊂ y  f : a → b
Funktionszeichen: {z ∈ x | ϕ(z, y_{1}, …, y_{n})} x ∪ y  x ∩ y
x \ y ⋃ y 𝔓(y)
{x, y}  {y_{1}, …, y_{n}} (x, y)
x × y  dom(R)  Im(R)
R^{−1}  f(x)  f[x]
f ↾ y
Konstantenzeichen: ∅

Folgerung 7.5 Aussonderungsaxiom und Ersetzungsaxiom bleiben gültig, wenn ϕ neu eingeführte Relationszeichen, Funktionszeichen und Konstanten enthält.

In unserer Mengenlehre sind die Elemente von Mengen wieder Mengen. Demgemäß sind die einzigen Mengen, die wir konkret angeben können, letztlich aus der leeren Mengen aufgebaut: ∅, {∅, {∅}}, usw. Wir nennen eine aus der leeren Menge aufgebaute Menge fundiert. Die folgende Definition ist noch unpräzise, weil wir den Begriff der unendlichen Folge noch nicht eingeführt haben.

Definition (informell) Eine Menge x heißt fundiert, wenn jede bei x anfangende absteigende ∈–Kette

x ∋ y_{0} ∋ y_{1} ∋ …

nach endlich vielen Schritten abbricht.

Das Fundierungsaxiom drückt aus, daß jede Menge fundiert ist:

Axiom (Fundierung)

∀x(¬ x =^{.} ∅ → ∃z ϵ x z ∩ x =^{.} ∅)

Das läßt sich (informell^{4}) folgendermaßen einsehen: Wenn x das Axiom nicht erfüllt, hat jedes Element von x ein Element, das wieder zu x gehört. Man findet also (mit dem Auswahlaxiom) eine unendliche ∈–Kette von Elementen von x. Wenn umgekehrt y_{0} ∋ y_{1} … eine unendliche ∈–Kette ist, verletzt x = {y_{0}, y_{1}, …} das Fundierungsaxiom.

Folgerung 7.6 Eine Menge kann sich nicht selbst als Element enthalten.

4Man kann diese Schlußweise erst präzise machen, wenn die natürlichen Zahlen eingeführt sind.

Daraus ergibt sich ein zweiter Beweis dafür, daß V keine Menge ist. Sonst wäre nämlich V ∈ V.

Es gibt drei Rechtfertigungen für die Annahme des Fundierungsaxioms:

1. Unheimliche Mengen, wie solche, die nur sich selbst als Element enthalten (!!!), werden ausgeschlossen.

2. Man kann mit Hilfe der übrigen Axiome zeigen, daß es zu jeder Menge eine Bijektion mit einer fundierten Menge gibt. Fundierte Mengen genügen also, um Mathematik zu betreiben.

3. Sei (M, E) ein Modell aller Axiome von ZFC bis auf das Fundierungsaxiom. Setze N = {m ∈ M | (M, E) ⊧ m ist fundiert}. Dann ist (N, E ∩N^{2}) ein Modell von ZFC, das zusätzlich das Fundierungsaxiom erfüllt.

Die letzten beiden Axiome diskutieren wir in den nächsten Abschnitten.

Axiom (Unendlichkeit)

∃x(∅ ϵ x ∧ ∀z ϵ x z ∪ {z} ϵ x)

Axiom (Auswahl)

∀x(¬ ∅ ϵ x → ∃f : x → V ∀z ϵ x f(z) ϵ z)

8 Die natürlichen Zahlen

Die rekursive Definition

\underline{n} = \{\underline{0}, \underline{1}, …, \underline{n − 1}\}

ordnet jeder natürlichen Zahl n eine Menge \underline{n} zu. Es ist zum Beispiel

\underline{0} = ∅
\underline{1} = \{∅\}
\underline{2} = \{∅, \{∅\}\}
\underline{3} = \{∅, \{∅\}, \{∅, \{∅\}\}\}

Wir schreiben im folgenden s(x) für die Nachfolgeroperation x ∪ {x}. In ZFC ist dann für alle n beweisbar, daß

\underline{n + 1} = s(\underline{n}).

Man zeigt leicht durch Induktion:

Lemma 8.1 Wenn m < n ist

ZFC ⊢ ¬ \underline{m} =^{.} \underline{n}.

□

Folgerung 8.2 Für alle n, m ist

m < n ⟹ ZFC ⊢ \underline{m} ϵ \underline{n}
m ≥ n ⟹ ZFC ⊢ ¬ \underline{m} ϵ \underline{n}

Weil wir noch nicht wissen, wie man rekursive Definitionen in ZFC ausdrückt, ist dadurch der formale Begriff natürliche Zahl noch nicht definiert. Wir brauchen dazu:

Definition (ZFC) Sei < eine Relation auf^{5} a.

1. < ist eine partielle Ordnung , wenn

a) < irreflexiv ist: ¬ x < x für alle x ∈ a.

b) < transitiv ist: x < y ∧ y < z → x < z für alle x, y, z ∈ a.

2. Eine partielle Ordnung < auf a heißt linear, wenn für alle x, y ∈ a

x < y ∨ x =^{.} y ∨ y < x.

Definition (ZFC) Eine Menge x heißt transitiv, wenn alle ihre Element auch Teilmengen sind:

z ϵ y ϵ x → z ϵ x.

5Eine Relation auf a ist eine Teilmenge von a × a.

x ist genau dann transitiv, wenn ⋃ x ⊂ x.

Definition (ZFC) x heißt natürliche Zahl, wenn

1. x transitiv ist,

2. ∈ eine lineare Ordnung auf x definiert

3. und jede nicht–leere Teilmenge von x bezüglich dieser Ordnung ein kleinstes und ein größtes Element besitzt.

Daß jede nicht–leere Teilmenge von x ein bezüglich ∈ minimales Element hat, folgt schon aus dem Fundierungsaxiom und brauchte in der Definition nicht eigens gefordert zu werden. Wir haben diese Bedingung einerseits aufgenommen, weil eine Menge mit einer linearen Ordnung genau dann endlich (siehe S.54) ist, wenn jede nicht–leere Teilmenge ein kleinstes und ein größtes Element hat. Anderseits hat man so auch in Abwesenheit des Fundierungsaxioms die richtige Definition.

∈ ist schon eine lineare Ordnung von x, wenn die Elemente von x bezüglich ∈ vergleichbar sind. Denn ∈ ist irreflexiv nach dem Fundierungsaxiom. ∈ ist transitiv auf x, weil a ∈ b ∈ c ∈ x zur Folge hat, daß a ≠ c und c ∉ a und daher a ∈ c.

Lemma 8.3 (ZFC) 1. Eine natürliche Zahl besteht aus natürlichen Zahlen.

2. \underline{0} ist eine natürliche Zahl. Wenn x eine natürliche Zahl ist, ist auch s(x) eine natürliche Zahl.

3. Jede natürliche Zahl ≠ \underline{0} hat die Form s(y) für eine natürliche Zahl y.

2. impliziert, daß alle \underline{n} natürliche Zahlen sind. Aus 3. folgt (informell), daß man jede natürliche Zahl aus ∅ mit endlichen vielen Anwendungen der Operation s gewinnen kann.

Beweis: 1: Sei x eine natürliche Zahl und y ein Element von x. ∈ ordnet y ebenfalls linear und jede nicht–leere Teilmenge von y hat bezüglich ∈ ein kleinstes und ein größtes Element. Zu zeigen bleibt, daß y transitiv ist. Das folgt aber sofort aus der Transitivität von ∈ auf x.

2: Leicht.

3: Wenn die natürliche Zahl x nicht leer ist, hat x ein ∈–größtes Element y. Es ist also

x = {z | z ∈ y ∨ z =^{.} y} = s(y).

□

Wir bezeichnen mit ω die Klasse der natürlichen Zahlen.

Lemma 8.4 (ZFC) ω ist eine Menge.

Beweis: Sei x eine Menge wie im Unendlichkeitsaxiom. Wir zeigen, daß ω eine Teilmenge von x ist. Die Behauptung folgt dann aus dem Aussonderungsaxiom. Nehmen wir an, es gäbe ein a aus ω \ x. Sei b das kleinste Element von s(a), das nicht zu x gehört. Dann sind alle Elemente von b (die ja selbst wieder zu ω gehören) Elemente von x. Weil b ∉ x, ist b nicht leer. Also hat b die Form s(c). Dann ist c ∈ x, woraus aber auch b ∈ x folgt. Ein Widerspruch. □

Aus dem Beweis folgt:

Folgerung 8.5 (ZFC, Induktion) Eine Menge von natürlichen Zahlen, die \underline{0} enthält und unter s abgeschlossen ist, besteht aus allen natürlichen Zahlen.

Wir schreiben < für die ∈–Relation zwischen natürlichen Zahlen.

{Lemma 8.6 \atop 1.} < ist eine lineare Ordnung auf ω. Jede nicht–leere Teilmenge von ω hat ein kleinstes Element.

2. Für alle n ∈ ω ist s(n) der unmittelbare Nachfolger^{6} von n.

3. Alle n > \underline{0} haben einen unmittelbaren Vorgänger.

1. sagt, daß < eine Wohlordnung auf ω ist.

Beweis: Alle Aussagen sind leicht zu beweisen, außer der Vergleichbarkeit von je zwei natürlichen Zahlen. Sei also m ∈ ω festgehalten. Wir zeigen durch Induktion, daß alle n ∈ ω mit m vergleichbar sind. Zuerst müssen wir zeigen, daß \underline{0} mit m vergleichbar ist. Wenn m ≠ \underline{0}, hat m ein kleinstes Element m_{0}. Weil die Elemente von m_{0} auch Elemente von m sind, muß m_{0} = \underline{0} sein. Jetzt nehmen wir an, daß n mit m vergleichbar ist, und zeigen, daß auch s(n) mit m vergleichbar ist. Das ist klar, wenn m ≤ n^{7}. Wenn n < m, sei n_{0} der unmittelbare Nachfolger von n in der linearen Ordnung von s(m). Es ist also n_{0} ≤ m und die Elemente von n_{0} sind genau die Elemente von n und n selbst. Das heißt aber n_{0} = s(n) und daher s(n) ≤ m. □

Um + und · definieren zu können, brauchen wir den Rekursionssatz für ω.

Satz 8.7 (ZFC, Rekursionssatz) Seien zwei Funktionen g : A → B und h : A×ω×B → B gegeben. Dann existiert ein, eindeutig bestimmtes, f : A×ω → B mit

f(a, \underline{0}) = g(a)
f(a, s(n)) = h(a, n, f(a, n))

für alle a ∈ A und n ∈ ω Beweis: Wir halten a ∈ A fest. Man zeigt leicht durch Induktion über m, daß es für alle m ∈ ω genau ein f′ : s(m) → B gibt mit ϕ(a, m, f′), wobei

6d.h. s(n) ist die kleinste Zahl, die größer als n ist.

7Hier und später ist x ≤ y eine Abkürzung für x < y ∨ x =^{.} y.

ϕ(a, m, f′) = (f′(\underline{0}) =^{.} g(a) ∧ ∀n < m f′(s(n)) =^{.} h(a, n, f′(n))).

Wir definieren jetzt

f = {(a, m, b) ∈ (A × ω × B) | ∃f′ ϕ(a, m, f′) ∧ f′(m) =^{.} b}.

□

Definition Addition + : ω × ω → ω und Multiplikation · : ω × ω → ω werden definiert durch die Rekursionsgleichungen

a + \underline{0} = a
a + s(n) = s(a + n)
a · \underline{0} = \underline{0}
a · s(n) = (a · n) + a.

Rechenregeln wie

m + n = n + m

beweist man leicht durch Induktion.

9 Ordinalzahlen und Kardinalzahlen

Definition Eine Ordinalzahl ist eine transitive Menge, die durch ∈ linear geordnet wird.

Alle natürlichen Zahlen und ω sind Ordinalzahlen. Wir bezeichnen mit On die Klasse der Ordinalzahlen.

{Lemma 9.1 \atop 1.} On wird durch ∈ linear geordnet. (Wir nennen diese lineare Ordnung <.)

2. Jede nicht–leere Teilklasse von On hat ein minimales Element.

3. Jede Ordinalzahl α ist die Menge ihrer Vorgänger:

α = {β ∈ On | β < α}

4. On ist keine Menge.

Beweis: Sei S ⊊ α ein echtes Anfangsstück (d.h. x < y ∈ S → y ∈ S) von α und β ∈ α das kleinste Element von α \ S. Dann ist offensichtlich β = S. Wenn nun α und β zwei Ordinalzahlen sind, ist S = α ∩ β ein Anfangsstück von α und β. S kann nicht sowohl von α als auch von β verschieden sein, weil sonst S selbst ein Element von α und β sein müßte. Wenn aber S = α, ist α ≤ β, und wenn S = β, ist β ≤ α. Daraus folgt, daß alle Ordinalzahlen vergleichbar sind. Wie auf Seite 47 folgt, daß ∈ die Klasse aller Ordinalzahlen linear ordnet. Daß jede nicht–leere Teilklasse von On ein minimales Element hat, folgt sofort aus dem Fundierungsaxiom.

3. bedeutet lediglich, daß Ordinalzahlen aus Ordinalzahlen bestehen. Das zeigt man aber wie Lemma 8.3 (1). Wenn On ein Menge wäre, wäre On selbst eine Ordinalzahl und müßte sich selbst als Element enthalten. □

Aus 2. folgt ein Induktionsprinzip: Eine Teilklasse U von On enthält alle Ordinalzahlen, wenn für alle α

α ⊂ U → α ∈ U.

Eine Ordinalzahl der Form s(α) heißt Nachfolgerzahl. Man schreibt auch α + 1 für den Nachfolger von α. Eine Ordinalzahl > \underline{0}, die keine Nachfolgerzahl ist, heißt Limeszahl.

Eine Klasse A ist ein System \{x | ϕ(x, \overline{a})\} von Mengen, die eine Formel ϕ(x, \overline{a}), mit festgehaltenen Parametern \overline{a} = a_{1}, …, a_{n}, erfüllen. Das Aussonderungsaxiom besagt, daß der Durchschnitt einer Menge mit einer Klasse wieder eine Menge ist.

Ein Funktional F : A → V ist eine funktionale Klasse von Paaren aus A×V. Es ist also ∀x ∈ A ∃! y (x, y) ∈ F. Das Ersetzungsaxiom läßt sich so formulieren: Wenn a eine Menge ist und F : V → V ein Funktional, ist F [a] eine Menge.

Satz 9.2 (ZFC, Rekursionssatz) Zu jedem Funktional G : V → V kann man ein Funktional F : On → V angeben, sodaß für alle α ∈ On

F (α) = G(F ↾ α).

Beweis: Wir zeigen zuerst, daß es für alle β genau eine Funktion f : β → V gibt, die für alle α ∈ β die Rekursionsgleichung erfüllt.

Zuerst die Eindeutigkeit: Wenn es ein anderes f′ : β → V gibt, gibt es ein kleinstes α < β mit f(α) ≠ f′(α). Aus f ↾ α = f′ ↾ α folgt aber f(α) = f′(α).

Wir zeigen die Existenz durch Induktion über β. Nehmen wir also an, daß die Behauptung schon für alle β′ < β gezeigt ist. Es gibt drei Fälle:

1. β = \underline{0}. Wir setzen f = ∅

2. β = β′ + 1. Wir wählen ein f′ : β′ → V, das die Rekursionsgleichung erfüllt und setzen f = f′ ∪ {(β′, G(f′))}.

3. β ist eine Limeszahl. Nach dem Ersetzungsaxiom ist

X = {f′ : β′ → V | β′ < β, f′ erfüllt die Rekursionsgleichung.}

eine Menge, weil die f′ eindeutig durch β′ bestimmt sind. Aus demselben Grund ist f = ⋃ X ein Funktion.

Schließlich setzen wir

F = ⋃{f : β → V | β ∈ On, f erfüllt die Rekursionsgleichung.}

□

Wenn wir V_{α} definieren durch

V\underline{0} = ∅
V_{α+1} = 𝔓(V_{α})
V_{λ} = ⋃_{α<λ} V_{α}, λ Limeszahl

erhalten wir die von Neumann Hierarchie. Man zeigt leicht, daß

V = ⋃_{α∈On} V_{α}.

V_{ω} besteht aus den erblich endlichen Mengen. Eine Menge heißt erblich endlich, wenn sie in einer endlichen (siehe S.54) transitiven Menge enthalten ist.

Ordinalzahlen werden durch < wohlgeordnet. Das folgende Lemma besagt, daß Ordinalzahlen Wohlordnungstypen sind.

Lemma 9.3 Jede Wohlordnung ist zu genau einer Ordinalzahl isomorph.

Beweis: Sei (a, <) eine Wohlordnung. Wir suchen eine Ordinalzahl α und eine Bijektion f : α → a, die ordnungstreu ist:

x < y ⇔ f(x) < f(y)

Sei ∗ eine Menge, die nicht zu a gehört^{8}. Wir definieren

F : On → a ∪ {∗}

durch

F (β) = \{ \begin{matrix}min(a \ F [β]) & wenn a ⊄ F [β] \\ ∗ & sonst \end{matrix}

Wenn ∗ nicht im Bild von F vorkäme, wäre F eine ordnungstreu (also injektive) Abbildung von On nach a. Dann wäre aber On = F^{−1}[a] eine Menge nach dem Ersetzungsaxiom. Sei α die kleinste Ordinalzahl, für die F (α) = ∗. Dann ist f = F ↾ α die gesuchte Bijektion. α ist eindeutig bestimmt. Denn sei f′ : α′ → a ein zweiter Isomorphismus. Dann erfüllt F′ = f′ ∪ {(β, ∗) | α ≤ β} die gleiche Rekursionsgleichung und es folgt F′ = F und α′ = α. □

Aus dem Beweis folgt, daß nicht nur α sondern auch der Isomorphismus zwischen a und α eindeutig bestimmt ist.

Eine Funktion f : x → V mit f(z) ∈ z für alle z ∈ x heißt Auswahlfunktion. Das Auswahlaxiom sagt, daß jede Menge x von nicht–leeren Mengen eine Auswahlfunktion besitzt. Wenn ⋃ x eine Wohlordnung besitzt, existiert eine Auswahlfunktion, ohne daß man das Auswahlaxiom annehmen muß. Man setzt einfach f(z) = min(z). Umgekehrt folgt aus dem Auswahlaxiom

Satz 9.4 (Wohlordnungssatz) Jede Menge hat eine Wohlordnung.

Beweis: Sei a eine Menge und ∗ ∉ a. Man wählt eine Auswahlfunktion g : 𝔓(a)\{∅} → a. Definiere

F : On → a ∪ {∗}

durch

F (β) = \{ \begin{matrix}g(a \ F [β]) & wenn a ⊄ F [β] \\ ∗ & sonst \end{matrix}

Wie im Beweis von 9.3 sieht man, daß es ein α gibt, für das f = F ↾ α eine Bijektion zwischen α und a ist. Diese Bijektion transportiert die Wohlordnung von α auf a: Wir setzen

x < y ⇔ f^{−1}(x) < f^{−1}(y).

8z.B. ∗ = a

□

Aus dem Auswahlaxiom folgt auch das Zornsche Lemma, das wie der Wohlordnungssatz zum Auswahlaxiom äquivalent ist.

Satz 9.5 (Zornsches Lemma) Sei (A, <) eine partielle Ordnung, in der jede linear geordnete Teilmenge K eine obere Schranke s besitzt. Dann besitzt A ein maximales Element m.

Eine (echte) obere Schranke von K ist ein Element s mit a ≤ s (a < s) für alle a ∈ K. m ist ein maximales Element von A, wenn A keine Elemente hat, die größer als m sind.

Beweis: Das Auswahlaxiom liefert uns ein Funktional G, das jeder Teilmenge von A, die eine echte obere Schranke hat, eine echte obere Schranke zuordnet und das sonst den Wert ∗ hat. Wir definieren

F : On → A ∪ {∗}

durch

F (β) = G(F [β]).

Wenn F den Wert ∗ nicht annehmen würde, wäre F eine ordnungstreue Abbildung von On nach A, was nicht geht. Sei α minimal mit F (α) = ∗. Dann ist K = F [α] eine linear geordnete Teilmenge von A, die keine echte obere Schranke hat. Sei m eine obere Schranke (und damit größtes Element) von K. Dann ist m maximal in A. □

Definition Zwei Mengen a und b heißen gleichmächtig (in Zeichen a ∼ b), wenn es eine Bijektion zwischen a und b gibt. Mit der Schreibweise a ⪯ b drücken wir aus, daß es eine Injektion f : a → b gibt.

a ⪯ b bedeutet, daß a gleichmächtig mit einer Teilmenge von b ist. Man überlegt leicht, daß a ⪯ b genau dann gilt, wenn a leer ist oder wenn es eine surjektive Abbildung von b nach a gibt.

Aus dem Wohlordnungssatz folgt, daß jede Menge gleichmächtig zu einer Ordinalzahl ist.

Definition Die Mächtigkeit |a| einer Menge a ist die kleinste Ordinalzahl, die gleichmächtig zu a ist:

|a| = min{α ∈ On | α ∼ a}

Lemma 9.6

(1)  a ∼ b ⇔ |a| = |b|
(2)  a ⪯ b ⇔ |a| ≤ |b|

Beweis:

(1) folgt sofort aus der Tatsache, daß ∼ eine Äquivalenzrelation ist. Die Richtung „⇐“ von (2) folgt aus β ≤ α ⇒ β ⊂ α. Die Umkehrung folgt aus dem nächsten Hilfssatz. □

Hilfssatz Sei α eine Ordinalzahl und S eine Teilmenge von α. Dann ist der Ordnungstyp von S (mit der induzierten Wohlordnung) nicht größer als α.

Beweis: Wir zeigen durch Induktion über β: Wenn es eine ordnungstreue Funktion f : β → α (z.B. mit Bildbereich S) gibt, ist β ≤ α: Sei die Behauptung für alle β′ < β bewiesen. Dann folgt β′ ≤ f(β′) < α für alle β′ < β. Daraus folgt β ≤ α. □

Wir nennen α eine Kardinalzahl, wenn α = |α|. Die Mächtigkeit einer Menge ist immer eine Kardinalzahl.

Lemma 9.7 Alle natürlichen Zahlen und ω sind Kardinalzahlen.

Beweis: Wir zeigen durch Induktion über n, daß n ∼ m ⇒ n = m für alle m ∈ ω. Das ist klar für n = \underline{0}. Sei f : n + 1 → m′ eine Bijektion. Weil m′ nicht \underline{0} sein kann, ist m′ = m + 1. Wenn f(n) = m, ist f ↾ n eine Bijektion zwischen n und m. Wir schließen n = m und daraus n + 1 = m′. Sonst sei f(x) = m für ein x < n. Dann ist die Funktion

g(z) = \{ \begin{matrix}f(n) & wenn z = x \\ z & sonst \end{matrix}

eine Bijektion zwischen n und m.

Aus n ⪯ ω folgt n = |n| ≤ |ω|. Also ist |ω| größer als alle n < ω. Es folgt |ω| = ω. □

Eine Menge a heißt endlich, wenn |a| < ω. Wenn |a| = ω, heißt a abzählbar.

Satz 9.8 (Cantor)

|a| < |𝔓(a)|

Beweis: Sei f : a → 𝔓(a) eine Abbildung. Die Menge

b = {x ∈ a | x ∉ f(x)}

kann nicht im Bild von f liegen. Es gibt also keine Surjektion von a nach 𝔓(a). □

Es folgt, daß es keine größte Kardinalzahl gibt. Man bezeichnet mit κ^{+} die kleinste Kardinalzahl, die größer als κ ist. Es ist ω^{+} ≤ |𝔓(ω)|. Die Aussage

ω^{+} = |𝔓(ω)|

ist die Kontinuumshypothese (CH). Wenn ZFC widerspruchsfrei ist, kann CH weder bewiesen noch widerlegt werden.

Man zeigt leicht durch Induktion, daß für disjunkte endliche Mengen

|a ∪ b| = |a| + |b|.

Daraus folgt (wiederum durch Induktion), daß

|m × n| = m · n

für alle m, n ∈ ω.

Satz 9.9 Wenn a unendlich ist, ist

|a × a| = |a|

Beweis: Wir führen den Beweis nur für abzählbare a. Den allgemeinen Fall beweist man ähnlich^{9}.

Die lexikographische Ordnung

(l, m, n) < (l′, m′, n′) ⟺ \{ \begin{matrix}l < l′ & & oder \\ l = l′, & m < m′ & oder \\ l = l, & m = m′, & n < n′ \end{matrix}

auf ω ×ω ×ω ist eine Wohlordnung. Wir definieren eine Wohlordnung von ω ×ω durch

(m, n) < (m′, n′) ⟺ (max(m, n), m, n) < (max(m′, n′), m′, n′).

Sei l = max(m, n) + 1. Dann sind alle Vorgänger von (m, n) in l × l enthalten. Es gibt also nur endlich viele (nämlich höchstens l · l) Vorgänger. Daraus folgt, daß der Ordnungstyp von (ω × ω, <) nicht größer als ω sein kann. Also ist |ω × ω| = ω. □

9Durch Induktion über |a|

10 Metamathematik von ZFC

Wir ordnen jeder L_{Me}–Formel ψ eine Konstante ⌜ψ⌝ in einer definitorischen Erweiterung von ZFC zu^{10} (siehe 7.4). Zunächst ordnen wir allen Zeichen einen Term zu:

⌜=^{.}⌝ = (\underline{0}, \underline{0})
⌜∧⌝ = (\underline{0}, \underline{1})
⌜¬ ⌝ = (\underline{0}, \underline{2})
⌜(⌝ = (\underline{0}, \underline{3})
⌜)⌝ = (\underline{0}, \underline{4})
⌜∃⌝ = (\underline{0}, \underline{5})
⌜ϵ⌝ = (\underline{0}, \underline{6})
⌜v_{0}⌝ = (\underline{1}, \underline{0})
⌜v_{1}⌝ = (\underline{1}, \underline{1})
… = …

Für eine Formel ψ = ζ_{0} ζ_{1} … ζ_{n−1} der Länge n setzen wir

⌜ψ⌝ = \{(\underline{0}, ⌜ζ_{0}⌝), …, (\underline{n−1}, ⌜ζ_{n−1}⌝)\}.

Satz 10.1 (Fixpunktsatz) Für jede L_{Me}–Formel Σ(x) gibt es eine Aussage ϕ mit

ZFC ⊢ ϕ ⟷ Σ(⌜ϕ⌝).

Beweis: Wir meinen mit ψ(⌜χ⌝) eigentlich die L_{Me}–Aussage, die in der definitorischen Erweiterung von ZFC zu ψ(⌜χ⌝) äquivalent ist (siehe 7.4). Wir brauchen das folgende Lemma:

Lemma 10.2 Es gibt eine in ZFC definierbare Funktion Sub mit

ZFC ⊢ ⌜ψ(⌜χ⌝)⌝ =^{.} Sub(⌜ψ⌝, ⌜χ⌝)

für alle L_{Me}–Formeln ψ(x) und χ.

Beweis: Sub beschreibt einfach die Einsetzung in Formeln. □

Sei nun ψ(v_{0}) die L_{Me}–Formel die zu Σ(Sub(v_{0}, v_{0})) äquivalent ist. Dann sind in ZFC die folgenden Aussagen äquivalent:

ψ(⌜ψ⌝) ∼ Σ(Sub(⌜ψ⌝, ⌜ψ⌝)) ∼ Σ(⌜ψ(⌜ψ⌝)⌝)

Wenn man jetzt ϕ = ψ(⌜ψ⌝) setzt, ergibt sich die Behauptung. □

Der folgende Satz von Tarski behauptet die Unmöglichkeit einer Wahrheitsdefinition in ZFC.

10In Abschnitt 14 werden wir mit ⌜ψ⌝ die Gödelnummer von ψ bezeichnen.

Folgerung 10.3 (Tarski) Wenn ZFC widerspruchsfrei ist, gibt es keine Formel W(x), so daß für alle Aussagen ϕ

ZFC ⊢ ϕ ⟷ W(⌜ϕ⌝)

Beweis: Wähle ein ϕ mit ZFC ⊢ ϕ ⟷ ¬ W(⌜ϕ⌝). □

Das Beweisbarkeitsprädikat

Sei Bew(x) die Formel, die (in ZFC) ausdrückt, daß x eine in ZFC beweisbare Aussage ist. Es sollte klar^{11} sein, daß Bew(x) die folgenden Loeb–Axiome erfüllt: (Man beachte, daß L3 gilt, weil L1 in ZFC beweisbar ist.)

L1 ZFC ⊢ ϕ ⟹ ZFC ⊢ Bew(⌜ϕ⌝)

L2 ZFC ⊢ Bew(⌜ϕ⌝) ∧ Bew(⌜ϕ → ψ⌝) → Bew(⌜ψ⌝)

L3 ZFC ⊢ Bew(⌜ϕ⌝) → Bew(⌜Bew(⌜ϕ⌝)⌝)

Folgerung 10.4

(1) ZFC ⊢ ϕ → ψ ⟹ ZFC ⊢ Bew(⌜ϕ⌝) → Bew(⌜ψ⌝)

(2) ZFC ⊢ Bew(⌜ϕ ∧ ψ⌝) ⟷ (Bew(⌜ϕ⌝) ∧ Bew(⌜ψ⌝))

Beweis:

(1) : Aus ZFC ⊢ ϕ → ψ folgt ZFC ⊢ Bew(⌜ϕ → ψ⌝) wegen L1, und daraus, mit L2, die Behauptung ZFC ⊢ Bew(⌜ϕ⌝) → Bew(⌜ψ⌝).

(2) ZFC ⊢ Bew(⌜ϕ ∧ ψ⌝) → Bew(⌜ϕ⌝) und ZFC ⊢ Bew(⌜ϕ ∧ ψ⌝) → Bew(⌜ψ⌝) folgen sofort aus (1). Aus (1) folgt auch

ZFC ⊢ Bew(⌜ϕ⌝) → Bew(⌜ψ → (ϕ ∧ ψ)⌝).

Wegen L2 ist

ZFC ⊢ Bew(⌜ψ⌝) ∧ Bew(⌜ψ → (ϕ ∧ ψ)⌝) → Bew(⌜ϕ ∧ ψ⌝).

Daraus folgt (Bew(⌜ϕ⌝) ∧ Bew(⌜ψ⌝)) → Bew(⌜ϕ ∧ ψ⌝).

□

Sei F eine Formel, deren Negation allgemeingültig ist, z.B. ¬ \underline{0} =^{.} \underline{0}. Die Aussage

CON_{ZFC} = ¬ Bew(⌜F⌝)

drückt dann die Konsistenz von ZFC aus.

11Im Abschnitt 19 werden wir uns mit dem Beweisbarkeitsprädikat der Peanoarithmetik etwas mehr Mühe geben.

Satz 10.5 (Zweiter Gödelscher Unvollständigkeitssatz für ZFC) Wenn ZFC konsistent ist, ist CON_{ZFC} in ZFC unbeweisbar.

Beweis: Natürlich folgt aus der Unbeweisbarkeit von CON_{ZFC} die Konsistenz von ZFC. Wenn wir den Satz (natürlich in ZFC) bewiesen haben, haben wir gezeigt, daß

ZFC ⊢ CON_{ZFC} ⟷ ¬ Bew(⌜CON_{ZFC}⌝).

Wir beginnen daher mit einer Formel ϕ, die

ZFC ⊢ ϕ ⟷ ¬ Bew(⌜ϕ⌝) (3)

erfüllt. Wir zeigen zuerst, daß tatsächlich^{12}

(4) ZFC ⊢ ϕ ⟷ CON_{ZFC}

Zunächst folgt aus ZFC ⊢ F → ϕ und (1), daß ZFC ⊢ Bew(⌜F⌝) → Bew(⌜ϕ⌝). Also ist ZFC ⊢ ϕ → CON_{ZFC}.

Dann folgt aus ZFC ⊢ ϕ → ¬ Bew(⌜ϕ⌝), daß

ZFC ⊢ Bew(⌜ϕ⌝) → Bew(⌜¬ Bew(⌜ϕ⌝)⌝).

Zusammen mit L3 ergibt das

ZFC ⊢ Bew(⌜ϕ⌝) → (Bew(⌜¬ Bew(⌜ϕ⌝)⌝) ∧ Bew(⌜Bew(⌜ϕ⌝)⌝)).

Weil aber wegen 10.4

ZFC ⊢ Bew(⌜¬ Bew(⌜ϕ⌝)⌝) ∧ Bew(⌜Bew(⌜ϕ⌝)⌝) → Bew(⌜F⌝),

folgt Bew(⌜ϕ⌝) → ¬ CON_{ZFC}, das heißt ZFC ⊢ CON_{ZFC} → ϕ. Damit ist (4) bewiesen.

Nehmen wir an, daß ZFC ⊢ CON_{ZFC}. Dann ist ZFC ⊢ ϕ wegen (4). Daraus folgt mit L1 ZFC ⊢ Bew(⌜ϕ⌝) und mit (3) ZFC ⊢ ¬ Bew(⌜ϕ⌝). ZFC wäre also inkonsistent. □

Wenn wir wüßten, daß alle Aussagen, die in ZFC beweisbar sind, auch wahr wären, wäre CON_{ZFC} unabhängig von ZFC: Weder CON_{ZFC} noch ¬ CON_{ZFC} sind dann aus ZFC beweisbar. Es ist aber denkbar^{13}, daß ZFC zwar konsistent ist, aber ZFC ⊢ ¬ CON_{ZFC}. Um (unter der Voraussetzung der Konsistenz) eine von ZFC unabhängige Aussage zu finden, müssen wir anders vorgehen.

Man kann leicht eine Liste ϕ_{0}, ϕ_{1}, … aller in ZFC beweisbaren Aussagen angeben. Wenn man es vernünftig gemacht hat, läßt sich

ϕ ist die n-te beweisbare Aussage mit einer L_{Me}–Formel Bew(x, y) ausdrücken, die die folgenden Eigenschaft hat:

12Wir verwenden nur „←“.

13 Nehmen wir an, daß ZFC ⊬ ¬ CON_{ZFC}. Dann ist ZFC^{+} = ZFC + CON_{ZFC} konsistent.

Aus dem zweiten Gödelschen Unvollständigkeitssatz (für ZFC^{+}) folgt, daß man in ZFC^{+} die Konsistenz von ZFC^{+} nicht beweisen kann. Man kann also nicht beweisen, daß ZFC ⊬ ¬ CON_{ZFC}.

Für alle n = 0, 1, … und alle Aussagen ϕ ist

(5)  ϕ = ϕ_{n} ⟹ ZFC ⊢ Bew(⌜ϕ⌝, \underline{n})
(6)  ϕ ≠ ϕ_{n} ⟹ ZFC ⊢ ¬ Bew(⌜ϕ⌝, \underline{n}).

Sei R eine Aussage mit

ZFC ⊢ R ⟷ ∀ y ϵ ω (Bew(⌜R⌝, y) → ∃z < y Bew(⌜¬ R⌝, z)).^{14} Man nennt R einen Rossersatz.

Satz 10.6 (Erster Gödelscher Unvollständigkeitssatz für ZFC) Wenn ZFC konsistent ist, ist R unabhängig von ZFC.

Beweis: Für beliebiges ψ sei ψ^{∗} die Aussage

∀ y ϵ ω (Bew(⌜ψ⌝, y) → ∃z < y Bew(⌜¬ ψ⌝, z)).

Wir zeigen zuerst

(7)  ZFC ⊢ ψ ⟹ ZFC ⊢ ¬ ψ^{∗}
(8)  ZFC ⊢ ¬ ψ ⟹ ZFC ⊢ ψ^{∗}.

Daraus folgt ZFC ⊢ R ⟺ ZFC ⊢ ¬ R und damit die Behauptung des Satzes. Beweis von (7): Wenn ZFC ⊢ ψ, gibt es nach (5) ein n mit ZFC ⊢ Bew(⌜ψ⌝, \underline{n}). Weil ZFC konsistent ist^{15}, ist wegen (6) ZFC ⊢ ¬ Bew(⌜¬ ψ⌝, \underline{m}) für alle m. Daraus folgt ZFC ⊢ ¬ ∃z < \underline{n} Bew(⌜¬ ψ⌝, z) und schließlich ZFC ⊢ ¬ ψ^{∗}. Beweis von (8): Wenn ZFC ⊢ ¬ ψ, gibt es ein m mit ZFC ⊢ Bew(⌜¬ ψ⌝, \underline{m}) und es ist ZFC ⊢ ¬ Bew(⌜ψ⌝, \underline{n}) für alle n. Daraus folgt

ZFC ⊢ ∀ y ϵ ω (Bew(⌜ψ⌝, y) → \underline{m} < y)

und schließlich ZFC ⊢ ψ^{∗}. □

14 Eigentlich müßte man statt Bew(⌜¬ R⌝, z) die Formel Bew(Neg(⌜¬ R⌝), z) nehmen, für eine definierbare Funktion Neg mit ZFC ⊢ ⌜¬ ϕ⌝ =^{.} Neg(⌜ϕ⌝) für alle ϕ.

15 (7) und 8) gelten natürlich auch, wenn ZFC inkosistent ist.

Rekursionstheorie

11 Registermaschinen

Wir fixieren eine L–elementiges Alphabet A = {a_{1}, …, a_{L}}. Mit A^{∗} bezeichnen wir die Menge der Wörter, die sich aus den Buchstaben von A bilden lassen. Eine Registermaschine über A mit Registern R_{0}, …, R_{R−1} ist eine Folge

M = (b_{0}, …, b_{N})

von Befehlen. Es gibt drei Sorten von Befehlen:

Stopbefehl : 0 Wir nehmen an, daß b_{N} = 0
Schreibbefehl : (r, l)  (r < R, l ≤ L)
Verzweigung : (r, c_{0}, …, c_{L}) (r < R, c_{i} ≤ N)

Eine Konfiguration ist ein R + 1–Tupel K = (c, R_{0}, …, R_{R−1}) mit c ≤ N und R_{i} ∈ A^{∗}. Die Anfangskonfiguration beim Input w_{1}, …, w_{n} ist (0, ∅, w_{1}, …, w_{n}, ∅, …). Eine Stopkonfiguration ist eine Konfiguration (c, …) mit b_{c} = 0).

Die Nachfolgekonfiguration M(K) ist wie folgt definiert: Sei

K = (c, R_{0}, …, R_{R−1})

und b = b_{c} der aktuelle Befehl.

1.Fall b = 0  Dann ist M(K) = K.

2.Fall (r, l) Dann ist M(K) = (c + 1, R_{0}, …, \overline{R}_{r}, …, R_{R−1}), wobei

\overline{R}_{r} = \{ \begin{matrix}R_{r}a_{l} & (l ≥ 1) \\ R_{r} . − 1 & (l = 0) \end{matrix}

3.Fall b = (r, c_{0}, …, c_{L}) Falls R_{r} ≠ ∅, sei a_{i} der letzte Buchstabe von R_{r}. Dann ist M(K) = (\overline{c}, R_{0}, …, R_{R−1}), wobei

\overline{c} = \{ \begin{matrix}c_{0} & falls R_{r} = ∅ \\ c_{i} & sonst \end{matrix}

Dabei entsteht w . − 1 aus w durch Streichen des letzten Buchstabens.

M berechnet auf folgende Weise eine partielle Funktion

F_{M}^{n} : \underbrace{A^{∗} × … A^{∗}}_{n} → A^{∗}.

Seien w_{1}, …, w_{n} der Input und K_{0} die Anfangskonfiguration. Wenn für alle s M^{s}(K_{0}) kein Stopkonfiguration ist, dann ist F_{M}^{n}(w_{1}, …, w_{n}) undefiniert. Wenn M^{s}(K_{0}) = (c, R_{0}, …) eine Stopkonfiguration ist, setzen wir F_{M}^{n}(w_{1}, …, w_{n}) = R_{0}.

Die Funktion F_{M}^{n} heißt maschinenberechenbar.

[figure: b_{0}; ⋮; b_{c}; ⋮; b_{N}; …; R_{0}; R_{1}; …; R_{n}; …; R_{R−1}]

Im Alphabet A = { | } = {a_{1}} stellen wir jede natürliche Zahl m durch m Striche |^{m} dar. M berechnet so eine partielle Funktion

F_{M}^{n} : ℕ^{n} → ℕ.

Wir geben eine äquivalente Beschreibung dieser Funktionen:

Definition Eine Funktion f : ℕ^{n} → ℕ, (n ≥ 0) heißt rekursiv, wenn sie sich aus den Grundfunktionen

R0 S(x)  = x + 1

I_{i}^{n}(x_{1}, …, x_{n}) = x_{i}  (1 ≤ i ≤ n)
C_{0}^{0}  = 0  nullstellig

durch Anwenden der Regeln R1 Sind die g_{i} und h rekursiv, dann auch

f(x_{1}, …, x_{n}) = h(g_{1}(x_{1}, …, x_{n}), …, g_{k}(x_{1}, …, x_{n}))

(Einsetzung)

R2 Sind g und h rekursiv, dann auch

f(x_{1}, …, x_{n}, y),

wobei

f(x_{1}, …, x_{n}, 0) = g(x_{1}, …, x_{n})

und

f(x_{1}, …, x_{n}, y + 1) = h(x_{1}, …, x_{n}, y, f(x_{1} …, x_{n}, y))

(primitive Rekursion)

R3 g sei rekursiv und es gelte ∀x_{1}, …, x_{n}∃y g(x_{1}, …, x_{n}, y) = 0. Dann ist auch

f(x_{1}, …, x_{n}) = μy (g(x_{1}, …, x_{n}, y) = 0)

rekursiv, wobei

μy A(y) = das kleinste y mit A(y).

(μ–Rekursion)

ergibt.

Anmerkungen:

Verwendet man nur R0, R1 und R2, heißt f primitiv rekursiv. Die konstante Funktionen

C_{m}^{n}(x_{1}, …, x_{n}) = m

sind zum Beispiel primitiv rekursiv: Es ist C_{m+1}^{0} = S(C_{m}^{0}). C_{m}^{n} entsteht aus C_{m}^{0} durch "Einsetzen"von k = 0–vielen n–stelligen Funktionen

Man kann rekursive Funktionen beliebig ineinander einsetzen. Zum Beispiel ist

f(x_{1}, x_{2}, x_{3}) = h(x_{1}, g(x_{2}, x_{2}))

rekursiv, wenn g und h rekursiv sind.

Satz 11.1 Die rekursiven Funktionen stimmen mit den maschinenberechenbaren Funktionen überein.

In diesem Paragraphen beweisen wir eine Richtung: Die rekursiven Funktionen sind berechenbar. Wir beschreiben Maschinen in naheliegender Weise durch Flußdiagramme. Unser Alphabet ist A = { | }. I und J seien Registerinhalte (also R–Tupel (R_{0}, …, R_{R−1})). Wir schreiben

I \overline{} ; M J,

wenn für ein s M^{s}((0, I)) eine Stopkonfiguration (c, J) ist.

Die \underline{Löschmaschine} L^{r}

(R_{0}, …, R_{r}, …, R_{R−1}) \overline{} ; L^{r} (R_{0}, …, ∅, …, R_{R−1})

löscht das r–te Register. Das Flußdiagramm von L^{r} ist

[figure: Input; R_{r}?; Stop; ∅; |; R_{r} . − 1]

Formal:

L^{r} = ((r, 3, 1), (r, 0), (0, 0, 0), 0)

Die \underline{Kopiermaschine} K_{h}^{r,s}

(R_{0}, …, R_{r}, …, R_{s}, …, R_{h}, …) \overline{} ; K_{h}^{r,s} (R_{0}, …, R_{r}, …, R_{r}, …, ∗, …)

kopiert R_{r} auf R_{s} mit Hilfsregister R_{h}, (h ∉ {r, s})

Flußdiagramm:

[figure: R_{s} + |; R_{r} + |; R_{h}?; |; R_{h} . − 1; Input; L^{h}; R_{r}?; L^{s}; ∅; |; ∅; Stop; R_{r} . − 1; R_{h} + |]

Formal:

K_{h}^{r,s} = ((h, 3, 1), (h, 0), (0, 0, 0), (r, 7, 4), (r, 0), (h, 1), (0, 3, 3), (s, 10, 8), (s, 0),
(0, 7, 7), (h, 15, 11), (h, 0), (r, 1), (s, 1), (0, 10, 10), 0)

Für das Hintereinanderausführen der Maschinen M_{1}, M_{2}, M_{3} verwenden wir die Notation

M_{1}M_{2}M_{3}.

Zum Beispiel kopiert die Maschine

K_{h}^{r_{1},...,r_{n};s_{1},...,s_{n}} = K_{h}^{r_{1},s_{1}} … K_{h}^{r_{n},s_{n}}

die Register R_{r_{1}}, …, R_{r_{n}} nach R_{s_{1}}, …, R_{s_{n}}. Wenn M eine n–stellige Funktion mit R–Registern berechnet, bezeichnen wir mit M^{∗} die Maschine

M^{∗} = L^{0}L^{n+1} … L^{R−1}M.

Zuerst zeigen wir, daß die Grundfunktionen R0 maschinenberechenbar sind:

S wird berechnet von K_{2}^{1,0}(R_{0} + |)
I_{i}^{n} wird berechnet von K_{n+1}^{i,0}
C_{0}^{0} wird berechnet von "Stop"

Die maschinenberechenbare Funktionen sind abgeschlossen unter der Regel R1:

Wenn zum Beispiel h(y_{1}, y_{2}) von H und die Funktionen f_{1}(x) und f_{2}(x) von F_{1} und F_{2} mit R Registern berechnet werden, wird f(x) = h(f_{1}(x), f_{2}(x)) berechnet von der Hintereinanderausführung der folgenden Maschinen. (Wir verwenden das Hilfsregister R_{R+2}.)

K^{1,R}  (rettet x auf R_{R})
F_{1}K^{0,R+1}  (berechnet f_{1}(x) und speichert den Wert in R_{R+1}.)
K^{R,1}F_{2}^{∗}K^{0,2} (berechnet f_{2}(x) und speichert den Wert in R_{2}.)
K^{R+1,1}H^{∗}  (berechnet h(f(x), f_{2}(x)).

Die maschinenberechenbare Funktionen sind abgeschlossen unter der Regel R2:

Wir zeigen das für den Fall n = 1. g(x) werde von G und h(x, y, z) werde von H mit R Registern berechnet. Dann wird f berechnet von folgendem Flußdiagramm: (Hilfsregister R_{R+3})

[figure: R_{R+1}+|; H^{∗}; K^{R,R+1,0;1,2,3}; R_{R+2} . −1; Input; K^{1,2;R,R+2}; G^{∗}; R_{R+2}?; Stop; ∅; |]

Die maschinenberechenbare Funktionen sind abgeschlossen unter der Regel R3:

Wir zeigen das für den Fall n = 1. Nehmen wir an, daß g(x, y) von G mit R Registern berechnet wird. Dann wird f(x) berechnet von der Maschine mit dem folgendem Flußdiagramm: (Hilfsregister R_{R+2})

[figure: Input; K^{1,R}; G^{∗}; R_{0}?; K^{R+1,0}; Stop; ∅; K^{R,R+1;1,2}; R_{R+1}+|; |]

12 Primitiv rekursive Funktionen und Gödelisierung

Lemma 12.1 Die Funktionen

x + y, x · y, x^{y}, x!, x . − y

sind primitiv rekursiv.

Dabei ist

x . − y = \{ \begin{matrix}x − y & wenn y ≤ x \\ 0 & sonst \end{matrix}

Beweis: x + y läßt sich, wie die anderen Funktionen, leicht durch primitive Rekursion definieren:

x + 0 = x, x + (y + 1) = S(x + y).

Ein Problem stellt vielleicht x . − y dar. Zuerst definieren wir y . − 1 durch 0 . − 1 =

0 und (y + 1) . − 1 = y. Und dann x . − 0 = x und x . −(y + 1) = (x . − y) . − 1. □

Definition Eine Relation (oder Prädikat) R heißt (primitiv) rekursiv, wenn die charakteristische Funktion

K_{R}(x_{1}, …, x_{n}) = \{ \begin{matrix}0 & wenn R(x_{1}, …, x_{n}) \\ 1 & sonst \end{matrix}

(primitiv) rekursiv ist.

Zum Beispiel ist die Relation x =^{.} 0 primitiv rekursiv, weil K_{=^{.}0}(0) = 0 und

K(x + 1) = 1. x < y ist primitiv rekursiv, weil K_{<}(x, y) = K_{=^{.}0}((x + 1 . − y)).

Lemma 12.2 Wenn P und Q (primitiv) rekursive Prädikate sind, dann auch P ∧ Q, P ∨ Q, ¬ P und P (f_{1}(x_{1}, …, x_{n}), …, f_{k}(x_{1}, …, x_{n})) für alle (primitiv) rekursiven f_{1}, …, f_{k}.

Beweis: Es ist

K_{P ∨Q} = K_{P} · K_{Q}
K_{¬ P} = 1 . − K_{P}
P ∧ Q ⇔ ¬ (¬ P ∨ ¬ Q).

Wenn man die f_{i} in die charakteristische Funktion von P einsetzt, erhält man die charakteristische Funktion von P (f_{1}(x_{1}, …, x_{n}), …, f_{k}(x_{1}, …, x_{n})). □

Lemma 12.3 Wenn P_{0}…. , P_{n−1} (primitiv) rekursive Prädikate und f_{0}, …, f_{n} (primitiv) rekursive Funktionen sind, so ist auch

f(\overline{x}) = \{ f_{0}(\overline{x}) falls P_{0}(\overline{x}) f_{1}(\overline{x}) falls ¬ P_{0}(\overline{x}) ∧ P_{1}(\overline{x}) ⋮ f_{n}(\overline{x}) falls ¬ P_{0}(\overline{x}) ∧ … ∧ ¬ P_{n−1}(\overline{x})

(primitiv) rekursiv.

Beweis: Die Prädikate Q_{0} = P_{0}, Q_{1} = ¬ P_{0} ∧ P_{1},…, Q_{n} = ¬ P_{0} ∧ … ∧ ¬ P_{n−1} sind (primitiv) rekursiv, also auch

f(\overline{x}) = ∑_{i=0}^{n}(1 . − K_{Q_{i}}(\overline{x}))f_{i}(\overline{x}).

□

Lemma 12.4 Sei P (primitiv) rekursiv. Dann sind auch die Relationen

R(\overline{x}, z) ⇔ ∀y < z P (\overline{x}, y)
S(\overline{x}, z) ⇔ ∃y < z P (\overline{x}, y)

(primitiv) rekursiv.

Beweis: Man definiert R durch primitive Rekursion:

R(\overline{x}, 0) ⇔ wahr
R(\overline{x}, z + 1) ⇔ R(\overline{x}, z) ∧ P (\overline{x}, z)

Schließlich ist S(\overline{x}, z) ⇔ ¬ ∀y < z ¬ P (\overline{x}, y) □

Lemma 12.5 R(\overline{x}, y) sei eine primitiv rekursive Relation und b(\overline{x}) eine primitiv rekursive Funktion. Wenn

∀\overline{x} ∃y ≤ b(\overline{x}) R(\overline{x}, y),

ist

f(\overline{x}) = μy R(\overline{x}, y)

primitiv rekursiv.

Beweis: Die Funktion h(\overline{x}, y) = μz (R(\overline{x}, z)∨z = y) ist primitiv rekursiv, weil h(\overline{x}, 0) = 0 und

h(\overline{x}, y + 1) = \{ \begin{matrix}h(\overline{x}, y) & falls R(\overline{x}, h(\overline{x}, y)) \\ y + 1 & sonst. \end{matrix}

Es ist f(\overline{x}) = h(\overline{x}, b(\overline{x})). □

\underline{Beispiele}

x|y (x teilt y) ist primitiv rekursiv (12.4). x ist Primzahl ist primitiv rekursiv (12.4). p(x) = (n + 1)–te Primzahl ist primitiv rekursiv wegen 12.5, weil sich μy in

p(x + 1) = μy (y prim ∧ y > p(x))

durch p(x)! + 1 beschränken läßt.

Wir schreiben p_{n} für p(n). Lemma 12.6 Durch

⟨x_{0}, …, x_{n−1}⟩ = p_{0}^{x_{0}} … p_{n−2}^{x_{n−2}}p_{n−1}^{x_{n−1}+1} − 1

ist eine Bijektion

⟨ ⟩ : ℕ^{∗} → ℕ

definiert. Es gilt

a) Die zweistellige Funktion Komponentenfunktion (x)_{i}, definiert durch

(⟨x_{0}, …, x_{n−1}⟩)_{i} = \{ \begin{matrix}x_{i} & (i < n) \\ 0 & sonst \end{matrix}

ist primitiv rekursiv.

b) Die Längenfunktion lg(x), definiert durch

lg(⟨x_{0}, …, x_{n−1}⟩) = n

ist primitiv rekursiv.

c) Für alle n ist ⟨ ⟩ : ℕ^{n} → ℕ primitiv rekursiv.

d) Für alle x ist lg(x) ≤ x. Wenn x > 0, ist (x)_{i} < x.

Wir nennen ⟨x_{0}, …, x_{n−1}⟩ die Gödelnummer der Folge (x_{0}, …, x_{n−1}). Beweis:

c) Folgt aus 12.1.

d) Klar

b) Es ist

lg(x) = μy ∀z ≤ x(y ≤ z → p(y) |̸ (x + 1)).

y kann durch x beschränkt werden. Wende jetzt 12.4 und 12.5 an. a) Es ist

(x)_{i} = \{ \begin{matrix}μy p(i)^{y+1} |̸ (x + 1) & (i < lg(x) − 1) \\ μy p(i)^{y+2} |̸ (x + 1) & (i = lg(x) − 1) \\ 0 & (i ≥ lg(x) − 1) \end{matrix}

y ist durch x . − 1 beschränkt.

□

Wenn es uns nur auf Rekursivität ankommt, sind nur die beiden Eigenschaften a) und b) von Bedeutung. Sei β : ℕ → ℕ eine rekursive Bijektion^{1}. Dann definiert

< x_{0}, …, x_{n−1} >^{β}= β ⟨x_{0}, …, x_{n−1}⟩

eine Gödelnumerierung mit rekursiver Komponentenfunktion und rekursiver Längenfunktion. Es gilt aber auch die Umkehrung:

Bemerkung Sei [ ] : ℕ^{∗} → ℕ eine Gödelnumerierung mit rekursiver Komponentenfunktion [x]_{i} und rekursiver Längenfunktion Lg(x). Dann gibt es eine rekursive Bijektion β : ℕ → ℕ mit [ ] = ⟨ ⟩^{β}.

Beweis: Man definiert β durch

β(s) = μt (Lg(t) = lg(s) ∧ ∀i < lg(s) [t]_{i} = (s)_{i}).
□

Gödelisierung von Registermaschinen

Wir ordnen allen Befehlen, Maschinen, Wörtern und Konfigurationen eine Zahl, ihre Gödelnummer zu:

Objekt  Gödelnummer
Stopbefehl b = 0  ⌜0⌝ = 0
Schreibbefehl b = (r, l)  ⌜b⌝ = ⟨r, l⟩
Verzweigung b = (r, c_{0}, …, c_{L})  ⌜b⌝ = ⟨r, c_{0}, …, c_{L}⟩
Maschine M = (b_{0}, …, b_{N})  ⌜M⌝ = ⟨⌜b_{0}⌝, …, ⌜b_{N}⌝⟩
Wort w = (a_{i_{1}}, …, a_{i_{n}})  ⌜w⌝ = ⟨i_{1}, …, i_{n}⟩
Konfiguration K = (c, R_{0}, …, R_{R−1}) ⌜K⌝ = ⟨c, ⌜R_{0}⌝, …, ⌜R_{R−1}⌝⟩

Lemma 12.7 Es gibt eine primitiv rekursive Funktion N(x, y), sodaß für alle Maschinen M und passende Konfigurationen K

N(⌜M⌝, ⌜K⌝) = ⌜M(K)⌝.

1Die Umkehrung μy β(y) = x einer rekursiven Bijektion ist wieder rekursiv

Beweis: Wir überlegen zuerst, daß die folgenden Funktionen primitiv rekursiv sind:^{2}

Ers(⟨x_{0}, …, x_{i}, …, x_{n−1}⟩, i, y) = ⟨x_{0}, …, y, …, x_{n−1}⟩
Anh(⟨x_{0}, …, x_{n−1}⟩, y)  = ⟨x_{0}, …, x_{n−1}, y⟩
Str(⟨x_{0}, …, x_{n−1}⟩)  = ⟨x_{0}, …, x_{n−2}⟩

Um N(m, k) zu definieren, verwenden wir die Abkürzungen c = (k)_{0}, b = (m)_{c},

r = (b)_{0}, w = (k)_{r+1}, l = lg(w) . − 1 und a = (w)_{l}. Dann ist

N(m, k) = \{ \begin{matrix}k & (lg(b) < 2) \\ Ers(Ers(k, 0, c + 1), r + 1, Str(w)) & (lg(b) = 2 ∧ (b)_{1} = 0) \\ Ers(Ers(k, 0, c + 1), r + 1, Anh(w, (b)_{1})) & (lg(b) = 2 ∧ (b)_{1} > 0) \\ Ers(k, 0, (b)_{a+1}) & (lg(b) > 2). \end{matrix}

□

Beweis von 11.1

Wir zeigen, daß jede maschinenberechenbare Funktion f(x_{1}, …, x_{n}) rekursiv ist. Wir machen Gebrauch von den folgenden Funktionen und Relationen, die man leicht als primitiv rekursiv erkennt:

Input(R, x_{1}, …, x_{n}) = ⌜(0, ∅, \underbrace{|^{x_{1}}, …, |^{x_{n}}}_{n}, \underbrace{∅, …, ∅}_{R−n−1} )⌝

ist die Anfangskonfiguration einer R–Registermaschine mit Input x_{1}, …, x_{n}.

Stop(m, k) ⟺ m_{(k)_{0}} = 0

trifft auf eine Maschine m = ⌜M⌝ und eine Konfiguration k = ⌜K⌝ zu, wenn K eine Stopkonfiguration von M ist.

Output(k) = lg((k)_{1})

ist der Inhalt von Register R_{0}, als Zahl interpretiert.

N^{s}(m, k)

ist die s–fach iterierte Nachfolgerfunktion, definiert durch N^{0}(m, k) = k und N^{s+1}(m, k) = N(m, N^{s}(m, k)).

2 In der Tat ist

Ers(x, i, y) = μz (lg(z) = lg(x) ∧ ∀j < lg(x)(j ≠ i → (z)_{j} = (x)_{j}) ∧ (z)_{i} = y).

Weil Ers(x, i, y) < (x + 1)p(i)^{y+2} läßt sich 12.5 anwenden. Weiterhin ist

Anh(x, y) = μz (lg(z) = lg(x) + 1 ∧ ∀j < lg(x)((z)_{j} = (x)_{j}) ∧ (z)_{lg(x)} = y).

Wieder hat man eine primitiv rekursive Schranke:

Anh(x, y) < (x + 1)p(lg(x))^{y+2} Schließlich ist

Str(x) = μz (lg(z) = lg(x) . − 1 ∧ ∀j < lg(z)((z)_{j} = (x)_{j}))

und Str(x) < (x + 1)p(lg(x) . − 1).

Wir definieren das primitiv rekursive Kleene–Prädikat

T_{n}(m, x_{1}, …, x_{n}, g) ⟺ N^{(g)_{1}}(m, Input(m, x_{1}, …, x_{n})) = (g)_{2}
∧ Stop(m, (g)_{2}) ∧ Output((g)_{2}) = (g)_{0},

das besagt, daß die Maschine m mit dem Input^{3} x_{1}, …, x_{n} nach (g)_{1} Schritten mit dem Output (g)_{0} stoppt^{4}.

Wenn f von M berechnet wird, ist f(x_{1}…. , x_{n}) = (μg T_{n}(⌜M⌝, x_{1}, …, x_{n}, g))_{0}. (1) f ist also rekursiv. Man nennt (1) die Kleene–Normalform von f.

Unser Beweis der Umkehrung von 11.1 macht keinen Gebrauch von den Details der Definition der Arbeitsweise von Registermaschinen. Er zeigt, daß alle irgendwie systematisch arbeitenden Rechenmaschinen nur rekursive Relationen berechnen können. Man nennt diese Erfahrungstatsache die Churchsche These:

Alle irgendwie berechenbaren Funktionen sind rekursiv.

3 dem wir sicherheitshalber m Register gegeben haben.

4 Außerdem ist (g)_{2} die Stopkonfiguration.

13 Rekursiv aufzählbare Mengen

Definition Eine Relation R heißt rekursiv aufzählbar (r.a.), wenn für eine rekursive Relation \overline{R}

R(x_{1}, …, x_{n}) ⟺ ∃y \overline{R}(x_{1}, …, x_{n}, y).

Insbesondere sind rekursive Relationen rekursiv aufzählbar. Lemma 13.1 Wenn P und R rekursiv aufzählbar sind, dann sind auch

1. P ∨ R

2. P ∧ R

3. ∃zR(x_{1}, …, x_{n}, z)

4. T (x_{1}, …, x_{n}, w) ⟺ ∀z < wR(x_{1}, …, x_{n}, z)

5. R(f_{1}(x_{1}, …, x_{n}), …, f_{k}(x_{1}, …, x_{n}))

rekursiv aufzählbar.

Beweis:

1. P (\overline{x}) ∨ R(\overline{x}) ⟺ ∃y (\overline{P} (\overline{x}, y) ∨ \overline{R}(\overline{x}, y))

2. P (\overline{x}) ∧ R(\overline{x}) ⟺ ∃s (\overline{P} (\overline{x}, (s)_{0}) ∧ \overline{R}(\overline{x}, (s)_{1}))

3. ∃zR(\overline{x}, z) ⟺ ∃s \overline{R}(\overline{x}, (s)_{0}, (s)_{1})

4. T (\overline{x}, w) ⟺ ∃s ∀z < w \overline{R}(\overline{x}, z, (s)_{z})

5. R(f_{1}(\overline{x}), …, f_{k}(\overline{x})) ⟺ ∃y \overline{R}(f_{1}(\overline{x}), …, f_{k}(\overline{x}), y)

□

Lemma 13.2 Eine Menge von natürlichen Zahlen ist genau dann rekursiv aufzählbar, wenn sie leer ist oder das Bild einer rekursiven Funktion.

Beweis: Das Bild R der rekursiven Funktion f ist rekursiv aufzählbar, weil R(x) ⟺ ∃z f(z) = x. Wenn umgekehrt R(x) ⟺ ∃y \overline{R}(x, y) und r ∈ R, ist R Bild der rekursiven Funktion

f(z) = \{ \begin{matrix}(x)_{0} & wenn \overline{R}((x)_{0}, (x)_{1}) \\ r & sonst \end{matrix}

□

Satz 13.3 Es gibt eine universelle rekursiv aufzählbare Relation U ⊂ ℕ^{2}. Das heißt

a) U ist rekursiv aufzählbar.

b) Für jede rekursiv aufzählbare Menge R gibt es ein e, sodaß

R = W_{e} = {x | U(e, x)}.

Beweis: Sei S(x, y) rekursiv und M eine Maschine, die versucht μy K_{S}(x, y) = 0 zu berechnen. M stoppt genau dann beim Input x, wenn ∃y S(x, y). Wir haben also ∃y S(x, y) ⟺ ∃g T_{1}(⌜M⌝, x, g). Die rekursiv aufzählbare Relation

U(e, x) ⟺ ∃g T_{1}(e, x, g)

ist also universell. □

Folgerung 13.4 Es gibt eine Menge, die rekursiv aufzählbar aber nicht rekursiv ist.

Beweis: ¬ U(x, x) kann nicht die Form W_{e} haben, weil ¬ U(e, e) ⟺ e ∉ W_{e}. Also ist ¬ U(x, x) nicht rekursiv aufzählbar. U(x, x) ist daher nicht rekursiv, aber rekursiv aufzählbar. □

Lemma 13.5 R ist genau dann rekursiv, wenn R und ¬ R rekursiv aufzählbar sind.

Beweis: Sei R(\overline{x}) ⟺ ∃y \overline{V} (\overline{x}, y) und ¬ R(\overline{x}) ⟺ ∃y \overline{W} (\overline{x}, y) für rekursive \overline{V} und \overline{W}. Dann ist

g(x) = μy (\overline{V} (\overline{x}, y) ∨ \overline{W} (\overline{x}, y))

für alle x definiert und rekursiv. Und wir haben

R(\overline{x}) ⟺ \overline{V} (\overline{x}, g(\overline{x})).
□

14 Gödelnummern von Formeln

Sei L = {λ_{1}, …, λ_{l}} eine endliche Sprache^{5}. Wir ordnen den Zeichen ζ

=^{.}  ∧  ¬  (  )  ∃
λ_{1}  …  λ_{l}  v_{0}  v_{1}  …

die folgenden Gödelnummern ⌜ζ⌝ zu:

⟨0, 0⟩ ⟨0, 1⟩ ⟨0, 2⟩ ⟨0, 3⟩ ⟨0, 4⟩  ⟨0, 5⟩
⟨0, 6⟩ … ⟨0, l + 5⟩ ⟨1, 0⟩ ⟨1, 1⟩  …

Eine Zeichenreihe ϕ = ζ_{1}ζ_{2} … ζ_{n} hat die Gödelnummer^{6}

⌜ϕ⌝ = ⟨⌜ζ_{1}⌝, ⌜ζ_{2}⌝, …, ⌜ζ_{n}⌝⟩.

Lemma 14.1 Die folgenden Mengen sind rekursiv (sogar primitiv rekursiv).

1. {⌜t⌝ | t L–Term}

2. {⌜ϕ⌝ | ϕ L–Formel}

3. {⌜ϕ⌝ | ϕ L–Aussage}

Beweis: Nach Churchs These sind die Mengen rekursiv. Eine genauere Überlegung zeigt die primitive Rekursivität. □

Definition Eine Theorie T heißt

1. axiomatisierbar, wenn {⌜ϕ⌝ | ϕ ∈ T } rekursiv aufzählbar ist.

2. entscheidbar, wenn {⌜ϕ⌝ | T ⊢ ϕ} rekursiv ist.

Ein Beweis von ϕ ist eine Folge ϕ_{0}, …, ϕ_{n} = ϕ von Formeln, die logische Axiome sind (siehe Seite 16) oder aus jeweils früheren Formeln mit Modus Ponens oder ∃–Einführung folgen. Die Gödelnummer eines solchen Beweises ist ⟨⌜ϕ_{0}⌝, …, ⌜ϕ_{n}⌝⟩.

Lemma 14.2 {(x, ⌜ϕ⌝) | x ist Gödelnummer eines Beweises von ϕ} ist primitiv rekursiv.

Beweis: Churchs These zeigt die Rekursivität. □

5Die Ergebnisse dieses Abschnitts verallgemeinern sich leicht auf rekursive Sprachen. Das sind Sprachen mit ausgezeichneten Aufzählungen (c_{i}), (f_{i}), (R_{i}) der Konstanten, Funktionszeichen und Relationszeichen, mit rekursiv von i abhängenden Stelligkeiten.

6Im Abschnitt 10 bezeichnete ⌜ψ⌝ einen Mengenterm.

Folgerung 14.3 {⌜ϕ⌝ | ⊢ ϕ} ist rekursiv aufzählbar.

Beweis:

⊢ ϕ ⟺ ∃x (x ist Gödelnummer eines Beweises von ϕ)

□

Satz 14.4 Wenn T axiomatisierbar ist, ist {⌜ϕ⌝ | T ⊢ ϕ} rekursiv aufzählbar.

Beweis: Die Funktion f, die der Gödelnummer einer Folge von Formeln ϕ_{0}, …, ϕ_{n} die Gödelnummer der Implikation (ϕ_{1} ∧ …, ϕ_{n}) → ϕ_{0} zuordnet, ist rekursiv. Sei T^{∗} = {⌜ϕ⌝ | ϕ ∈ T } und A = {⌜ϕ⌝ | ⊢ ϕ}. Weil T^{∗} und A rekursiv aufzählbar sind, ist auch

{⌜ϕ⌝ | T ⊢ ϕ} = {(x)_{0} | f(x) ∈ A ∧ ∀ i < lg(x) (0 < i → (x)_{i} ∈ T^{∗})}

rekursiv aufzählbar. □

Definition Eine widerspruchsfreie L–Theorie T heißt vollständig, wenn

T ⊢ ϕ oder T ⊢ ¬ ϕ

für jede L–Aussage ϕ.

Folgerung 14.5 Wenn T axiomatisierbar und vollständig ist, ist T entscheidbar.

Beweis: Sei A die Menge der Gödelnummern aller L–Aussagen, und B die Menge der Gödelnummern der T beweisbaren L–Aussagen. f sei eine rekursive Funktion mit f(⌜ϕ⌝) = ⌜¬ ϕ⌝. Aus der Vollständigkeit von T folgt dann

x ∉ B ⇔ x ∉ A ∨ f(x) ∈ B.

Mit 13.5 folgt die Behauptung. □

15 Ein anderer Aufbau der rekursiven Funktionen

Satz 15.1 Alle rekursiven Funktionen lassen sich aus den Grundfunktionen

S(x), I_{i}^{n}, C_{0}^{0}, +, ·, K_{<}

durch Anwenden der Regeln R1 (Einsetzung) und R3 (μ–Rekursion) gewinnen.

Wir werden den Satz im Rest dieses Abschnitts beweisen. Wir nennen die Funktionen, die sich so aufbauen wie im Satz angegeben, ∗–rekursiv . Wenn wir zeigen können, daß die Klasse der ∗–rekursiven Funktionen abgeschlossen ist unter R2 (primitive Rekursion), sind wir fertig.

{Lemma 15.2 \atop 1.} x . − y ist ∗–rekursiv.

2. Die Klasse der ∗–rekursiven Relationen ist abgeschlossen unter Booleschen Kombinationen und beschränkter Quantifizierung. (Siehe 12.2 und 12.4.)

3. x =^{.} y ist ∗–rekursiv.

4. x ≡ y (mod z) ist ∗–rekursiv.

5. Die Klasse der ∗–rekursiven Funktionen ist abgeschlossen unter Definition durch Fallunterscheidung. (Siehe 12.3.)

Beweis:

1. x . − y = μz x < (y + z) + 1

2. Die Abgeschlossenheit unter booleschen Kombinationen sieht man wie in 12.2. Wenn P (x, y) ∗–rekursiv ist, definieren wir

g(x, z) = μy (P (x, y) ∨ y =^{.} z).

Dann ist

∃y < z P (x, y) ⇔ g(x, z) < z

∗–rekursiv.

3. x =^{.} y ⇔ (¬ x < y ∧ ¬ y < x)

4. x ≡ y (mod z) ⇔ ∃w < (x + y + 1)(x =^{.} y + wz ∨ y =^{.} x + wz)

5. Wie 12.3.

□

Lemma 15.3 (Gödels β–Funktion) Es gibt eine ∗–rekursive Funktion β(a, b, i) mit folgender Eigenschaft. Für jede endliche Folge c_{0}, c_{1}, …, c_{n−1} gibt es a und b, sodaß

β(a, b, i) = c_{i}

für i = 0, …, n − 1.

Beweis:

β(a, b, i) = μz z ≡ a (mod b(i + 1) + 1)

ist ∗–rekursiv. Seien c_{0}, c_{1}, …, c_{n−1} gegeben. Wir wählen für b eine Zahl, die durch alle Zahlen zwischen 1 und n teilbar ist und die größer ist als alle c_{i}. Dann sind die b · 1 + 1, b · 2 + 1, …, b · n + 1 paarweise teilerfremd. Wenn nämlich p ein Primteiler von bi + 1 ist, teilt p nicht b. Würde p auch bj + 1 teilen, für ein j ≠ i, wäre p Teiler b(j − i) und daher auch von von j − i. j − i könnte kein Teiler von b sein, ein Widerspruch.

a sei eine gemeinsame Lösung der Kongruenzen

a ≡ c_{0}  (mod b · 1 + 1)
a ≡ c_{1}  (mod b · 2 + 1)
⋮  ⋮
a ≡ c_{n−1} (mod b · n + 1)

Weil c_{i} < b(i + 1) + 1, ist c_{i} jeweils die kleinste natürliche Zahl, die zu a kongruent modulo b(i + 1) + 1 ist. □

Beweis (von 15.1): Wir müssen zeigen, daß die ∗–rekursiven Funktionen unter primitiver Rekursion abgeschlossen sind. Nehmen wir also an, daß g und h ∗–rekursiv sind und daß f definiert ist durch

f(x, 0) = g(x)
f(x, y + 1) = h(x, y, f(x, y)).

Die Relation

R(x, y, a, b) ⇔ (β(a, b, 0) = g(x) ∧ ∀i < y β(a, b, i + 1) = h(x, i, β(a, b, i)))

ist ∗–rekursiv. Offenbar gilt ∀x, y ∃a, b R(x, y, a, b). Also ist

S(x, y) = μs ∃a, b ≤ s R(x, y, a, b)

∗–rekursiv. Dann ist

f(x, y) = μz ∃a, b ≤ S(x, y) (R(x, y, a, b) ∧ z = β(a, b, y))

und f ist ∗–rekursiv. □

Arithmetik

16 Definierbare Relationen

Definition Eine Relation R ⊂ ℕ^{n} heißt arithmetisch, wenn sie in der Struktur

𝔑 = (ℕ, 0, S, +, · , <)

definierbar ist.

Das bedeutet, daß für eine L_{N}–Formel ϕ

R(a_{1}, …, a_{n}) ⟺ 𝔑 ⊧ ϕ[a_{1}, …, a_{n}].

Eine Funktion heißt f arithmetisch, wenn ihr Graph arithmetisch ist:

f(a_{1}, …, a_{n}) = a_{0} ⟺ 𝔑 ⊧ ϕ_{f}[a_{0}, …, a_{n}].

Lemma 16.1 Rekursive Funktionen sind arithmetisch.

Beweis: Wir verwenden 15.1: Die Grundfunktionen S(x), I_{i}^{n}, C_{0}^{0}, +, ·, K_{<} sind klarerweise arithmetisch. Zum Beispiel ist

K_{<}(a_{1}, a_{2}) = a_{0} ⟺ 𝔑 ⊧ (a_{0} =^{.} \underline{0} ∧ a_{1} < a_{2}) ∨ (a_{0} =^{.} S(\underline{0}) ∧ ¬ a_{1} < a_{2}).

Es bleibt zu zeigen, daß das System aller arithmetischen Funktionen unter den Regeln R1 und R3 abgeschlossen ist. Um die Notation zu vereinfachen, nehmen wir an, daß n = 2.

R1: Sei h durch ϕ_{h} und die g_{i} durch ϕ_{i} definiert. Dann wird h(g_{1}(x_{1}), g_{2}(x_{1})) = x_{0} durch ∃y_{1}, y_{2} (ϕ_{1}(y_{1}, x_{1}) ∧ ϕ(y_{2}, x_{2}) ∧ ϕ_{h}(x_{0}, y_{1}, y_{2})) definiert.

R3 : Sei g(x_{1}, x_{2}) = x_{0} definiert durch ϕ(x_{0}, x_{1}, x_{2}). Dann wird μx_{2} (g(x_{1}, x_{2}) =^{.} 0) = x_{0} definiert durch

ϕ(\underline{0}, x_{1}, x_{0}) ∧ ∀x_{2} < x_{0} ¬ ϕ(\underline{0}, x_{1}, x_{2}).

□

Folgerung 16.2 Alle rekursiv aufzählbaren Relationen sind arithmetisch.

Beweis: Sei R(x_{1}, …, x_{n}) ⇔ ∃y \overline{R}(x_{1}, …, x_{n}, y) für eine rekursiv Relation \overline{R}. Wenn ϕ(x_{0}, …, x_{n}, y) die charakteristische Funktion von \overline{R} definiert, wird R definiert von ∃y ϕ(\underline{0}, x_{1}, …, x_{n}, y). □

Folgerung 16.3 Die Theorie

Th(𝔑) = {ϕ | ϕ L_{N}–Aussage, 𝔑 ⊧ ϕ}

der natürlichen Zahlen ist unentscheidbar.

Beweis: Sei

Δ_{a} = S^{a}(\underline{0})

der kanonische L_{N}–Term, der in 𝔑 die Zahl a darstellt^{1}. Wenn Th(𝔑) entscheidbar wäre, wären alle arithmetischen Mengen

{a | ϕ(Δ_{a}) ∈ Th(𝔑)}

rekursiv. Es gibt aber rekursiv aufzählbare Mengen, die nicht rekursiv sind (13.4). □ Es gilt sogar:

Satz 16.4 Th(𝔑) ist nicht arithmetisch.

Beweis: Betrachte die Relation U(e, a), die genau dann gilt, wenn e die Gödelnummer einer Formel ϕ = ϕ(v_{0}) ist, für die 𝔑 ⊧ ϕ(Δ_{a}). Weil jede arithmetische Relation die Form

{a | U(e, a)}

für geeignetes e hat, kann die Relation ¬ U(x, x) nicht arithmetisch sein. Daraus folgt, daß auch Th(𝔑) nicht arithmetisch ist. □

Folgerung 16.5 (Erster Gödelscher Unvollständigkeitssatz) Jede arithmetische Teiltheorie von Th(𝔑) ist unvollständig.

Beweis: Wenn T arithmetisch ist, ist auch T^{∗} = {ϕ | T ⊢ ϕ} arithmetisch. Wäre T vollständig, wäre aber T^{∗} = Th(𝔑) und Th(𝔑) arithmetisch. □

1Rekursive Definition: Δ_{0} = \underline{0}, Δ_{a+1} = S(Δ_{a})

17 Das System Q

Die Axiome des Systems Q sind

Q1 ∀x x + \underline{0} =^{.} x

Q2 ∀x, y x + S(y) =^{.} S(x + y)

Q3 ∀x x · \underline{0} =^{.} \underline{0}

Q4 ∀x, y x · S(y) =^{.} x · y + x

Q5 ∀x ¬ x < \underline{0}

Q6 ∀x, y x < S(y) ⟷ (x =^{.} y ∨ x < y)

Q ist offenbar eine wahre L_{N}–Theorie (damit meinen wir, daß die Axiome von Q in 𝔑 gelten.) Die ersten zwei Axiome kann man auffassen als eine rekursive Definition der Addition, die nächsten beiden als eine rekursive Definition der Multiplikation und die letzten beiden als eine rekursive Definition der Kleiner– Relation. Man erhält zum Beispiel sofort: Lemma 17.1 In Q sind für alle a und b ableitbar:

Q^{∗}1 Δ_{a} + Δ_{b} =^{.} Δ_{a+b}

Q^{∗}2 Δ_{a} · Δ_{b} =^{.} Δ_{ab}

Q^{∗}3 ∀x x < Δ_{a} ⟷ (x =^{.} Δ_{0} ∨ x =^{.} Δ_{1} ∨ ⋯ ∨ x =^{.} Δ_{a−1}) □

Man nennt die Theorie, die aus den drei Axiomenschemata Q^{∗}1, Q^{∗}2, Q^{∗}3 besteht, Q^{∗} .^{2} Wir fassen Q^{∗} als Teiltheorie von Q auf.

Aus Q^{∗}3 folgt sofort (durch Induktion über b) Folgerung Für alle natürlichen Zahlen a und b

a ≠ b ⟹ Q^{∗} ⊢ ¬ Δ_{a} =^{.} Δ_{b}
a < b ⟹ Q^{∗} ⊢ Δ_{a} < Δ_{b}
a ≮ b ⟹ Q^{∗} ⊢ ¬ Δ_{a} < Δ_{b}

Man schließt leicht daraus (vgl. den Beweis von 17.2): Folgerung Alle wahren quantorenfreien L_{N}–Aussagen sind in Q^{∗} beweisbar.

Das läßt sich auch so ausdrücken: Sei 𝔐 ein Modell von Q^{∗} und 𝔘 die Unterstruktur mit Universum {Δ_{a}^{𝔐} | a ∈ ℕ}. Dann ist 𝔘 ≅ 𝔑.

2Oder auch Cobhams Theorie.

Definition Eine Σ_{1}–Formel entsteht aus quantorenfreien Formeln durch Anwenden von ∧, ∨, ∃x und beschränkten Allquantoren

∀x < t.

Dabei ist t ein Term und ∀x < t ϕ bedeutet ∀x (x < t → ϕ).

Eine Σ_{1}–Formel im engeren Sinn entsteht aus Formeln der Form \underline{0} =^{.}

x, S(x) =^{.} y, x + y =^{.} z, x · y =^{.} z, x =^{.} y, ¬ x =^{.} y, x < y, ¬ x < y

durch Anwenden von ∧, ∨, ∃x, ∀x < y.

Bemerkung Jede Σ_{1}–Formel ist zu einer Σ_{1}–Formel im engeren Sinn äquivalent.

Beweis: Man eliminiert kompliziertere Terme mit Hilfe von Existenzquantoren. Zum Beispiel ist S(x) + y =^{.} S(z) äquivalent zu

∃ x_{1}, z_{1} (S(x) =^{.} x_{1} ∧ S(z) =^{.} z_{1} ∧ x_{1} + y =^{.} z_{1}).

Satz 17.2 Alle wahren Σ_{1}–Aussagen sind in Q^{∗} beweisbar.

Beweis: Wir zeigen für alle Σ_{1}–Formeln ϕ(x_{1}, …, x_{n}) im engeren Sinn und alle natürlichen Zahlen a_{1}, …, a_{n}, daß

𝔑 ⊧ ϕ[a_{1}, …, a_{n}] ⟹ Q^{∗} ⊢ ϕ(Δ_{a_{1}}, …, Δ_{a_{n}})

durch Induktion über den Aufbau von ϕ. Wenn ϕ eine Primformel ist, folgt die Behauptung aus Lemma 17.1. Der Induktionsschritt ist einfach, wenn ϕ eine Konjunktion oder eine Disjunktion ist.

Wenn 𝔑 ⊧ ∃x_{0}ψ[a_{1}, …, a_{n}], ist 𝔑 ⊧ ψ[a_{0}, a_{1}, …, a_{n}] für ein a_{0} ∈ ℕ. Nach Induktionsvoraussetzung Q^{∗} ⊢ ψ(Δ_{a_{0}}, Δ_{a_{1}}, …, Δ_{a_{n}}) und daher

Q^{∗} ⊢ ∃x_{0}ψ(x_{0}, Δ_{a_{1}}, …, Δ_{a_{n}}).

Wenn 𝔑 ⊧ ∀x_{0} < x_{1}ψ[a_{1}, …, a_{n}], ist 𝔑 ⊧ ϕ[a_{0}, a_{1}, …, a_{n}] und daher nach Induktionsvoraussetzung Q^{∗} ⊢ ϕ[Δ_{a_{0}}, Δ_{a_{1}}, …, Δ_{a_{n}}] für alle a_{0} < a_{1}. Wegen Q^{∗}3 folgt daraus

Q^{∗} ⊢ ∀x_{0} < x_{1}ψ[a_{1}, …, a_{n}].
□

Lemma 17.3 Alle rekursiven Funktionen und alle rekursiv aufzählbaren Relationen sind mit Σ_{1}–Formeln definierbar.

Beweis: Der Beweis von Lemma 16.1 muß nur an einer Stelle abgeändert werden. Wenn man zeigen will, daß die Σ_{1}–definierbaren Funktionen unter R3 abgeschlossen sind, verwendet man statt ¬ ϕ(\underline{0}, x_{1}, x_{2}) die Formel ∃y(¬ \underline{0} =^{.} y ∧ ϕ(y, x_{1}, x_{2})). □ Übung Σ_{1}–definierbare Relationen sind rekursiv aufzählbar, Σ_{1}–definierbare Funktionen rekursiv.

Folgerung 17.4 Q ist unentscheidbar. Es ist sogar jede wahre Erweiterung von Q^{∗} unentscheidbar.^{3}

Beweis: Sei R(x) rekursiv aufzählbar und definiert durch die Σ_{1}–Formel ϕ. T sei eine wahre Erweiterung von Q^{∗}. Dann ist für alle a

\begin{aligned}R(a) & → & 𝔑 ⊧ ϕ(Δ_{a}) & → & Q^{∗} ⊢ ϕ(Δ_{a}) & → & T ⊢ ϕ(Δ_{a}) \\ ¬ R(a) & → & 𝔑 |̸= ϕ(Δ_{a}) & → & & & T ⊬ ϕ(Δ_{a}) \end{aligned}

Wenn T entscheidbar wäre, wären also alle rekursiv aufzählbare Relationen rekursiv. □

Satz 17.5 Der Prädikatenkalkül ist unentscheidbar: Es gibt eine endliche Sprache L, für die

{ϕ | ϕ allgemeingültige L–Formel}

nicht rekursiv ist.

Beweis: Man überlegt sich leicht:

Übung Wenn man eine entscheidbare Theorie um endlich viele Axiome erweitert, erhält man wieder eine entscheidbare Theorie.

Q ist endliche unentscheidbare Erweiterung der leeren L_{N}–Theorie. Also ist die leere L_{N}–Theorie unentscheidbar und L = L_{N} beweist den Satz. □

Definition Sei T eine L_{N}–Theorie und f : ℕ^{n} → ℕ eine Funktion. Die Formel ϕ(x_{0}, …, x_{n}) repräsentiert f in T, wenn für alle a_{0} = f(a_{1}, …, a_{n})

T ⊢ ∀x(x_{0} =^{.} Δ_{a_{0}} ⟷ ϕ(x_{0}, Δ_{a_{1}}, …, Δ_{a_{n}})

Wenn T eine wahre Theorie ist und ϕ die Funktion f repräsentiert, wird f auch von ϕ definiert. Wenn ϕ eine Σ_{1}–Formel ist, und T wahre Σ_{1}–Formeln beweist, repräsentiert eine Σ_{1}–Formel ϕ die Funktion f genau dann, wenn ϕ f definiert und für alle a_{1}, …, a_{n}

T ⊢ ∀x_{0}, x′_{0} (ϕ(x_{0}, Δ_{a_{1}}, …, Δ_{a_{n}}) ∧ ϕ(x′_{0}, Δ_{a_{1}}, …, Δ_{a_{n}})) → x_{0} =^{.} x′_{0}.

Wenn die wahre Theorie T axiomatisierbar ist, und f in T von ϕ repräsentierbar wird, ist f rekursiv, weil dann die Relation

a_{0} = f(a_{1}, …, a_{n}) ⟺ T ⊢ ϕ(Δ_{a_{0}}, Δ_{a_{1}}, …, Δ_{a_{n}})

rekursiv aufzählbar ist.

3… und damit auch Q^{∗}.

Lemma 17.6 Jede rekursive Funktion läßt sich in Q^{∗} durch eine Σ_{1}–Formel repräsentieren.

Beweis: Die Konstruktion im Beweis von 16.1 (und 17.3) funktioniert auch hier, bis auf den Fall R3. Sei also g(x_{1}, x_{2}) = x_{0} in Q^{∗} repräsentiert durch ϕ(x_{0}, x_{1}, x_{2}). Dann wird f(x_{1}) = μx_{2} (g(x_{1}, x_{2}) = 0) definiert durch

ψ(x_{0}, x_{1}) = (α(x_{0}, x_{1}) ∧ β(x_{0}, x_{1}) ∧ γ(x_{0})),

wobei

α(x_{0}, x_{1}) = ϕ(\underline{0}, x_{1}, x_{0})
β(x_{0}, x_{1}) = ∀x_{2} < x_{0} ∃y (¬ \underline{0} =^{.} y ∧ ϕ(y, x_{1}, x_{2}))
γ(x_{0}) = (\underline{0} ≤ x_{0} ∧ ∀z < x_{0} S(z) ≤ x_{0})^{4}.

(α ∧ β) ist die schon im Beweis von 17.3 benutzte Formel; γ(x_{0}) trifft in 𝔑 auf alle Zahlen zu. Also wird f von ψ definiert. Sei nun a_{0} = f(a_{1}). Wir müssen zeigen, daß

Q^{∗} ⊢ ∀x_{0} (ψ(x_{0}, Δ_{a_{1}}) → x_{0} =^{.} Δ_{a_{0}})

Wir argumentieren in Q^{∗}: Zunächst ist klar, daß, für alle a_{2} ∈ ℕ, ∃y (¬ \underline{0} =^{.} y ∧ ϕ(y, a_{1}, a_{2})) gleichbedeutend ist mit ¬ ϕ(\underline{0}, a_{1}, a_{2}). Nehmen wir an, daß ψ(x_{0}, a_{1}). Aus γ(x_{0}) folgt induktiv, daß x_{0} entweder größer ist als alle 0, …, a_{0}, oder gleich einer dieser Zahlen ist. Im ersten Fall würde aus a_{0} < x_{0} folgen, daß sich α(a_{0}, a_{1}) und β(x_{0}, a_{1}) widersprechen. Wenn x_{0} gleich einer der Zahlen 0, …, a_{0} − 1 ist, folgt x_{0} < a_{0}, und α(x_{0}, a_{1}) liegt im Widerspruch mit β(a_{0}, a_{1}) . Also ist x = a_{0}. □

Folgerung 17.7 Jeder rekursive Relation R wird in Q^{∗} von einer Σ_{1}–Formel ϕ repräsentiert:

R(a_{1}, …, a_{n}) ⇒ Q^{∗} ⊢ ϕ(Δ_{a_{1}}, …, Δ_{a_{n}})
¬ R(a_{1}, …, a_{n}) ⇒ Q^{∗} ⊢ ¬ ϕ(Δ_{a_{1}}, …, Δ_{a_{n}})

Beweis: Sei K_{R} repräsentiert von ρ. Setze ϕ(x_{1}, …, x_{n}) = ρ(\underline{0}, x_{1}, …, x_{n}). □

Satz 17.8 (Fixpunktsatz) Zu jeder L_{N}–Formel ψ(v_{0}) gibt es eine L_{N}–Aussage ϕ mit

Q^{∗} ⊢ ϕ ⟷ ψ(Δ_{⌜ϕ⌝}).

Wenn ψ(v_{0}) eine Σ_{1}–Formel ist, findet man auch ϕ als Σ_{1}–Formel.

Beweis:

4s ≤ t steht für (s < t ∨ s =^{.} t).

(Eine Variante des Beweises von 10.1) Termeinsetzen wird beschrieben durch eine rekursive Funktion

Sub(⌜χ(v_{0})⌝, a) = ⌜χ(Δ_{a})⌝.

Sei Sub in Q^{∗} repräsentiert durch die Σ_{1}–Formel σ. Dann ist also für alle χ(v_{0}) und a

Q^{∗} ⊢ ∀x_{0} ( x_{0} =^{.} Δ_{⌜χ(Δ_{a})⌝} ⟷ σ(x_{0}, Δ_{⌜χ(v_{0})⌝}, Δ_{a}) ).

Wir setzen

ρ(v_{0}) = ∃x_{0} (ψ(x_{0}) ∧ σ(x_{0}, v_{0}, v_{0})).

Dann ist für alle χ(v_{0})

Q^{∗} ⊢ ρ(Δ_{⌜χ(v_{0})⌝})⟷ ψ(Δ_{⌜χ(Δ_{⌜χ(v_{0})⌝})⌝}).

Für χ = ρ ergibt sich

Q^{∗} ⊢ ρ(Δ_{⌜ρ(v_{0})⌝})⟷ ψ(Δ_{⌜ρ(Δ_{⌜ρ(v_{0})⌝})⌝}).

Also leistet ϕ = ρ(Δ_{⌜ρ(v_{0})⌝}) das Gewünschte. □

Folgerung 17.9 Jede konsistente Erweiterung von Q^{∗} ist unentscheidbar.

Beweis: Sei T eine entscheidbare Erweiterung von Q^{∗}. Die Menge der Gödelnummern aller T beweisbaren Aussagen sei in Q^{∗} durch die Formel τ repräsentiert. Das heißt, daß Q^{∗} ⊢ τ(Δ_{⌜ϕ⌝}) für in T beweisbare und Q^{∗} ⊢ ¬ τ(Δ_{⌜ϕ⌝}) für in T unbeweisbare ϕ. Mit dem Fixpunktsatz verschaffen wir uns eine Aussage δ mit

Q^{∗} ⊢ δ ⟷ ¬ τ(Δ_{⌜δ⌝}).

Die beiden Implikationsketten

T ⊬ δ ⇒ Q^{∗} ⊢ ¬ τ(Δ_{⌜δ⌝}) ⇒ Q^{∗} ⊢ δ ⇒ T ⊢ δ,

und

T ⊢ δ ⇒ Q^{∗} ⊢ τ(Δ_{⌜δ⌝}) ⇒ Q^{∗} ⊢ ¬ δ ⇒ T ⊢ ¬ δ,

zeigen, daß T inkonsistent ist. □

Folgerung 17.10 Jede mit Q konsistente L_{N}–Theorie ist unentscheidbar.

Beweis: T ∪ Q ist eine unentscheidbare endliche Erweiterung von T. □

Man kann zeigen, daß sogar jede mit Q^{∗} konsistente L_{N}–Theorie unentscheidbar ist.

Gödel hat den Ersten Unvollständigkeitssatz (16.5) auf folgende Weise mit dem Fixpunktsatz bewiesen: Sei T eine wahre arithmetischen Theorie. Wir wollen zeigen, daß T unvollständig ist. Die Folgerungen aus T bilden eine arithmetische Menge. Also gibt es ein τ mit

𝔑 ⊧ τ(Δ_{⌜χ⌝}) ⇔ T ⊢ χ

für alle χ. Sei ϕ eine Aussage mit

Q^{∗} ⊢ ϕ ⟷ ¬ τ(Δ_{⌜ϕ⌝}).

Dann ist

𝔑 ⊧ ϕ ⇔ 𝔑 ⊧ ¬ τ(Δ_{⌜ϕ⌝}) ⇔ T ⊬ ϕ.

Weil T wahr ist, ist das ist nur möglich, wenn 𝔑 ⊧ ϕ und T ⊬ ϕ, wenn also ϕ eine wahre, aber unbeweisbare Aussage ist.

Aus 17.9 folgt, daß jede konsistente axiomatisierbare Erweiterung von Q unvollständig ist. Das gilt nicht für arithmetische Erweiterungen:

Bemerkung Sei L eine endliche (oder rekursive) Sprache. Dann hat jede arithmetische L–Theorie eine arithmetische Vervollständigung.

18 Peanoarithmetik

Die Axiome der Peanoarithmetik P sind die Axiome von Q und das Induktionsschema:

∀x_{1}, …, x_{n}[(ϕ(x̄, \underline{0}) ∧ ∀y(ϕ(x̄, y) → ϕ(x̄, S(y))) → ∀yϕ(x̄, y)]

Ein Modell von Q ist genau dann ein Modell von P, wenn jede definierbare Menge von Elementen, die \underline{0} enthält und unter S abgeschlossen ist, alle Elemente enthält.

Lemma 18.1 In P sind ableitbar:

1. Die Nachfolgeroperation S ist injektiv. Jedes Element außer \underline{0} hat einen Vorgänger.

2. < ist eine lineare Ordnung. \underline{0} ist kleinstes Element; S(x) ist unmittelbarer Nachfolger von x.

3. +, · definieren einen kommutativen Halbring mit Nullelement \underline{0} und Einselement Δ_{1}.

4. + und · sind monoton. Es ist gilt x ≤ y ⟷ ∃z x + z =^{.} y.

Das ist alles, was man braucht, um elementare Zahlentheorie zu entwickeln. Nach 16.5 ist P zwar unvollständig (siehe auch 19.4), man hat aber erst vor wenigen Jahren „mathematische“ Sätze gefunden, die in P nicht beweisbar sind.

Beweis: Ich zeige nur 2. Der Beweis der anderen Behauptungen ist ebenso leicht.

Beweis von 2: Aus Q6 folgt, daß die Menge aller x, die größer oder gleich \underline{0} sind, unter S abgeschlossen ist. Mit dem Induktionsaxiom folgt also

\underline{0} ≤ y. (1)

für alle x. Als nächstes zeigen wir, daß für alle x

∀y (y < x → S(y) ≤ x). (2)

Die Menge A aller Elemente mit dieser Eigenschaft enthält \underline{0} wegen Q5. Nehmen wir an, daß x ∈ A. Um zu zeigen, daß S(x) ∈ A, betrachten wir ein y < S(x). Aus Q6 folgt y ≤ x. Wenn y < x, folgt S(y) ≤ x, weil x ∈ A, und daraus S(y) < S(x) wegen Q6. Aus y = x folgt S(y) = S(x).

Jetzt zeigen wir durch Induktion, daß alle x mit allen anderen Elementen vergleichbar sind. Wegen (1) ist Null mit allen Elementen vergleichbar. Nehmen wir an, daß x mit allen Elementen vergleichbar ist. Dann ist auch S(x) mit jedem y vergleichbar: Wenn y ≤ x, ist y < S(x) wegen Q6, und wenn x < y, ist S(x) ≤ y wegen (2).

Die Transitivität

x < y < z → x < z

beweisen wir mit Induktion über z. Für z = \underline{0}, ist nichts zu zeigen. Aus x < y < S(z) folgt x < y ≤ z und daraus, nach Induktionsvoraussetzung, x < z und damit x < S(z).

Auch die Irreflexivität

¬ x < x

beweisen wir durch Induktion: ¬ \underline{0} < \underline{0} folgt aus Q5. Für den Induktionsschritt nehmen wir an, daß S(x) < S(x). Daraus folgt S(x) ≤ x. Zusammen mit x < S(x) und der Transitivität ergibt sich x < x, was der Induktionsvoraussetzung widerspricht.

Für lineare Ordnungen drückt Q6 gerade aus, daß S(x) unmittelbarer Nachfolger von x ist. □

Das nächste Lemma bedeutet, daß alle Modelle von P definierbar–wohlgeordnet sind: Jede nicht–leere definierbare Teilmenge hat ein kleinstes Element.

Lemma 18.2 (Verallgemeinerte Induktion) In P ist beweisbar:

∀x_{1}, …, x_{n}[(∀y(∀z < y ϕ(x̄, z) → ϕ(x̄, y)) → ∀yϕ(x̄, y)]

Beweis: Wir halten x_{1}, …, x_{n} fest und nehmen an, daß ∀y(∀z < y ϕ(x̄, z) → ϕ(x̄, y)). Sei A die Menge aller y mit ∀z < y ϕ(x̄, z). A enthält \underline{0} und, wenn y zu A gehört, folgt ϕ(x̄, y) und damit S(y) ∈ A. Also gehören alle Elemente zu A. □

Sei ϕ(v_{0}, …, v_{n}) eine Σ_{1}–Formel, die in P eine Funktion definiert:

P ⊢ ∀v_{1}, …, v_{n}∃! v_{0}ϕ(v_{0}, …, v_{n}).

Wir führen für jedes solche ϕ ein Funktionszeichen F_{ϕ} ein. L^{∗} sei die so entstandene Erweiterung von L_{N} und

P^{∗} = P ∪ {∀v_{1}, …, v_{n}ϕ(F_{ϕ}(v_{1}, …, v_{n}), v_{1}, …, v_{n}) | ϕ wie oben}

die entsprechende definitorische Erweiterung von P. Wir nennen F_{ϕ} eine Σ_{1}^{P}– Funktion .

Im Exkurs über definitorische Erweiterungen haben wir gesehen, daß P^{∗} eine konservative Erweiterung von P ist und daß jede L^{∗}–Formel in P^{∗} zu einer L_{N}– Formel äquivalent ist (Satz 7.4). Insbesondere gilt in P^{∗} das Induktionsschema für alle L^{∗}–Formeln. Wenn man sich den Beweis von 7.4 vor Augen führt, sieht man, daß jede Σ_{1}–Formel aus L^{∗} in eine Σ_{1}–Formel aus L_{N} übersetzt wird. Daraus folgt, daß P^{∗∗} nichts neues liefert, was wir als P^{∗∗} = P^{∗} notieren.

Jedes F_{ϕ} definiert eine Funktion ℕ^{n} → ℕ, die in P^{∗} durch die Formel v_{0} =^{.} F_{ϕ}(v_{1}, …, v_{n}) repräsentiert wird, in P aber durch ϕ.

Satz 18.3 Jede primitiv rekursive Funktion ist durch eine Σ_{1}^{P}–Funktion definierbar.

Zum Beweis brauchen wir ein Lemma.

{Lemma 18.4 \atop i)} Die Gödelsche β–Funktion ist durch eine Σ_{1}^{P}–Funktion, die wir wieder mit β bezeichnen, definierbar.

ii) Für diese Funktion gilt

P^{∗} ⊢ ∀a, b, c, i ∃ a′, b′ (∀j < i β(a, b, j) =^{.} β(a′, b′, j) ∧ c =^{.} β(a′, b′, i))

Beweis:

1. β(a, b, i) wird von der Σ_{1}–Formel

ϕ(v_{0}, v_{1}, v_{2}, v_{3}) = (v_{0} < v_{2}(v_{3} + 1) + 1 ∧ ∃y v_{1} =^{.} v_{0} + y(v_{2}(v_{3} + 1) + 1))

definiert (vgl. Lemma 15.3).

2. Die in P^{∗} zu beweisende Eigenschaft ist wahr. Denn wenn a, b, c, i gegeben sind, wendet man 15.3 auf die Folge

c_{0} = β(a, b, 0), …, c_{i−1} = β(a, b, i − 1), c_{i} = c

an. Man erhält a′, b′ mit

c_{0} = β(a′, b′, 0), …, c_{i−1} = β(a′, b′, i − 1), c_{i} = β(a′, b′, i).

Die Behauptung folgt jetzt aus dem Prinzip, daß sich alle einfachen arithmetischen Sachverhalte in P^{∗} beweisen lassen.

□

Beweis (von 18.3): Die definierenden Formeln für S, I_{i}^{n} und C_{0}^{0} definieren offenbar Σ_{1}^{P}–Funktionen (siehe 16.1). Ebenso wie in 16.1 sieht man, daß man durch Einsetzen von Σ_{1}^{P}– Funktionen in Σ_{1}^{P}–Funktionen wieder Σ_{1}^{P}–Funktionen erhält. Es bleibt zu zeigen, daß die Σ_{1}^{P}–Funktionen unter primitiver Rekursion (R2) abgeschlossen sind. Sei also f gegeben durch

f(x, 0) = g(x), f(x, y + 1) = h(x, y, f(x, y))

und g und h definiert durch die Σ_{1}^{P}–Funktionen G und H. Dann wird f definiert durch die die Σ_{1}–Formel

ϕ(v_{0}, v_{1}, v_{2}) = ∃a, b Φ(v_{0}, v_{1}, v_{2}, a, b),

wobei

Φ(v_{0}, v_{1}, v_{2}, a, b) = ( β(a, b, 0) =^{.} G(v_{1})

∧ ∀x < v_{2} β(a, b, x + 1) =^{.} H(v_{1}, x, β(a, b, x))

∧ v_{0} =^{.} β(a, b, v_{2})).

Die Funktionalität von ϕ beweisen wir in P^{∗} durch Induktion über v_{2}:

• v_{2} = 0 :

Es ist klar, daß P^{∗} ⊢ ∃! v_{0}ϕ(v_{0}, v_{1}, \underline{0}): Nach 18.4 gibt es a, b mit β(a, b, 0) = G(v_{1}). Wenn ϕ(v_{0}, v_{1}, \underline{0}), muß v_{0} gleich G(v_{1}) sein.

• v_{2} → v_{2} + 1 : Um zu zeigen, daß es ein v_{0} mit ϕ(v_{0}, v_{1}, v_{2} + 1) gibt, wählen wir zunächst mit Hilfe der Induktionsvoraussetzung ein y für das ϕ(y, v_{1}, v_{2}) und a′, b′ mit Φ(y, v_{1}, v_{2}, a′, b′). Lemma 18.4 liefert a, b mit ∀x ≤ v_{2} β(a′, b′, x) = β(a, b, x) und β(a, b, v_{2} + 1) = H(v_{1}, v_{2}, y) = v_{0}. Dann gilt Φ(v_{0}, v_{1}, v_{2} + 1, a, b) und ϕ(v_{0}, v_{1}, v_{2} + 1).

Sei ϕ(v′_{0}, v_{1}, v_{2} + 1) für ein anderes v′_{0}. Es gibt dann a, b mit Φ(v′_{0}, v_{1}, v_{2} + 1, a, b). Sei y′ = β(a, b, v_{2}). Dann gilt Φ(y′, v_{1}, v_{2}, a, b) und y′ = y nach Induktionsvoraussetzung. Es folgt v′_{0} = H(v_{1}, v_{2}, y′) = H(v_{1}, v_{2}, y) = v_{0}.

□

Zusatz 18.5 Wenn die Σ_{1}^{P}–Funktion F (x, y) wie eben durch primitive Rekursion aus H und G definiert wird, ist in P^{∗} beweisbar:

∀x (F (x, \underline{0}) =^{.} G(x) ∧ ∀y F (x, y + 1) =^{.} H(x, y, F (x, y)). (3)

□

Das Teilsystem von P^{∗}, das aus P durch Hinzufügen der Aussagen (3) für alle primitiv rekursiven Funktionen entsteht, nennt man primitiv rekursive Arithmetik. Genauer geht man so vor: Für alle Terme G und H (und jede Stelligkeit), fügt man ein neues Funktionszeichen F und das Axiom (3) ein. Dieser Prozeß wird abzählbar oft iteriert.

Übung Man zeige, daß nicht jede rekursive Funktion durch eine Σ_{1}^{P}–Funktion definiert werden kann.

Hinweis: Sei ϕ_{0}, ϕ_{1}, … eine rekursive Aufzählung aller einstelligen Σ_{1}^{P}–Funktionen ϕ_{i}(v_{0}, v_{1}) und f_{1}, f_{2}, … die dadurch definierten Funktionen ℕ → ℕ. Dann ist f(x) = f_{x}(x) + 1 ein Gegenbeispiel.

Definition Eine Δ_{1}^{P}–Formel ϕ ist eine Σ_{1}–Formel, die in P zur Negation einer Σ_{1}–Formel ψ äquivalent ist:

P ⊢ ϕ ⟷ ψ

Folgerung 18.6 Jede primitiv rekursive Relation ist durch eine Δ_{1}^{P}–Formel definierbar.

Beweis: Quantorenfreie Formeln aus L^{∗} sind in P^{∗} zu Δ_{1}^{P}–Formeln äquivalent. Sei R primitiv rekursiv. Nach 18.3 wird K_{R} von einer Σ_{1}^{P}–Funktion F definiert und R daher von der quantorenfreien Formel F (v_{1}) =^{.} \underline{0}. □ Man kann mit den eben angegebenen Methoden leicht zeigen, daß sich die primitiv rekursive Funktion

β′(a, i) = β((a)_{0}, (a)_{1}, i)

mit einer Σ_{1}^{P}–Funktion definieren läßt, sodaß, wie im Lemma 18.4,

Folgerung 18.7

P^{∗} ⊢ ∀a, c, i ∃ a′ (∀j < i β′(a, j) =^{.} β′(a′, j) ∧ c =^{.} β′(a′, i))

19 Der Zweite Gödelsche Unvollständigkeitssatz

Wir beginnen mit einer allgemeinen Beobachtung. Wir sagen, daß eine Formel ϕ = ϕ(x̄) logisch aus T folgt, wenn ∀x̄ ϕ in allen Modellen von T gilt (vergleiche die Definition auf Seite 22.)

Lemma 19.1 (Deduktionslemma) Sei T eine L–Theorie. Eine L–Formel ϕ folgt genau dann logisch aus T, wenn ϕ im Hilbertkalkül aus den Axiomen von T herleitbar ist.

Beweis: Nehmen wir an, daß ϕ = ϕ(x̄) logisch aus T folgt. Aus 4.5 folgt die Existenz von ψ_{1}, …, ψ_{n} aus T, für die ψ_{1} ∧ ⋯ ∧ ψ_{n} → ∀x̄ ϕ einen Beweis im Hilbertkalkül hat. Es ist nun leicht zu sehen, daß im Hilbertkalkül ϕ aus ψ_{1} ∧ ⋯ ∧ ψ_{n} → ∀x̄ ϕ und den Axiomen ψ_{1}, …, ψ_{n} herleitbar ist.

Die Umkehrung zeigt man durch Induktion über Länge der Herleitung von ϕ. Die Behauptung ist klar, wenn ϕ ein Kalkülaxiom oder ein Axiom von T ist. Schließlich prüft man leicht nach, daß die beiden Schlußregeln Modus Ponens und ∃–Einführung Formeln, die logisch aus T folgen, in Formeln überführen, die ebenfalls logisch aus T folgen. □

Wir wollen das Beweisbarkeitsprädikat für die Peanoarithmetik definieren. Zunächst beschreiben wir die primitiv rekursiven Relationen

• Aus = {⌜ϕ⌝| ϕ L_{N}–Aussage}

• Ax = {⌜ϕ⌝| ϕ L_{N}–Formel, Axiom des Hilbertkalküls oder Axiom von P}

• Reg = {(⌜ϕ⌝, ⌜ψ⌝, ⌜χ⌝) | ϕ, ψ, χ L_{N}–Formeln, ϕ folgt aus ψ und χ mit einer der Regeln des Hilbertkalküls}

durch Σ_{1}–Formeln. Die Σ_{1}–Formel

B′(s, n) = ∀i < n(Ax(β′(s, i)) ∨ ∃j, k < i Reg(β′(s, i), β′(s, i), β′(s, k))),

definiert in dann 𝔑 die Menge aller Paare (s, n), für die β′(s, 0),… β′(s, n − 1) eine Herleitung aus den Axiomen von P ist (im Sinn der Definition S. 74). Das vorläufige Beweisbarkeitsprädikat wird dann definiert durch

Bew′(f) = Aus(f) ∧ ∃ n, s (β′(s, n) =^{.} f ∧ B′(s, n + 1)).

Aus dem Deduktionlemma 19.1 folgt, daß Bew in 𝔑 die Menge der Gödelnummern der in P beweisbaren Aussagen definiert.

Man kann leicht zeigen (wie im Beweis von Lemma 19.3), daß Bew′ die auf Seite 57 eingeführten Loebaxiome L1 und L2 erfüllt. Für die Gültigkeit von L3 müßte man aber die Formeln Ax und Reg sorgfältiger wählen. Es genügt nicht, zu wissen, daß Ax und Reg in 𝔑 die richtigen Relationen definieren. Um L3 in einfacher Weise zu erfüllen, verwenden wir einen Kunstgriff. Wir fügen zu den Axiomen von P alle wahren Σ_{1}–Aussagen hinzu. Das ändert nichts an der Theorie, weil nach Satz 17.2 alle wahren Σ_{1}–Aussagen in P beweisbar sind.

Wir machen Gebrauch von folgendem Lemma, das wir später (S. 94) beweisen.

Lemma 19.2 Es gibt eine Σ_{1}–Formel W_{1}(x), sodaß für alle Σ_{1}–Aussagen ϕ

P ⊢ ϕ ⟷ W_{1}(Δ_{⌜ϕ⌝}).

Für die Peanoarithmetik P läßt sich leicht das Analogon von Tarskis Satz 10.3 beweisen. Das Lemma gilt also nicht für beliebige Aussagen.

Weil die Menge der Gödelnummern von Σ_{1}–Aussagen primitiv rekursiv ist, können wir annehmen, daß

P ⊢ ¬ W_{1}(Δ_{n}),

wenn n nicht die Gödelnummer einer Σ_{1}–Aussage ist.

Wir setzen jetzt

B(s, n) = ∀i < n(W_{1}(β′(s, i)) ∨ (Ax(β′(s, i)) ∨
∨ ∃j, k < i Reg(β′(s, i), β′(s, j), β′(s, k)))

und

Bew(f) = Aus(f) ∧ ∃ n, s (β′(s, n) =^{.} f ∧ B(s, n + 1)).

Es ist klar, daß Bew in 𝔑 die Menge der Gödelnummern der in P beweisbaren Aussagen definiert.

Lemma 19.3 Bew(x) erfüllt die Loeb–Axiome:

L1 P ⊢ ϕ ⟹ P ⊢ Bew(Δ_{⌜ϕ⌝})

L2 P ⊢ Bew(Δ_{⌜ϕ⌝}) ∧ Bew(Δ_{⌜ϕ→ψ⌝}) → Bew(Δ_{⌜ψ⌝})

L3 P ⊢ Bew(Δ_{⌜ϕ⌝}) → Bew(Δ_{⌜Bew(Δ_{⌜ϕ⌝})⌝})

Beweis: L1: Wenn P ⊢ ϕ, ist 𝔑 ⊧ Bew(Δ_{⌜ϕ⌝}). Weil Bew(Δ_{⌜ϕ⌝}) eine Σ_{1}–Formel ist, folgt P ⊢ Bew(Δ_{⌜ϕ⌝}). Die Umkehrung gilt natürlich auch. (17.2).

L2: Es ist klar, daß P ⊢ Reg(Δ_{⌜ψ⌝}, Δ_{⌜ϕ⌝}, Δ_{⌜ϕ→ψ⌝}) und P ⊢ Aus(Δ_{⌜ψ⌝}). Jetzt argumentieren wir in P. Angenommen Bew(⌜ϕ⌝) und Bew(⌜ϕ → ψ⌝), Dann gibt es s, m und t, n mit β′(s, m) = ⌜ϕ⌝, β′(t, n) = ⌜ϕ → ψ⌝, B(s, m + 1) und B(t, n + 1). Wegen der Eigenschaften von β′ (Folgerung 18.7), gibt es ein u, sodaß für alle i ≤ m + n + 2

β′(u, i) = \{ \begin{matrix}β′(s, i) & , wenn & i ≤ m \\ β′(t, i − m − 1) & , wenn & m < i ≤ m + n + 1 \\ ⌜ψ⌝ & , wenn & i = m + n + 2 \end{matrix}

Es ist klar, daß B(u, m + n + 3). Damit ist gezeigt, daß Bew(⌜ψ⌝).

L3: Für alle Σ_{1}–Aussagen ψ gilt P ⊢ ψ → Bew(Δ_{⌜ψ⌝}). Beweis: Weil Aus(f) eine Σ_{1}–Formel ist, ist Aus(Δ_{⌜ψ⌝}) in P beweisbar. Wir argumentieren jetzt in P: Aus ψ folgt wegen 19.2, daß W_{1}(⌜ψ⌝). Wir wählen ein s, sodaß β′(s, 0) = ⌜ψ⌝. Dann gilt B(s, 1). Zusammen mit Aus(⌜ψ⌝) folgt Bew(⌜ψ⌝).

□

Wenn F eine Formel ist, deren Negation allgemeingültig ist, drückt die Aussage

CON_{P} = ¬ Bew(Δ_{⌜F⌝})

die Konsistenz von P aus. Aus 19.3 und dem Fixpunktsatz 17.8 ergibt sich, wie früher

Satz 19.4 (Zweiter Gödelscher Unvollständigkeitssatz für P) CON_{P} ist wahr, aber in P unbeweisbar. □

Statt den Beweis von 10.5 zu wiederholen, zeigen wir eine Verallgemeinerung, den Satz von Loeb.

Satz 19.5 (Satz von Loeb) Für jede L_{N}–Aussage ψ ist

P ⊢ Bew(Δ_{⌜Bew(Δ_{⌜ψ⌝})→ψ⌝}) → Bew(Δ_{⌜ψ⌝}).

Für ψ = F ergibt sich

P ⊢ Bew(Δ_{⌜CON_{P}⌝}) → ¬ CON_{P}.

Also

𝔑 ⊧ Bew(Δ_{⌜CON_{P}⌝}) ⟹ 𝔑 ⊧ ¬ CON_{P}.

Das ist der zweite Gödelscher Unvollständigkeitssatz für P. Umgekehrt läßt sich der Satz von Loeb auffassen als der zweite Gödelsche Unvollständigkeitssatz für P ∪ {¬ ψ}.

Beweis: Der Übersichtlichkeit zuliebe schreiben wir □ ϕ für Bew(Δ_{⌜ϕ⌝}).^{5} Zunächst bemerken wir, daß, wie in 10.4, aus L1 und L2 folgt

P ⊢ ϕ → ψ ⟹ P ⊢ □ ϕ → □ ψ (1) P ⊢ □ (ϕ ∧ ψ) ⟷ (□ ϕ ∧ □ ψ]) (2)

5Diese Notation ist dem Artikel [5] entnommen. Solovay betrachtet modallogische Formeln f = f(p_{1}, …, p_{n}). Das sind Formeln, die sich aus den Aussagenvariablen p_{i} mit ¬, ∧ und □ aufbauen. Wir schreiben ⊢ f, wenn P ⊢ f(ϕ_{1}, …, ϕ_{n}) für alle L_{N} –Aussagen ϕ_{i}. Das Hauptresultat von [5] besagt, daß ⊢ f genau dann, wenn f sich mit den Regeln

• ⊢ f , ⊢ f → g ⟹ ⊢ g

• ⊢ f ⟹ ⊢ □ f aus Tautologien und den Axiomen

• ⊢ □ f ∧ □ (f → g) → □ g

• ⊢ □ f → □ □ f

• ⊢ □ (□ f → f) → □ f herleiten läßt. Das letzte Axiomenschema ist der Loebsche Satz.

Aus 17.8 folgt die Existenz eines ϕ mit

P ⊢ ϕ ⟷ (□ ϕ → ψ) (3)

Daraus folgt mit (1) P ⊢ □ ϕ → □ (□ ϕ → ψ). (4)

L3 ist P ⊢ □ ϕ → □ □ ϕ. (5)

Aus (2) und (1) folgt

P ⊢ (□ (□ ϕ → ψ) ∧ □ □ ϕ) → □ ψ (6)

Aus (4),(5) und (6) folgt P ⊢ □ ϕ → □ ψ (7)

und daraus mit (3)

P ⊢ (□ ψ → ψ) → ϕ.

Mit (1) folgt daraus

P ⊢ □ (□ ψ → ψ) → □ ϕ

und nochmal mit (7) die Behauptung

P ⊢ □ (□ ψ → ψ) → □ ψ.
□

Beweis von Lemma 19.2: Es genügt, die Behauptung für Σ_{1}–Formeln im engeren Sinn zu beweisen^{6}. Alle Σ_{1}–Formeln im Beweis seien Σ_{1}–Formeln im engeren Sinn. Wir notieren endliche Folgen von Zahlen als σ, τ, … und schreiben in Anlehnung an die Notation von Lemma 12.6 (σ)_{i} für das Element mit Index i.

Eine Σ_{1}–Formel ϕ(v_{0}, …, v_{s−1}) trifft genau dann eine Folge σ der Länge s zu, wenn, wenn es eine Folge ϕ_{0}, …, ϕ_{N} von Σ_{1}–Formeln gibt und eine Folge σ_{0}, …, σ_{N} von endlichen Folgen, sodaß ϕ_{N} = ϕ, σ_{N} = σ und für alle n ≤ N

• Wenn s_{n} die Länge von σ_{n} ist, kommen höchsten die Variablen v_{0}, …, v_{s_{n}−1} frei in ϕ_{n} vor.

• Wenn ϕ_{n} = \underline{0} =^{.} v_{i}, ist 0 = (σ_{n})_{i}.

• Wenn ϕ_{n} = S(v_{i}) =^{.} v_{j}, ist (σ_{n})_{i} + 1 = (σ_{n})_{j}.

• Wenn ϕ_{n} = v_{i} + v_{j} =^{.} v_{k}, ist (σ_{n})_{i} + (σ_{n})_{j} = (σ_{n})_{k}.

• Wenn ϕ_{n} = v_{i} · v_{j} =^{.} v_{k}, ist (σ_{n})_{i} · (σ_{n})_{j} = (σ_{n})_{k}.

• Wenn ϕ_{n} = v_{i} =^{.} v_{j}, ist (σ_{n})_{i} = (σ_{n})_{j}.

6Sei W′_{1} eine Wahrheitsdefinition für Σ_{1}–Formeln im engeren Sinn. Die Funktion, die der Gödelnummer einer Σ_{1}–Formel die Gödelnummer einer beweisbar äquivalenten Σ_{1}–Formel im engeren Sinn zuordnet, sei durch eine Σ_{1}^{P}–Funktion ES definiert, (siehe Bemerkung auf S.81.)

Dann funktioniert W_{1}(x) = W′_{1}(ES(x)) für alle Σ_{1}^{P}–Funktionen.

• Wenn ϕ_{n} = ¬ v_{i} =^{.} v_{j}, ist (σ_{n})_{i} ≠ (σ_{n})_{j}.

• Wenn ϕ_{n} = v_{i} < v_{j}, ist (σ_{n})_{i} < (σ_{n})_{j}.

• Wenn ϕ_{n} = ¬ v_{i} < v_{j}, ist (σ_{n})_{i} ≮ (σ_{n})_{j}.

• Wenn ϕ_{n} = ϕ′ ∧ ϕ′′, gibt es n′, n′′ < n, mit ϕ_{n′} = ϕ′, ϕ_{n′′} = ϕ′′ und σ_{n′} = σ_{n′′} = σ_{n}.

• Wenn ϕ_{n} = ϕ′ ∨ ϕ′′, gibt es n′ < n, mit ϕ_{n′} = ϕ′ und σ_{n′} = σ_{n} oder ein n′′ < n mit ϕ_{n′′} = ϕ′′ und σ_{n′′} = σ_{n}.

• Wenn ϕ_{n} = ∃v_{i} ϕ′, gibt es ein n′ < n mit ϕ_{n′} = ϕ′ und (σ_{n′})_{k} = (σ_{n})_{k} für alle k mit k < min(s_{n}, s_{n′}) und k ≠ i.

• Wenn ϕ_{n} = ∀v_{i} < v_{j} ϕ′, gibt es für alle a < (σ_{n})_{j} ein n′ < n mit ϕ_{n′} = ϕ′ und (σ_{n′})_{i} = a und (σ_{n′})_{k} = (σ_{n})_{k} für alle k mit k < min(s_{n}, s_{n′}) und k ≠ i.

Man verwendet jetzt, daß die verwendeten syntaktischen Dekonstruktionen primitiv rekursiv sind. Das heißt zum Beispiel, daß die Menge

{⌜∀v_{i} < v_{j} ϕ′⌝ | i, j ∈ ℕ, ϕ′ Σ_{1}–Formel}

und die Funktionen

f(⌜∀v_{i} < v_{j} ϕ′⌝) = i
g(⌜∀v_{i} < v_{j} ϕ′⌝) = j
h(⌜∀v_{i} < v_{j} ϕ′⌝) = ⌜ϕ′⌝

primitiv rekursiv sind. Wegen Satz 18.3 ist das also alles Σ_{1}–definierbar. Wenn wir endliche Folgen mit Hilfe der β′–Funktion beschreiben (siehe Folgerung 18.7), erhalten wir eine Σ_{1}–Formel W′_{1}(f, a), sodaß für alle Σ_{1}–Formeln ϕ = ϕ(v_{0}, …, v_{s−1})

P^{∗} ⊢ ∀a (ϕ(β′(a, Δ_{0}), …, β′(a, Δ_{s−1})) ⟷ W′_{1}(Δ_{⌜ϕ⌝}, a)).

Man zeigt das durch Induktion über den Aufbau von ϕ.

Schließlich setzen wir W_{1}(x) = W′_{1}(x, \underline{0}). □

Literaturverzeichnis

[1] H.-D.Ebbinghaus, J.Flum, and W.Thomas. Einführung in die mathematische Logik. Spektrum Akademischer Verlag, 1996. 4. Auflage.

[2] Bruno Poizat. Cours de Théorie des Modèles. Nur Al-Mantiq Wal-Ma’rifah, Villeurbanne, 1985.

[3] Alexander Prestel. Einführung in die Mathematische Logik und Modelltheorie. vieweg studium, Aufbaukurs Mathematik. Friedr. Vieweg & Sohn, Braunschweig, Wiesbaden, 1986.

[4] Joseph R. Shoenfield. Mathematical Logic. Addison–Wesley Series in Logic. Addison–Wesley Publishing Company, 1973.

[5] Robert M. Solovay. Provability interpretations of modal logic. Israel J. Math., 25:287–304, 1976.

Index

α + 1, 50 ∀x < t, 81 ∀–Einführung, 16 ∀–Quantorenaxiom, 16 𝔄 ≡ 𝔅, 11 𝔄 ⊧ ϕ, 11 𝔄 ⊧ ϕ[β], 9 a ⪯ b, 53 a ∼ b, 53 a × b, 41 a × b × c, 41 |a|, 53 ↔, 6 ∀, 6 β \frac{a}{x}, 10 β(a, b, i), 77, 88 β′(a, i), 90 ⊢ ϕ, 16 ⊢_{L} ϕ, 16 C_{m}^{n}, 62 Δ_{a}, 79 dom(R), 41 Δ_{1}^{P}–Formel, 89 ∨, 6 ∨ ⋯ ∨, 6 ∃!, 42 ∃–Einführung, 15 ∃–Quantorenaxiome, 14 ∃, 6 F_{M}^{n}, 61 ϕ\frac{s}{x}, 11 ⌜ϕ⌝, 56, 74 f(x) = y, 42 f : a → b, 42 f[c], 42 f ↾ c, 42

=^{.}, 6

Im(R), 42 →, 6 <, 48 K_{h}^{r,s}, 63 K_{R}, 66 κ^{+}, 55 x ≤ y, 48 ∧, 6 ∧ ⋯ ∧, 6 L_{G}, 4 L_{N}, 4 L_{O}, 4 L_{R}, 4 L_{AK}, 4 L_{∅}, 4 L_{Me}, 4 lg(x), 68 L^{r}, 63 M(K), 60 ⊧ ϕ, 13 μ–Rekursion, 62 N(x, y), 69 \underline{n}, 46 ℕ, 3 𝔑, 3 ¬, 6 On, 50 ∅, 40 ω, 47 𝔓(y), 41 p_{n}, 68 P, 86 Q, 80 Q^{∗}, 80 R^{−1}, 42 S, 3, 4 s(x), 46 Σ_{1}–Formel, 81

im engeren Sinn, 81 Σ_{1}^{P}–Funktion, 87 Sub, 56, 84 T ⊢_{L} ϕ, 20 Th( ), 79 T_{n}(m, x_{1}, …, x_{n}, g), 71 t\frac{s}{x}, 11 t^{𝔄}[β], 9 T ⊢ ϕ, 22 T ⊧ ϕ, 22 ⋃ y, 41 V, 40 W_{e}, 73 w . − 1, 61 (x)_{i}, 68 (x, y), 40 ⟨x_{0}, …, x_{n−1}⟩, 68 {x, y}, 40 x ist frei für s in ϕ, 11 x ∩ y, 40 x ∪ y, 41 x . − y, 66 x \ y, 40 x ⊂ y, 39 (x, y, z), 41 {z | ϕ(z, y_{1}, …, y_{n})}, 38

Abbildung

ordnungstreue, 52 abgeleitete Axiome und Regeln, 16 abzählbare Menge, 54 Addition, 49 äquivalente Formeln, 30 Äquivalenz, 6 allgemeingültige Formel, 13 Allquantor, 6

beschränkter, 81 Alphabet, 60 Anfangskonfiguration, 60 arithmetische Relation, 78 atomareFormel, 6 Aussage, 11 Aussagenlogik, 13 Aussagenvariable, 13 Aussonderungsaxiom, 40 Auswahlaxiom, 45 Auswahlfunktion, 52 axiomatisierbare Theorie, 74

Befehle, 60 Belegung, 9 beschränkter Allquantor, 81 Beweis, 17, 74 beweisbare Formel, 16 Beweisbarkeit, 16, 22 Beweisbarkeitsprädikat von P, 92 von ZFC, 57 bijektive Funktion, 43 Bildbereich, 42 Bindungsstärke, 6

CON_{P}, 93 CON_{ZFC}, 57 CH, 55 charakteristische Funktion, 66 Churchsche These, 71 Cobhams Theorie, 80

Deduktionslemma, 91

deduktiv abgeschlossene Theorie, 20 Definitionsbereich, 41 definitorische Erweiterung, 43, 44 Differenzmenge, 40 Disjunktion, 6 disjunktive Normalform, 32 Durchschnitt, 40

Einführen neuer Funktionszeichen, 43 neuer Konstanten, 43 neuer Relationszeichen, 43

Einschränkung, 13 Einsetzung, 62 elementare Äquivalenz, 11 endliche Menge, 54 entscheidbare Theorie, 74 erblich endliche Menge, 51 Ersetzungsaxiom, 42 Erster Gödelscher Unvollständigkeitssatz, 59, 79

Erweiterung definitorische, 44 konservative, 43 existentielle Formel, 30 Existenzeinführung, 15 Existenzquantor, 6 Expansion, 13 Extensionalitätsaxiom, 38, 39

Fixpunktsatz, 56, 83

Formel, 6 allgemeingültige, 13 atomare, 6 beweisbare, 16 existentielle, 30

universelle, 30 Σ_{1}–Formel, 81

im engeren Sinn, 81 freies Vorkommen, 10 fundierte Menge, 44 Fundierungsaxiom, 44 Funktion, 42

primitiv rekursive, 62 bijektive, 43 charakteristische, 66 injektive, 43 maschinenberechenbare, 61 rekursive, 61 surjektive, 43

Σ_{1}^{P}–Funktion, 87 Funktional, 51 Funktionalität, 43 Funktionszeichen, 4

geordnetes Paar, 40 Gleichheitsaxiome, 14 Gleichheitszeichen, 6, 24, 31 gleichmächtige Mengen, 53 Gödelisierung, 69 Gödelnummer, 68, 69, 74 Gödels β–Funktion, 77, 88 Graph einer Funktion, 42 Grundmenge, 4 Gültigkeit, 11

Henkintheorie, 18 Herbrand–Normalform, 31 Hilbertkalkül, 16

Implikation, 6 Induktion, 50 Induktionsschema, 86 injektive Funktion, 43 Interpolationssatz, 28 inverse Relation, 42 irreflexiv, 46 Isomorphie, 4 Isomorphismus, 4

Junktor, 6

Kardinalzahl, 54 Klammern, 5, 6 Klasse, 50 Klausel, 33 Kleene–Normalform, 71 Kleene–Prädikat, 71 Komprehensionsaxiom, 38 Konfiguration, 60 Kongruenzrelation, 14 Konjunktion, 6 konjunktive Normalform, 33 konservative Erweiterung, 43 konsistente Theorie, 18 Konstante, 3 Konstantenzeichen, 3 konstanter Term, 21 Kontinuumshypothese, 55 Kopiermaschine, 63

Löschmaschine, 63 leere Menge, 40 L–Formel, 6 Limeszahl, 50 lineare Ordnung, 46 Loeb–Axiome, 57, 92 logische Folgerung, 22, 91 logische Zeichen, 5 L–Struktur, 4 L–Term, 4

Mächtigkeit, 53 maschinenberechenbare Funktion, 61 Menge

abzählbare, 54 endliche, 54

Modell, 11, 18 Modus Ponens, 15 Multiplikation, 49

Nachfolgekonfiguration, 60 Nachfolgeroperation, 3, 46 Nachfolgerzahl, 50 Naive Mengenlehre, 38 natürliche Zahl, 47 Negation, 6 Normalform

disjunktive, 32

Herbrand–Normalform, 31 konjunktive, 33 pränexe, 30 Skolem-Normalform, 30

Ordinalzahl, 50 Ordnung

lineare, 46

partielle, 46 ordnungstreue Abbildung, 52

Paar, siehe geordnetes Paar Paarmenge, 40 Paarmengenaxiom, 40 partielle Ordnung, 46 Peanoarithmetik, 86 Potenzmenge, 41 Potenzmengenaxiom, 41 Prädikat, 4, 66 pränexe Normalform, 30 Primformel, 6 primitiv rekursive

Arithmetik, 89 Funktion, 62 Relation, 66

primitive Rekursion, 62 Produkt, 41

r.a., siehe rekursiv aufzählbar Registermaschine, 60 rekursiv aufzählbar, 72 rekursive

Funktion, 61 Relation, 66

Relation, 41 primitiv rekursive, 66 arithmetische, 78 rekursiv aufzählbare, 72 rekursive, 66

Relationszeichen, 4 ϕ repräsentiert

eine Funktion, 82 eine Relation, 83

Resolution, 33 Rossersatz, 59 Russell, Bertrand, 38

Satz von Cantor, 54 von Herbrand, 31 von Loeb, 93 von Tarski, 57

Schreibbefehl, 60 Sequenz, 25

allgemeingültige, 25 Sequenzenkalkül, 25 Skolem–Normalform, 30 Skolemfunktion, 31 Sprache, 3

rekursive, 74 Stelligkeit, 4 Stopbefehl, 60 Stopkonfiguration, 60 Struktur, 4 Substitutionslemma, 12 surjektive Funktion, 43

L–Theorie, 18 Tautologie, 13 Teilmenge, 39 Term, 4

konstanter, 21 Theorie, 18

axiomatisierbare, 74

deduktiv abgeschlossene, 20 entscheidbare, 74 konsistente, 18 vollständige, 19, 75 widerspruchsfreie, 18

Tripel, 41

Unendlichkeitsaxiom, 45 Unifikationssatz, 35 universelle rekursiv aufzählbare Rela-

tion, 73 universelle Formel, 30 unmittelbarer Nachfolger, 48 Unvollständigkeitssatz, 58, 59, 79, 93

Variable, 4 Vereinigung, 41 Vereinigungsmengenaxiom, 41 Verzweigungsbefehl, 60 Volles Komprehensionsaxiom, siehe Kom-

prehensionsaxiom vollständige Theorie, 19, 75 vollständiges Diagramm, 18 Vollständigkeitssatz, 16 von Neumann Hierarchie, 51

wahre L_{N}–Theorie, 80 Wahrheit, 11 Wahrheitstafel, 13 Wahrheitswert, 13 widerspruchsfreie Theorie, 18 Wohlordnung, 48 Wohlordnungssatz, 52 Wohlordnungstyp, 51 Wort, 60

ZFC, 39 Zornsches Lemma, 53 Zweiter Gödelscher Unvollständig-

keitssatz, 58, 93

Änderungen

Version 6.6 (12.11.2006)

Druckfehler auf Seite 33.

Version 6.7 (6.12.2006)

Korrektur des Beweises des Hilfssatzes im Beweis von 1.1.

Version 7.0 (14.1.2007)

Kleine Korrekturen. Neues über Gleichheitszeichen: Lemma 4.8, Bemerkung auf Seite 31, Folgerung 6.8.

Version 7.1 (23.1.2007)

Schreibfehler in 6.1. Bemerkung auf Seite 31 korrigiert.

Version 7.2 (31.1.2007)

Besserer Index in Abschnitt 6. Beweis und Beispiel für Satz 6.7 verbessert.

Version 7.3 (25.4.2007)

Erwähnung von Prädikat auf S.4. Falsche Indices auf den Seiten 11 und 21.

Version 7.4 (8.5.2007)

Die Definition definitorischer Erweiterungen auf S.44 wurde auf Konstanten ausgedehnt. Danach wird bemerkt, daß konservative und definitorische Erweiterungen das gleiche sind^{1}. Folgerung 7.5 wurde entsprechend erweitert. Der Beweis von Lemma 4.2.1 wurde geändert.

Version 7.5 (9.5.2007)

Der Beweis von 4.2.1 wurde noch einmal geändert.

Version 7.6 (4.6.2007)

Atomare Formeln heißen jetzt überall Primformeln. Druckfehler in Formulierung und Beweis von 5.2. Bemerkung nach 6.2. Die Bemerkung auf S.44 wurde korrigiert.

Version 7.7 (4.7.2007)

Kommafehler und Druckfehler. Formulierung von 8.7 präzisiert. Druckfehler im Beweis von 9.5. Verbesserung im Beweis von 9.7. Umformulierungen im Beweis von 10.6. Druckfehler in den Diagrammen von Abschnitt 11. Fehler in der Definition der Kopiermaschine auf Seite 63.

Version 7.8 (10.7.2007)

Fehler im Beweis von 13.1. Umformulierung des Beweises von 14.5. Druckfehler in Abschnitt 9. Offizielle Definition von vollständiger Theorie auf Seite 75.

Version 7.9 (16.4.2008)

Druckfehler im Beweis von 13.5.

Version 17.10 (22.7.2008)

Wahre Theorie definiert in Kapitel 17. Druckfehler im Paragraphen nach 6.6.

1in Version 7.6 korrigiert