Einführung in die Mathematische Logik

Wintersemester 2007/08

Mitschrift von Yves Radunz

Inhaltsverzeichnis

1 Aspekte der mathematischen Logik 5

2 Aussagenlogik 7 2.1 Die Spache der Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Ableiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Elementare Logik 23 3.4 Strukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.5 Elementare Sprachen (Die Sprachen des Prädikatenkalküls 1. Stufe) . . . . . . . . 26 3.6 Semantik der Prädikatenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.7 Ableiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.8 Gödels Vollständigkeitssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4 Gödels Unvollständigkeitssatz 55 4.9 Rekursive Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.10 Der Unvollständigkeitssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5 Mengenlehre (für den täglichen Gebrauch) 65 5.12 Wohlordnungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.13 Ordinalzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.14 Kardinalzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.15 Kofinalität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.16 Das Zermelo-Fraenkelsche Axiomensystem (ZF) . . . . . . . . . . . . . . . . . . . . 84

Index 86

Kapitel 1

Aspekte der mathematischen Logik

Vorlesung am 17.10.2007

1. Schaffung einer exakten Grundlage der Mathematik Entwicklung der Mengenlehre (Georg Cantor 1845-1918) → Grundlagenkrise Prinzipia Mathematica (Russell 1877-1970, Whilehead 1861-1947) ⇝ Mengenlehre

2. Formalisierung der Mathematik Einführung formaler Sprachen Einführung elementarer Sprachen (Prädikatenkalkül 1. Stufe) von Leibnitz (1646-1716), Peano (1858-1932) und Frege (1848-1925) ⇝ Programmiersprachen

3. Semantik

Mathematische Struktur  ⊧  Aussage in einer elementaren Sprache

↑ Gültigkeit ↓

M  ⊧  φ

⇝ Modelltheorie ⇝ Semantik von Programmiersprachen Wie stark ist der Isomorphietyp von M durch {φ|M ⊧ φ}

4. Was ist ein Beweis?

Σ ⊧ φ φ ist aus der Aussagenmenge Σ ableitbar.

Es existiert eine Folge formaler Beweisschritte, die φ beweisen.

⊧ φ In allen zu φ passenden Strukturen M gilt M ⊧ φ, d.h. φ ist allgemeingültig.

Theorem (Kurt Gödel 1906-1978): ⊧ φ ⇔⊢ φ ⇝ Beweistheorie ⇝ automatisches Theorembeweisen ⇝ logische Programmierung

5. Berechenbarkeit Welche Funktionen f : ℕ^{n} → ℕ sind berechenbar? Definitionen: Turingmaschinen, rekursive Funktionen, ... Für alle bekannten Definitionen der Berechenbarkeit wurde die Äquivalenz gezeigt. ⇝ Church’sche These: Diese Konzepte erfüllen ihren Zweck. ⇝ Rekursionstheorie ⇝ Komplexitätstheorie

6. Hilberts (1862-1943) Programm L sei eine elementare Sprache mit den Zeichen +, −, ·, 0, 1 und <. Hilbert: Gibt es eine effektiv gegebene Menge Σ von Axiomen aus denen sich alle auf den natürlichen Zahlen gültigen Aussagen aus L ableiten lassen? Theorem von Gödel: Nein!

Aussagenlogik

2.1 Die Spache der Aussagenlogik

• Grundzeichen: P = {p_{0}, p_{1}, ...} Menge der Aussagenvariablen

• Konnektoren: ¬ (einstellig) und ∨, ∧, →, ↔ (zweistellig)

• Hilfszeichen: ( und )

• Das Alphabet G besteht aus den Grundzeichen, Konnektoren und den Hilfszeichen.

• Ein Wort w der Länge l(w) ist ein Element aus W (G) (Informatik: G^{∗}) und ist eine Folge von l(w) Elementen aus G.

• Das leere Wort (bzw. das Wort mit der Länge 0) ist ⟨⟩ (Informatik: ε).

• Wir verwenden ≡ für die Gleichheit von Worten, da das Gleichheitszeichen (=) später selbst ein Element eines Wortes sein wird.

• Mit p, q, r bezeichnen wir auch Aussagenvariablen.

• Mit φ, ψ, χ bezeichnen wir Wörter über dem Alphabet G.

Definition (Menge der Formeln (von oben)) Die Menge F der Formeln (auch Ausdrücke) über P ist die kleinste Teilmenge von W (G) mit:

1. P ⊆ F

2. ∀φ ∈ F : ¬φ ∈ F

3. ∀φ, ψ ∈ F, α ∈ {∨, ∧, →, ↔} : (φαψ) ∈ F

Definition (Menge der Formeln (von unten)) Wir definieren F_{0} = P und für n ∈ ℕ:

F_{n+1} = F_{n} ∪ {¬φ|φ ∈ F_{n}} ∪ {(φαψ)|φ, ψ ∈ F_{n}, α ∈ {∨, ∧, →, ↔}}

Lemma 2.1. (1.1) Es gilt F = ⋃_{n∈ℕ} F_{n}. Beweis: Offensichtlich gilt P ⊆ ⋃_{n∈ℕ} F_{n}. Weiterhin ist ⋃_{n∈ℕ} F_{n} abgeschlossen unter ¬, ∨, ∧, → und ↔. Damit folgt F ⊆ ⋃_{n∈ℕ} F_{n}. Die Relation F ⊇ ⋃_{n∈ℕ} F_{n} zeigen wir induktiv:

1. Induktionsanfang: n = 0

Es gilt F_{n} = F_{0} = P ⊆ F.

2. Induktionsschritt: Es gelte F_{n} ⊆ F.

Damit folgt F_{n+1} = F_{n} ∪ {¬φ|φ ∈ F_{n}} ∪ {(φαψ)|φ, ψ ∈ F_{n}, α ∈ {∨, ∧, →, ↔}} ⊆ F.

Letztendlich erhalten wir also ⋃_{n∈ℕ} F_{n} ⊇ F und damit die Behauptung.

Definition Für φ ∈ F sei h(φ) = min{n ∈ ℕ|φ ∈ F_{n}}.

Bemerkung (Beweismethode der Induktion über den Formelaufbau) Es sei 𝔈(φ) eine Eigenschaft von Formeln φ. Um ∀φ ∈ F : 𝔈(φ) zu zeigen, reicht es aus,

1. ∀p ∈ P : 𝔈(p)

2. ∀φ ∈ F, 𝔈(φ) : 𝔈(¬φ)

3. ∀φ, ψ ∈ F, 𝔈(φ), 𝔈(ψ) : ∀α ∈ {∨, ∧, →, ↔} : 𝔈((φαψ))

nachzuweisen.

Beispiel (h(φ) < l(φ)) Für alle φ ∈ F gilt h(φ) < l(φ). Beweis: Der Beweis erfolgt durch Induktion über den Aufbau der Formeln φ:

1. ∀p ∈ P : h(p) = 0 < 1 = l(p)

2. ∀φ ∈ F, h(φ) < l(φ) : h(¬φ) = 1 + h(φ) < 1 + l(φ) = l(¬φ)

3. ∀φ, ψ ∈ F, h(φ) < l(φ), h(ψ) < l(ψ) : ∀α ∈ {∨, ∧, →, ↔} :

\begin{aligned}h((φαψ)) & = 1 + max\{h(φ), h(ψ)\} < 1 + max\{l(φ), l(ψ)\} \\ & < 1 + l(φ) + l(ψ) < 3 + l(φ) + l(ψ) = l((φαψ)) \end{aligned}

Eindeutigkeit des Formelaufbaus Wir wollen nun beweisen, dass der Aufbau der Formeln eindeutig ist.

Definition ((echtes) Anfangsstück) φ ≡ a_{0}a_{1}...a_{n−1} ist ein Anfangsstück von ψ = b_{0}b_{1}...b_{m−1}, wenn n < m und a_{i} = b_{i} für 0 ≤ i ≤ n−1 gilt. φ ist ein echtes Anfangsstück von ψ, wenn φ ein Anfangsstück von ψ ist und ⟨⟩ ≠ φ ≠ ψ gilt.

Lemma 2.2. (1.2) Für φ ∈ W (G) bezeichne o(φ) die Anzahl der öffnenden Klammern in φ und s(φ) die Anzahl der schließenden Klammern in φ. Wenn φ eine Formel ist, so gilt o(φ) = s(φ).

Beweis: Der Beweis wurde in der Übung durch Induktion über den Aufbau der Formel φ geführt und wird daher an dieser Stelle dem Leser als Übungsaufgabe überlassen.

Lemma 2.3. (1.3) Sei φ eine Formel und ϑ ein Anfangsstück von φ. Dann gilt o(ϑ) ≥ s(ϑ).

Beweis: Auch dieser Beweis erfolgt durch Induktion über den Aufbau der Formel φ.

Lemma 2.4. (1.4) Seit φ eine Formel, die mit einer öffnenden Klammer beginnt und ϑ ein echtes Anfangsstück von φ. Dann gilt o(ϑ) > s(ϑ).

Beweis: Der Beweis ähnelt dem Beweis des Lemmas 1.3.

Lemma 2.5. (1.5) Sei φ ∈ F und ϑ ein echtes Anfangsstück von φ. Dann gilt ϑ ∉ F.

Beweis: Auch hier wird der Beweis dem Leser überlassen.

Vorlesung am 22.10.2007

Satz 2.1. (Eindeutigkeit des Formelaufbaus (1.6)) Für jede Formel φ tritt genau einer der folgenden Fälle ein:

1. φ ist eine Aussagenvariable.

2. Es existiert eine eindeutig bestimmte Formel ψ und es gilt φ ≡ ¬ψ.

3. Es existiert ein eindeutig bestimmtes α ∈ {∨, ∧, →, ↔} und eindeutig bestimmte Formeln ψ und χ mit φ ≡ (ψαχ).

Beweis: Wir haben F = ⋃_{n∈ℕ} F_{n}. Wenn φ ∈ F, so beginnt φ mit p, ¬ oder (.

1. Wenn φ mit p beginnt, so folgt φ ≡ p. Fall 1 tritt ein.

2. Wenn φ mit ¬ beginnt, so folgt φ ≡ ¬ψ und Fall 2 tritt ein.

3. Wenn φ mit ( beginnt, so folgt φ ≡ (ψαχ). Ist nun (ψαχ) ≡ (μβν) möglich? In diesem Fall wäre μ echtes Anfangsstück von ψ oder ψ echtes Anfangsstück von μ und damit nach Lemma 1.5 keine Formel. ⇒ ψ = μ, α = β, χ = ν

Korollar 2.1. (1.7) Der Baum einer Formel ist eindeutig bestimmt. Für alle Formeln φ und ψ gilt h(¬φ) = h(φ) + 1 und h((φαψ)) = max{h(φ), h(ψ)} + 1.

Satz 2.2. (Definition über den Formelaufbau (1.8)) Seien E eine Menge, e_{0} : P → E und f_{¬} : F × E → E gegeben. Weiterhin sei für jedes α ∈ {∨, ∧, →↔} die Funktion g_{α} : F^{2} × E^{2} → E definiert. Dann existiert eine eindeutig bestimmte Abbildung e : F → E, welche die folgenden Bedingungen erfüllt:

1. e|_{P} = e_{0}.

2. ∀φ ∈ F : e(¬φ) = f_{¬}(φ, e(φ))

3. ∀α ∈ {∨, ∧, →↔}, φ, ψ ∈ F : e((φαψ)) = g_{α}(φ, ψ, e(φ), e(ψ))

Beweis: Wir zeigen induktiv über n ∈ ℕ, dass eine eindeutig bestimmte Funktion e_{n} : F_{n} → E existiert, welche die Bedingungen erfüllt. Wegen der eindeutigen Bestimmtheit setzt e_{n} die Funktion e_{n−1} fort. Für n = 0 ist e_{0} gegeben. Sei φ ∈ F_{n}. Wenn φ ∈ F_{n−1}, so muss wegen der Induktionsvoraussetzung e_{n}(φ) = e_{n−1}(φ) gesetzt werden. Sei φ ∈ F_{n} \ F_{n−1}. Durch Satz 1.6 existiert eine eindeutig bestimmte Darstellung von φ als φ = ¬ψ oder φ = (ψαχ). Wegen der Eindeutigkeit der Darstellung ist die folgende Definition sinnvoll:

e_{n}(φ) = \{ \begin{matrix}f_{¬}(φ, e_{n−1}(ψ)) & , falls φ ≡ ¬ψ \\ α(ψ, χ, e_{n−1}(ψ), e_{n−1}(χ)) & , falls φ ≡ (ψαχ) \end{matrix}

⇒ e_{n} ist eindeutig festgelegt und setzt e_{n−1} fort.

Anwendung tf(φ) sei die Menge der Teilformeln von φ. Für φ ≡ p sei tf(φ)){p}. Für φ ≡ ¬ψ sei tf(φ) = tf(ψ) ∪ {φ}. Für φ ≡ (ψαχ) sei tf(φ) = tf(ψ) ∪ tf(χ) ∪ {φ}. Nach dem Satz über den eindeutigen Formelaufbau ist tf eindeutig auf F definiert: E ist die Menge aller endlichen Mengen von Formeln, e_{0}(p) = {p}, f_{¬}(φ, Φ) = Φ ∪ {¬φ} und g_{α}(φ, ψ, Φ, Ψ) = Φ ∪ Ψ ∪ {(φαψ)}.

Definition (Substitution) Seien φ, ψ_{0}, ..., ψ_{n−1} beliebige Formeln und p_{0}, ..., p_{n−1} ∈ P. Dann sei φ_{ψ_{0}/p_{0},...,ψ_{n−1}/p_{n−1}} die Formel, die man aus φ erhält, indem man simultan jedes p_{i} in φ durch ψ_{i} ersetzt.

Bemerkung (Regeln zum Klammernsparen) Wir erlauben das Weglassen von Klammern in den folgenden Fällen.

1. Außenklammern können weggelassen werden: (ϑ) ⇝ ϑ.

2. ∨ und ∧ binden stärker als → und ↔: (p ∨ q) → r ⇝ p ∨ q → r.

Die so erhaltenen Formeln sind als Abkürzungen der Originale zu betrachten.

2.2 Semantik

Die Formeln sollen Verknüpfungen von Aussagen der Umgangssprache formalisieren. Die Aussagenvariablen entsprechen dabei den Grundaussagen. Diese sind entweder wahr oder falsch. Kennen wir die Wahrheitswerte der Grundaussagen, so möchten wir den Wahrheitswert jeder Formel bestimmen.

Definition P, G und F seien wie im Abschnitt 1.1 gegeben. Eine Belegung der Menge P ist eine Abbildung B : P → {0, 1}. 0 (falsch) und 1 (wahr) sind Wahrheitswerte. Induktiv über den Formelaufbau, können wir jede Belegung B von P zu einer Belegung B^{∗} aller Formeln φ ∈ F mit Wahrheitswerten 0 und 1 fortsetzen, wobei die folgenden Bedingungen gelten:

1. ∀p ∈ P : B^{∗}(p) = B(p)

2. B^{∗}(¬φ) = 1 − B^{∗}(φ)

3. B^{∗}(φ ∧ ψ) = min{B^{∗}(φ), B^{∗}(ψ)}

4. B^{∗}(φ ∨ ψ) = max{B^{∗}(φ), B^{∗}(ψ)}

5. B^{∗}(φ → ψ) = max{1 − B^{∗}(φ), B^{∗}(ψ)}

6. B^{∗}(φ ↔ ψ) = \{ \begin{matrix}1 & , falls B^{∗}(φ) = B^{∗}(ψ) \\ 0 & , sonst \end{matrix}

Existenz und Eindeutigkeit folgt aus dem Satz 1.6. In der Definition kann man 0 und 1 auch im Ring ℤ der ganzen Zahlen betrachten. Die Sache vereinfacht sich, wenn man sie stattdessen im Körper 𝔽_{2} = ℤ/2ℤ betrachtet.

Bemerkung Wenn X und Y Mengen sind, so bezeichnen wir mit X^{Y} die Menge aller Abbildungen von Y in X. Die Menge aller Belegungen von P ist also {0, 1}^{P}. B^{∗}(φ) ist der Wahrheitswert von φ unter der Belegung B. Wenn B^{∗}(φ) = 1 gilt, so sagen wir auch, dass B die Formel φ erfüllt. Wir schreiben in diesem Fall B ⊧ φ. B |̸= φ steht für B^{∗}(φ) = 0. φ ist erfüllbar, falls eine Belegung B mit B ⊧ φ existiert. φ ist eine Tautologie, falls B ⊧ φ für alle Belegungen B gilt. Man schreibt hier ⊧ φ. φ ist eine Kontradiktion, falls B |̸= φ für alle B gilt.

Die Regeln für die Verknüpfungen lassen sich auch tabellarisch darstellen:

\begin{matrix}φ & ψ & ¬φ & φ ∨ ψ & φ ∧ ψ & φ → ψ & φ ↔ ψ \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 \end{matrix}

Vorlesung am 24.10.2007

Definition (Menge der Aussagenvariablen einer Formel) av(φ) sei die Menge der Aussagenvariablen, die in φ vorkommen.

Lemma 2.6. (2.1) Für alle Formeln φ und alle Belegungen A und B gilt: Wenn A(p) = B(p) für p ∈ av(φ) gilt, so folgt A^{∗}(φ) = B^{∗}(φ).

Beweis: Induktion über den Formelaufbau.

Bemerkung Weil p → (q → p) eine Tautologie ist, ist auch φ → (ψ → φ) für alle Formeln φ und ψ eine Tautologie.

Lemma 2.7. (2.2) Wenn φ eine Tautologie ist, so ist auch φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}} eine Tautologie.

Beweis: Dieses Lemma ist eine direkte Folgerung aus dem folgenden Lemma 2.3.

Lemma 2.8. (2.3) Seien φ, ψ_{1}, ..., ψ_{n} Formeln, p_{1}, ..., p_{n} seien paarweise verschiedenen Aussagenvariablen und B sei eine Belegung. Wir definieren eine Belegung A durch ∀p ∈ P \ {p_{1}, ..., p_{n}} : A(p) = B(p) und A(p) = B^{∗}(ψ_{i}) für p = p_{i}. Dann gilt B^{∗}(φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}}) = A^{∗}(φ).

Beweis: Induktion über den Aufbau von φ:

1. φ ≡ p

p ∉ {p_{1}, ..., p_{n}} ⇒ φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}} ≡ p ⇒ B(p) = A(p)

p = p_{i} ⇒ φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}} ≡ ψ_{i} ⇒ B^{∗}(ψ_{i}) = A(p_{i})

2. φ = ¬ψ

A^{∗}(φ) = 1 − A^{∗}(ψ) = 1 − B^{∗}(ψ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}}) = B^{∗}(φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}})

3. φ ≡ (ψ ∧ χ) (analog gilt dies für ∨, →, ↔)

A^{∗}(φ) = min{A^{∗}(ψ, A^{∗}(χ)} = min{B^{∗}(ψ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}}), B^{∗}(χ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}})}
= B^{∗}(ψ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}} ∧ χ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}})
= B^{∗}((ψ ∧ χ)_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}}) = B^{∗}(φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}})

Lemma 2.9. (2.4) Für jede Formel φ kann man effektiv entscheiden, ob φ { erfüllbar | Tautologie | Kontradiktion } ist.

Beweis: Sei av(φ) = {p_{1}, ..., p_{n}}. Dann gibt es 2^{n} Belegungen dieser n Aussagenvariablen. Für diese wird der Wahrheitswert ausgerechnet.

Bemerkung Ein Problem ist in der Komplexitätsklasse P, wenn es sich in polynomialer Zeit auf einer Turingmaschine entscheiden lässt. Ist φ erfüllbar? Existiert ein Polynom p(x) ∈ ℤ[X], so dass man hächstens p(|av(φ)|) Rechenschritte zur Beantwortung der Frage benötigt? Wenn ja, wäre “Ist φ erfüllbar?” in P. Das Problem ist in NP, d.h. nichtdeterministisch polynomial, da die Frage “Gilt B^{∗}(φ) = 1?” in polynomialer Zeit beantwortet werden kann. Wenn dieses Erfüllbarkeitsproblem nicht in P ist, so gilt P ≠ NP. Wenn das Erfüllbarkeitsproblem in P liegt, so gilt P = NP (weil das Erfüllbarkeitsproblem NP -vollständig ist).

Definition φ und ψ sind logisch äquivalent, wenn für jede Belegung B die Gleichung B^{∗}(φ) = B^{∗}(ψ) gilt. Wir schreiben dann φ ∼ ψ.

Bemerkung Die obige Definition ist äquivalent zu der Aussage, dass φ ↔ ψ eine Tautologie ist. Weiterhin gibt es folgende wichtige logische Äquivalenzen:

1. Assoziativität

(a) φ ∧ (ψ ∧ χ) ∼ (φ ∧ ψ) ∧ χ

(b) φ ∨ (ψ ∨ χ) ∼ (φ ∨ ψ) ∨ χ

2. Kommutativität

(a) φ ∧ ψ ∼ ψ ∧ φ

(b) φ ∨ ψ ∼ ψ ∨ φ

(c) φ ↔ ψ ∼ ψ ↔ φ

3. Distributivität

(a) φ ∧ (ψ ∨ χ) ∼ (φ ∧ ψ) ∨ (φ ∧ χ)

(b) φ ∨ (ψ ∧ χ) ∼ (φ ∨ ψ) ∧ (φ ∨ χ)

(c) φ → (ψ ∨ χ) ∼ (φ → ψ) ∨ (φ → χ)

(d) φ → (ψ ∧ χ) ∼ (φ → ψ) ∧ (φ → χ)

4. Idempotenz

(a) φ ∧ φ ∼ φ

(b) φ ∨ φ ∼ φ

5. Negation

(a) ¬¬φ ∼ φ

(b) ¬(φ ∧ ψ) ∼ ¬φ ∨ ¬ψ

(c) ¬(φ ∨ ψ) ∼ ¬φ ∧ ¬ψ
(d) ¬(φ → ψ) ∼ φ ∧ ¬ψ
(e) ¬(φ ↔ ψ) ∼ (φ ∧ ¬ψ) ∨ (¬φ ∧ ψ)

Lemma 2.10. (2.5) ∼ ist eine Äquivalenzrelation und sie ist mit allen logischen Konnektoren verträglich. Beweis: Es ist klar, dass ∼ eine Äquivalenzrelation darstellt. Es bleibt noch zu zeigen: Wenn φ ∼ ψ gilt, so folgt auch ¬φ ∼ ¬ψ. Wenn φ ∼ ψ und χ ∼ ξ gilt, so folgt φπχ ∼ ψπξ für alle π ∈ {∨, ∧, →, ↔}. Für die Negation (¬) gilt B^{∗}(¬φ) = 1 − B^{∗}(φ) = 1 − B^{∗}(ψ) = B^{∗}(¬ψ). Für die Implikation (→) gilt

B^{∗}(φ → χ) = max{1 − B^{∗}(φ), B^{∗}(χ)} = max{1 − B^{∗}(ψ), 1 − B^{∗}(ξ)} = B^{∗}(ψ → ξ). Dies gilt analog für die anderen zweistelligen Konnektoren. Lemma 2.11. (2.6) Seien φ, ψ_{1}, ..., ψ_{n}, ϑ_{1}, ..., ϑ_{n} Formeln mit ψ_{i} ∼ ϑ_{i} für i = 1, ..., n. Dann gilt φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}} ∼ φ_{ϑ_{1}/p_{1},...,ϑ_{n}/p_{n}}. Beweis: Der Beweis erfolgt durch Induktion über den Formelaufbau.

1. φ ≡ p Für ∀i = 1, ..., n : p ≠ p_{i} erhalten wir φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}} ≡ p ≡ φ_{ϑ_{1}/p_{1},...,ϑ_{n}/p_{n}}. Für p = p_{i} erhalten wir φ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}} ≡ ψ_{i} ∼ ϑ_{i} ≡ φ_{ϑ_{1}/p_{1},...,ϑ_{n}/p_{n}}.

2. φ ≡ ¬μ Wir erhalten μ_{ψ_{1}/p_{1},...,ψ_{n}/p_{n}} ∼ μ_{ϑ_{1}/p_{1},...,ϑ_{n}/p_{n}} nach Lemma 2.5.

3. Analog erhalten wir dies für die zweistelligen Konnektoren. Korollar 2.2. (2.7) Wenn in einer Formel φ eine Teilformel durch eine logisch äquivalente Formel ersetzt wird, so ist das Resultat π zur Ausgangsformel φ logisch äquivalent. Beweis: Die Teilformel ψ werde durch χ ersetzt, wobei ψ ∼ χ gilt. ξ entstehe aus φ durch Ersetzen von ψ durch eine neue Aussagenvariable q. Dann gilt φ = ξ_{ψ/q} ∼ ξ_{χ/q} = π. Lemma 2.12. (2.8) Man findet zu jeder Formel φ eine logisch äquivalente Formel ψ, welche nur die Zeichen ¬, → enthält. Analog gilt dies für ¬, ∨ und ¬, ∧. Beweis: Wir müssen lediglich die übrigen Konnektoren durch ¬ und → darstellen:

1. φ ∧ ψ ∼ ¬(φ → ¬ψ)

2. φ ∨ ψ ∼ ¬φ → ψ

3. φ ↔ ψ ∼ ¬((φ → ψ) → ¬(ψ → φ)) Wir verwenden Korollar 2.7 und ersetzen die entsprechenden Teilformeln mit den falschen Konnektoren im Formelaufbau.

Vorlesung am 29.10.2007 Definition (Normalformen) ψ ist in konjunktiver Normalform, wenn ψ = ⋀_{i<n}(⋁_{j<m_{i}} ψ_{i,j}). ψ ist in disjunktiver Normalform, wenn ψ = ⋁_{i<n}(⋀_{j<m_{i}} ψ_{i,j}). ψ_{i,j} sind Literale, d.h. Aussagenvariablen oder negierte Aussagenvariablen.

Lemma 2.13. (2.9) Jede Formel φ ist einer Formel ψ logisch äquivalent, wobei ψ nur ¬, ∧, ∨ benutzt und ¬ nur vor Aussagenvariablen vorkommt.

Beweis: Nach Korollar 2.8 können wir o.B.d.A. annehmen, dass φ nur mit Hilfe von ¬, ∧ und ∨ aufgebaut ist. Nun führen wir den Beweis des zweiten Teils durch vollständige Induktion über die Formellänge l(φ).

1. l(φ) = 1, d.h. φ = p. ⇒ fertig.

2. φ = (ψ ∧ χ) oder φ ≡ (ψ ∨ χ), φ ≡ ¬ψ, l(φ), l(χ) < l(φ). Nach Induktionsvoraussetzung existieren ψ′ und χ′ in der gewünschten Form. Also haben wir φ ∼ ψ′ ∨ χ′, φ ∼ ψ′ ∧ χ′ oder φ ∼ ¬ψ′. In den ersten beiden Fällen sind wir fertig. Es bleibt also der dirtte Fall. Betrachten wir wieder den Aufbau von ψ.

(a) Wenn ψ = p ∈ P, so gilt φ = ¬p. Das ist die gewünschte Form.

(b) Wenn ψ = ¬μ mit l(μ) < l(φ), so haben wir durch die Induktionsvoraussetzung eine Formel μ′ ∼ μ ∼ ¬¬μ ∼ φ in der gewünschten Form.

(c) Wenn ψ ≡ (μ ∧ ν) ∼ ¬μ ∨ ¬ν. Wegen l(¬μ), l(¬ν) < l(¬ψ) existieren μ′ ∼ ¬μ und ν′ ∼ ¬ν in der gewünschten Form. Wir erhalten also wieder die gewünschte Form für φ.

(d) Der Fall ψ ≡ (μ ∨ ν) lässt sich analog zum vorhergehenden Fall bearbeiten.

Satz 2.3. (Darstellung in Normalform (2.10)) Zu jeder formel φ gibt es logisch äquivalente Formeln in konjunktiver und disjunktiver Normalform.

Beweis: Wir zeigen die Existenz einer Formel ψ in konjunktiver Normalform mit φ ∼ ψ. Der disjunktive Fall verläuft analog. Nach Lemma 2.9 können wir o.B.d.A. annehmen, dass φ nur aus ∨, ∧ und ¬ aufgebaut ist, wobei ¬ höchstens unmittelbar vor den Aussagenvariablen vorkommt. Durch Induktion über l(φ) erhalten wir:

1. Wenn φ ≡ p oder φ ≡ ¬p, so sind wir fertig.

2. φ ≡ (μ ∧ ν) oder φ(μ ∨ ν).

Da l(μ), l(ν) < l(φ), existieren μ′, nu′ in konjunktiver Normalform und μ ∼ μ′, nu ∼ ν′. Im ersten Fall haben wir φ ∼ μ′ ∧ ν′ in konjunktiver Normalform. Im zweiten Fall haben wir μ′ ≡ ⋀_{i<n} μ_{i}, ν′ ≡ ⋀_{i<k} ν_{i}. Wir erhalten φ ∼ (⋀_{i<n} μ_{i}) ∨ (⋀_{i<k} ν_{i}) ∼ ⋀_{i<m} ⋀_{j<k}(μ_{i} ∨ ν_{j}) in konjunktiver Normalform.

Beispiel Der Beweis liefert ein Verfahren zum Auffinden von Normalformen. Dieses wollen wir nun an einem Beispiel anwenden. Wir suchen die Normalform von (p → q) → (¬q → p):

(p → q) → (¬q → p) ∼ ¬(¬p ∨ q) ∨ (¬¬q ∨ p)
∼ (p ∧ ¬q) ∨ (p ∨ q)  disjunktive Normalform
∼ (p ∨ p ∨ q) ∧ (¬q ∨ p ∨ q)  konjunktive Normalform
∼ p ∨ q  disjunktive und konjunktive Normalform

Definition (Erfüllbarkeit von Formelmengen) Sei Σ eine Menge von Formeln. Eine Belegung B erfüllt Σ (B ⊧ Σ), wenn B ⊧ φ für alle φ aus Σ gilt. B nennt man dann eine Realisierung oder ein Modell von Σ.

Definition (Deduktiver Abschluss) Die Formel ψ folgt aus Σ, wenn für eine Belegung B, die Σ erfüllt, auch B ⊧ ψ gilt. Wir schreiben Σ ⊧ ψ. Mit anderen Worten: Ein Modell B von Σ ist auch ein Modell von ψ. Σ ist erfüllbar, falls ein Modell von Σ existiert. Ded(Σ) = {ψ|Σ ⊧ ψ} ist der deduktive Abschluss.

Bemerkung

1. Ded(∅) ist die Menge der Tautologien.

2. Wenn Σ nicht erfüllbar ist, so ist Ded(Σ) die Menge aller Formeln.

3. Ded ist ein Hüllenoperator:

(a) Σ ⊆ Ded(Σ)

(b) Δ ⊆ Σ ⇒ Ded(Δ) ⊆ Ded(Σ) Sei φ ∈ Ded(Δ), d.h. ∃B : B ⊧ Δ ⇒ B ⊧ φ. Wenn nun eine Belegung B ⊧ Σ gilt, so folgt auch B ⊧ Δ, also B ⊧ φ. Es folgt also φ ∈ Ded(Σ).

(c) Ded(Ded(Σ)) = Ded(Σ)

Definition (Boolesche Funktion) Eine n-stellige Boolesche Funktion f ist ein Element von {0, 1}^{{0,1}^{n}}. Mit anderen Worten: jedem n-Tubel von 0 und 1 wird 0 oder 1 zugeordnet. Wenn {a_{0}, ..., a_{n−1}} ∈ {0, 1}^{n} mit n = {0, ..., n−1}, so kann dies als Belegung B(p_{i}) = a_{i} für i < n angesehen werden. f wird durch φ mit av(φ) = {p_{0}, ..., p_{n−1}} repräsentiert, wenn B^{∗}(φ)f(B(p_{0}), ..., B(p_{n−1})) für alle Belegungen B von p_{0}, ..., p_{n−1} gilt.

Satz 2.4. (2.11) Jede n-stellige Boolesche Funktion wird durch eine Formel repräsentiert.

Beweis: Übung.

2.3 Ableiten

Ziel Unser Ziel ist die Formalisierung des aussagenlogischen Teils des mathematischen Schließens. Wir geben Axiome und Schlussregeln an. Die Axiome aind Tautologien und die Schlussregeln sind formale Formelmanipulationen, die wieder Tautologien erzeugen, wenn wir von Tautologien ausgehen. Als Endergebnis möchten wir haben, dass eine Formel genau dann eine Tautologie ist, wenn sie sich ableiten lässt.

Vorlesung am 31.10.2007

Einschränkung der Sprache der Aussagenlogik Wir schränken unsere Sprache auf Formeln ein, dir nur Aussagenvariablen, Klammern, → und ¬ enthalten. Andere Formeln werden dann als Abkürzungen betrachtet.

Definition (Axiome) Die Axiome unseres Ableitungskalküls sind die folgenden Mengen von Formeln:

1. Ax1: φ → (ψ → φ) für alle φ, ψ

2. Ax2: (φ → (ψ → χ)) → ((φ → ψ) → (φ → χ)) für alle φ, ψ, χ

3. Ax3: (¬ψ → ¬φ) → ((¬ψ → φ) → ψ) für alle φ, ψ

Die Schlussregel ist die Abtrennungsregel (Modus Ponens): Aus φ und φ → ψ erhält man ψ. Man schreibt für diese Regel auch \frac{φ φ→ψ}{ψ}. Ein Beweis für eine Formel φ ist eine Folge φ_{0}, ..., φ_{n−1} mit den folgenden Eigenschaften:

1. φ_{n−1} ≡ φ

2. Für jedes i < n gilt: φ_{i} ist ein Axiom oder es existieren l, k < i mit φ_{l} ≡ φ_{k} → φ_{i}, d.h. φ_{i} wird aus den Vorgängern durch Modus Ponens gewonnen.

φ ist ableitbar, wenn ein Beweis für φ existiert. Wir schreiben in diesem Fall ⊢ φ.

Definition (Σ-Beweis) Es sei Σ eine Formelmenge und φ eine Formel. Ein Σ-Beweis für φ ist eine Folge φ_{0}, ..., φ_{n−1} mit den folgenden Eigenschaften:

1. φ_{n−1} ≡ φ

2. Für jedes i < n gilt: φ_{i} ∈ Σ, φ_{i} ist ein Axiom oder es existieren l, k < i mit φ_{l} ≡ φ_{k} → φ_{i}, d.h. φ_{i} wird aus den Vorgängern durch Modus Ponens gewonnen.

Wenn ein Σ-Beweis für φ existiert, so ist φ aus Σ ableitbar.

Lemma 2.14. (3.1) Für jede Formel φ gilt φ → φ.

Beweis:

\begin{matrix}(1) & (Ax2) & (φ → ((φ → φ) → φ)) → ((φ → (φ → φ)) → (φ → φ)) \\ (2) & (Ax1) & φ → ((φ → φ) → φ) \\ (3) & MP (1, 2) & (φ → (φ → φ)) → (φ → φ) \\ (4) & (Ax1) & φ → (φ → φ) \\ (5) & MP (3, 4) & φ → φ \end{matrix}

Bemerkung

1. Jedes Anfangsstück eines Σ-Beweises ist wieder ein Σ-Beweis.

2. Wenn Σ ⊢ φ, so kann man φ in Σ-Beweisen benutzen, da man statt φ den gesamten Σ-Beweis an dieser Stelle einsetzen könnte.

3. Abl(Σ) = {φ|Σ ⊢ φ} ist ein Hüllenoperator.

4. Wenn Σ ⊢ φ gilt, so existiert eine endliche Teilmenge Σ_{0} ⊆ Σ mit Σ_{0} ⊢ φ: Sei Σ_{0} die Menge der Formeln aus Σ, die in einem fixierten Σ-Beweis von φ vorkommen. Weil der Beweis endlich ist, ist auch Σ_{0} endlich.

Lemma 2.15. (3.2) Wenn Σ ⊢ φ gilt, so folgt Σ ⊧ φ.

Beweis: Sei B eine Belegung, sodass B ⊧ Σ. Es ist zu zeigen, dass B ⊧ φ gilt. Sei φ_{0}, ..., φ_{n−1} ≡ φ ein Σ-Beweis für φ. Induktiv über i zeigen wir nun, dass B ⊧ φ_{i} gilt.

1. Wenn φ_{i} ein Axiom ist, so gilt B ⊧ φ_{i}, weil alle Axiome Tautologien sind.

2. Wenn φ_{i} ∈ Σ gilt, so folgt B ⊧ φ_{i}, weil nach Voraussetzung B ⊧ Σ gilt.

3. Wenn φ_{i} durch die Schlussregel Modus Ponens aus φ_{k} und φ_{l} mit φ_{k} ≡ φ_{l} → φ_{i} (k, l < i) gewonnen wird, so folgt nach Induktionsvoraussetzung B ⊧ φ_{l} → φ_{i} und B ⊧ φ_{l}. D.h. B^{∗}(φ_{l} → φ_{i}) = 1 und B^{∗}(φ_{l}) = 1. Damit erhalten wir B^{∗}(φ_{i}) = 1, also B ⊧ φ.

Satz 2.5. (Deductions Theorem - Herbrand 1930 (3.3)) Sei Σ eine Menge von Formeln und φ, ψ Formeln. Wenn Σ ∪ {φ} ⊢ ψ gilt, so folgt Σ ⊢ φ → ψ. Beweis: Sei ψ_{0}, ..., ψ_{n−1} ein Beweis von ψ aus Σ ∪ {φ}. Dann gilt ψ_{n−1} ≡ ψ. Wir zeigen induktiv über i: Σ ⊢ φ → ψ_{i}.

1. i = 0 Hier gilt ψ_{0} ∈ Σ, ψ_{0} ≡ φ oder ψ_{0} ist ein Axiom.

(a) ψ_{0} ≡ φ Hier haben wir ⊢ φ → ψ_{0} nach Lemma 3.1 (⊢ φ → φ).

(b) ψ_{0} ist ein Axiom oder ψ_{0} ∈ Σ

Hier haben wir nach Axiom 1 den Σ-Beweis ψ_{0} → (φ → ψ_{0}), φ → ψ_{0} für φ → ψ_{0}.

2. 0 < i < n Für alle k < i ist Σ ⊢ φ → ψ_{n} bewiesen. Es treten 4 Fälle auf:

(a) ψ_{i} ist ein Axiom. Hier verwenden wir den Beweis aus dem Induktionsanfang i = 0.

(b) ψ_{i} ∈ Σ ⇝ i = 0

(c) ψ_{i} ≡ φ

⇝ i = 0

(d) Es existieren k, j < i mit ψ_{k} ≡ ψ_{j} → ψ_{i}.

Wir schreiben nun einfach einen Beweis auf:

\begin{matrix}(1) & (Σ) & φ → ψ_{j} \\ (2) & (Σ) & φ → (ψ_{j} → ψ_{i}) \\ (3) & (Ax2) & (φ → (ψ_{j} → ψ_{i})) → ((φ → ψ_{j}) → (φ → ψ_{i})) \\ (4) & MP (2, 3) & (φ → ψ_{j}) → (φ → ψ_{i}) \\ (5) & MP (1, 4) & φ → ψ_{i} \end{matrix}

Korollar 2.3. (3.4)

1. {φ → ψ, ψ → χ} ⊢ φ → χ

2. {φ → (ψ → χ), ψ} ⊢ φ → χ

3. Wenn ⊢ φ → ψ mit ⊢ ψ → χ, so gilt ⊢ φ → χ. Beweis:

1. Nach Satz 3.3 und {φ → ψ, ψ → χ, φ} ⊢ χ erhalten wir die Behauptung. Ein Beweis ist

\begin{matrix}(1) & (V or) & φ → ψ \\ (2) & (V or) & ψ → χ \\ (3) & (V or) & φ \\ (4) & MP (1, 3) & ψ \\ (5) & MP (2, 4) & χ \end{matrix}

2. Übungsaufgabe.

3. Übungsaufgabe.

Lemma 2.16. (3.5) Es gilt: 1. ⊢ ¬¬ψ → ψ

2. ⊢ ψ → ¬¬ψ

3. ⊢ ¬φ → (φ → ψ)

4. ⊢ (¬ψ → ¬φ) → (φ → ψ)

5. ⊢ (φ → ψ) → (¬ψ → ¬φ)

6. ⊢ φ → (¬ψ → ¬(φ → ψ))

7. ⊢ (φ → ψ) → ((¬φ → ψ) → ψ) Beweis:

1. Ein Beweis:

\begin{matrix}(1) & (Ax3) & (¬ψ → ¬¬ψ) → ((¬ψ → ¬ψ) → ψ) \\ (2) & (Lemma 3.1) & ¬ψ → ¬ψ \\ (3) & Cor. 3.4.2(1, 2), T h. 3.3 & (¬ψ → ¬¬ψ) \\ (4) & (Ax1) & ¬¬ψ → (¬ψ → ¬¬ψ) \\ (5) & Cor. 3.4.3(3, 4) & ¬¬ψ → ψ \end{matrix}

2. Noch ein Beweis:

\begin{matrix}(1) & (Ax3) & (¬¬¬ψ → ¬ψ) → ((¬¬¬ψ → ψ) → ¬¬ψ) \\ (2) & (3.5.1) & ¬¬¬ψ → ¬ψ \\ (3) & MP (1, 2) & (¬¬¬ψ → ψ) → ¬¬ψ \\ (4) & (Ax1) & ψ → (¬¬¬ψ → ψ) \\ (5) & Cor. 3.4.2(3, 4) & ψ → ¬¬ψ \end{matrix}

3. Zuerst zeigen wir {¬φ, φ} ⊢ ψ:

\begin{matrix}(1) & (V or) & ¬φ \\ (2) & (V or) & φ \\ (3) & (Ax1) & φ → (¬ψ → φ) \\ (4) & (Ax1) & ¬φ → (¬ψ → ¬φ) \\ (5) & MP (2, 3) & ¬ψ → φ \\ (6) & MP (1, 4) & ¬ψ → ¬φ \\ (7) & (Ax3) & (¬ψ → ¬φ) → ((¬ψ → φ) → ψ) \\ (8) & MP (5, MP (6, 7)) & ψ \end{matrix}

Mit dem Deduktionstheorem erhalten wir nun {¬φ} ⊢ φ → ψ, also auch ⊢ ¬φ → (φ → ψ).

4. Übungsaufgabe.

5. Übungsaufgabe.

6. Übungsaufgabe.

7. Übungsaufgabe.

Vorlesung am 05.11.2007

Definition ((In-)Konsistenz) Eine Menge von Formeln Σ heißt inkonsistent (bzw. widerspruchsvoll), wenn es eine Aussage φ gibt, so dass Σ ⊢ φ und Σ ⊢ ¬φ gilt. Wenn solch ein φ nicht existiert, so heißt Σ konsistent (bzw. widerspruchsfrei).

Bemerkung (Σ erfüllbar ⇒ Σ konsistent) Wenn Σ erfüllbar ist, d.h. es existiert eine Belegung B mit ∀φ ∈ Σ : B^{∗}(φ) = 1, so ist Σ konsistent. Beweis: Wäre Σ inkosistent, so existierte eine Formel ψ mit Σ ⊢ ψ und Σ ⊢ ¬ψ. Nach Lemma 3.2 gilt dann Σ ⊧ ψ und Σ ⊧ ¬ψ. Dies ist jedoch ein Widerspruch zur Definition von ⊧.

Ziel Unser Ziel ist nun, die Umkehrung der vorherigen Bemerkung zu zeigen, d.h. eine konsistente Formelmenge Σ ist auch erfüllbar.

Lemma 2.17. (3.6) Wenn Σ inkonsistent ist, so gilt ∀ψ ∈ F : Σ ⊢ ψ.

Beweis: Da Σ inkosistent ist, existiert ein φ mit Σ ⊢ φ und Σ ⊢ ¬φ. Sei ψ gegeben. Wir geben nun einen Σ-Beweis für ψ an.

(1) (V or)  Σ ⊢ φ
(2) (V or)  Σ ⊢ ¬φ
(3) (Σ ⊆ Σ ∪ {¬ψ}) Σ ∪ {¬ψ} ⊢ ¬φ
(4) (Deduktion)  Σ ⊢ ¬ψ → ¬φ
(5) (Lemma 3.5.4) Σ ⊢ (¬ψ → ¬φ) → (φ → ψ)
(6) MP (4, 5)  Σ ⊢ φ → ψ
(7) MP (1, 6)  Σ ⊢ ψ

Lemma 2.18. (3.7) Wenn Σ ∪ {¬φ} inkonsistent ist, dann gilt Σ ⊢ φ.

Beweis: Nach Lemma 3.6 gilt Σ ∪ {¬φ} ⊢ ¬ψ, wobei ψ = p → (q → p).

\begin{matrix}(1) & (Deduktion) & Σ ⊢ ¬φ → ¬ψ \\ (2) & (Lemma 3.5.4) & Σ ⊢ (¬φ → ¬ψ) → (ψ → φ) \\ (3) & MP (1, 2) & Σ ⊢ ψ → φ \\ (4) & (Ax1) & Σ ⊢ ψ \\ (5) & MP (3, 4) & Σ ⊢ φ \end{matrix}

Definition (Vollständigkeit) Eine Formelmenge Σ ist vollständig, wenn für jede Formel φ entweder Σ ⊢ φ oder Σ ⊢ ¬φ gilt. Damit ist Σ maximal konsistent.

Satz 2.6. (Lindenbaum (3.8)) Jede konsistente Formelmenge Σ lässt sich zu einer vollständigen Menge Σ′ erweitern.

Beweis: Es existieren nur abzählbar viele Formeln. Sei φ_{0}, φ_{1}, ... eine Aufzählung aller Formeln und sei Σ_{0} = Σ. Induktiv definieren wir nun eine konsistente Menge Σ_{n} aus Σ_{n−1}, sodass für alle φ_{i} mit i < n entweder φ_{i} ∈ Σ_{n} oder ¬φ_{i} ∈ Σ_{n} gilt. Ist Σ_{n} ∪ {¬φ_{n}} konsistent, so setzen wir Σ_{n+1} = Σ_{n} ∪ {¬φ_{n}}, sonst gilt nach Lemma 3.7, dass Σ_{n} ⊢ φ_{n}. In dem zweiten Fall erzeugen wir die konsistente Menge Σ_{n+1} durch Σ_{n+1} = Σ_{n} ∪{φ_{n}}. Wäre Σ_{n+1} ⊢ ψ und Σ_{n+1} ⊢ ¬ψ, so erhielten wir aus Σ_{n+1}-Beweisen auch Σ_{n}-Beweise, da wir immer φ_{n} im Σ_{n+1} durch den Σ_{n}-Beweis ersetzen könnten. Sei nun Σ′ = ⋃_{n=0}^{∞} Σ_{n}. Σ′ ist konsistent, denn: Wenn Σ′ ⊢ χ und Σ′ ⊢ ¬χ, so lägen die Formeln in entsprechenden Σ′-Beweisen schon in Σ_{n} für genügend großes n vor. Nach Konstruktion gilt entweder φ_{n} ∈ Σ′ oder ¬φ_{n} ∈ Σ′. Damit haben wir für alle Formeln φ_{n} auch Σ ⊢ φ_{n} oder Σ ⊢ ¬φ_{n}.

Satz 2.7. (3.9) Eine Menge Σ von Formeln ist genau dann konsistent, wenn sie erfüllbar ist.

Beweis: “⇐“: Siehe Bemerkung im Anschluss an die Definition von Konsistenz. “⇒“: Nach Satz 3.8 existiert eine vollständige Formelmenge Σ′ ⊇ Σ. Wir definieren B(p_{i}) = 1 genau dann, wenn Σ′ ⊢ p_{i}. Wir beweisen nun B ⊧ Σ (d.h. B ⊧ φ genau dann, wenn Σ′ ⊢ φ) durch Induktion über den Formelaufbau:

1. Wenn φ ≡ p, p ∈ P so haben wir die Erfüllbarkeit von φ nach der Definition von B.

2. φ ≡ ¬ψ

Sei B ⊧ ¬ψ. Wäre Σ′ ⊬ ¬ψ, dann erhielten wir Σ′ ⊢ ψ, wegen der Vollständigkeit von Σ′. Durch die Induktionsvoraussetzung erhalten wir B ⊧ ψ im Widerspruch zur Annahme. Es gilt also Σ′ ⊢ ¬ψ.

Wenn Σ′ ⊢ ¬ψ gilt, dann folgt Σ′ ⊬ ψ, da Σ′ konsistent ist. Durch die Induktionsvoraussetzung erhalten wir B |̸= ψ, also B ⊧ ¬ψ ≡ φ.

3. Weil die Sprache auf ¬ und → eingeschränkt ist, müssen wir hier nur einen binären Konnektor betrachten. Sei also φ ≡ ψ → χ.

Wenn B ⊧ ψ → χ, so folgt B ⊧ ¬ψ oder B ⊧ χ. Wir führen nun eine Fallunterscheidung durch:

(a) B ⊧ ¬ψ Durch die Induktionsvoraussetzung erhalten wir Σ′ ⊢ ¬ψ. Nach Lemma 3.5.3 gilt Σ′ ⊢ ¬ψ → (ψ → χ). Durch Modus Ponens erhalten wir Σ′ ⊢ ψ → χ.

(b) B ⊧ χ

Nach Induktionsvoraussetzung erhalten wir Σ′ ⊢ χ. Durch die Axiome der Gruppe 1 ergibt sich Σ′ ⊢ χ → (ψ → χ) und mit Modus Ponens auch Σ′ ⊢ ψ → χ.

Annahme: Σ′ ⊢ ψ → χ und B |̸= ψ → χ. Wir zeigen nun einen Widerspruch:

Wir haben B ⊧ ψ, aber B ⊧ ¬χ. Nach Induktionsvoraussetzung erhalten wir Σ′ ⊢ ψ und Σ′ ⊬ χ.

Wegen der Vollständigkeit erhalten wir Σ′ ⊢ ¬χ.

Mit Lemma 3.5.6 erhalten wir Σ′ ⊢ ψ → (¬χ → ¬(ψ → χ)).

⇒ Σ′ ⊢ ¬χ → ¬(ψ → χ) (MP)

⇒ Σ ⊢ ¬(ψ → χ) (MP)

Damit ist Σ inkonsistent, womit wir einen Widerspruch erhalten.

Satz 2.8. (Vollständigkeitssatz für die Aussagenlogik (3.10)) Es gilt Σ ⊧ φ genau dann, wenn Σ ⊢ φ gilt.

Beweis: “⇐“: Wir erhalten diese Richtung durch das Lemma 3.2. “⇒“: Gegeben ist Σ ⊧ φ. Zu zeigen ist Σ ⊢ φ. Wenn B ⊧ Σ, so folgt auch B ⊧ φ, d.h. Σ ∪ {¬φ} ist nicht erfüllbar. Mit Theorem 3.9 folgt, dass Σ ∪ {¬φ} inkonsistent ist. Nach Lemma 3.7 folgt nun Σ ⊢ φ.

Korollar 2.4. (3.11) Σ ist genau dann erfüllbar, wenn jede endliche Teilmenge Σ_{0} erfüllbar ist.

Beweis: “⇒“: Diese Richtung ist trivial, da aus einer erfüllenden Belegung für Σ auch eine erfüllende Belegung für jede endliche Teilmenge gegeben ist. “⇐“: Es sei jede endliche Teilmenge Σ_{0} erfüllbar. Mit Satz 3.9 ist Σ_{0} auch konsistent. Damit ist Σ konsistent, da Σ-Beweise für χ und ¬χ sind auch schon Σ_{0}-Beweise. Also ist Σ nach Satz 3.9 erfüllbar.

Elementare Logik

3.4 Strukturen

Eine Signatur σ(L) einer Sprache L ist gegeben durch 1. Namen für Elemente (Konstantensymbole) c_{0}, c_{1}, ...

2. Namen für Relationen (Relationssymbole) R_{0}, R_{1}, ...

3. Namen für Funktionen (Funktionssymbole) f_{0}, f_{1}, ... Den Relations- und Funktionssymbolen wird eine Stellenzahl zugeordnet, z.B. (0, 1, <, +, −, ·) hat 0, 1 als Konstantensymbole, < als zweistelliges Relationssymbol, − als einstelligs Funktionssymbol und +, · als zweistellige Funktionssymbole.

Vorlesung am 07.11.2007

Definition

1. Eine Struktur M der Signatur σ(L) hat die Form ⟨dom(M), c_{0}^{M}, c_{1}^{M}, …, R_{0}^{M}, R_{1}^{M}, …, f_{0}^{M}, f_{1}^{M}, …⟩, wobei

(a) dom(M) ist die Menge der Elemente der Struktur.

(b) c_{0}^{M}, c_{1}^{M}, … sind Elemente aus dom(M), die durch die Konstantensymbole c_{0}, c_{1}, … Namen bekommen haben.

(c) Wenn R_{i} ein n-stelliges Relationssymbol ist, so ist R_{i}^{M} eine n-stellige Relation auf dom(M).

(d) Wenn f_{i} ein n-stelliges Funktionssymbol ist, so ist f_{i}^{M} eine n-stellige Funktion auf

dom(M).

2. Man nennt M eine L-Struktur.

3. R_{i}^{M}(a_{0}, …, a_{n−1}) heißt, dass R_{i}^{M} auf (a_{0}, …, a_{n}) zutrifft.

4. f_{i}^{M}(a_{0}, …, a_{n−1}) = a heißt, dass f_{i}^{M} dem Tupel (a_{0}, …, a_{n−1}) den Wert a zuordnet.

5. Es wird nicht immer zwischen dom(M) und M unterschieden und wir lassen oft in c_{i}^{M}, R_{i}^{M} und f_{i}^{M} das M weg.

6. |M| bezeichnet die Mächtigkeit der Struktur, d.h. |M| = |dom(M)|.

Beispiel In der Signatur (0, 1, <, +, ·) können wir die folgenden Strukturen betrachten: ℕ, ℤ, ℚ, ℝ und ℂ, wobei im letzten Fall die Definition von < fragwürdig ist. Wie sehen allgemein L-Strukturen für σ(L) = (c_{o}, c_{1}, R_{0}, f_{0}, f_{1}) aus? R_{0}, f_{0}, f_{1} seien dabei zweistellig. Eine Möglichkeit wäre:

• c_{0}^{M} = 1001

• c_{1}^{M} = 111

• R_{0}(a, b) genau dann, wenn 2|a + b

• f_{0}(a, b) = a^{b}

• f_{1}(a, b) = \{ \begin{matrix}a^{2} & , wenn a ∈ ℙ (eine Primzahl) ist \\ b^{5} & , sonst \end{matrix}

Definition (Homomorphismus) Seien M und N L-Strukturen. Ein Homomorphismus von M in N ist eine Abbildung h von dom(M) in dom(N), die folgenden Bedingungen genügt:

1. Für jedes Konstantensymbol c aus σ(L) gilt h(c^{M}) = c^{N}.

2. Für jedes n-stellige Relationssymbol R aus σ(L) gilt:

Wenn R^{M}(a_{0}, …, a_{n−1}) für a_{0}, …, a_{n−1} aus dom(M) gilt, dann gilt R^{N}(h(a_{0}), …, h(a_{n−1})).

3. Für jedes n-stellige Funktionssymbol f aus σ(L) gilt:

h(f^{M}(a_{0}, …, a_{n−1})) = f^{N}(h(a_{0}), …, h(a_{n−1})) für alle a_{0}, …, a_{n−1} ∈ dom(M). Wir schreiben h : M → N. Beispiel (Gruppenhomomorphismus) Im Fall von σ(L) = (1, ·) seien zwei L-Strukturen M und N gegeben. h ist ein Homomorphismus von M nach N, wenn h(1^{M}) = 1^{N} und h(a ·^{M} b) = h(a) ·^{M} h(b) gilt. Definition Eine Abbildung h von M in N ist

1. injektiv, wenn aus a ≠ b in M stets h(a) ≠ h(b) folgt.

2. surjektiv, falls für jedes Element c ∈ dom(N) ein a in dom(M) existiert mit h(a) = c.

3. bijektiv, falls h injektiv und surjektiv ist. Definition

1. N ist homomorphes Bild von M, falls ein surjektiver Homomorphismus von M auf N existiert.

2. Ein Monomorphismus von M in N ist ein injektiver Homomorphismus h von M in N, für den die folgende (verschärfte) Bedingung gilt: Für alle a_{0}, …, a_{n−1} ∈ dom(M) und alle n-stelligen Relationssymbole R gilt die folgende Äquivalenz: R^{M}(a_{0}, …, a_{n−1}) ⇔ R^{N}(a_{0}, …, a_{n−1}).

3. Monomorphismen werden auch als Einbettungen bezeichnet.

Wir schreiben dies als h : M ↪ N.

4. Ein Isomorphismus ist ein surjektiver Monomorphismus.

Wir schreiben in diesem Fall M ≅ N.

5. Die Relation ≅ ist eine Äquivalenzrelation.

6. Die Äquivalenzklassen werden Isomorphietypen genannt.

7. Ein Automorphismus von M ist ein Isomorphismus von M auf M. Bemerkung

1. Isomorphe Strukturen besitzen die gleiche Mächtigkeit.

2. Ein bijektiver Homomorphismus ist im allgemeinen kein Isomorphismus.

Beispiel:

Wir betrachten σ(L) = (P), wobei P ein einstelliges Relationssymbol ist. Weiterhin setzen wir dom(M) = {a_{i}, i ∈ ℕ}, P^{M} = {a_{i}|i ∈ ℕ, i ≠ 0} und dom(N) = {b_{i}, i ∈ ℕ}, P^{N} = {a_{i}|i ∈ ℕ}. h(a_{i}) = b_{i} ist eine Bijektion und h ist ein Homomorphismus, wegen P^{M}(a_{i}) ⇒ P^{N}(h(a_{I})). h ist jedoch kein Isomorphismus, weil P^{M}(a_{0}) nicht gilt, P^{N}(b_{0}) jedoch erfüllt ist.

3. Falls keine Relationssymbole vorkommen, so ist natürlich jeder bijektive Homomorphismus auch ein Isomorphismus.

4. Ein Homomorphismus h von M in N ist genau dann ein Isomorphismus, wenn ein Homo-

morphismus g von N in M existiert, sodass g ∘ h = id_{M} und h ∘ g = id_{N} gilt. Definition (Unterstrukturen) Seien σ(L) und zwei L-Strukturen M und N gegeben. Dann ist M eine Unterstruktur von N, wenn

1. dom(M) ⊆ dom(N)

2. c^{M} = c^{N}

3. ∀a_{0}, …, a_{n−1} ∈ dom(M), R n-stellige Relation : R^{M}(a_{0}, …, a_{n−1}) ⇔ R^{N}(a_{0}, …, a_{n−1})

4. ∀a_{0}, …, a_{n−1} ∈ dom(M), f n-stellige Funktion : f^{M}(a_{0}, …, a_{n−1}) = f^{N}(a_{0}, …, a_{n−1}) Bemerkung

1. Man kann in der obigen Definition auch sagen, dass M die Einschränkung von N auf dom(M) ist.

2. N wird auch als Oberstruktur von M bezeichnet. Wir schreiben M ⊆ N.

3. Es gilt M ⊆ N genau dann, wenn dom(M) ⊆ dom(N) und id(a) = a eine Einbettung von

M in N ist. Definition Wenn X ⊆ dom(M), so sei ⟨X⟩_{M} die kleinste Unterstruktur von M, die X enthält. Bemerkung Sei X_{0} = X ∪ {c^{M}|c ∈ σ(L)} und X_{i+1} = X_{i} ∪ {f^{M}(a_{0}, …, a_{n−1})|f ∈ σ(L), a_{0}, …, a_{n−1} ∈ X_{i}}. Dann gilt ⟨X⟩_{M} = ⋃_{i∈ℕ} X_{i}.

Definition Sei σ(L_{0}) ⊆ σ(L). Wenn M eine L-Struktur ist, so ist M ↾ L_{0} die L_{0}-Struktur, die man aus M erhält, indem man die Interpretation der Symbole aus L \ L_{0} weglässt. M ↾ L_{0} ist das L_{0}-Redukt von M und M ist Expansion von M ↾ L_{0}. Beispiel: Wir betrachten σ(L) = (0, 1, <, +, ·), σ(L_{0}) = (<). ℚ ↾ L_{0} ist dann eine dichte lineare Ordnung. Definition Seiein M_{i} (mit i ∈ I) L-Strukturen (I geordnet). Dann ist M = ∏_{i∈I} M_{i} die folgende L Struktur:

1. dom(M) = \{\overline{a}|\overline{a} = (a(i), i ∈ I), a(i) ∈ M_{i}\}

2. c^{M} = \overline{a}, wenn a(i) = c^{M_{i}} für alle i ∈ I

3. R^{M}(\overline{a}_{0}, …, \overline{a}_{n−1}), falls R^{M_{i}}(\overline{a}_{0}, …, \overline{a}_{n−1}) für alle i ∈ I

4. f^{M}(\overline{a}_{0}, …, \overline{a}_{n−1}) = \overline{a}, falls R^{M_{i}}(\overline{a}_{0}, …, \overline{a}_{n−1}) = a_{i} für alle i ∈ I M ist das kartesische Produkt der M_{i}. Im Fall von I = {0, …, n − 1} schreiben wir auch M = M_{0} × … × M_{n−1}. Wenn M_{i} = N gilt, so schreiben wir auch M = N^{I}.

Vorlesung am 12.11.2007

3.5 Elementare Sprachen (Die Sprachen des Prädikatenkal-

küls 1. Stufe)

Wir benutzen L, um die zu konstruierende Sprache zu bezeichnen. Die Elemente der Sprache sind Formeln. Die Formeln sind spezielle Worte über dem folgenden Alphabet:

1. logische Zeichen: ¬, ∨, ∧, →, ↔, ∀, ∃ und =,

2. die Symbole der gegebenen Signatur σ(L) (auch nichtlogische Zeichen genannt),

3. Variablen v_{0}, v_{1}, ...,

4. Klammern “(”, “)” und andere technische Zeichen. Wir nutzen oft x, y, x_{0}, y_{0}, z, ..., um anzudeuten, dass an der betreffenden Stelle eine der Variablen v_{0}, v_{1}, ... steht. D.h. f(x, y) = z steht für f(v_{0}, v_{1}) = v_{2}, aber auch für f(v_{13}, v_{10}) = v_{20}, etc.. Definition (Term) Eiin Wort über dem angegebenen Alphabet ist ein Term, wenn es durch endlich viele Anwendungen der folgenden Regeln erhalten wird:

1. Jede Variable ist ein Term.

2. Jedes Konstantensymbol ist ein Term.

3. Sind t_{0}, ..., t_{n−1} Terme, und f ein n-stelliges Funktionssymbol, so ist f(t_{0}, ..., t_{n−1}) ein Term.

Beispiel Sei σ(L) = {c_{0}, c_{1}, R, f_{1}, f_{2}, f_{3}). Dann ist f_{1}(f_{1}(f_{2}(c_{0}, v_{2}), v_{0}), f_{3}(c_{1}, v_{7})) ein Term. Mit c_{0} ≡ 0, c_{1} ≡ 1, R ≡<, f_{1} ≡ +, f_{2} ≡ − und f_{3} ≡ · erhalten wir die Darstellung ((0 − v_{2}) + v_{0}) + (1 · v_{7}).

Lemma 3.1. (Eindeutigkeit des Termaufbaus (5.1)) Wenn t ein L-Term ist, so tritt genau einer der drei folgenden Fälle ein:

1. t ist eine Variable.

2. t ist ein Konstantensymbol.

3. Es existieren eindeutig bestimmte Terme t_{0}, ..., t_{n−1} und ein eindeutig bestimmtes n-stelliges Funktionssymbol mit t ≡ f(t_{0}, ..., t_{n−1}).

Beweis: Ansatz für den Fall, dass die Klammern und Kommas weggelassen werden: Wir definieren das Geweicht G eines Wortes über {v_{0}, v_{1}, ...., c_{0}, c_{1}, ..., f_{0}, f_{1}, ...} = X durch: G(v_{i}) = −1, G(c_{i}) = −1, G(f_{i}) = n − 1 für ein n-stelliges Funktionssymbol f_{i} und G(a_{0}...a_{m−1}) = ∑_{i=0}^{m−1} G(a_{i}) für ein Wort der Länge m. Behauptung: Ein Wort w über X ist genau dann ein Term, wenn G(W) = −1 und G(u) ≥ 0 für jedes echte Anfangsstück von w gilt. Damit folgt der Beweis dieses Lemmas leicht.

Bemerkung Durch die Eindeutigkeit des Termaufbaus sind wir jetzt wieder in der Lage, Definitionen induktiv über den Termaufbau vorzunehmen.

Definition (Substitution / Simultane Ersetzung) Seien x_{0}, ..., x_{n−1} Variablen und u_{0}, ..., u_{n−1} Terme. Der Term t^{u_{0}/x_{0},...,u_{n−1}/x_{n−1}} wird dann wie folgt induktiv über den Termaufbau definiert.

1. Wenn t ≡ v_{i}, so setzen wir t^{u_{0}/x_{0},...,u_{n−1}/x_{n−1}} ≡ \{ \begin{matrix}u_{i} & , falls v_{i} = x_{j} \\ v_{i} & , falls v_{i} ∉ \{x_{0}, ..., x_{n−1}\} \end{matrix}

2. Wenn t ≡ f(t_{0}, ..., t_{r−1}), so setzen wir

t^{u_{0}/x_{0},...,u_{n−1}/x_{n−1}} ≡ f(t_{0}^{u_{0}/x_{0},...,u_{n−1}/x_{n−1}}, ..., t_{r−1}^{u_{0}/x_{0},...,u_{n−1}/x_{n−1}}).

Wir schreiben auch t(x_{0}, ..., x_{n−1}), um anzudeuten, dass alle Variablen, die in t vorkommen in x_{0}, ..., x_{n−1} enthalten sind. Ist die Substitution für alle x_{i} festgelegt, so schreiben wir auch t(u_{0}, ..., u_{n−1}).

Definition (Atomformeln) Atomformeln einer Sprache L sind alle Worte über dem Alphabet aus dem am Anfang dieses Abschnitts angegebenen Alphabet, die man mit Hilfe der folgenden Regeln erhält:

1. Wenn t_{1}, t_{2} Terme sind, dann ist t_{1} = t_{2} eine Atomformel.

2. Wenn R ein n-stelliges Relationssymbol und t_{0}, ..., t_{n−1} Terme sind, dann ist R(t_{0}, ..., t_{n−1}) eine Atomformel.

Definition (Formeln) Die Formeln der Sprache L erhält man durch endlich viele Anwendungen der folgenden Regeln:

1. Atomformeln sind Formeln.

2. Wenn φ und ψ Formeln sind, so sind auch ¬φ und (φαψ) Formeln, wobei α ∈ {∨, ∧, →, ↔}.

3. Wenn φ eine Formel und x eine Variable ist, so sind auch ∃xφ und ∀xφ Formeln.

Die Sprache L ist die Menge der L-Formeln. Alle Elemente von L sind endliche Zeichenreihen.

Beispiel Die Zeichenfolge ∀y∀x∀x_{0}∃z(R(x, x_{0}, z) → R(f(x), f(x_{0}), y)) ist eine Formel.

Lemma 3.2. (Eindeutigkeit des Formelaufbaus (5.2)) Wenn φ eine formel ist, so tritt genau einer der 6 folgenden Fälle ein:

1. Es gibt eudeutig bestimmte Terme t_{1}, t_{2}, sodass φ ≡ t_{1} = t_{2}.

2. Es existieren eindeutige bestimmte Terme t_{0}, ..., t_{n−1} und eine eindeutig bestimmte n-stellige Relation R mit φ ≡ R(t_{0}, ..., t_{n−1}).

3. Es existiert eine eindeutig bestimmte Formel ψ mit φ ≡ ¬ψ.

4. Es existieren eindeutig bestimmte Formeln ψ, chi und α ∈ {∨, ∧, →, ↔}, so dass φ ≡ (ψαχ).

5. Es existiert eine eindeutig bestimmte Formel ψ und eine Variable x, sodass φ ≡ ∃xφ.

6. Es existiert eine eindeutig bestimmte Formel ψ und eine Variable x, sodass φ ≡ ∀xφ.

Beweis: Weil wir chronisch faul sind, lassen wir den Beweis an dieser Stelle weg. Der Leser mag sich damit gerne selbst die Zeit vertreiben. ;-)

Bemerkung (Vereinfachungen)

1. Wir lassen Klammern nach den Regeln des Aussagenkalküls weg, falls dies nicht zu Zweideutigkeiten führt, oder fügen zusätzliche Klammern hinzu, um bessere Lesbarkeit zu erreichen.

2. Wir nutzen ⋀_{i<n} φ_{i} und ⋁_{i<n} φ_{i}.

3. Wir schreiben für ∃x_{0}∃x_{1}...∃x_{n−1}φ auch ∃\overline{x}φ, mit \overline{x} = (x_{0}, ..., x_{n−1}) oder ∃x_{0}...x_{n−1}φ.

4. Wir erweitern den Kalkül zeitweise um konstante Atomformeln ⊤ und ⊥.

5. Wir nutzen t_{1} ≠ t_{2} statt ¬(t_{1} = t_{2}).

Bemerkung (Induktive Definitionen, Menge der Teilformeln) Der eindeutige Formelaufbau erlaubt wieder Definitionen über den Formelaufbau. Beispiel: Menge der Teilformeln tf(φ)

1. Wenn φ eine Atomare Formel ist, so gilt tf(φ) = {φ}.

2. Wenn φ ≡ ¬ψ gilt, so setzen wir tf(φ) = {φ} ∪ tf(ψ).

3. Wenn φ ≡ (ψαχ) gilt, so setzen wir tf(φ) = {φ} ∪ tf(ψ) ∪ tf(χ).

4. Wenn φ ≡ ∃xψ oder φ ≡ ∀ψ gilt, so setzen wir tf(φ) = {φ} ∪ tf(ψ).

Definition (Wirkungsbereich, gebundene und freie Vorkommen) Wenn ∃xψ bzw. ∀xψ eine Teilformel von φ ist, so ist ψ der Wirkungsbereich des Quantors ∃x bzw. ∀x (in φ). Jedes Vorkommen von x in φ im Wirkungsbereich eines Quantors ∃x oder ∀x ist ein gebundenens Vorkommen. Jedes Vorkommen von x in φ, das kein gebundenes Vorkommen ist, heißt freies Vorkommen.

Bemerkung x kann in einer Formel sowohl frei, als auch gebunden vorkommen: Sei σ(L) = {c, f, R} und seien f und R zweistellig. Dann kommt x in φ ≡ ∀y(R(x, y) → ∃xf(x, c) = y) sowohl gebunden als auch frei vor. y kommt nur gebunden vor.

Definition (konstante Terme, Aussagen) Ein Term ohne freie Variablen ist ein konstanter Term. Eine Formel ohne freie Variablen ist eine Aussage.

Vorbemerkung Wenn wir Variablen in Formeln substituieren, müssen wir gebundene Variablen beachten. Sei z.B. ∀x_{0}R(x_{0}, x_{1}) gegeben. Ersetzen wir x_{1} durch x_{0}, so erhalten wir eine Variablenkollision, d.h. der Sinn unserer Formel wird total verändert: ∀x_{0}R(x_{0}, x_{0}). Um die Substitution x_{0}/x_{1} durchführen zu können, ersetzen wir erst x_{0} durch eine vollig neue Variable y. Der Sinn der Fomel wird dabei nicht verändert, wie wir später noch sehen werden: ∀x_{0}R(x_{0}, x_{1}) ∼ ∀yR(y, x_{1}). Nun können wir problemlos x_{1} durch x_{0} ersetzen.

Definition (Substitution φ^{t_{0}/x_{0},...,t_{n−1}/x_{n−1}}) Zuerst werden in φ gebundene Variablen umbenannt, aber nur, wenn eine Variable x aus den t_{i} durch die Substitution in den Wirkungsbereich eines Quantors Qx in φ gelangen würde (Variablenkollision). Zur Umbenennung werden dann völlig neue Variablen genommen. Dann werden die freien Vorkommen der x_{i} durch t_{i} ersetzt.

Bemerkung Die Umbenennungen fallen unter anderem in den folgenden Fällen weg:

1. φ^{c/x}, c ist ein Konstantensymbol

2. φ^{t(c)/x}, t(c) ist ein konstanter Term

3. φ^{y/x}, y kommt in φ nicht vor.

Das Resultat ist nicht eindeutig, da wir die “völlig neuen” Variablen frei wählen können. Wir werden jedoch sehen, dass alle möglichen Ergebnisse logisch äquivalent sind.

Vorlesung am 14.11.2007

Bemerkung Wir schreiben auch φ(x_{0}, ..., x_{n−1}), wenn sich alle freien Variablen von φ unter x_{0}, ..., x_{n−1} befinden (bzw. φ(\overline{x}) mit \overline{x} = (x_{0}, ..., x_{n−1})).

3.6 Semantik der Prädikatenlogik

Wir betrachten eine L-Struktur M, \overline{a} = (a_{0}, ..., a_{n−1}) sei ein Tupel von Elementen aus M. φ(\overline{a}) bzw. t(\overline{a}) entstehen, indem wir jedes freie Vorkommen von x_{i} jeweils durch a_{i} ersetzen. Für φ(\overline{x}) bzw. t(\overline{x}) interessieren uns also (nur) die freien Vorkommen der x_{i}. Wir definieren induktiv über den Formelaufbau M ⊧ φ(\overline{a}) (“in M gilt φ(\overline{a})”), wobei \overline{a} ein passendes Tupel für \overline{x} in φ(\overline{x}) ist. In jedem Schritt der Definition überprüfen wir folgendes Lemma, d.h. wir beweisen es parallel zur Definition.

Lemma 3.3. (Koinzidenzlemma für die Erfüllbarkeit (6.1)) M ⊧ φ(\overline{a}) hängt nur von der Belegung der freien Variablen unter den Variablen x_{i} von φ(\overline{x}) durch a_{i} un den Konstanten, Funktionen und Relationen in M ab, deren Symbole in φ(\overline{x}) vorkommen. Analoges gilt für die induktive Definition des Wertes t(\overline{a}) eines Terms.

Definition (Wert eines Terms) Der Wert t^{M}(\overline{a}) des Termes t(\overline{x}) unter der Belegung \overline{a} in der L-Struktur M wird induktiv über den Termaufbau definiert:

1. t ≡ c ⇒ t^{M} = c^{M}

2. t ≡ x_{i} für eine Variable x_{i} ⇒ t^{M}(\overline{a}) = a_{i}.

3. t ≡ f(t_{0}(\overline{x}), ..., t_{n−1}(\overline{x})), wobei f ein n-stelliges Funktionssymbol und t_{i}(\overline{x}) Terme sind ⇒ t^{M}(\overline{a}) = f^{M}(t_{0}^{M}(\overline{a}), ..., t_{n−1}^{M}(\overline{a}))

Weil wir nur die Symbole aus t für die Definition verwenden, ist die Behauptung des obigen Lemmas erfüllt.

Definition Sei M eine L-Struktur. Induktiv über den Formelaufbau von φ(\overline{x}) definieren wir für passende Tupel \overline{a} ∈ dom(M)^{n} die Beziehung M ⊧ φ(\overline{a}). Im Folgenden sind alle Zeichen ihre Standardinterpretation, insbesondere verwenden wir ψ, ψ_{1}, ψ_{2}, ..., χ als Formeln und t, t_{0}, t_{1}, ... als Terme.

1. Sei φ(\overline{x}) eine Atomformel.

(a) φ(\overline{x}) ≡ t_{1}(\overline{x}) = t_{2}(\overline{x}) Hier setzen wir M ⊧ t_{1}(\overline{a}) = t_{2}(\overline{a}), wenn t_{1}^{M}(\overline{a}) = t_{2}^{M}(\overline{a}).

(b) φ(\overline{x}) ≡ R(t_{0}(\overline{x}), ..., t_{n−1}(\overline{x})) Hier setzen wir M ⊧ R(t_{0}(\overline{a}), ..., t_{n−1}(\overline{a})), wenn R^{M}(t_{0}^{M}(\overline{a}), ..., t_{n−1}^{M}(\overline{a})) gilt.

(c) Wenn φ(\overline{x}) ≡ ⊤ bzw. φ(\overline{x}) ≡ ⊥, dann setzen wir M ⊧ ⊤ und M |̸= ⊥.

Auch hier gilt das Lemma.

2. Aussagenlogische Verknüpfungen

(a) φ(\overline{x}) ≡ ¬ψ(\overline{x})

Hier setzen wir genau dann M ⊧ ¬ψ(\overline{a}), wenn M |̸= ψ(\overline{a}).

(b) φ(\overline{x}) ≡ ψ_{1}(\overline{x}) ∧ ψ_{2}(\overline{x})

Hier setzen wir genau dann M ⊧ ψ_{1}(\overline{a}) ∧ ψ_{2}(\overline{a}), wenn M ⊧ ψ_{1}(\overline{a}) und M ⊧ ψ_{2}(\overline{a}).

(c) φ(\overline{x}) ≡ ψ_{1}(\overline{x}) ∨ ψ_{2}(\overline{x})

Hier setzen wir genau dann M ⊧ ψ_{1}(\overline{a}) ∨ ψ_{2}(\overline{a}), wenn M ⊧ ψ_{1}(\overline{a}) oder M ⊧ ψ_{2}(\overline{a}).

(d) φ(\overline{x}) ≡ ψ_{1}(\overline{x}) → ψ_{2}(\overline{x})

Hier setzen wir genau dann M ⊧ ψ_{1}(\overline{a}) → ψ_{2}(\overline{a}), wenn M |̸= ψ_{1}(\overline{a}) oder M ⊧ ψ_{2}(\overline{a}).

(e) φ(\overline{x}) ≡ ψ_{1}(\overline{x}) ↔ ψ_{2}(\overline{x})

Hier setzen wir genau dann M ⊧ ψ_{1}(\overline{a}) ↔ ψ_{2}(\overline{a}), wenn M ⊧ ψ_{1}(\overline{a}) ⇔ M ⊧ ψ_{2}(\overline{a}).

Ach hier mag der geneigte Leser die Gültigkeit des Lemmas 6.1 überprüfen.

3. Quantoren In χ(x, \overline{x}) heben wir die Variable x hervor, sie komme nicht in \overline{x} vor.

(a) φ(\overline{x}) ≡ ∃xχ(x, \overline{x}) Dann setzen wir M ⊧ ∃xχ(x, \overline{a}), wenn es ein Element a ∈ dom(M) mit M ⊧ χ(a, \overline{a}) gibt.

(b) φ(\overline{x}) ≡ ∀xχ(x, \overline{x})

Dann setzen wir M ⊧ ∀xχ(x, \overline{a}), wenn für alle Elemente a ∈ dom(M) auch M ⊧ χ(a, \overline{a}) gilt.

Wieder einmal bleibt die Überprüfung des Lemmas 6.1 dem Leser überlassen.

Bemerkung Wir haben diese Definition gewählt, da sie der Praxis entspricht. Unschön ist, dass wir erlauben, dass in Formeln für Variablen Elemente aus M eingesetzt werden. Eine andere Möglichkeit ist: Für jedes Element a ∈ dom(M) wird ein neues Konstantensymbol c_{a} in die Signatur aufgenommen. Dann werden nur Aussagen der neuen Sprache betrachtet - wir haben eine Konstantenerweiterung der Sprachre.

Definition (Konstantenerweiterung) Wenn L unsere Sprache ist, so sei L_{C} oder auch L(C) die Sprache, die wir erhalten, wenn wir die Menge C von neuen Konstantensymbolen zur (Signatur der) Sprache hinzufügen. Sei M eine L-Struktur und A ⊆ dom(M). Dann sei L(A) die Konstantenerweiterung von L um die Menge {c_{a}|a ∈ A} = C von neuen Konstantensymbolen. M(A) sei die L(A)-Struktur, die aus M durch Belegung der c_{a} durch a entsteht.

Definition (Wert eines L_{M}-Terms) Sei M eine L-Struktur, M^{∗} = M(M) und t ein konstanter Term in L(M). Der Wert T^{M^{∗}} von t in M^{∗} ist induktiv wie folgt definiert:

1. t ≡ c ⇒ t^{M^{∗}} ≡ c^{M} ≡ c^{M^{∗}}

2. t ≡ c_{a}, a ∈ M ⇒ t^{M^{∗}} ≡ a ≡ c_{a}^{M^{∗}}

3. t ≡ f(t_{0}(\overline{x}), ..., t_{n−1}(\overline{x})), wobei f ein n-stelliges Funktionssymbol und t_{i}(\overline{x}) Terme sind

⇒ t^{M^{∗}}(\overline{a}) ≡ f^{M^{∗}}(t_{0}^{M^{∗}}(\overline{a}), ..., t_{n−1}^{M^{∗}}(\overline{a}))

Definition (Gültigkeit von L_{M}-Aussagen) Sei M eine L-Struktur und φ eine L(M)-Aussage. Wir definieren M^{∗} ⊧ φ induktiv über den Formelaufbau: Im Rahmen der folgenden Definition seien t_{0}, ..., t_{n−1} konstante L_{M}-Terme, R n-stellige Relationssymbole, ψ, ψ_{1}, ψ_{2} L_{M}-Aussagen und χ(x) eine L_{M}-Formel mit höchstens der freien Variable x.

1. Sei φ eine Atomformel.

(a) φ ≡ t_{1} = t_{2} Dann setzen wir M^{∗} ⊧ t_{1} = t_{2}, wenn t_{1}^{M^{∗}} = t_{2}^{M^{∗}}.

(b) φ ≡ R(t_{0}, ..., t_{n−1}) Hier setzen wir M^{∗} ⊧ R(t_{0}, ..., t_{n−1}), wenn R^{M^{∗}}(t_{0}^{M^{∗}}, ..., t_{n−1}^{M^{∗}}) gilt.

(c) φ ≡ ⊤ bzw. φ ≡ ⊥, dann setzen wir M^{∗} ⊧ ⊤ und M^{∗} |̸= ⊥.

2. Aussagenlogische Verknüpfungen

(a) φ ≡ ¬ψ Hier setzen wir genau dann M^{∗} ⊧ ¬ψ), wenn M^{∗} |̸= ψ.

(b) φ ≡ ψ_{1} ∧ ψ_{2})

Hier setzen wir genau dann M^{∗} ⊧ ψ_{1} ∧ ψ_{2}, wenn M^{∗} ⊧ ψ_{1} und M^{∗} ⊧ ψ_{2}.

(c) φ ≡ ψ_{1} ∨ ψ_{2} Hier setzen wir genau dann M^{∗} ⊧ ψ_{1} ∨ ψ_{2}, wenn M^{∗} ⊧ ψ_{1} oder M^{∗} ⊧ ψ_{2}.

(d) φ ≡ ψ_{1} → ψ_{2} Hier setzen wir genau dann M^{∗} ⊧ ψ_{1} → ψ_{2}, wenn M^{∗} |̸= ψ_{1} oder M^{∗} ⊧ ψ_{2}.

(e) φ ≡ ψ_{1} ↔ ψ_{2} Hier setzen wir genau dann M^{∗} ⊧ ψ_{1} ↔ ψ_{2}, wenn M^{∗} ⊧ ψ_{1} ⇔ M^{∗} ⊧ ψ_{2}.

3. Quantoren

(a) φ ≡ ∃xχ(x) Dann setzen wir M^{∗} ⊧ ∃xχ(x), wenn es ein Element a ∈ dom(M) gibt, mit M^{∗} ⊧ χ(a).

(b) φ ≡ ∀xχ(x) Dann setzen wir M^{∗} ⊧ ∀xχ(x), wenn für alle Elemente a ∈ dom(M) auch M^{∗} ⊧ χ(a) gilt.

Bemerkung

1. Literatur: A.Tarski: Der Wahheitsbegriff in den formalisierten Sprachen. Studia Philosoph. 1, Warschau 1935, 261-405

2. Sei M eine L-Struktur, \overline{a} = (a_{0}, ..., a_{n−1}) ein n-Tupel aus M, t(x_{0}, ..., x_{n−1}) ein L-Term und φ(x_{0}, ..., x_{n−1}) eine L-Formel.

Der Wert t^{M}(\overline{a}) des Terms t(\overline{x}) in M an der Stelle \overline{a} ist t^{M^{∗}}(c_{a_{0}}, ..., c_{a_{n−1}}).

Wir schreiben später auch t(\overline{a}) statt t^{M}(\overline{a}).

3. M ⊧ φ(\overline{a}) ⇔ M^{∗} ⊧ φ(c_{a_{0}}, ..., c_{a_{n−1}})

Definition

1. φ(\overline{x}) ist erfüllbar in M, falls es ein (passendes) Tupel \overline{a} in M gibt, so dass M ⊧ φ(\overline{a}).

2. φ(\overline{x}) ist gültig (wahr) in M, fass jedes passende Tupel φ in M erfüllt, d.h. φ(\overline{x}) ist gültig in M gdw. M ⊧ ∀\overline{x}φ(\overline{x}).

3. φ ist erfüllbar, wenn eine L-Struktur M existiert, in der φ(\overline{x}) erfüllbar ist.

4. φ ist kontradiktorisch, falls φ nicht erfüllbar ist.

5. φ ist allgemeingültig, wenn φ in jeder L-Struktur gültig ist, d.h. genau dann, wenn ∀\overline{x}φ(\overline{x}) allgemeingültig ist.

Schreibweise: ⊧ ∀\overline{x}φ(\overline{x}) bzw. ⊧ φ(\overline{x}).

Vorlesung am 21.11.2007

Definition (Logische Äquivalenz) Seien φ(\overline{x}), ψ(\overline{x}) L-Formeln. φ(\overline{x}) und ψ(\overline{x}) sind logisch äquivalent (wir schreiben φ ∼ ψ), wenn für alle L-Strukturen M und alle passenden Tupel \overline{a} ∈ M auch M ⊧ φ(\overline{a}) ⇔ M ⊧ ψ(\overline{a}) gilt, d.h. wenn ∀\overline{x}(φ(\overline{x}) ↔ ψ(\overline{x})) eine allgemeingültige Aussage ist.

Definition L^{+} entstehe aus L durch Hinzufügen eines n-stelligen Relationssymbols R. Sei ψ(x_{1}, …, x_{n}) ∈ L und φ(\overline{y}) aus L^{+}. Dann sei φ_{ψ/R}(\overline{y}) die L-Formel, die aus φ entsteht, wenn man R(x_{1}, …, x_{n}) durch ψ(x_{1}, …, x_{n}) ersetzt.

Lemma 3.4. (6.2)

1. ∼ ist eine Äquivalenzrelation.

2. Wenn φ ∼ ψ gilt, so folgt auch ¬φ ∼ ¬ψ.

3. Wenn φ ∼ φ′ und ψ ∼ ψ′ gilt, so gilt auch (φαψ) ∼ (φ′αψ′) für alle α ∈ {∨, ∧, →, ↔}.

4. Wenn φ(x, \overline{y}) ∼ φ′(x, \overline{y}) gilt, so gilt auch Qxφ(x, \overline{y}) ∼ Qxφ′(x, \overline{y}) für alle Q ∈ \{∃, ∀\}.

5. Wenn R(\overline{x}) ein neues Relationssymbol ist und ψ(\overline{x}) ∼ ψ′(\overline{x}) gilt, so folgt auch φ_{ψ/R} ∼ φ_{ψ′/R}.

Beweis:

1. bis 4. folgen direkt aus der Definition der Gültigkeitsbeziehung ⊧. 5. wird induktiv über den Formelaufbau und mit Hilfe von 1. bis 4. bewiesen.

Lemma 3.5. (6.3) Wenn φ′(\overline{x}) aus φ(\overline{x}) durch gebundene Umbenennungen entsteht, so gilt φ∼φ′.

Beweis: Es reicht aus, dies für eine einzige gebundene Umbenennung zu zeigen, da ∼ nach Lemma 6.2 eine Äquivalenzrelation ist. Sei Qxψ(x, \overline{x}) eine Teilformel von φ. Sei y eine Variable, die nicht in φ vorkommt. Dann gilt Qxψ(x, \overline{x}) ∼ Qyψ(y, \overline{x}). Sei χ(\overline{x}) die Formel, die aus φ(\overline{x}) durch Ersetzen der Teilformel Qxψ(x, \overline{x}) durch R(\overline{x}) entsteht. (R sei dabei ein neues Relationssymbol mit der Stelligkeit von \overline{x}.)

Aus Lemma 6.2.5 folgt φ ≡ χ_{Qxψ(x,\overline{x})/R} ∼^{6.2} χ_{Qyψ(y,\overline{x})/R} ≡ φ′.

Lemma 3.6. (6.4)

1. Sei φ(\overline{y}) eine L-Formel, \overline{y} = (y_{0}, …, y_{m−1}), t_{i}(\overline{x}) L-Terme (i < m), \overline{x} = (x_{0}, …, x_{n−1}), M eine L-Struktur und \overline{a} = (a_{0}, …, a_{n−1}) ∈ M. Dann gilt M ⊧ φ(t_{0}(\overline{a}), …, t_{m−1}(\overline{a})) ⇔ M ⊧ φ(t_{0}^{M}(\overline{a}), …, t_{m−1}^{M}(\overline{a})).

2. Wenn φ(\overline{y}) ∼ φ′(\overline{y}) gilt und t_{i}(\overline{x}) Terme wie oben sind, dann gilt:

φ(t_{0}(\overline{x}), …, t_{m−1}(\overline{x})) ∼ φ′(t_{0}(\overline{x}), …, t_{m−1}(\overline{x})).

Beweis:

1. Mit Lemma 6.3 können wir eventuell nötige gebundene Umbenennungen vornehmen. Also haben wir o.B.d.A. keine Variablenkollisionen. Wir können also die freien Vorkommen der y_{i} direkt durch die t_{i} ersetzen. Wir zeigen nun für beliebige Terme u(\overline{x}) u_{t_{0}/y_{0},...,t_{m−1}/y_{m−1}}^{M}(\overline{a}) = u^{M}(t_{0}^{M}(\overline{a}), …, t_{m−1}^{M}(\overline{a})). induktiv über den Formelaufbau:

(a) u ≡ y_{i} u_{t_{0}/y_{0},...,t_{m−1}/y_{m−1}}^{M}(\overline{a}) = t_{i}^{M}(\overline{a}) = u^{M}(t_{0}^{M}(\overline{a}), …, t_{m−1}^{M}(\overline{a}))

(b) u ≡ c Bei Konstantensymbolen werden keine Substitutionen vorgenommen.

(c) u ≡ f(s_{0}(\overline{y}), …, s_{r−1}(\overline{y}))

u_{t_{0}/y_{0},...,t_{m−1}/y_{m−1}}^{M}(\overline{a}) = f^{M}(s_{0}^{M_{t_{0}/y_{0},...,t_{m−1}/y_{m−1}}} (\overline{a}), …, s_{r−1}^{M_{t_{0}/y_{0},...,t_{m−1}/y_{m−1}}} (\overline{a}))

= f^{M}(s_{0}^{M}(t_{0}^{M}(\overline{a}), …, t_{m−1}^{M}(\overline{a})), …, s_{r−1}^{M}(t_{0}^{M}(\overline{a}), …, t_{m−1}^{M}(\overline{a})))

= u^{M}(t_{0}^{M}(\overline{a}), …, t_{m−1}^{M}(\overline{a}))

Die Behauptung folgt induktiv nach der Definition von ⊧.

2. Dieser Punkt folgt aus 1..

Definition (Boolesche Kombination) Sei Σ eine Menge von L-Formeln. Eine Boolsche Kombination über Σ ist eine L-Formel, die man wie die Formeln des Aussagenkalküls erhält, indem man die Formeln aus Σ statt der Aussagenvariablen einsetzt. Wenn μ eine aussagenlogische Formel über den Aussagenvariablen p_{0}, …, t_{n−1} ist, so definieren wir als φ ≡ μ_{φ_{0}/p_{0},...,φ_{n−1}/p_{n−1}} die L-Formel, die man erhält, indem man simultan die p_{i} durch φ_{i} ∈ L ersetzt. Ist μ in konjunktiver (bzw. disjunktiver) Normalform und die φ_{i} Atomformeln, so sagen wir, dass auch φ in konjunktiver (bzw. disjunktiver) Normalform ist.

Definition (Tautologie) Ist μ eine Tautologie, so nennen wir μ_{φ_{0}/p_{0},...,φ_{n−1}/p_{n−1}} prädikatenlogische Tautologie.

Lemma 3.7. (6.5)

1. Sei μ eine aussagenlogische Formel über p_{0}, …, p_{n−1} und φ_{0}, …, φ_{n−1} Formeln. Wenn μ eine Tautologie ist, so ist μ_{φ_{0}/p_{0},...,φ_{n−1}/p_{n−1}} eine allgemeingültige Formel.

2. Aussagenlogische Äquivalenz impliziert prädikatenlogische Äquivalenz.

Beweis: Sei M eine L-Struktur, φ_{i} ≡ φ_{i}(x_{0}, …, x_{n−1}) und \overline{a} = (a_{0}, …, a_{n−1}) ∈ M. Wir definieren die Belegung B_{μ\overline{a}} der p_{i} durch B_{μ\overline{a}}(p_{i}) = B(μ, \overline{a})(p_{i}) = 1 ⇔ M ⊧ φ_{i}(\overline{a}). Wir beweisen dann induktiv über den aussagenlogischen Formelaufbau von μ: B_{μ,\overline{a}}^{∗}(μ) = 1 ⇔ M ⊧ μ_{φ_{0}/p_{0},...,φ_{n−1}/p_{n−1}(\overline{a})}.

Lemma 3.8. (6.6) Seien φ und ψ beliebige L-Formeln. Dann gilt:

1. ¬∀xφ ∼ ∃x¬φ ∀xφ ∼ ¬∃x¬φ ∃xφ ∼ ¬∀x¬φ

2. ∀x(φ ∧ ψ) ∼ ∀xφ ∧ ∀xψ

3. ∃x(φ ∨ ψ) ∼ ∃xφ ∨ ∃xψ

4. ∃x(φ → ψ) ∼ ∀xφ → ∃xψ

5. ∀x∀yφ ∼ ∀y∀xφ

6. ∃x∃yφ ∼ ∃y∃xφ Die folgenden Formeln sind allgemeingültig:

7. ∃x(φ ∧ ψ) → ∃xφ ∧ ∃xψ

8. ∀xφ ∨ ∀xψ → ∀x(φ ∨ ψ)

9. ∃x∀yφ → ∀y∃xφ Wenn x nicht frei in ψ vorkommt gelten:

10. ∀xψ ∼ ∃xψ ∼ ψ

11. ∀x(φ ∧ ψ) ∼ ∀xφ ∧ ψ

12. ∃x(φ ∨ ψ) ∼ ∃xφ ∨ ψ

13. ∀x(φ ∨ ψ) ∼ ∀xφ ∨ ψ

14. ∃x(φ ∧ ψ) ∼ ∃xφ ∧ ψ

15. ∃x(ψ → φ) ∼ ψ → ∃xφ

16. ∀x(ψ → φ ∼ ψ → ∀xφ

17. ∃x(φ → ψ) ∼ ∀xφ → ψ

18. ∀x(φ → ψ) ∼ ∃xφ → ψ

Beweis:

1. Sei M ⊧ ¬∀xφ(\overline{a}, x), d.h. es existiert ein b ∈ M mit M ⊧ ¬φ(\overline{a}, b), also M ⊧ ∃x¬φ(\overline{a}, x). Ebenso andersherum.

2. Leicht, ähnlich.

3. \begin{aligned}∃x(φ ∨ ψ) & ∼^{AL} ∃x¬(¬φ ∧ ¬ψ) ∼^{1.} ¬∀x(¬φ ∧ ¬ψ) \\ & ∼^{2.} ¬(∀x¬φ ∧ ∀x¬ψ) ∼^{AL} ¬∀x¬φ ∨ ¬∀x¬ψ ∼^{1.} ∃xφ ∨ ∃xψ \end{aligned}

4. ∃x(φ → ψ) ∼^{AL} ∃x(¬φ ∨ ψ) ∼^{3.} ∃x¬φ ∨ ∃xψ ∼^{1.} ¬∀xφ ∨ ∃xψ ∼^{AL} ∀xφ → ∃xψ

5. klar.

6. klar.

7. einfache Übungsaufgabe.

8. einfach, Übung.

9. klar, aber Umkehrung gilt (wie auch in 7. und 8.) nicht.

(Jeder Hund hat ein Halsband. ⇏ Es gibt ein Halsband für alle Hunde.)

10. M ⊧ ∀x(ψ(\overline{a})) ⇔ Für jedes b ∈ M gilt M ⊧ ψ(\overline{a})

⇔ Es existiert ein b ∈ M mit M ⊧ ψ(\overline{a})

(Lemma 6.1, da x nicht frei in ψ vorkommt.) ⇔ M ⊧ ψ(\overline{a})

11. aus 10. und 2.

12. aus 10. und 3.

13. ähnlich 10.

14. aus 13. und 1.

15. Folgerung aus 12.:

∃x(ψ → φ) ∼^{AL} ∃x(¬ψ ∨ φ) ∼^{10+12} ¬ψ ∨ ∃xφ ∼^{AL} ψ → ∃xφ

16. analog zu 15.

17. ∃x(φ → ψ) ∼^{AL} ∃(¬φ ∨ ψ) ∼^{10+12} ∃x¬φ ∨ ψ ∼^{1} ¬∀xφ ∨ ψ ∼^{AL} ∀xφ → ψ

18. analog mit 13., 1., 10..

Vorlesung am 26.11.2007

Definition (Quantorenfreiheit, Normalformen) Sei φ(\overline{x}) eine Formel.

1. φ(\overline{x}) heißt quantorenfrei, falls φ keine Quantoren enthält.

2. φ(\overline{x}) ist in pränexer (Normal-)Form, falls φ(\overline{x}) ≡ Q_{0}y_{0} … Q_{n−1}y_{n−1}ψ(\overline{x}, \overline{y}), wobei ψ quantorenfrei ist und Q_{i} ∈ \{∃, ∀\}, i = 0, …, n − 1 gilt. Dabei wird ψ(\overline{x}, \overline{y}) auch Matrix von φ(\overline{x}) genannt.

3. φ(\overline{x}) ist in konjunktiver pränexer Normalform, falls φ in pränexer Normalform und ψ konjunktiver Normalform ist.

4. φ(\overline{x}) ist in disjunktiver pränexer Normalform, falls φ in pränexer Normalform und ψ disjunktiver Normalform ist.

Lemma 3.9. (6.7) Jede Formel χ(\overline{x}) ∈ L ist zu einer Formel in konjunktiver pränexer Normalform und zu einer Formel in disjunktiver pränexer Normalform äquivalent.

Beweis: Sei χ(\overline{x}) ∈ L beliebig. Nach Lemma 6.5 und der Aussagenlogik existiert eine Formel φ(\overline{x}) ∼ χ, wobei φ nur aus ¬, ∧ und Quantoren aufgebaut ist. Wir zeigen zunächst induktiv über die Länge von φ: Es existiert ein φ′ ∼ φ in pränexer Normalform mit l(φ′) = l(φ), sodass φ nur durch ¬, ∧ und Quantoren aufgebaut ist.

1. φ ist eine Atomformel

Hier setzen wir φ′ ≡ φ, weil φ quantorenfrei ist.

2. φ ≡ ¬ψ

Nach Induktionsvoraussetzung existiert ψ′ ∼ ψ in pränexer Form mit l(ψ′) = l(ψ), sodass ψ′ nur durch ¬, ∧ und Quantoren aufgebaut ist.

Wir haben also ψ′(\overline{x}) ≡ Q_{0}y_{0} … Q_{n−1}y_{n−1}ξ(\overline{x}, \overline{y}) (Q_{i} ∈ \{∃, ∀\}, i = 0, …, n − 1 und ξ quantorenfrei). Wir definieren Q_{i}^{∗} ≡ ∃ im Fall von Q_{i} ≡ ∀ und Q_{i}^{∗} ≡ ∀ im Fall von Q_{i} ≡ ∃. Nach Lemma 6.6.1 (n-mal angewandt) folgt:

\begin{aligned}¬ψ′ & ≡ ¬Q_{0}y_{0} … Q_{n−1}y_{n−1}ξ(\overline{x}, \overline{y}) \\ & ∼ Q_{0}^{∗}y_{0} … Q_{n−1}^{∗}y_{n−1}¬ξ(\overline{x}, \overline{y}) ≡ φ′(\overline{x}) \end{aligned}

Also haben wir φ′ ∼ φ und l(φ′) = l(φ), mit φ′ in pränexer Form und nur durch ¬, ∧ und Quantoren aufgebaut.

3. φ ≡ (ξ ∧ π)

Nach Induktionsvoraussetzung existieren ξ′ ∼ ξ und π′ ∼ π, mit l(ξ′) = l(ξ) und l(π′) = l(π), ξ′, π′ in pränexer Form und nur mit ¬, ∧, ∃ und ∀ aufgebaut.

Nach Lemma 6.3 können wir gebunden Umbenennen, d.h. ξ′ ∼\overline{Q}^{0}\overline{y}ψ(\overline{x}, \overline{y}) und π′∼\overline{Q}^{1}\overline{z}ϑ(\overline{x}, \overline{z}), wobei \overline{Q}^{0}\overline{y} ≡ Q_{0}^{0}y_{0} … Q_{n−1}^{0}y_{n−1} und \overline{Q}^{1}\overline{z} ≡ Q_{0}^{1}z_{0} … Q_{n−1}^{1}z_{n−1}. Weiterhin haben wir:

(a) l(ξ′) = l(Q^{0}\overline{y}ψ(\overline{x}, \overline{y})) und l(π′) = l(Q^{1}\overline{z}ϑ(\overline{x}, \overline{z}))

(b) Die Variablen aus \overline{y} kommen nicht in ϑ vor und die Variablen aus \overline{z} kommen nicht in ψ vor.

Nach Lemma 6.6 (11. und 14.) folgt φ′ ≡ \overline{Q}^{0}\overline{y}\overline{Q}^{1}\overline{z}ψ(\overline{x}, \overline{y}) ∧ ϑ(\overline{x}, \overline{z}) und l(φ′) = l(φ). φ′ ist dabei in pränexer Form und nur durch ¬, ∧ und Quantoren aufgebaut.

4. φ ≡ Qxψ, Q ∈ {∃, ∀}

Nach Induktionsvoraussetzung existiert ψ′ ∼ ψ mit ψ in pränexer Normalform und so weiter und so fort…

Mit Lemma 6.2.4 erhalten wir φ′ ≡ Qxψ′ ∼ φ, wobei φ′ die gewünschten Eigenschaften hat.

Also haben wir χ(\overline{x}) ∼ φ′(\overline{x}) ≡ \overline{Q}\overline{y}ψ(\overline{x}, \overline{y}) mit \overline{Q}\overline{y} ≡ Q_{0}y_{0} … Q_{n−1}y_{n−1}, Q_{i} ∈ \{∃, ∀\}, i = 0, …, n−1 und ψ quantorenfrei. Nun ist aber eine quantorenfreie Formel (ψ) eine Boolesche Kombination über den Atomformeln, d.h. sie kann aus einer aussagenlogischen Formel π über gewisse Aussagenvariablen p_{0}, …, p_{k−1} durch Substitution von Atomformeln φ_{i} gewonnen werden: ψ(\overline{x}, \overline{y}) ≡ π_{φ_{0}/p_{0},...,φ_{k−1}/p_{k−1}}. Nach Aussagenlogik existiert π′ ∼ π, sodass π′ in konjunktiver (bzw. disjunktiver) Normalform vorliegt. Damit folgt nach Lemma 6.5.2, dass ψ(\overline{x}, \overline{y}) ≡ π_{φ_{0}/p_{0},...,φ_{k−1}/p_{k−1}} ∼ π′_{φ_{0}/p_{0},...,φ_{k−1}/p_{k−1}}. Mit Lemma 6.2.4 ergibt sich also χ(\overline{x}) ∼ \overline{Q}\overline{y}ψ(\overline{x}, \overline{y}) ∼ \overline{Q}\overline{y}π′_{φ_{0}/p_{0},...,φ_{k−1}/p_{k−1}} ≡ χ′(\overline{x}). χ′ ist in konjunktiver (bzw. disjunktiver) pränexer Normalform.

Definition (Universiell, existentiell) Eine Formeln in pränexer Form heißt universell, falls sie die Form ∀\overline{x}ψ(\overline{x}) hat, wobei ψ quantorenfrei ist. Sie heißt existentiell, falls sie die Form ∃\overline{x}ψ(\overline{x}) hat, wobei ψ quantorenfrei ist.

Beispiel Wir betrachten die reellen Zahlen und die Signatur σ(L) = {+, −, ·, 1, f(x), y} und schreiben |x − x_{0}| < ε für x − x_{0} = 0 ∨ (0 < x − x_{0} ∧ x − x_{0} < ε) ∨ (0 < x_{0} − x ∧ x_{0} − x < ε), sowie x ≥ y statt y < x ∨ y = x. Nun ist die gleichmäßige Stetigkeit durch ∀ε∃δ∀xx_{0}(|x − x_{0}| < δ → |f(x) − f(x_{0})| < ε) gegeben. Die Negation dieser Formel ist ¬∀ε∃δ∀xx_{0}(|x − x_{0}| < δ → |f(x) − f(x_{0})| < ε) was zu der Formel ∃ε∀δ∃xx_{0}(|x − x_{0}| < δ ∧ |f(x) − f(x_{0})| ≥ ε) äquivalent ist.

Folgern und Modelle

Sei Σ eine Menge von L-Aussagen und φ(\overline{x}), ψ(\overline{x}) L-Formeln und M eine L-Struktur.

Definition (Modell)

1. M ist ein Modell von Σ (M ⊧ Σ), falls für alle Aussagen ϑ ∈ Σ auch M ⊧ ϑ gilt.

2. Σ heißt erfüllbar, wenn es ein Modell besitzt.

3. φ(\overline{x}) folgt aus Σ(Σ ⊧ φ(\overline{x}), falls für jedes Modell M ⊧ Σ gilt: M ⊧ φ(\overline{x}). Wir sagen auch φ(\overline{x}) ist Folgerung aus Σ.

4. Der deduktive Abschluss Σ^{⊧} ist die Menge aller Aussagen, die Folgerung aus σ sind.

5. φ(\overline{x}) und ψ(\overline{x}) heißen Σ-äquivalent (φ ∼_{Σ} ψ), falls Σ ⊧ ∀\overline{x}(φ(\overline{x}) ↔ ψ(\overline{x})).

Bemerkung 1. ∅^{⊧} ist die Menge aller allgemeingültigen Aussagen.

2. Wir schreiben ⊧ φ statt ∅ ⊧ φ.

3. ( )^{⊧} ist ein Hüllenoperator:

(a) Σ ⊆ Σ^{⊧}

(b) Σ ⊆ Δ ⇒ Σ^{⊧} ⊆ Δ^{⊧}

(c) (Σ^{⊧})^{⊧} = Σ^{⊧}

4. Es gilt M ⊧ Σ ⇔ M ⊧ Σ^{⊧}.

5. Σ ist genau dann erfüllbar, wenn es keine Aussage φ mit φ, ¬φ ∈ Σ^{⊧} gibt. Lemma 3.10. (6.8) Seien L eine Sprache, \overline{c} ein Tupel von paarweise verschiedenen neuen Konstantensymbolen, φ(\overline{x}) eine L-Formel und Σ eine Menge von L-Aussagen. Wenn Σ ⊧_{L(\overline{c})} φ(\overline{c}), so auch Σ ⊧_{L} φ(\overline{x}). Beweis: Seine M ⊧ Σ und \overline{a} ∈ M beliebig gewählt mit |\overline{a}| = |\overline{c}| = |\overline{x}|. Wir haben M ⊧_{L} Σ, also (M, \overline{a}) ⊧_{L(\overline{c})} Σ, da \overline{c} nicht in Σ vorkommt. Nach Voraussetzung folgt (M, \overline{a}) ⊧_{L(\overline{c})} φ(\overline{a}), d.h. aber M ⊧_{L} φ(\overline{a}). Weil aber \overline{a} ∈ M beliebig war, folgt M ⊧_{L} ∀\overline{x}φ(\overline{x}) und somit da M ⊧ Σ beliebig, auch Σ ⊧_{L} ∀\overline{x}φ(\overline{x}), also Σ ⊧_{L} φ(\overline{x}). Lemma 3.11. (Deduktionslemma für die Prädikatenlogik (6.9)) Seien Σ eine Menge von Aussagen, φ eine Aussage und ψ(\overline{x}) eine Formel. Dann gilt: Σ ⊧ φ → ψ(\overline{x}) ⇔ Σ ∪ \{φ\} ⊧ ψ(\overline{x}) Beweis: Offensichtlich (vgl. Übungsaufgabe in der AL).

Theorien

Definition (Theorie)

1. Eine L-Theorie ist eine erfüllbare und deduktiv abgeschlossene Menge von L-Aussagen. (Manchmal wird auch die deduktive Abgeschlossenheit weggelassen.)

2. Sei 𝕄 eine Klasse von L-Strukturen.

Eine L-Theorie von 𝕄 ist T h(𝕄) = {φ|φ Aussage, für alle M ∈ 𝕄 gilt M ⊧ φ}.

3. Sei T eine Theorie.

Mod(T) ist die Klasse der Modelle von T.

Bemerkung T^{⊧} = T h(Mod(T))

Vorlesung am 28.11.2007

Beispiel (Theorie) L = {<} Theorie: φ_{1} ≡ ∀xy(x < y ∨ x = y ∨ y < x) (total) φ_{2} ≡ ∀xyz(x < y ∧ y < z) → x < z (transitiv) φ_{3} ≡ ∀x¬x < x (nicht reflexiv) Die Theorie T ist der deduktive Abschluss von ⋂_{i=1}^{3} φ_{i} ⇝ Mod(T) besteht gerade aus den totalen Ordnungen, z.B. (ℤ, <) oder (ℚ, <) etc.

Lemma 3.12. (6.10) Sei Σ eine erfüllbare Menge von L-Aussagen. Es sind äquivalent:

1. Σ ist maximal erfüllbar (bzgl. ⊆), d.h. ∀Σ′ ⊃ Σ : Σ′ ist nicht erfüllbar.

2. Σ ist eine maximale L-Theorie.

3. Σ = T h(M) für eine L-Struktur M.

4. Für jede L-Aussage φ gilt φ ∈ Σ oder ¬φ ∈ Σ.

Beweis:

1. (1) ⇒ (2)

Ist Σ maximal erfüllbar, so gilt offenbar Σ = Σ^{⊧}, also ist Σ eine Theorie, d.h. es gilt (2).

2. (2) ⇒ (3)

Σ ist erfüllbar, also existiert M ⊧ Σ. Dann ist Σ ⊆ Th(M). Wegen (2) gilt auch die Gleichheit.

3. (3) ⇒ (4)

In M gilt für alle φ : M ⊧ φ oder M ⊧ ¬φ.

⇒ fertig.

4. (4) ⇒ (1)

Sei Σ erfüllbar.

Dann gilt für alle φ entweder φ ∈ Σ oder ¬φ ∈ Σ. Wäre Σ nicht maximal erfüllbar, so existierte φ′ ∉ Σ mit Σ′ = Σ ∪ {φ′} erfüllbar.

Da φ′ ∉ Σ, ¬φ′ ∈ Σ ⊆ Σ′, stellt dies einen Widerspruch zur Erfüllbarkeit von Σ′ dar.

Definition (vollständige Theorie) Eine solche Theorie Σ (wie in Lemma 6.10) heißt vollständig.

Beispiel Das obige Beispiel ist nicht vollständig, da für φ ≡ ∀xy(x < y → (∃zx < z ∧ z < y)) weder φ ∈ T noch ¬φ ∈ T gilt.

Bemerkung Jede Theorie ist ein einer vollständigen Theorie enthalten. Beweis: Sei T eine Theorie. Wähle M ⊧ T. Dann gilt T ⊆ Th(M).

Definition (vollständige Aussagenmenge) Eine erfüllbare Aussagenmenge Σ heißt vollständig, falls Σ^{⊧} eine vollständige Theorie ist.

Beispiel Sei p = 0 oder eine Primzahl und σ(L) = {+_{2}, ·_{2}, −_{1}, 0, 1} (der Index bezeichne die Stelligkeit). ACF_{p} sei der deduktive Abschluss der folgenden Aussagenmenge:

1. ∀xyz(x + y) + z = x + (y + z)

2. ∀x(x + 0 = x)

3. ∀x(x + (−x) = 0)

4. ∀x(x + y = y + x)

5. ∀xyz((x · y) · z = x · (y · z)

6. ∀x(x · 1 = x)

7. ∀xy(x · y = y · x)

8. ∀x∃y(x ≠ 0 → xẏ = 1)

9. ¬0 = 1

10. Für jedes n ≥ 1: ∀x_{1} … x_{n}∃yy^{n} + x_{1}y^{n−1} + … + x_{0} = 0

11. Für p ∈ ℙ: \underbrace{1 + … + 1}_{p−mal} = 0

12. Für p = 0: Für alle n ∈ ℕ \ \{0\} : ¬ \underbrace{1 + … + 1}_{n−mal} = 0

Für ACF_{p} = Σ^{⊧} gilt: Mod(ACF_{p}) = {algebraisch abgeschlossener Körper der Charakteristik p}

Satz 3.1. (Tarski (6.11)) ACF_{p} ist vollständig und Modelle von ACF_{p} sind eindeutig bis auf Isomorphie durch die Kardinalität einer Transzendenzbasis. Die angegeben Aussagen axiomatisieren ACF_{p}.

Beweis: Kein Beweis und kein Bezug zur Vorlesung.

Definition ((endlich) axiomatisierbar) Eine Klasse 𝕂 von L-Strukturen heißt elementar (oder elementar axiomatisierbar), falls eine Menge Σ von L-Aussagen mit 𝕂 = Mod(Σ) existiert. Man sagt: Σ axiomatisiert 𝕂. Ist Σ endlich wählbar, d.h. Σ = {φ}, so heißt 𝕂 endlich axiomatisierbar.

Beispiel ((nicht) endlich axiomatisierbar) Die Klasse der Körper in σ(L) = {+, ·, −, 0, 1} ist endlich axiomatisierbar. ACF_{p} ist nicht endlich axiomatisierbar.

Sei P A (→ Peaono Arithmetik) der deduktive Abschluss der Menge der folgenden Axiome über der Signatur σ(L) = {0, 1, +, ·}.

1. ∀x(x + 1 ≠ 0)

2. ∀xy(x + 1 = y + 1 → x = y)

3. ∀x(x + 0 = x)

4. ∀xy((x + y) + 1 = x + (y + 1)))

5. ∀x(x · 0 = 0)

6. ∀xy(x · (y + 1) = x · y + x

7. Für jede L-Formel φ(x) mit höchstens x als freie Variable:

(φ(0) ∧ ∀x(φ(x) → φ(x + 1))) → ∀xφ(x)

Bemerkung (ℕ, +, ·, 0, 1) ⊧ P A ⇒ P A ist eine Theorie.

Satz 3.2. (6.12 (Gödel)) P A ≠ Th(ℕ), d.h. P A ist nicht vollständig.

Beweis: Später.

Bemerkung Gödel zeigt noch viel mehr: Es ist nicht möglich, ein effektiv berechenbares Axiomensystem Σ anzugeben, sodass Th(ℕ) = Σ^{⊧}.

Definierbare Mengen

Definition

1. Sei M eine L-Struktur, φ(\overline{x}, \overline{y}) eine L-Formel, \overline{x} ein n-Tupel, \overline{y} ein m-Tupel und \overline{b} ein m-Tupel aus M. Wir setzen ψ(M^{n}, \overline{b} = \{(a_{0}, …, a_{n−1}) ∈ M^{n}|M ⊧ ψ(\overline{a}, \overline{b})\}.

ψ(M^{n}, \overline{b}) ist die durch ψ(\overline{x}, \overline{b}) in M^{n} definierte Teilmenge von M^{n}. Dabei sind \overline{b} die Parameter.

2. X ⊆ M^{n} heißt definierbar, falls es eine L-Formel ψ(\overline{x}, \overline{y}) und ein m-Tupel \overline{b} in M mit X = ψ(M^{n}, \overline{b}) existiert.

Beispiel (definierbare Mengen)

1. Endliche Teilmengen von M^{n} sind stets definierbar.

Eine Definition von \{a_{1}, …, a_{n}\} ist ψ(x, \overline{a}) ≡ x = a_{1} ∨ x = a_{2} ∨ … ∨ x = a_{k}.

2. Wenn zwei Mengen X, Y ⊆ M^{n} definierbar sind, so sind auch X ∪ Y, X ∩ Y, X^{c} definierbar, indem man die Disjunktion, Konjunktion oder Negation der definierenden Formeln von X und Y verwendet.

3. In N = (ℕ, +, ·, 0, 1) kann die Menge der ungerade Primzahlen definiert werden:

ψ(x) ≡ ¬x = 0 ∧ ¬x = 1 ∧ ¬x = 1 + 1 ∧ (∀yz(y · z = x → (y = 1 ∨ z = 1)))

4. In R = (ℝ, +, ·, 0, 1) kann < definiert werden:

Wir definieren ψ(x, y) = {(x, y) ∈ ℝ^{2}|x < y}, i.e. ψ(x, y) ≡ ∃z(y − x = z · z ∧ ¬x = y).

Lemma 3.13. Sei h : M → N ein Isomorphismus von L-Strukturen. Dann gilt für alle L-Formeln ψ(\overline{x}) und alle a_{0}, …, a_{n−1} ∈ M: M ⊧ ψ(\overline{a}) ⇔ N ⊧ ψ(h(a_{0}), …, h(a_{n−1})).

Beweis: Der Beweis erfolgt durch Induktion über den Formelaufbau. Zunächst zeigen wir für alle Terme t(\overline{x}): h(t^{M}(a_{0}, …, a_{n−1}) = t^{N}(h(a_{0}), …, h(a_{n−1})). Dann zeigen wir für atomare Formeln:

1. ψ(\overline{x}) ≡ R\overline{x}

Gilt per Definition.

2. ψ(\overline{x}) ≡ t_{1}(\overline{x}) = t_{2}(\overline{x})

Dann gilt natürlich M ⊧ ψ(\overline{a}) ⇔ t_{1}^{M}(\overline{a}) = t_{2}^{M}(\overline{a}).

⇔ h(t_{1}^{M}(\overline{a})) = h(t_{2}^{M}(\overline{a})) ⇔ t_{1}^{N}(h(\overline{a})) = t_{2}^{N}(h(\overline{a}))

⇔ N ⊧ ψ(h(\overline{a}))

Bei den booleschen Konnektoren und Quantoren gehen wir ähnlich vor.

Korollar 3.1. (6.14) Ist h ∈ Aut(M) mit h(b) = b für b aus \overline{b}, so gilt ψ(M^{n}, \overline{b}) = h(ψ(M^{n}, \overline{b})).

Beweis: Mit vorherigem Lemma.

Korollar 3.2. (6.15) M ≅ N ⇒ Th(M) = Th(N) (Die Umkehrung gilt im Allgemeinen nicht.)

Beweis: Kein Beweis.

Definition (elementar äquivalente L-Strukturen) Zwei L-Strukturen M, N heißen elementar äquivalent (wir schreiben M ≡N), falls Th(M)=Th(N) gilt.

Satz 3.3. (6.16) Zu jeder L-Struktur M existiert eine L-Struktur N mit N ≡ M und der folgenden Eigenschaft: Wann immer A ⊆ N endlich und X ⊆ N definierbar ist, so ist X genau dann mit Parametern aus A definierbar (A-definierbar), wenn ∀σ ∈ Aut(N), σ|_{A} = id_{A} : σ(X) = X.

Beweis: Kein Beweis

Bemerkung Dies ist sehr nützlich, wenn man wissen möchte, ob eine Menge A-definierbar ist.

Vorlesung am 03.12.2007

3.7 Ableiten

Vereinfachung Analog zur Aussagenlogik betrachten wir ∧, ∨, ↔ und ∃ lediglich als Abkürzungen. Wir arbeiten also nur mit Formeln, die mit ¬, →, ∀ und = gebildet werden.

Definition (Axiome) Wir verwenden in unserem Beweissystem die folgenden Axiome:

1. Aussagenlogische Axiome

(a) φ → (ψ → φ)

(b) (φ → (ψ → χ)) → ((φ → ψ) → (φχ))

(c) (¬ψ → ¬φ) → ((¬ψ → φ) → ψ)

für alle Formeln φ, ψ, χ. (Als prädikatenlogische Tautologien sind diese alle allgemeingültig.)

2. Quantorenaxiome

(a) ∀x(φ → ψ) → (φ → ∀xψ), wenn x nicht frei in φ vorkommt.

(b) ∀xφ(x, \overline{y}) → φ(t(\overline{y}), \overline{y}), falls die freien Vorkommen von x in φ nicht im Wirkungsbereich von Quantoren ∀y stehen, wobei y in t vorkommt. Dies ist zum Beispiel für konstante Terme immer der Fall.

3. Identitätsaxiome

Für alle Variablen x, y, alle Terme t(z_{0}, ..., z_{n−1}) und alle Atomformeln φ(z_{0}, ..., z_{n−1}) sind die folgenden Aussagen Axiome:

(a) ∀x(x = x)

(b) ∀x∀y∀\overline{z}(x = y → t(z_{0}, ..., z_{i−1}, x, z_{i+1}, ..., z_{n−1}) = t(z_{0}, ..., z_{i−1}, y, z_{i+1}, ..., z_{n−1})) für alle

i=0, ..., n − 1

(c) ∀x∀y∀\overline{z}(x = y → (φ(z_{0}, ..., z_{i−1}, x, z_{i+1}, ..., z_{n−1}) → φ(z_{0}, ..., z_{i−1}, y, z_{i+1}, ..., z_{n−1}))) für

alle i = 0, ..., n − 1

Wir lassen gegebenfalls auch die führenden Allquantoren weg.

Definition (Schlussregeln) Wir verwenden die folgenden Schlussregeln:

1. \frac{φ,φ→ψ}{ψ} (Modus Ponens)

2. \frac{φ}{∀xφ} (Generalisierung)

Definition (Σ-Beweis) Ein Σ-Beweis für φ ist eine endliche Folge φ_{0}, ..., φ_{n−1}, wobei

1. φ_{n−1} ≡ φ

2. Für jedes i < n gilt: φ_{i} ∈ Σ, φ_{i} ist ein Axiom oder es existieren l, k < i mit φ_{l} ≡ φ_{k} → φ_{i} (d.h. φ_{i} wird aus den Vorgängern durch Modus Ponens gewonnen) oder φ_{i} ≡ ∀xφ_{k} (d.h. φ_{i} wird durch Generalisierung gewonnen).

Wenn für eine Aussagenmenge Σ ein Σ-Beweis für φ existiert, so ist φ Σ-ableitbar. Wir schreiben Σ ⊢ φ. Wenn Σ = ∅ ist, so schreiben wir ⊢ φ, d.h. φ ist ableitbar.

Lemma 3.14. (7.1) Sei Σ eine Menge von Aussagen. Wenn Σ ⊢ χ, so gilt Σ ⊧ χ.

Beweis: Es sei also φ_{0}, ..., φ_{n−1} ein Beweis für χ aus Σ und M ein Modell für Σ. Wir zeigen induktiv über i < n, dass M ⊧ φ_{i}.

1. Wenn φ_{i} ∈ Σ gilt, so folgt M ⊧ φ_{i}, weil nach Voraussetzung M ⊧ Σ gilt.

2. Wenn φ_{i} ein Axiom ist, so gibt es die folgenden Fälle:

(a) Falls φ_{i} ein aussagenlogisches Axiom ist, so gilt M ⊧ φ, nach Lemma 6.5.

(b) Im Fall von φ_{i} ≡ ∀x(φ → ψ) → (φ → ∀xψ), wobei x nicht frei in φ vorkommt, ist φ_{i} allgemeingültig nach Lemma 6.6.16. Also gilt M ⊧ φ_{i}.

(c) Wenn φ_{i} ≡ ∀xφ(x, \overline{y}) → φ(t(\overline{y}), \overline{y}), wobei freie Vorkommen von x nicht im Wirkungsbereich eines Quantors ∀y mit y in t liegen, gilt: Sei M ⊧ ∀xφ(x, \overline{a}). Dann folgt aus der Definition der Gültigkeit M ⊧ φ(t(\overline{a}), \overline{a}). Nach Lemma 6.4. folgt M ⊧ φ(t(\overline{y}), \overline{y})(\overline{a}). Die Voraussetzung sichert, dass es keine Variablenkollisionen gibt und wir eindeutig substituieren können.

(d) Bei den Identitätsaxiomen ist die Allgemeingültigkeit klar.

3. Wenn φ_{i} durch die Schlussregel Modus Ponens aus φ_{k} und φ_{l} mit φ_{k} ≡ φ_{l} → φ_{i} (k, l < i) gewonnen wird, so folgt nach Induktionsvoraussetzung M ⊧ φ_{l} → φ_{i} und M ⊧ φ_{l}, also M ⊧ φ_{i}.

4. Wenn φ_{i} durch Generalisierung gewonnen wird, so haben wir φ_{i} ≡ ∀xφ_{j} mit j < i. Nach Induktionsvoraussetzung haben wir M ⊧ φ_{j}, d.h. M ⊧ ∀xφ_{j}.

Induktiv ergibt sich nun die Behauptung.

Korollar 3.3. (7.2) Wenn ⊢ φ, so ist φ allgemeingültig.

Korollar 3.4. (7.3) Wenn Σ ⊢ φ, so existiert eine endliche Teilmenge Σ_{0} ⊆ Σ, so dass Σ_{0} ⊢ φ.

Beweis: Sei Σ_{0} die Menge der Formeln aus Σ, die in einem fixierten Σ-Beweis von φ vorkommen. Weil der Beweis endlich ist, ist auch Σ_{0} endlich.

Definition (Abl) Wir definieren den Hüllenoperator Abl durch Abl(Σ) = {φ|Σ ⊢ φ}.

Bemerkung

1. Wenn φ_{0}, ..., φ_{n−1} ein Σ-Beweis ist, so ist φ_{0}, ..., φ_{i} für i < n ein Σ-Beweis für φ_{i}.

2. Man kann gewonnene Σ-Beweise in Σ-Beweisen als Unterbeweise einsetzen.

Lemma 3.15. (7.4) Wenn φ eine prädikatenlogische Tautologie ist, so gilt ⊢ φ.

Beweis: Weil φ eine prädikatenlogische Tautologie ist, existiert eine Tautologie μ über den Aussagenvariablen p_{0}, ..., p_{n−1}, sodass φ ≡ μ_{φ_{0}/p_{0},...,φ_{n−1}/p_{n−1}}. Nach Voraussetzung gilt ⊧ μ. Mit dem Vollständigkeitssatz der Aussagenlogik (3.10) gilt ⊢ μ. Sei μ^{0}, ..., μ^{m−1} ein aussagenlogischer Beweis für μ = μ^{m−1}. Dann ist μ_{φ_{0}/p_{0},...,φ_{n−1}/p_{n−1}}^{0}, ..., μ_{φ_{0}/p_{0},...,φ_{n−1}/p_{n−1}}^{m−1} ein Beweis für φ. Falls weitere Aussagenvariablen im Beweis vorkommen, können diese beliebig belegt werden. Bemerkung: Man kann diese weiteren Aussagenvariablen möglicherweise bei der geeigneten Wahl eines aussagenlogischen Beweises ganz vermeiden.

Lemma 3.16. (7.5) Wenn Σ ⊢ ∀x(φ ∧ ψ), so gilt Σ ⊢ ∀xφ.

Beweis: Im Fall von (φ ∧ ψ)^{x/x} ≡ (φ ∧ ψ) lässt sich das zweite Quantorenaxiom anwenden.

\begin{matrix}(1) & Q.Ax(2) & ⊢ & ∀x(φ ∧ ψ) → (φ ∧ ψ) \\ (2) & (V or.) & Σ⊢ & ∀x(φ ∧ ψ) \\ (3) & MP (1, 2) & Σ⊢ & φ ∧ ψ \\ (4) & Lemma(7.4) & ⊢ & φ ∧ ψ → φ \\ (5) & MP (3, 4) & Σ⊢ & φ \\ (6) & Generalisierung(5) & Σ⊢ & ∀xφ \end{matrix}

Satz 3.4. (Deduktionstheorem(7.6)) Sei Σ eine Menge von L-Aussagen, φ eine L-Aussage und ψ eine L-Formel. Wenn Σ ∪ {φ} ⊢ ψ, so gilt Σ ⊢ φ → ψ.

Beweis: Sei ψ_{0}, ..., ψ_{n−1} ein Σ ∪ {φ}-Beweis für ψ. Wir zeigen induktiv für i < n, dass Σ ⊢ φ → ψ_{i} gilt: Wenn ψ_{i} ein Axiom ist, ψ_{i} ∈ Σ oder ψ_{i} ≡ φ gilt, bzw. wenn ψ_{i} durch Modus Ponens erhalten wird, so schreiben wir einfach den Beweis aus der Aussagenlogik ab. Sei ψ_{i} ≡ ∀xψ_{j} mit j < i.

\begin{matrix}(1) & (IV) & Σ⊢ & φ → ψ_{j} \\ (2) & Generalisierung(1) & Σ⊢ & ∀x(φ → ψ_{j}) \\ (3) & Q.Ax(2) & Σ⊢ & ∀x(φ → ψ_{j}) → (φ → ∀xψ_{j}) \\ (4) & MP (2, 3) & Σ⊢ & φ → ∀xψ_{j} \end{matrix}

Bemerkung (Umkehrung des Deduktionstheorems) Die Umkehrung des Deduktionstheorems gilt nach Modus Ponens.

Vorlesung am 05.12.2007

Lemma 3.17. (7.7) x_{0}, ..., x_{n−1} seien genau die Variablen, die frei in φ vorkommen. φ(t_{0}, ..., t_{n−1}) entsteht, indem man simultan die freien Vorkommen von x_{i} durch t_{i} ersetzt, wobei t_{i} konstante Terme sind.

1. Wenn Σ ⊢ φ(x_{0}, ..., x_{n−1}), so gilt auch Σ ⊢ φ(t_{0}, ..., t_{n−1}).

2. Wenn c_{0}, ..., c_{n−1} neue Konstantensymbole sind, die nicht Σ ∪ {φ} vorkommen, dann folgt aus Σ ⊢ φ(c_{0}, ..., c_{n−1}) auch Σ ⊢ φ(x_{0}, ..., x_{n−1}).

Beweis:

1.

\begin{matrix}(1) & (V or) & Σ⊢ & φ(x_{0}, ..., x_{n−1}) \\ (2) & Generalisierung(1) & Σ⊢ & ∀\overline{x}φ(\overline{x}) \\ (3) & Q.Ax(2) & Σ⊢ & ∀\overline{x}φ(\overline{x}) → φ(\overline{t}) \\ (4) & MP (2, 3) & Σ⊢ & φ(\overline{t}) \end{matrix}

2. Wir haben Σ ⊢ φ(\overline{c}).

Sei φ_{0}(\overline{c}), ..., φ_{n−1}(\overline{c}) ≡ φ(\overline{c}) ein Σ-Beweis für φ(\overline{c}). Ersetzen wir die c_{i} durch y_{i}, wobei y_{i} neue Variablen sind, die sonst nicht vorkommen, so ist φ_{0}(\overline{y}), ..., φ_{n−1}(\overline{y}) ein Σ-Beweis für φ(\overline{y}).

\begin{matrix}(1) & (V or) & Σ⊢ & φ(\overline{y}) \\ (2) & Generalisierung(1) & Σ⊢ & ∀\overline{y}φ(\overline{y}) \\ (3) & Q.Ax(2) & Σ⊢ & ∀\overline{y}φ(\overline{y}) → φ(\overline{x}) \\ (4) & MP (2, 3) & Σ⊢ & φ(\overline{x}) \end{matrix}

Beispiel (Anwendung des obigen Lemmas) Wir wollen zeigen: ⊢ ∀x(φ → ψ) → (∀xφ → ∀xψ). Durch Ersetzung aller freien Variablen außer x in φ und ψ durch neue Konstanten erhalten wir φ′ bzw. ψ′. Weiterhin betrachten wir Σ = {∀x(φ′ → ψ′), ∀xφ′}.

( 1 ) (∈ Σ)  Σ⊢∀x(φ′ → ψ′)
( 2 ) Q.Ax(1)  Σ⊢∀x(φ′ → ψ′) → (φ′ → ψ′)
( 3 ) MP (1, 2)  Σ⊢φ′ → ψ′
( 4 ) Q.Ax(2)  Σ⊢∀xφ′ → φ′
( 5 ) (∈ Σ)  Σ⊢∀xφ′
( 6 ) MP (4, 5)  Σ⊢φ′
( 7 ) MP (3, 6)  Σ⊢ψ′
( 8 ) Generalisierung  Σ⊢∀xψ′
( 9 ) (Ded)  {∀x(φ′ → ψ′)}⊢∀xφ′ → ∀xψ′
(10) (Ded)  ⊢∀x(φ′ → ψ′) → (∀xφ′ → ∀xψ′)
(11) Lemma(7.7)  ⊢∀x(φ → ψ) → (∀xφ → ∀xψ)

Definition (Inkonsistent, widerspruchsvoll) Σ sei eine Menge von Aussagen. Σ ist inkonsistent (bzw. widerspruchsvoll), wenn eine Formel φ existiert, sodass Σ ⊢ φ und Σ ⊢ ¬φ. Σ ist konsistent (bzw. widerspruchsfrei), wenn Σ nicht inkonsistent ist.

Lemma 3.18. (7.8)

1. Wenn Σ inkonsistent ist, so gilt Σ ⊢ ψ für alle ψ.

2. Sei χ eine Aussage. Dann ist Σ ∪ {χ} genau dann inkonsistent, wenn Σ ⊢ ¬χ gilt.

3. Σ ist genau dann konsistent, wenn jede endliche Teilmenge konsistent ist.

Beweis:

1.

\begin{matrix}(1) & (präd.log.T aut.) & ⊢ & φ → (¬φ → ψ) \\ (2) & (V or) & Σ⊢ & φ \\ (3) & (V or) & Σ⊢ & ¬φ \\ (4) & MP (1, 2) & Σ⊢ & ¬φ → ψ \\ (5) & MP (3, 4) & Σ⊢ & ψ \end{matrix}

2. Die Rückrichtung ist klar. Kümmern wir uns um die Hinrichtung.

Sei Σ ∪ {χ} inkonsistent. Nach 1. haben wir Σ ∪ {χ} ⊢ ¬χ. Durch das Deduktionstheorem erhalten wir Σ ⊢ χ → ¬χ.

Weiterhin können wir die prädikatenlogische Tautologie (χ → ¬χ) → ¬χ ableiten. Mit Modus Ponens ergibt sich Σ ⊢ ¬χ.

3. Sei Σ konsistent und eine endliche Teilmenge Σ_{0} ⊆ Σ gegeben. Dann ist auch Σ_{0} konsistent.

Nun zur Rückrichtung: Sei Σ inkonsistent.

Dann existieren Σ-Beweise φ_{0}, ..., φ_{n−1} ≡ φ und ψ_{0}, ..., ψ_{m−1} ≡ ¬φ. Wenn Σ_{0} die Menge der Aussagen aus Σ ist, die in den φ_{i} und ψ_{i} vorkommen, so gilt auch Σ_{0} ⊢ φ und Σ_{0} ⊢ ¬φ, d.h. wir haben eine endlich inkonsistente Teilmenge gefunden.

Definition (maximal konsistente Aussagenmengen) Eine Aussagenmenge Σ ist maximal konsistent, wenn Σ konsistent ist und jedes Σ^{+} ⊃ Σ inkonsistent ist.

Lemma 3.19. (7.9) Sei Σ maximal konsistent und ψ, χ Aussagen. Dann gilt:

1. χ ∈ Σ ⇔ Σ ⊢ χ

2. χ ∉ Σ ⇔ Σ ⊢ ¬χ

3. χ → ψ ∈ Σ ⇔ ¬χ ∈ Σ oder ψ ∈ Σ

4. χ ∧ ψ ∈ Σ ⇔ χ ∈ Σ und φ ∈ Σ Beweis:

1. ⇐:

trivial. ⇒: Sei Σ ⊢ χ. Dann ist Σ ∪ {χ} konsistent da χ ∈ Abl(Σ). Durch die Maximalität von Σ erhalten wir ⇒ Σ = Σ ∪ {χ}, d.h. χ ∈ Σ.

2. ⇐:

Wenn ¬χ ∈ Σ, so gilt χ ∉ Σ, da Σ sonst inkonsistent wäre. ⇒: χ ∉ Σ. Da Σ maximal konsistent ist, ist Σ ∪ {χ} inkonsistent. Nach Lemma 7.8.2 gilt Σ ⊢ ¬χ und nach 1. ¬χ ∈ Σ.

3. ⇒:

Wir haben ⊢ (χ → ψ) → (¬ψ → ¬χ) als prädikatenlogische Tautologie. Nach Voraussetzung haben wir χ → ψ ∈ Σ. Wenn ψ ∉ Σ gilt, haben wir χ → ψ, ¬ψ ∈ Σ. Zweimalige Anwendung von Modus Ponens ergibt Σ ⊢ ¬χ. Nach 1. haben wir auch ¬χ ∈ Σ. ⇐: Wir haben zunächst die prädikatenlogische Tautologie ¬χ → (χ → ψ). Wenn ¬χ ∈ Σ, so haben wir auch Σ ⊢ χ → ψ mit Modus Ponens. Mit 1. erhalten wir χ → ψ ∈ Σ. Mit dem Axiom ψ → (χ → ψ) erhalten wir (im Fall von ψ ∈ Σ), dass Σ ⊢ χ → ψ gilt, d.h. χ → ψ ∈ Σ.

4. Übung.

Definition (Vorbereitung von Zorn’s Lemma) Wir betrachten die Signatur mit der zweistelligen Relation <. ⟨A, <⟩ ist eine Halbordnung, wenn gilt:

1. A ⊧ ∀x¬x < x

2. A ⊧ ∀xyz(x < y ∧ y < z → x < z) Wenn X ⊆ A, so ist a ∈ A eine obere Schranke für X, wenn b < a oder b = a für alle b ∈ X gilt. a ist ein maximales Element in A, falls a ∈ A gilt und a < b für jedes b unmöglich ist. X ist eine Kette in A, falls für alle b, c ∈ X einer der drei Fälle b < c, b = c oder c < b eintritt. Lemma 3.20. (Zorn’s Lemma/Auswahlaxiom (7.10)) Sei ⟨A, <⟩ eine Halbordnung und jede Kette in A besitze eine obere Schranke. Dann besitzt A ein maximales Element. Beweis: Kein Beweis Satz 3.5. (Lindenbaums Theorem (7.11)) Jede konsistente Menge Σ lässt sich zu einer maximal konsistenten Menge erweitern.

Beweis: Sei A die Menge aller konsistenten Mengen Δ in L. Wir setzen Δ_{1} < Δ_{2} genau dann, wenn Δ_{1} ⊂ Δ_{2}. Wenn X eine Kette in A ist, dann ist ⋃_{Δ∈X} Δ = ⋃ X eine obere Schranke für X: Wir haben auf jeden Fall Δ < ⋃ X für alle Δ ∈ X. Es bleibt also zu zeigen, dass ⋃ X ∈ A gilt, d.h. dass diese Menge konsistent ist. Mit Lemma 7.8.3 ist ⋃ X genau dann konsistent, wenn jede endliche Teilmenge {φ_{0}, ..., φ_{n−1}} ⊆ ⋃ X konsistent ist. Sei φ_{i} ∈ Δ_{i} und Δ_{K} sei maximal in Δ_{0}, ..., Δ_{n−1}. Δ_{K} existiert, weil X eine Kette ist. Also haben wir {φ_{0}, ..., φ_{n−1}} ⊆ Δ_{K} und damit ist Δ_{K} konsistent. Nun können wir Zorn’s Lemma anwenden, wass uns ein maximales Element in A verschafft. Weil dieses in A enthelten ist, ist es maximal konsistent.

Lemma 3.21. (7.12) Für konstante Terme t_{1}, t_{2} definieren wir t_{1} ∼ t_{2}, wenn Σ ⊢ t_{1} = t_{2}. Dann ist ∼ eine Äquivalenzrelation.

Beweis:

1. Reflexiviät Wir haben ⊢ x = x durch die Identitätsaxiome und damit ⊢ t = t nach Lemma 7.7.1.

2. Symmetrie Wir haben x = y → (x = t_{1} → y = t_{2}) aus den Identitätsaxiomen. Mit Lemma 7.7.1 erhalten wir t_{1} = t_{2} → (t_{1} = t_{1} → t_{2} = t_{1}). Mit Hilfe von Modus Ponens, der Voraussetzung und 1. erhalten wir Σ ⊢ t_{2} = t_{1}.

3. Transitivität

\begin{matrix}(1) & (V or) & Σ⊢ & t_{1} = t_{2} \\ (2) & (V or) & Σ⊢ & t_{2} = t_{3} \\ (3) & (Id.Ax) & ⊢ & y = z → (t_{1} = y → t_{1} = z) \\ (4) & (Lemma 7.7.1) & ⊢ & t_{2} = t_{3} → (t_{1} = t_{2} → t_{1} = t_{3}) \\ (5) & MP (2, 4) & Σ⊢ & t_{1} = t_{2} → t_{1} = t_{3} \\ (6) & MP (1, 5) & Σ⊢ & t_{1} = t_{3} \end{matrix}

Vorlesung am 10.12.2007

Lemma 3.22. (7.13) Σ sei eine Aussagenmenge in der Sprache L, s_{0}, ..., s_{n−1} und t_{0}, ..., t_{n−1} konstante Terme, u(x_{0}, ..., x_{n−1}) ein Term und φ(x_{0}, ..., x_{n−1}) eine Atomformel.

1. Wenn s_{i} ∼ t_{i} (d.h. Σ ⊢ s_{i} = t_{i}) für 0 ≤ i < n, dann gilt Σ ⊢ u(s_{0}, ..., s_{n−1}) = u(t_{0}, ..., t_{n−1}).

2. Wenn s_{i} ∼ t_{i} für 0 ≤ i < n und Σ ⊢ φ(s_{0}, ..., s_{n−1}), so folgt Σ ⊢ φ(t_{0}, ..., t_{n−1}).

Beweis:

1.

\begin{matrix}( 1 ) & Id.Ax(2) & ⊢ & x_{0} = y_{0} → u(x_{0}, ..., x_{n−1}) = u(y_{0}, x_{1}, ..., x_{n−1}) \\ (  ) & ⋮ & ⊢ & ⋮ \\ ( n ) & Id.Ax(2) & ⊢ & x_{0} = y_{0} → u(y_{0}, ..., y_{n−2}, x_{n−1}) = u(y_{0}, ..., y_{n−1}) \\ ( n + 1 ) & Lemmma(7.7.9) & Σ⊢ & s_{0} = t_{0} → u(s_{0}, ..., s_{n−1}) = u(t_{0}, s_{1}, ..., s_{n−1}) \\ (  ) & ⋮ & ⊢ & ⋮ \\ ( 2n ) & Lemmma(7.7.9) & Σ⊢ & s_{n−1} = t_{n−1} → u(t_{0}, ..., t_{n−2}, s_{n−1}) = u(t_{0}, ..., t_{n−1}) \\ (2n + 1) & (V or) & Σ⊢ & s_{0} = t_{0} \\ (  ) & ⋮ & ⊢ & ⋮ \\ ( 3n ) & (V or) & Σ⊢ & s_{n−1} = t_{n−1} \\ (3n + 1) & MP (n + 1, 2n + 1) & Σ⊢ & u(s_{0}, ..., s_{n−1}) = u(t_{0}, s_{1}, ..., s_{n−1}) \\ (  ) & ⋮ & ⊢ & ⋮ \\ ( 4n ) & MP (2n, 3n) & Σ⊢ & u(t_{0}, ..., t_{n−2}, s_{n−1}) = u(t_{0}, ..., t_{n−1}) \end{matrix}

Mit Lemma 7.12 (Transitivität) erhalten wir Σ ⊢ u(s_{0}, ..., s_{n−1}) = u(t_{0}, ..., t_{n−1}) Damit ergibt sich u(s_{0}, ..., s_{n−1}) ∼ u(t_{0}, ..., t_{n−1}).

2.

\begin{matrix}( 1 ) & Id.Ax(3) & ⊢ & x_{0} = y_{0} → (φ(x_{0}, ..., x_{n−1}) → φ(y_{0}, x_{1}, ..., x_{n−1})) \\ (  ) & ⋮ & ⊢ & ⋮ \\ ( n ) & Id.Ax(3) & ⊢ & x_{0} = y_{0} → (φ(y_{0}, ..., y_{n−2}, x_{n−1}) → φ(y_{0}, ..., y_{n−2}, y_{n−1})) \\ ( n + 1 ) & Lemmma(7.7.9) & Σ⊢ & s_{0} = t_{0} → (φ(s_{0}, ..., s_{n−1}) → φ(t_{0}, s_{1}, ..., s_{n−1})) \\ (  ) & ⋮ & ⊢ & ⋮ \\ ( 2n ) & Lemmma(7.7.9) & Σ⊢ & s_{n−1} = t_{n−1} → (φ(t_{0}, ..., t_{n−2}, s_{n−1}) → φ(t_{0}, ..., t_{n−1})) \\ (2n + 1) & (V or) & Σ⊢ & s_{0} = t_{0} \\ (  ) & ⋮ & ⊢ & ⋮ \\ ( 3n ) & (V or) & Σ⊢ & s_{n−1} = t_{n−1} \\ (3n + 1) & MP (n + 1, 2n + 1) & Σ⊢ & φ(s_{0}, ..., s_{n−1}) → φ(t_{0}, s_{1}, ..., s_{n−1}) \\ (  ) & ⋮ & ⊢ & ⋮ \\ ( 4n ) & MP (2n, 3n) & Σ⊢ & φ(t_{0}, ..., t_{n−2}, s_{n−1}) → φ(t_{0}, ..., t_{n−1}) \end{matrix}

Damit haben wir durch Abtrennung Σ ∪ {φ(s_{0}, ..., s_{n−1})} ⊢ φ(t_{0}, ..., t_{n−1}). Mit Hilfe des Deduktionstheorems erhalten wir Σ ⊢ φ(s_{0}, ..., s_{n−1}) → φ(t_{0}, ..., t_{n−1}).

3.8 Gödels Vollständigkeitssatz

Ziel: Jede konsistente Menge Σ von Aussagen besitzt ein Modell. Sei L fixiert, Σ eine L-Aussagenmenge und C eine Menge von Konstantensymbolen in L.

Definition C ist Henkin-Erfüllungsmenge für Σ, wenn für jede Formel φ(x) ein c ∈ C existiert, sodass aus Σ die Formel ∃xφ(x) → φ(c) beweisbar ist, d.h. Σ ⊢ ∃xφ(x) → φ(c).

Finden eines Modells Sei Σ konsistent.

1. Zuerst erweitern wir L um neue Konstantensymbole C, sowie Σ zu Σ^{+}, sodass C Henkin-Erfüllungsmenge für Σ^{+} ist. Dabei soll Σ^{+} wieder konsistent sein.

2. Im zweiten Schritt zeigen wir, dass jede konsistente Menge Σ mit Henkin-Erfüllungsmenge ein Modell besitzt.

Lemma 3.23. (8.1) Sei Σ eine konsistente L-Aussagenmenge und C eine neue Menge von Konstantensymbolen mit |C| = |L|. Wir setzen L^{+} = L(C). Dann kann Σ zu einer konsistenten L^{+}-Menge von Aussagen erweitert werden, für die C Henkin-Erfüllungsmenge ist.

Beweis: O.B.d.A. sei L abzählbar. Wir definieren C = {c_{β}|β ∈ ℕ}. Dann ist L^{+} = L(C) auch abzählbar und {φ_{β}(x_{β})|β ∈ ℕ} sei eine Aufzählung aller Formeln aus L^{+} mit höchstens einer freien Variablen x_{β}. Wir definieren induktiv über β ∈ ℕ eine aufsteigende Kette Σ = Σ_{0} ⊆ Σ_{1} ⊆ Σ_{2} ⊆ ... ⊆ Σ_{β} ⊆ ... von L^{+}-Aussagen und eine Folge (d_{β})_{β∈ℕ} von Konstanten aus C, sodass gilt:

1. Σ_{β} ist konsistent

2. Σ_{β+1} = Σ_{β} ∪ {∃x_{β}φ_{β}(x_{β}) → φ_{β}(d_{β})} Wenn L überabzählbar ist, dann wird mit Ordinalzahlen indiziert und transfinite Induktion benutzt. Wir beweisen nun induktiv die beiden Eigenschaften: Im Induktionsanfang ist Σ_{0} = Σ gegeben und nach Voraussetzung konsistent. Nun erfülle Σ_{β} die beiden geforderten Eigenschaften. Weiterhin kommen in Σ_{β} nur endlich viele der c_{α} ∈ C vor, da Σ_{0} ⊆ L. Sei d_{β} das c_{α} (mit minimalem α), das nicht in Σ_{β} und φ_{β} vorkommt. Zu zeigen ist nun, dass Σ_{β+1} = Σ_{β} ∪ {∃x_{β}φ_{β}(x_{β}) → φ_{β}(d_{β}) konsistent ist. Annahme: Σ_{β+1} sei nicht konsistent. Dann erhalten wir nach Lemma 7.8.2 Σ_{β} ⊢ ¬(∃x_{β}φ_{β}(x_{β}) → φ_{β}(d_{β})). Wir haben die prädikatenlogische Tautologie ¬(∃x_{β}φ_{β}(x_{β}) → φ_{β}(d_{β})) → (∃x_{β}φ_{β}(x_{β}) ∧ ¬φ_{β}(d_{β})). Durch Modus Ponens erhalten wir Σ_{β} ⊢ ∃x_{β}φ_{β}(x_{β}) ∧ ¬φ_{β}(d_{β}). Da d_{β} weder in Σ_{β} noch in φ_{β} vorkommt, gilt nach Lemma 7.7.2: Σ_{β} ⊢ ∀x_{β}(∃x_{β}φ_{β}(x_{β}) ∧ ¬φ_{β}(x_{β})). Mit Lemma 7.5 erhalten wir Σ_{β} ⊢ ∀x_{β}∃x_{β}φ_{β}(x_{β}) und Σ_{β} ⊢ ∀x_{β}¬φ_{β}(x_{β}). Da x_{β} in ∃x_{β}φ_{β}(x_{β}) nicht frei vorkommt, gilt Σ_{β} ⊢ ∀x_{β}∃x_{β}φ_{β}(x_{β}) → ∃x_{β}φ_{β}(x_{β}) durch die Quantorenaxiome. Modus Ponens mit Σ_{β} ⊢ ∀x_{β}∃x_{β}φ_{β}(x_{β}) ergibt nun Σ_{β} ⊢ ∃x_{β}φ_{β}(x_{β}). Diese Formel ist jedoch eine Abkürzung für Σ_{β} ⊢ ¬∀x_{β}¬φ_{β}(x_{β}). Damit ist Σ_{β} jedoch im Widerspruch zur Induktionsvoraussetzung inkonsistent. Sei nun Σ^{+} = ⋃_{β∈ℕ} Σ_{β}. C ist dann nach Konstruktion Henkin-Erfüllungsmenge für Σ^{+}. Σ^{+} ist konsistent, da jede endliche Teilmenge in einem Σ_{β} enthalten und damit konsistent ist (Lemma 7.8.3).

Lemma 3.24. (8.2) Sei Σ eine konsistente Menge von L-Aussagen und C eine Henkin-Erfüllungs-menge für Σ. (Wir können durch das vorhergehende Lemma auch C ⊆ L annehmen.) Dann besitzt Σ ein Modell M, wobei jedes Element von M durch eine Interpretation c^{M} für ein c ∈ C gegeben wird.

Beweis: Nach Satz 7.11 (Satz von Lindenbaum) lässt sich Σ zu einer maximalen konsistenten Menge Σ^{+} erweitern. C ist dann auch Henkin-Erfüllungsmenge für Σ^{+}. Daher können wir auch o.B.d.A. annehmen, dass Σ = Σ^{+} maximal konsistent ist. Für alle konstanten Terme t_{1}, t_{2} aus L definieren wir t_{1} ∼ t_{2} genau dann, wenn Σ ⊢ t_{1} = t_{2}. Dann gilt:

1. t_{1} ∼ t_{2} genau dann, wenn t_{1} = t_{2} ∈ Σ, da Σ maximal konsistent ist.

Nach Lemma 7.12 ist ∼ eine Äquivalenzrelation.

Für das gesuchte Modell M sei dom(M) = {c̃|c ∈ C}, wobei c̃ die Äquivalenzklasse von c ist. Wenn R einn-stelliges Relationssymbol in L ist, dann definieren wir

2. R^{M}(c̃_{0}, ..., c̃_{n−1}), wenn R(c_{1}, ..., c_{n}) ∈ Σ für c_{i} ∈ c̃_{i}.

Nach 7.13 haben wir c_{i} ∼ c′_{i} für 0 ≤ i < n mit R(c_{1}, ..., c_{n}) ∈ L ⇒ Σ ⊢ R(c′_{0}, ..., c′_{n−1}), d.h. R(c′_{0}, ..., c′_{n−1}) ∈ Σ, da Σ maximal konsistent. D.h. die Definition 2 ist unabhängig von den Repräsentanten. Sei d ein Konstantensymbol aus L. Wir definieren

3. d^{M} = c̃, wenn d = c ∈ Σ.

Da ∼ eine Äquivalenzrelation ist, ist die Definition unabhängig vom Repräsentanten. (Man beachte, dass hier immer Σ ⊢ φ genau dann gilt, wenn φ ∈ Σ gilt.)

Vorlesung am 12.12.2007

Hier ist noch die Existenz eines c ∈ C mit d = c ∈ Σ zu zeigen.

(*) Wir zeigen allgemein, dass für jeden konstanten Term t ein c ∈ C mit (t = c) ∈ Σ existiert:

\begin{aligned}(1) & Q.Ax(2) & ⊢ & ∀x¬t = x → ¬t = t \\ (2) & P räd.Log.T aut. & ⊢ & (∀x¬t = x → ¬t = t) → (t = t → ¬∀x¬t = x) \\ (3) & MP (1, 2) & ⊢ & t = t → ¬∀x¬t = x \\ (4) & (Abk) & ⊢ & t = t → ∃xt = x \\ (5) & Id.Ax & ⊢ & t = t \\ (6) & MP (4, 5) & ⊢ & ∃xt = x \\ (7) & (Henkin) & Σ⊢ & ∃xt = x → t = c \\ (8) & MP (6, 7) & Σ⊢ & t = c \end{aligned}

⇒ t = c ∈ Σ Für ein n-stelliges Funktionssymbol f definieren wir

4. f^{M}(c̃_{0}, ..., c̃_{n−1}) = c̃, wenn f(c_{0}, ..., c_{n−1} = c, c_{i} ∈ c̃_{i}, c ∈ c̃. Nach Lemma 7.13 gilt: Wenn (c_{i} = c′_{i}) ∈ Σ, so gilt Σ ⊢ f(c_{0}, ..., c_{n−1}) = f(c′_{0}, ..., c′_{n−1}). Das heißt, c̃ ist unabhängig von der Wahl der c_{i} in c̃_{i}, d.h. es existiert ein eindeutig bestimmter Wert c̃. Damit ist M eine L-Struktur. Der Wert t^{M} = c̃ für ein c ∈ C ist deshalb definiert. Mit (*) folgt für t die Existenz eines c′ mit (t = c′) ∈ Σ. Wir definieren also

5. M ⊧ t = c genau dann, wenn (t = c) ∈ Σ. Für jedes t existiert auch ein solches c ∈ C. Induktiv über den Aufbau von Aussagen φ zeigen wir nun

6. M ⊧ φ ⇔ φ ∈ Σ:

(a) Atomaussagen i. M ⊧ t_{1} = t_{2} ⇔ (t_{1} = t_{2}) ∈ Σ folgt aus 5. und 1. ii. M ⊧ R(t_{0}, ..., t_{n−1}) ⇔ R(t_{0}, ..., t_{n−1}) ∈ Σ

Wir haben:

M ⊧ R(t_{0}, ..., t_{n−1}) ⇔ R^{M}(t_{0}^{M}, ..., t_{n−1}^{M})
⇔ ∃c_{0}, ..., c_{n−1} mit c̃_{i} = t_{i}^{M} und R(c_{0}, ..., c_{n−1})
⇔ ∃c_{0}, ..., c_{n−1} mit c_{i} = t_{i} ∈ Σ und R(c_{0}, ..., c_{n−1})
⇔ ∃c_{0}, ..., c_{n−1} mit c_{i} = t_{i} ∈ Σ und R(t_{0}, ..., t_{n−1})
⇔ R(t_{0}, ..., t_{n−1}) ∈ Σ

(b) Aussagenlogische Verknüpfungen

Wir betrachten hier nur ¬ und →.

i. φ ≡ ¬ψ

\begin{matrix}M ⊧ ¬ψ ⇔ & M |̸= ψ \\ ⇔ & ψ ∉ Σ \\ ⇔ & ¬ψ ∈ Σ \end{matrix}

ii. φ ≡ ψ → χ

M ⊧ ψ → χ ⇔ M |̸= ψ oder M ⊧ χ
⇔ ψ ∉ Σ oder χ ∈ Σ
⇔ ψ → χ ∈ Σ

(c) Quantoren

Wir betrachten hier nur ∀, d.h. sei φ ≡ ∀xψ. Es ist zu zeigen, dass M ⊧ ∀xψ ⇔ ∀xψ ∈ Σ.

i. ⇐ Wenn ∀xψ ∈ Σ, so ψ(c) ∈ Σ für jedes c ∈ C, da ⊢ ∀xψ → ψ(c) mit Hilfe der Quantorenaxiome gilt und wir den letzten Teil abtrennen können. Wir haben nun M ⊧ ψ(c) für alle c ∈ C, d.h. M ⊧ ψ(c̃) für alle c̃ ∈ dom(M), d.h. M ⊧ ∀xψ(x). ii. ⇒

Wenn ∀xψ ∉ Σ, so erhalten wir ¬∀xψ ∈ Σ nach Lemma 7.9.2.

Betrachten wir nun den folgenden Beweis:

(1) P räd.Log.T aut. ⊢¬¬ψ(x) → ψ(x)
(2) Gen(1)  ⊢∀x(¬¬ψ(x) → ψ(x))
(3)  ⊢∀x¬¬ψ(x) → ∀xψ(x)
(4)  ⊢¬∀xψ(x) → ¬∀x¬¬ψ(x)
(5) (∈ Σ)  Σ⊢¬∀xψ
(6) MP (4, 5)  Σ⊢¬∀x¬¬ψ(x)

Wir haben also ∃x¬ψ(x) ∈ Σ.

Da C Henkin-Erfüllungsmenge ist, gilt Σ ⊢ ∃x¬ψ(x) → ¬ψ(c) für ein c ∈ C. Nach Modus Ponens erhalten wir Σ ⊢ ¬ψ(c), d.h. ¬ψ(c) ∈ Σ. Aus der Induktionsvoraussetzung folgt M ⊧ ¬ψ(c), d.h. M ⊧ ¬ψ(c̃), und damit M |̸= ∀xψ(x).

Satz 3.6. (Modell-Existenz-Theorem (8.3)) Es sei Σ eine Menge von L-Aussagen. Wenn Σ konsistent ist, dann besitzt Σ ein Modell.

Beweis: Sei |C| = |L|. Nach Lemma 8.1 existiert eine konsistente Erweiterung Σ^{+} ⊇ Σ in L(C), sodass C Henkin-Erfüllungsmenge für Σ^{+} ist. Nach Lemma 8.2 existiert ein Modell M^{+} für Σ^{+}. Das Redukt M von M^{+} auf L ist dann Modell von Σ.

Bemerkung (Umkehrung des Modell-Existenz-Satzes) Wenn ein Modell M ⊧ Σ existiert, dann ist Σ konsistent. Wäre Σ inkonsistent, so wäre Σ ⊢ φ und Σ ⊢ ¬φ für eine Aussage φ. Mit Lemma 7.1 hätten wir Σ ⊧ φ und Σ ⊧ ¬φ. Damit existierte jedoch der Widerspruch M ⊧ φ und M ⊧ ¬φ.

Korollar 3.5. (Löwenheim - Skolem abwärts (8.4)) Jede konsistente Menge Σ von L-Aus-sagen besitzt ein Modell mit einer Mächtigkeit von höchstens |L|.

Beweis: |C| = |L| und dom(M) = {c̃_{i} ∈ C} ⇒ |dom(M)| ≤ |C| = |L|

Satz 3.7. (Gödel (8.5)) Es gilt Σ ⊧ φ genau dann, wenn Σ ⊢ φ.

Beweis:

1. ⇐

ist trivial durch Lemma 7.1

2. ⇒

Sei Σ ⊧ φ, aber nicht Σ ⊢ φ. Nach Lemma 7.8 ist Σ ∪ {¬φ} konsistent. Nach Theorem 8.3 existiert ein Modell M ⊧ Σ mit M ⊧ ¬φ. Dies ist jedoch ein Widerspruch zu M ⊧ φ.

Korollar 3.6. (Endlichkeitssatz (8.6)) Eine Menge Σ von Aussagen besitzt genau dann ein Modell, wenn jede endliche Teilmenge Σ_{0} ⊆ Σ ein Modell besitzt.

Beweis:

1. ⇒

trivial

2. ⇐

Wennn jede endliche Teilmenge von Σ_{0} ⊆ Σ ein Modell besitzt, dann ist sie konsistent. Nach Lemma 7.8.2 ist dann Σ konsistent. Nach Theorem 8.3 existiert ein Modell M ⊧ Σ.

Korollar 3.7. (Löwenheim - Skolem aufwärts (8.7)) Σ sei eine Menge von L-Aussagen. Besitzt Σ ein unendliches Modell (oder endliche Modelle, sodass für jedes n ∈ ℕ ein Modell existiert, dass größer als n ist) und ist λ eine Kardinalzahl mit λ ≥ |L|, so existiert ein Modell mit M ⊧ Σ und |M| ≥ λ.

Beweis: Sei C = {c_{α}|α < λ}, wobei α Ordinalzahlen sind. Wir definieren Σ^{+} = Σ ∪ {c_{α} ≠ c_{β}|α ≠ β}. Dann besitzt jede endliche Teilmenge Σ_{0} von Σ^{+} ein Modell. Nach dem Endlichkeitssatz erhalten wir, dass Σ^{+} ein Modell M^{+} besitzt. Das L-Redukt M von M^{+} ist dann ein Σ-Modell mit mindestens λ Elementen.

Anwendung: Körpertheorie Wir betrachten die Theorie T F (Körpertheorie) in der Signatur σ = (+, −, ·, 0, 1). Sei M ⊧ T F, d.h. M erfüllt die Körperaxiome.

Vorlesung am 17.12.2007

Korollar 3.8. (8.8) Sei L die elementare Sprache der Signatur +, −, ·, 0, 1.

1. Sei Σ eine Menge von L-Aussagen mit T F ⊆ Σ^{⊧}. Wenn Σ Modelle beliebig großer Charakteristik besitzt, so besitzt Σ ein Modell der Charakteristik 0.

2. Sei φ eine L-Aussage. Wenn T F_{0} ⊧ φ, so existiert eine Zahl p_{φ} so dass für alle Primzahlen p > p_{φ} auch T F_{p} ⊧ φ gilt.

Beweis: Der Beweis ist eine typische Anwendung des Endlichkeitssatzes:

1. Sei Σ′ = Σ ∪ {p · 1 ≠ 0|p ∈ ℙ}.

Sei Σ′_{0} eine endliche Teilmenge von Σ′.

Dann existieren p_{0} < ... < p_{m} Primzahlen, sodass Σ′_{0} = Σ_{0} ∪{p_{i} ·1 ≠ 0|i ≤ m}, wobei Σ_{0} eine endliche Teilmenge von Σ ist. Nach Voraussetzung existiert ein Modell M von Σ mit einer Charakteristik Char(M) = q > p_{m} > ... > p_{0} oder Char(M) = 0. D.h. M ist Modell von Σ′_{0}. Dies gilt für alle endlichen Teilmengen von Σ′. Also existiert nach dem Endlichkeitssatz ein Modell K von Σ′. Es folgt also char(K) = 0 mit K ⊧ Σ.

2. Wäre die Behauptung nicht wahr, so besäße T F ∪ {¬φ} Modelle beliebig großer Charakteristik. Mit 1. besitzt dann T F_{0} ∪ {¬φ} ein Modell im Widerspruch zur Voraussetzung T F_{0} ⊧ φ.

Definition (elementare Unterstruktur) Seien M, N L-Strukturen mit M ⊆ N. Dann ist M elementare Unterstruktur von N, wenn für alle φ(\overline{x}) aus L und alle \overline{a} aus M genau dann M ⊧ φ(\overline{a}) gilt, wenn N ⊧ φ(\overline{a}).

Bemerkung Es reicht aus, die Hinrichtung (⇒) nachzuweisen, um die Eigenschaft einer elementaren Unterstruktur zu zeigen.

Definition (elementare Einbettung) Eine Einbettung f : M ↪ N ist elementar, wenn für alle φ(\overline{x}) aus L und alle \overline{a} aus M genau dann M ⊧ φ(\overline{a}) gilt, wenn N ⊧ φ(f(\overline{a})).

Lemma 3.25. (8.9) Die Signatur von L sei {+, ·, 0, 1, <}. Wenn M ⊧ Th(ℕ), so existiert eine elementare Einbettung von ℕ in M.

Beweis: Für alle n ∈ ℕ existiert ein konstanter Term k_{n} ≡ \underbrace{1 + ... + 1}_{n mal} (mit k_{0} ≡ 0), sodass n = k_{n}^{ℕ}. Wenn

M ⊧ Th(ℕ), so definieren wir f(n) = k_{n}^{M}. Behauptung f ist die gesuchte elementare Einbettung. Sei \overline{n} ein Tupel mit Komponenten aus ℕ. Dann ist \overline{n} = (k_{n_{1}}^{ℕ}, ..., k_{n_{m}}^{ℕ}) = \overline{k}ℕ ; \overline{n} und es gilt:

ℕ ⊧ φ(\overline{n}) ⇔ ℕ ⊧ φ(\overline{k}ℕ ; \overline{n}) ⇔ ℕ ⊧ φ(\overline{k}\overline{n})

⇔ φ(\overline{k}\overline{n}) ∈ Th(ℕ) = Th(M) ⇔ M ⊧ φ(\overline{k}\overline{n}) ⇔ M ⊧ φ(\overline{k}M ; \overline{n}) ⇔ M ⊧ φ(f(\overline{n}))

Korollar 3.9. (8.10) ℕ besitzt eine elementare Erweiterung M und ein Element 0 ≠ a ∈ M, so dass jede natürliche Zahl n ≠ 0 aus ℕ das Element a teilt.

Beweis: Wir definieren x|y ≡ ∃zx · z = y. Nun wählen wir ein neues Konstantensymbol c und setzen Σ = Th(ℕ) ∪ {k_{n}|c|n ∈ ℕ, n ≠ 0}. Behauptung: Jede endliche Teilmenge Σ_{0} ⊆ Σ besitzt ein Modell. Sei Σ_{0} = Σ_{0}^{∗} ∪ {k_{n_{1}}|c, k_{n_{2}}|c, ..., k_{n_{m}}|c} eine endliche Teilmenge von T h(ℕ). Sei n = ∏_{i=1}^{m} n_{i}. Dann ist (ℕ, n), wobei n die Interpretation von c sein soll, ein Modell von Σ_{0}. Nach dem Endlichkeitssatz existiert ein Modell (M, a) von Σ, wobei a die Interpretation von c ist. Dann gilt M ⊧ Th(ℕ) und M ⊧ k_{n}|c, d.h. M ⊧ k_{n}|a. Nach Lemma 8.9 kann man ℕ mit einer elementaren Unterstruktur von M identifizieren.

Korollar 3.10. (8.11) Es existiert ein Modell M ⊧ Th(ℕ), mit Elementen, die größer als alle k_{n} sind.

Beweis: Th(ℕ) ∋ ∀xy(x|y → x ≤ y) ⇒ M ⊧ k_{n} < a für alle n ∈ ℕ

Gödels Unvollständigkeitssatz

4.9 Rekursive Funktionen

Wir betrachten die Struktur der natürlichen Zahlen ℕ mit der Signatur σ(L) = (S, +, ·, 0, <). Dabei werden +, ·, 0 und 1 entsprechend unserer intuitiven Vorstellung interpretiert und S bezeichnet die Nachfolgerfunktion, d.h. S(x) = x + 1. f, g, h seien Funktionen von ℕ^{n} nach ℕ. P, Q, R seien Relationen auf ℕ^{n}. Relationen werden auch Prädikate genannt. U.a. zeigen wir in diesem Abschnitt, dass es kein Entscheidungsverfahren für ℕ ⊧ φ gibt.

Definition (Charakteristische Funktion) Wenn P ein n-stelliges Prädikat auf ℕ ist, so definieren wir die charakteristische Funktion ch_{P}

durch ch_{P} (\overline{a}) = \{ \begin{matrix}1 & , falls P (\overline{a}) \\ 0 & , falls ¬P (\overline{a}) \end{matrix} .

Definition (Projektion, const_{k}^{n}(·), μx(·))

1. p_{i}^{n}(a_{1}, ..., a_{n}) = a_{i} ist die i-te Projektion.

2. Für ein n-stelliges Tupel definieren wir const_{k}^{n}(\overline{a}) = k.

3. Wenn 𝔈(x) eine Eigenschaft von x ist, so sei μx(𝔈(x)) die kleinste natürlicher Zahl x mit 𝔈(x).

Definition (rekursive Funktion ((R1), (R2), (R3))) f ist eine rekursive Funktion, wenn man f durch endlich viele Anwendungen der folgenden Regeln erhält:

1. (R1) Die Funktionen p_{i}^{n}, +, ·, ch_{<} und const_{1}^{n} sind rekursiv.

2. (R2) Wenn h_{1}, ..., h_{m} und g rekursive Funktionen sind, so ist auch f(\overline{a}) = g(h_{1}(\overline{a}), ..., h_{m}(\overline{a})) eine rekursive Funktion.

3. (R3) Wenn g eine rekursive Funktion ist und für jedes Tupel \overline{a} von natürlichen Zahlen eine natürliche Zahl x mit g(\overline{a}, x) = 0 existiert, so ist f(\overline{a}) = μx(g(\overline{a}, x) = 0) eine rekursive Funktion.

Vorlesung am 19.12.2007 Churchs These Mit den rekursiven Funktionen haben wir den Begriff der Berechenbarkeit formalisiert. Begründung: Alle Versuche die Berechenbarkeit zu formalisieren (z.B. Turingmaschinen) haben zu äquivalenten Berechenbarkeitsbegriffen geführt.

Definition Ein Prädikat P (\overline{a}) über den natürlichen Zahlen ist rekursiv, wenn ch_{P} rekursiv ist.

Lemma 4.1. ((R4), (R5))

1. (R4) Wenn Q ein rekursives Prädikat und h_{1}, ..., h_{k} rekursive Funktionen sind, so ist auch das Prädikat P (\overline{a}) ⇔ Q(h_{1}(\overline{a}), ..., h_{k}(\overline{a})) rekursiv.

2. (R5) Wenn P ein rekursives Prädikat ist und ∀\overline{a}∃xP (\overline{a}, x) gilt, dann ist f(\overline{a}) = μxP (\overline{a}, x) eine rekursive Funktion.

Beweis:

1. ch_{P} (\overline{a}) = ch_{Q}(h_{1}(\overline{a}), ..., h_{k}(\overline{a})) ist nach (R2) rekursiv.

2. f(\overline{a}) = μx(ch_{<}(ch_{P} (\overline{a}, x), const_{1}^{n+1}(\overline{a}, x)) = 0) ist nach (R1), (R2) und (R3) rekursiv.

Beispiel Wir definieren f(a, b) = g(b, μx(h(a, x, a) = 0), b) für rekursive Funktionen g und h. Weiterhin gelte ∀a∃x(h(a, x, a) = 0). Wir wollen zeigen, dass f rekursiv ist: Sei h^{∗}(a, x) = h(p_{1}^{2}(a, x), p_{2}^{2}(a, x), p_{1}^{2}(a, x)). h^{∗} ist nach (R2) rekursiv und h^{∗}(a, x) = h(a, x, a). Dann ist auch h^{∗∗}(a) = μx(h^{∗}(a, x) = 0) rekursiv nach (R3). f(a, b) = (p_{2}^{2}(a, b), h^{∗∗}(p_{1}^{2}(a, b)), p_{2}^{2}(a, b)) ist rekursiv nach R2.

Lemma 4.2. ((R6)) (R6) Jede konstante Funktion ist rekursiv.

Beweis: Wir zeigen die Rekursivität von const_{k}^{n} induktiv über k.

1. k = 0

const_{0}^{n}(\overline{a}) = μx(p_{n+1}^{n+1}(\overline{a}, x) = 0)

2. k = 1

Folgt direkt aus (R1).

3. k → k + 1, k > 0

const_{k+1}^{n}(\overline{a}) = const_{k}^{n}(\overline{a}) + const_{1}^{n}(\overline{a})

Definition Für P und Q definieren wir:

1. ¬P (\overline{a}) genau dann, wenn nicht P (\overline{a}) gilt.

2. P (\overline{a}) ∧ Q(\overline{a}) genau dann, wenn P (\overline{a}) und Q(\overline{a}) erfüllt ist.

3. ∨, → und ↔ können wir analog definieren und als Abkürzungen von Konstrukten, bestehend aus ¬ und ∧, betrachten.

Lemma 4.3. ((R7))

1. (R7) Wenn P und Q rekursiv sind, so sind auch ¬P und P αQ mit α ∈ {∧, ∨, →, ↔} rekursiv.

2. (R8) Die Prädikate <, ≤, >, ≥ und = sind rekursiv.

Beweis:

1. ch_{¬P} (\overline{a}) = ch_{<}(ch_{P} (\overline{a}), const_{1}^{n}(\overline{a}))

2. Übung.

Nur (R1) bis (R7) benutzen.

Definition Es sei 𝔈(x) eine Eigenschaft von x. Dann verwenden wir μx_{x<b}(𝔈(x)) als Abkürzung für μx(𝔈(x) ∨ x = b).

Lemma 4.4. ((R9)) (R9) Wenn P rekursiv ist, so ist auch f(\overline{a}, b) = μ_{x<b}(P (\overline{a}, x)) rekursiv.

Beweis: Kein Beweis.

Definition Für eine Eigenschaft 𝔈 definieren wir ∃x_{x<b}(𝔈(x)) als Abkürzung für μx_{x<b}(𝔈(x)) < b und ∀x_{x<b}(𝔈(x)) als Abkürzung für ¬∃x_{x<b}(¬𝔈(x)).

Lemma 4.5. ((R10)) (R10) Wenn R rekursiv ist, so sind auch P und Q rekursiv, wobei P und Q wie folgt definiert sind:

1. P (\overline{a}, b) genau dann, wenn ∃x_{x<b}R(\overline{a}, x)

2. Q(\overline{a}, b) genau dann, wenn ∀x_{x<b}R(\overline{a}, x)

(ohne Beweis) 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42

Definition

a ˙−b = \{ \begin{matrix}a − b & , wenn a ≥ b \\ 0 & , sonst \end{matrix}

Lemma 4.6. ((R11), (R12))

1. (R11) Die Funktion ˙− ist rekursiv. (a ˙−b = μx(b + x = a ∨ a < b))

2. (R12) g_{1}, ..., g_{k} seien rekursive Funktionen, d.h. R_{1}, ..., R_{k} seien rekursive Prädikate, so dass immer genau ein R_{i} zutrifft. Dann ist f(\overline{a}) = g_{i}(\overline{a}) falls R_{i}(\overline{a}) zutrifft rekursiv.

3. Q_{1}, ..., Q_{k} seien rekursive Prädikate und R_{1}, ..., R_{k} wie in (R12). Dann ist P (\overline{a}) ⇔ Q_{i}(\overline{a}) falls R_{i}(\overline{a}) ebenfalls rekursiv.

Beweis: Kein Beweis.

Lemma 4.7. (Gödel (9.1)) Es gibt eine binäre rekursive Funktion β mit β(a, i) ≤ a ˙−1 für alle a und i und für alle a_{0}, ..., a_{n−1} existiert ein a mit β(a, i) = a_{i} für i < n.

Beweis: Sei Div(a, b) das (rekursive) Prädikat ∃x_{x≤a}(a = bx) (a ist durch b dividierbar) und RP (a, b) das (ebenfalls rekursive) Prädikat a ≠ 0 ∧ b ≠ 0 ∧ ∀x(Div(ax, b) → Div(x, b)), d.h. der größte gemeinsame Teiler von a und b ist 1.

1. RP (a, b) → RP (b, a)

Beweis:

Es gelte RP (a, b) und Div(bx, a), d.h. bx = ay für ein y. Dann gilt Div(ay, b). Wegen RP (a, b) gilt Div(y, b), d.h. y = bz. Damit folgt bx = abz, also x = az. Es folgt also Div(x, a).

2. Seien a_{1}, ..., a_{n}, b_{1}, ..., b_{m} verschieden von 0 und 1. Weiterhin gelte RP (a_{i}, b_{j}) für alle i und j. Dann existiert ein c mit Div(c, a_{i}) für alle i und ¬Div(c, b_{j}) für alle j. Beweis: Wir führen eine Induktion über n durch. Wenn n = 0, so setzen wir c = 1. Wenn n ≠ 0, div(c′, a_{i}) für 1 ≤ i < n und ¬Div(c′, b_{j}) für alle j, dann erfüllt c = c′a_{n} das Verlangte.

3. k ≠ 0 ∧ z ≠ 0 ∧ Div(z, k) → RP (1 + (j + k)z, 1 + jz)

Beweis: Zunächst machen wir die Beobachtung Div(x + xjz, z) → Div(x, z). Weiterhin gilt RP (1 + jz, z) und nach 1. RP (z, 1 + jz). Wir nehmen nun Div(x+x(j +k)z, 1+jz) an. Es folgt Div(xkz, 1+jz), also Div(xk, 1+jz). Nach Voraussetzung gilt Div(z, k) und damit Div(xz, 1 + jz) RP (z, 1 + jz) impliziert nun Div(x, 1 + jz).

4. Wir definieren OP (a, b) = (a + b)^{2} + a + 1. Dann gilt OP (a, b) = OP (a′, b′) → a = a′ ∧ b = b′. Beweis: a + b < a′ + b′ ist unmöglich, da sonst OP (a, b) ≤ (a + b + 1)^{2} ≤ (a′ + b′)^{2} < OP (a′, b′). Analog kann nicht a + b > a′ + b′ gelten, also folgt a + b = a′ + b′. Es folgt

\begin{aligned}a & = (a + b)^{2} + a + 1 − (a + b)^{2} − 1 = OP (a, b) − (a + b)^{2} − 1 \\ & = OP (a′, b′) − (a′ + b′)^{2} − 1 = (a′ + b′)^{2} + a′ + 1 − (a′ + b′)^{2} − 1 = a′ \end{aligned}

und damit auch b = (a + b) − a = (a′ + b′) − a′ = b′.

5. Wir definieren β(a, i) = μx_{x≤a ˙−1}∃y_{y<a}∃z_{z<a}(a = OP (y, z) ∧ Div(y, 1 + (OP (x, i) + 1)z)). β(a, i) ist offensichtlich rekursiv und es gilt β(a, i) ≤ a ˙−1. Es bleibt also noch zu zeigen, dass für alle a_{0}, ..., a_{n−1} ein a existiert, sodass β(a, i) = a_{i} gilt. Seien n und a_{0}, ..., a_{n−1} gegeben. Gesucht ist ein a mit β(a, i) = a_{i}. Sei c = 1 + max{OP (a_{i}, i)|i < n} und z eine Zahl, die durch alle Zahlen, die nicht größer als c sind, dividierbar ist, z.B. z = c!. Für j < l ≤ c folgt aus 3. mit k = l−j die Eigenschaft RP (1+jz, 1+lz). Nach 2. existiert ein y, sodass dieses für jedes j < c genau dann durch 1 + jz teilbar ist, wenn j = OP (a − i, i) + 1 für ein i mit 0 ≤ i < n existiert. Sei a = OP (y, z). Nach 4. sind y und z die einzigen Zahlen mit a = OP (y′, z′). Zu zeigen ist, dass a_{i} das kleinste x mit Div(y, 1 + (OP (x, i) + 1)z) ist. Nach Definition von y gilt Div(y, 1 + (OP (a_{i}, i) + 1)z). Wäre x < a_{i}, dann OP (x, i) ≤ OP (a, i) < c. OP (x, i) ist kein OP (a_{j}, j) nach 4.. Also teilt Definition 1 + (OP (x, i) + 1)z nicht y, was einen Widerspruch darstellt.

Lemma 4.8. Aus β(a, i) ≤ a ˙−1 folgt 6. β(0, i) = 0 und

7. a ≠ 0 impliziert β(a, 1) < a. Beweis: Beweis? Ja ... ähm ... nun ja ... also ... ach nee, lieber nicht.

Definition (Folgennummer) Jedem n-Tupel (a_{1}, ..., a_{n}) wird jetzt die kleinste Zahl a zugeordnet, so dass β(a, 0) = n und β(a, i) = a_{i} für 1 ≤ i ≤ n. a = ⟨a_{1}, ..., a_{n}⟩ existiert nach Lemma 9.1 mit a = 0 für die leere Folge. a heißt Folgennummer (bzw. Sequenzennummer) von a_{1}, ..., a_{n}. ⟨a_{1}, ..., a_{n}⟩ = μx(β(x, 0) = n ∧ ⋀_{k=1}^{n} β(x, k) = a_{k}) Wenn n fixiert ist, so ist ⟨a_{1}, ..., a_{n}⟩ eine rekursive Funktion. Rekursiv sind auch lh(a) = β(a, 0) und (a)_{i} = β(a, i + 1). Es gilt also lh(a) = n und (a)_{i} = a_{i} (i < n) für a = ⟨a_{0}, ..., a_{n−1}⟩. Wir verwenden nun die Abkürztung (a)_{i,j} = ((a)_{i})_{j}. Nach (7) gilt nun

8. a ≠ ⟨⟩ → lh(a) < a ∧ (a)_{i} < a.

Definition (Menge der Folgennummern, Seq) Seq(a) ⇔ ∀x_{x<a}(lh(x) ≠ lh(a) ∨ ∃i_{i<lh(a)}((x)_{i} ≠ (a)_{i})) Die Menge der Folgennummern Seq ist also rekursiv.

Lemma 4.9. in(a, i) ist rekursiv.

Beweis: Wir setzen in(a, i) = μx_{x<a}(lh(x) = j ∧ ∀j_{j<i}((x)_{j} = (a)_{j})) , d.h. in (⟨a_{1}, ..., a_{n}⟩, i) = ⟨a_{1}, ..., a_{i}⟩.

Definition (Verkettung) Wir definieren die Verkettung durch ⟨a_{1}, ..., a_{n}⟩ ∗ ⟨b_{1}, ..., b_{m}⟩ = ⟨a_{1}, ..., a_{n}, b_{1}, ..., b_{m}⟩.

Lemma 4.10. Die Verkettung ∗ ist rekursiv.

Beweis: a ∗ b = μx(lh(x) = lh(a) + lh(b) ∧ ∀i_{i<lh(a)}((x)_{i} = (a)_{i}) ∧ ∀j_{j<lh(b)}((x)_{lh(a)+j} = (b)_{j}))

Definition Wir definieren

9. Für eine n-stellige Funktion f definieren wir ⟨f⟩(a) = f((a)_{0}, ..., (a)_{n−1}).

Lemma 4.11. Es gilt

10. f(a_{1}, ..., a_{n}) = ⟨f⟩(⟨a_{1}, ..., a_{n}⟩).

Beweis: Mal was für Insider: Dies ist offensichtlich eine nicht weiter tiefsinnige Trivialität - es passiert ja nichts. *g*

Definition Für Prädikate definieren wir

11. ⟨P ⟩(a) ⇔ P ((a)_{0}, ..., (a)_{n−1}).

Lemma 4.12. Es gilt

12. P (a_{1}, ..., a_{n}) = ⟨P ⟩(⟨a_{1}, ..., a_{n}⟩).

Beweis: Scharf hingucken reicht.

Lemma 4.13. 1. f rekursiv ⇔ ⟨f⟩ rekursiv.

2. P rekursiv ⇔ ⟨P ⟩ rekursiv.

Beweis: Kein Beweis.

Lemma 4.14. Sei f eine n + 1-stellige Funktion und n ≠ 0. \overline{f}(0, \overline{a}) = 0 und (13) \overline{f}(a, \overline{a}) = ⟨f(0, \overline{a}), f(1, \overline{a}), ..., f(a − 1, \overline{a})⟩ für a > 0. Dann ist \overline{f} genau dann rekursiv, wenn f rekursiv ist.

Beweis:

1. \overline{f}(a, \overline{a}) = μx(lh(x) = a ∧ ∀i_{i<a}((x)_{i} = f(i, \overline{a})))

2. f(a, \overline{a}) = (\overline{f}(a + 1, \overline{a}))_{a}

Definition (Induktive Definition, Folgennummer eines Anfangsstücks) f(a, \overline{a}) ist induktiv definiert, falls f(a, \overline{a}) = g(\overline{f}(a, \overline{a}), \overline{a}, a). Weiterhin definieren wir in(x, i) als die Folgennummer des Anfangsstücks der Länge i von x.

Lemma 4.15. (R14) Wenn f induktiv wie oben definiert und g rekursiv ist, dann ist auch f rekursiv.

Beweis: Sei h(a, \overline{a}) = μx(Seq(x) ∧ lh(x) = a ∧ ∀i_{i<a}((x)_{i} = g(in(x, i), \overline{a}, i). Dann ist h = \overline{f} und f(a, \overline{a}) = g(h(a, \overline{a}), \overline{a}, a).

Beispiel f(a, b) = b^{a} ist rekursiv: f(0, b) = 1, f(a + 1, b) = f(a, b) · b.

Vorlesung am 07.01.2008

Definition Ein Prädikat P heißt rekursiv aufzählbar, wenn P (\overline{a}) ⇔ ∃xQ(\overline{a}, x) und Q rekursiv ist.

Vorlesung am 09.01.2008

Definition Sei N die folgende Menge von Aussagen:

1. (N1) ∀x(Sx ≠ 0)

2. (N2) ∀xy(Sx = Sy → x = y)

3. (N3) ∀x(x + 0 = x)

4. (N4) ∀xy(x + Sy = S(x + y))

5. (N5) ∀x(x · 0 = 0)

6. (N6) ∀xy(x · Sy = (x · y) + y

7. (N7) ∀x(¬x < 0)

8. (N8) ∀xy(x < Sy ↔ x < y ∨ x = y)

9. (N9) ∀xy(x < y ∨ x = y ∨ y < x)

Bemerkung N ist endlich und ℕ ⊧ N.

Definition (Funktion Num, Nummeral) Num(0) = ⟨SN(0)⟩ = ⌜0⌝ Num(a + 1) = ⟨SN(S), Num(a)⟩ Die Terme 0, S(0), S(S(0)), ... heißen Nummerale. k_{n} sei das Nummeral mit n Vorkommen von S. Es gilt Num(a) = ⌜k_{a}⌝.

Definition (repräsentierbare Funktion (durch Formel)) Sei f eine n-stellige Funktion. Die Formel φ(x_{1}, ..., x_{n}, y) repräsentiert die Funktion f, wenn für alle natürlichen Zahlen a_{1}, ..., a_{n} gilt: ⊢_{N} φ(k_{a_{1}}, ..., k_{a_{n}}, y) ↔ y = k_{f(a_{1},...,a_{n})}. Existiert für f eine solche Formel φ, so ist f repräsentierbar.

Definition (repräsentierbares Prädikat) Ein n-stelliges Prädikat P wird durch die Formel φ(x_{1}, ..., x_{n}) repräsentiert, wenn (¬)P (a_{1}, ..., a_{n}) die Ableitbarkeit ⊢_{N} (¬)φ(k_{a_{1}}, ..., k_{a_{n}}) impliziert. Ein Prädikat, für welches eine derartige Formel existiert, heißt repräsentierbar.

Definition (repräsentierbare Funktion (durch Term)) Ein Term t(x_{1}, ..., x_{n}) repräsentiert die Funktion f(x_{1}, ..., x_{n}), wenn ⊢_{N} t(k_{a_{1}}, ..., k_{a_{n}}) = k_{f(a_{1},...,a_{n})} für alle a_{1}, ..., a_{n} gilt, d.h. f(x_{1}, ..., x_{n}) wird durch die Formel f(x_{1}, ..., x_{n}) = y repäsentiert.

Vorlesung am 14.01.2008

Vorlesung am 16.01.2008

Beweis:

3. (R3) Sei g(x_{1}, ..., x_{n}, y) repräsentierbar und f(a_{1}, ..., a_{n}) = μx(g(a_{1}, ..., a_{n}, x) = 0), wobei für jede Folge a_{1}, .., a_{n} die Existenz eines b mit g(a_{1}, ..., a_{n}, b) = 0 gesichert ist. Zu zeigen ist nun, dass f repräsentierbar ist. Sei b minimal zu a_{1}, ..., a_{n} gewählt, φ(x_{1}, ..., x_{n}, y, z) repräsentiere g und w sei eine neue Variable. Dann wird f durch die folgende Formel repräsentiert: ψ(x_{1}, ..., x_{n}, y) ≡ φ(x_{1}, ..., x_{n}, y, 0) ∧ ∀w(w < y → ¬φ(x_{1}, ..., x_{n}, w, 0)) φ′ und ψ′ erhalten wir, indem wir in φ bzw. ψ die Vorkommen von x_{i} durch k_{a_{i}} ersetzen. Zu zeigen ist nun, dass ⊢_{N} ψ(y) ↔ y = k_{b}, d.h. ⊢_{N} φ′(y_{0}) ∧ ∀w(w < y → ¬φ′(w, 0)) ↔ k_{b}. Da φ(x_{1}, ..., x_{n}, y, z) g repräsentiert, gilt ⊢_{N} φ′(k_{i}, z) ↔ z = k_{c_{i}}, wobei c_{i} = g(a_{1}, ..., a_{n}, i). Also haben wir ⊢_{N} φ′(k_{i}, 0) ↔ k_{0} = k_{c_{i}}. Nach Annahme folgt c_{i} ≠ 0 für i < b. Da = repräsentierbar ist, gilt ⊢_{N} k_{c_{i}} ≠ k_{0}, also ⊬_{N} φ′(k_{i}, 0) für i < b. Nach Wahl ist c_{b} = 0. Da = repäsentierbar, gilt ⊢_{N} k_{c_{b}} = k_{0}, also ⊢_{N} φ′(k_{b}, 0). Die Vorausetzung von Lemma 10.5 sind somit erfüllt und wir erhalten ⊢_{N} φ′(y, 0) ∧ ∀w(w < y → ¬φ′(w, 0)) ↔ y = k_{b}, d.h. ⊢_{N} ψ′(y) ↔ y = k_{b}

Korollar 4.1. (10.6) P rf_{N}(x) und P r_{N}(x, y) sind repräsentierbare Prädikate.

4.10 Der Unvollständigkeitssatz

Definition Für ein zweistelliges Prädikat P definieren wir das Prädikat P_{(b)} durch P_{(b)}(a) ⇔ P (a, b).

Lemma 4.16. (Diagonallemma (G. Cantor)) Wenn P (a, b) ein zweistelliges Prädikat und Q(a) ⇔ ¬P (a, a), dann ist Q(a) von allen Prädikaten P_{(b)} verschieden.

Beweis: Ann. Q(a) = P_{(b)}(a) für alle a. Dann gilt P (b, b) = P_{(b)}(b) = Q(b) = ¬P (b, b), was einen Widerspruch darstellt.

Bemerkung Wir verwenden die Signatur σ(L) = (S, +, ·, 0, <). Weiterhin sei T eine Theorie, d.h. T besitzt Modelle und ist deduktiv abgeschlossen (d.h T ⊧ φ ⇒ φ ∈ T für alle Aussagen φ). Seien N ⊆ Σ ⊆ T, φ(z) ∈ L, T = Abl(Σ) und E(φ) = {n ∈ ℕ| ⊢_{Σ} φ(k_{n})}. Behauptung: Wenn A ⊆ ℕ eine rekursive Teilmenge ist, dann existiert eine Formel φ(z), so dass A = E(φ). Nach dem Repräsentationstheorem 10.3. existiert für A eine Formel φ(z), die A repräsentiert. Zu zeigen ist A = E(φ). Wenn a ∈ A, so gilt ⊢_{N} φ(k_{a}), also ⊢_{Σ} φ(k_{a}), d.h. a ∈ E(φ). Wenn a ∉ A, so gilt ⊢_{N} ¬φ(k_{a}), also ⊢_{Σ} ¬φ(k_{a}), d.h. a ∉ E(φ).

Wir definieren P (a, b) ⇔ T hm_{Σ}(Sub(b, ⌜z⌝, \underbrace{Num(a)}_{=⌜k_{a}⌝})).

Wenn b = ⌜φ⌝, so P_{(b)} = E(φ), denn P (a, ⌜φ⌝) besagt, dass ein Σ-Beweis für φ(k_{a}) existiert. Wenn Q(a) ⇔ ¬P (a, a), dann ist Q(a) von allen P_{(b)} verschieden, also ist Q(a) von allen E(φ) verschieden. Damit ist Q(a) nicht rekursiv. Aus Q(a) ⇔ ¬T hm_{Σ}(Sub(a, ⌜z⌝, Num(a))) folgt, dass T hm_{Σ} nicht rekursiv ist, weil Sub, Num und ¬ rekursiv sind. Also ist T unentscheidbar.

Satz 4.1. (Churchs Theorem (11.2)) Wenn T eine Theorie ist, die N erweitert, dann ist T unentscheidbar. Damit sind z.B. N^{⊧}, P A und T h(N) unentscheidbar. T hm_{N} ist ein Beispiel für eine rekursiv aufzählbare Menge, die nicht rekursiv ist.

Beweis: Vorherige Bemerkung.

Satz 4.2. (Negationstheorem (11.3)) Ein Prädikat P ist genau dann rekursiv, wenn P und ¬P rekursiv aufzählbar sind.

Beweis: Wenn P rekursiv ist, so sind P und auch ¬P rekursiv und damit auch rekursiv aufzählbar. Nun seien P und ¬P rekursiv aufzählbar, d.h. es existieren rekursive Prädikate Q(y, x) und R(y, x), sodass P (a) ⇔ ∃xQ(a, x) und ¬P (a) ⇔ ∃R(a, x). Da P (a) oder ¬P (a) gilt, existiert ein c mit Q(a, c) ∨ R(a, c), d.h. f(a) = μx(Q(a, x) ∨ R(a, x)) ist eine rekursive Funktion. Somit ist P (a) ⇔ Q(a, f(a)) ebenfalls rekursiv.

Definition (rekursiv axiomatisierbar) T ist rekursiv axiomatisierbar, wenn T = Abl(Σ) gilt und NLAx_{Σ} rekursiv ist.

Korollar 4.2. (11.4) Wenn T rekursiv axiomatisierbar und vollständig ist, dann ist T entscheidbar.

Beweis: Sei T = Abl(Σ) und NLAx_{Σ} rekursiv. Nach Theorem 10.1 ist T hm_{Σ} rekursiv aufzählbar. Wegen der Vollständigkeit ist auch ¬T hm_{Σ} rekursiv aufzählbar. Es gilt ¬T hm_{Σ}(⌜φ⌝) ⇔ T hm_{Σ}(⌜¬φ⌝). Nach Lemma 11.3 ist T hm_{Σ} rekursiv, d.h. T entscheidbar.

Satz 4.3. (K. Gödel: Unvollständigkeitssatz (11.5)) Wenn T eine rekursiv axiomatisierbare Erweiterung von N ist, dann ist T nicht vollständig.

Beweis: Wäre T vollständig, so wäre T entscheidbar. Dies ist jedoch ein Widerspruch zu 11.2.

Vorlesung am 21.01.2008

Korollar 4.3. (11.6) Für die angegebene Signatur ist die elementare Logik unentscheidbar, d.h. die Menge der Gödelzahlen der allgemeingültigen Aussagen in dieser Signatur ist nicht rekursiv.

Beweis: Wir nehmen an, dass wir ein Entscheidungsverfahren für ⊢ φ hätten. ⋀ N sei die Konjunktion der 9 Axiome aus N. Nach Deduktionstheorem erhalten wir ⊢_{N} φ ⇔ ⊢ ⋀ N → φ. Dies würde uns ein Entscheidungsverfahren für N liefern, was einen Widerspruch zu Churchs Theorem darstellt.

Bemerkung (Matijasevič)

1. Das Problem der Lösbarkeit von ganzzahligen mehrstelligen Polynomgleichungen ist nicht entscheidbar.

2. Die Existenzaussagen von T h(ℕ) sind nicht entscheidbar.

3. Für jede rekursiv aufzählbare Menge A ⊆ ℕ existiert ein Polynom p(z_{1}, …, z_{n}) mit Koeffizienten z_{1}, …, z_{n} ∈ ℤ so dass A = {m ∈ ℕ|∃a_{1}, …, a_{n} : p(a_{1}, …, a_{n}) = m}. (Leider sind diese Polynome für sehr viele z_{1}, …, z_{n} negativ. Daher ist auch das sogenannte Primzahlpolynom nicht sehr hilfreich, um Primzahlen zu finden.)

Wesentliche Vorarbeiten stammen von Julia Robinson.

Mengenlehre (für den täglichen Gebrauch)

5.12 Wohlordnungen

Definition (Ordnung) Eine Struktur M der Signatur <, wobei < eine zweistellige Relation ist, heißt partielle Ordnung, wenn

1. M ⊧ ∀x(¬x < x) (Irreflexivität)

2. M ⊧ ∀xyz(x < y ∧ y < z → x < z) (Transitivität)

Wenn weiterhin

3. M ⊧ ∀xy(x < y ∨ x = y ∨ y > x (Totalität)

gilt, dann heißt M (lineare bzw. totale) Ordnung (auch Kette).

Ziel Unser Ziel ist die Einführung von Ordnungsstrukturen, transfiniter Induktion und Kardinalzahlen. Vorgehen: Wir bewegen uns in einem Mengenuniversum, d.h. einer großen Struktur V mit der Signatur ⟨∈⟩, wobei ∈ zweistellig ist und für die Elementbeziehung steht. Wir haben also x ∈ y genau dann, wenn x ein Element von y ist. Die Elemente von V sind Mengen. V bildet den Rahmen für die mathematische Arbeit. Normalerweise nimmt man an, dass die Struktur ⟨V, ∈⟩ den Axiomen der Zarmelo-Fraenkelschen Mengenlehre (ZF) und dem Auswahlaxiom AC (Axiom of Choice) genügt. Wir fassen diese auch zu ZF C zusammen.

Definition (Zusammenfassung von Mengen, Klassen) Wichtig am Mengenbegriff ist das Zusammenfassen von Mengen mit einer Eigenschaft E. Nach unserem Sprachgebrauch handelt es sich um definierbare Mengen in V^{n} mit Parametern. Diese nennt man Klassen. Manche Klassen sind wieder Mengen.

Beispiel (Klassen)

1. {x, y} = {z|z = x ∨ z = y} (Paarmenge)

2. ⋃ x = {z|∃y(z ∈ y ∧ y ∈ x} (Vereinigung)

3. P(x) = {z|z ⊆ x} (Potenzmenge)

wobei z ⊆ x, wenn ∀y(y ∈ z → y ∈ x).

Wir schreiben z ⊂ x, wenn z ⊆ x und z ≠ x. Klassen, die Mengen sind, sind intuitiv gesehen “klein”. Echte Klassen sind groß, z.B. {x|x = x} = dom(V).

Man kann nicht erlauben, dass alle Klassen Mengen sind! Dafür betrachte man z.B. die Russellsche Antinomie: Sei X = {x|x ∉ x}. Wäre X eine Menge und X ∈ X, so gilt nach Definition X ∉ X. Auch X ∉ X führt nach Definition auf den Widerspruch X ∈ X.

Bisher haben wir von außen auf ⟨V, ∈⟩ geschaut. Nun soll aber ⟨V, ∈⟩ der Rahmen unserer Untersuchungen sein, d.h. V ist eine Klasse. Wir lassen jetzt also zu, dass es auch Strukturen mit Klassen als Grundbereich gibt. Speziell erlauben wir dies für lineare Ordnungen ⟨V, <⟩.

Definition (Anfangsstück, Abschnitt) Ein Anfangsstück einer linearen Ordnung ⟨V, <⟩ ist eine Teilklasse von X, die mit a ∈ X auch alle b ∈ X mit b < a enthält. Ein Abschnitt hat die Form X_{a} = {x ∈ X|x < a} für ein a. ⟨V, <⟩ genügt der Abschnittsbedingung, wenn alle X_{a} für a ∈ X Mengen sind. Wenn X Menge ist, dann ist die Abschnittsbedingung erfüllt.

Definition (Wohlordnung) Eine Wohlordnung ist eine lineare Ordnung, die der Abschnittsbedingung genügt und in der jede nichtleere Teilklasse ein kleinstes Element besitzt. Wenn der Grundbereich eine Menge ist, so sprechen wir von einer wohlgeordneten Menge.

Beispiel (Wohlordnung)

1. Endliche Ordnungen sind Wohlordnungen.

2. Die Ordnung der natürlichen Zahlen ist eine Wohlordnung.

3. X = {x ∈ ℚ|x ≥ 0} ist keine Wohlordnung, da z.B. die Menge Y = {x ∈ X|x > 0} kein kleinstes Element besitzt.

Bemerkung Wenn f ein Homomorphismus zwischen linearen Ordnungen ist, dann gilt genau dann a < b, wenn f(a) < f(b), d.h. f ist eine Einbettung: Nach Definition des Homomorphismus’ gilt a < b ⇒ f(a) < f(b). Sei nun f(a) < f(b). Wenn b < a, so gilt f(b) < f(a) und wegen Transitivität f(a) < f(a), was einen Widerspruch zur Irreflexivität darstellt. Mit a = b (also f(a) = f(b)) erhalten wir diesen Widerspruch ebenfalls. Also bleibt wegen a < b ∨ a = b ∨ a > b nur noch a < b.

Bemerkung

1. Teilordnungen von Wohlordnungen sind wieder Wohlordnungen.

2. Eine lineare Ordnung mit der Abschnittsbedingung ist genau dann eine Wohlordnung, wenn es keine unendlichen absteigenden Ketten gibt, d.h. a_{0} > a_{1} > . . .. Man sagt, dass die Ordnung fundiert ist.

3. Die leere Menge ist immer Anfangsstück.

4. Ein Anfangsstück einer Wohlordnung ist entweder ein Abschnitt oder X selbst.

5. Jede Wohlordnung ist ordnungsisomorph zu der durch Inklusion geordneten Klasse der Abschnitte.

Beweis:

4. Sei I ein Anfangsstück von X, I ≠ X und a das kleinste Element von X \ I. Sei b ∈ X. Wenn b < a, so b ∈ I, sonst wäre a nicht das kleinste Element.

Wenn a ≤ b, so b ∉ I, da sonst a ∈ I.

⇒ X_{a} = I

Vorlesung am 23.01.2008

Lemma 5.1. (12.1)

1. Wenn f Homomorphismus einer Wohlordnung ⟨X, <⟩ in sich selbst ist, so gilt f(x) ≥ x für alle x ∈ X.

2. Eine Wohlordnung kann nicht isomorph zu einem ihrer Abschnitte sein.

Beweis:

1. Wäre f(x) < x für ein x aus X, dann erhielten wir eine unendliche Folge von strikt monoton absteigenden Elementen in X: f^{3}(x) < f^{2}(x) < f(x) < x. (Aus f(x) < x folgt f^{2}(x) < f(x), weil f ein Homomorphismus ist. Dies können wir dann iterieren, um f^{n}(x) < f^{n−1}(x) zu erhalten.)

⇒ Widerspruch.

2. Wäre f : X → X_{a} ein Isomorphismusm, dann hätten wir f(a) < a, was einen Widerspruch zu 1. darstellt.

Satz 5.1. (Induktionsprinzip (12.2)) Sei ⟨X, <⟩ eine Wohlordnung und P eine Eigenschaft für Elemente von X. Wenn für alle a ∈ X die Bedingung

1. Hat jedes b < a in X die Eigenschaft P, so auch a.

gilt, so haben alle Elemente von X die Eigenschaft P.

Beweis: Annahme: Es gibt eine Menge ∅ ≠ Y ⊆ X von Elementen, welche die Eigenschaft P nicht erfüllen. Weil es in dieser Menge keine unendliche absteigende Folge geben kann, muss es ein kleinstes Element a geben, das P nicht erfüllt. Dies ist jedoch ein Widerspruch zu der vorausgesetzten Eigenschaft von P.

Situation Sei ⟨X, <⟩ eine Wohlordnung, W eine Klasse und F eine Rekursionsvorschrift. Gesucht ist eine Funktion f : X → W, sodass f die folgende Eigenschaft hat: Wenn f_{a} : X_{a} → W gegeben ist, so haben wir f(a) = F (f_{a}).

Satz 5.2. (Rekursionsprinzip (12.3)) Sei ⟨X, <⟩ eine Wohlordnung und W eine beliebige Klasse. Für jedes a ∈ X sei F_{a} die Klasse aller Funktionen von X_{a} nach W. Für jede Funktion F : ⋃_{a∈X} F_{a} → W gibt es eine eindeutig bestimmte Funktion f, welche die Rekursionsbedingung f(a) = F (f|_{X_{a}}) für alle a ∈ X erfüllt.

Beweis: (Hinweis: Die Funktionen aus F_{a} kann man als Teilklassen von X_{a} × W ansehen.) Sei F = ⋃_{a∈X}{g ∈ F_{a}|∀b < a : g(b) = F (g|_{X_{b}})}. Wir zeigen zunächst, dass aus jedem F_{a} höchstens eine Funktion in der Vereinigung F enthalten ist. Daraus folgt dann auch die Eindeutigkeit der gesuchten Funktion f. Behauptung(en): Für jedes a ∈ X enthält F ∩ F_{a} höchstens eine Funktion. Für alle g, h ∈ F gilt g ≤ h oder h ≤ g, wobei hier ≤ die Fortsetzung von Funktionen bezeichne.

Beweis der Behauptung(en): Die erste Behauptung folgt sofort aus der zweiten. (Seien g_{1}, g_{2} ∈ F ∩ F_{a}. Dann gilt g_{1} ≤ h und g_{2} ≤ h für h ∈ F ∩ F_{b} und a ≤ b. Also erhalten wir g_{1} = g_{2}.) Beweisen wir also die zweite Behauptung. Sei g ∈ F ∩ F_{a} und h ∈ F ∩ F_{c}, wobei a ≤ c. Es gilt nun g = h|_{X_{a}}. (Sonst existierte ein kleineste b < a in X mit g(b) ≠ h(b). Damit erhielten wir g|_{X_{b}} = h|_{X_{b}}, da b minimal mit g(b) ≠ h(b). Nach Definition von F gilt g(b) = F(g|_{X_{b}}) = F(h|_{X_{b}}) = h(b), was einen Widerspruch darstellt.)

Es bleibt also die Existenz zu zeigen (Wir nutzen nun das Induktionsprinzip aus Satz 12.2.). (Induktionsvoraussetzung:) Für jedes b < a ist F ∩F_{b} ≠ ∅, d.h. es existieren Funktionen f_{b}:X_{b} →W mit f_{b}(c) = F (f_{b}|_{X_{c}}) für c < b. Mit der vorherigen Behauptung über die Eindeutigkeit gilt nun f_{b_{1}} ≤ f_{b_{2}} für b_{1} < b_{2} < a. Es ist nun zu zeigen, dass ein f_{a} ∈ F ∩ F_{a} existiert.

1. Fall (a ist eine Limeszahl): Für jedes c < a existiert ein d mit c < d < a.

Dann definieren wir f_{a} = ⋃_{c<a} f_{c} ∈ F_{a} ∩ F.

Das funktioniert, da sich die f_{c} fortsetzen.

2. Fall (a ist eine Nachfolgerzahl): Es existiert c < a sodass für alle d < a auch d ≤ c gilt.

Nach Vorausetzung existiert f_{c} ∈ F_{c} ∩ F sodass X_{a} = X_{c} ∪ {c} mit f_{a} = f_{c} für d < c und f_{a}(c) = F (f_{c}).

Dann gilt f_{a} ∈ F_{a} ∩ F.

Nach 12.2 ist f somit auf ganz X definiert.

Definition (Auswahlaxiom) Zu jeder Menge X von nichtleeren disjunktion Mengen gibt es eine Menge, die aus jedem Element von X genau ein Element enthält. X könnte z.B. die Menge der Äquivalenzklassen einer Äquivalenzrelation sein. Das Auswahlaxiom würde uns dann die Existenz eines Repräsentantensystems garantieren.

Satz 5.3. (12.4) Die folgenden Aussagen sind äquivalent:

1. Auswahlaxiom

2. Jede Menge X lässt sich wohlordnen, d.h. es existiert eine Teilmenge < von X × X, die eine Wohlordnung ist.

3. Zornsches Lemma:

Wenn jede Kette in einer partiell geordneten Menge X eine obere Schranke in X besitzt, so existiert ein maximales Element in X.

Beweis: Kein Beweis.

5.13 Ordinalzahlen

ZFC enthält das Fundierungsaxiom ∀z(z ≠ ∅ → ∃x(x ∈ z ∧ x ∩ z = ∅)). ⇒ In keiner Menge existieren Kreise oder absteigenden Ketten bezüglich der Relation ∈. Nachweis, dass keine Kreise (der Länge 1) existieren, d.h. es gilt ¬∃x(x ∈ x): Sonst würde für das einzige x in der Menge z = {x} sofort x ∩ {x} = x gelten, d.h. es gäbe kein y in {x} mit {x} ∩ y = ∅, was einen Widerspruch zum Fundierungsaxiom darstellt.

Definition Eine Klasse heißt transitiv, falls für alle x ∈ y ∈ X auch x ∈ X gilt. (Wir bezeichnen Klassen mit großen und Mengen mit kleinen Buchstaben.)

Lemma 5.2. Für eine Klasse X sind folgende Bedingungen äquivalent:

1. X ist transitiv.

2. x ∈ X folgt x ⊆ X.

3. Aus Y ⊆ X folgt ⋃ Y ⊆ X.

Beweis:

1. (1) ⇔ (2): erledigt

2. (2) ⇒ (3)

Sei y ∈ ⋃ Y.

Dann gilt y ∈ y′ ∈ Y ⊆ X.

⇒ y ∈ y′ ∈ X ⇒ y ∈ y′ ⊆ X ⇒ y ∈ X

3. (3) ⇒ (2)

Sei x ∈ X. Mit (3) erhalten wir mit x ∈ X ⊆ X auch x ⊆ ⋃ X ⊆ X.

Bemerkung X ist das größte Element in X ∪ {X} bezüglich ∈, falls X transitiv ist.

Lemma 5.3. (13.1) Sei X eine transitive Menge, auf der ∈ eine partielle Ordnung (bzw. Wohlordnung) ist. Dann ist auch X ∪{X} eine transitive Menge auf der ∈ eine partielle Ordnung (bzw. Wohlordnung) ist.

Beweis: Sei y ∈ X ∪ {X}. Dann gilt y ∈ X oder y = X, d.h. y ⊆ X (da X transitiv ist) oder y = X ⊆ X. Die Irreflexivität x ∉ x folgt aus dem Fundierungsaxiom. Transitivität von ∈ auf X ∪ {X}: Seien x ∈ y ∈ z in X ∪ {X}. Wenn alle Elemente von X sind, dann ist die Transitivität klar. Sonst bleibt x, y ∈ X, z = X, d.h. x ∈ X = z. Da X ein ∈-maximales Element ist, bleiben Wohlordnungen erhalten.

Vorlesung am 28.01.2008

Definition (Ordinalzahl) Eine Ordinalzahl ist eine transitive Menge, auf der ∈ eine Wohlordnung ist. On sei die Klasse aller Ordinalzahlen.

Lemma 5.4. 1. Es gibt keine unenendlich absteigende Kette α_{0} ∋ α_{1} ∋ ... von Ordinalzahlen.

2. Durchschnitte von Ordinalzahlen sind wieder Ordinalzahlen.

3. Nach Lemma 13.1 ist mit α auch α ∪ {α} eine Ordinalzahl.

4. Transitive Teilmengen von Ordinalzahlen sind Ordinalzahlen.

5. Jedes Element einer Ordinalzahl ist eine Ordinalzahl.

6. Die Vereinigung einer Klasse (bzw. Menge) transitiver Mengen ist eine transitive Klasse bzw. Menge.

Beweis:

1. Wenn es eine derartige Kette gäbte, dann wäre (wegen der Transitivität von α_{0}) α_{1} ∋ α_{2} ∋ ... eine unendlich absteigende Kette in α_{0}.

5. Sei z ∈ α. Dann gilt z ⊆ α. Es reicht zu zeigen, dass z transitiv ist.

Sei x ∈ y ∈ z. Dann gilt x ∈ y ∈ α, da z ⊆ α. Damit erhalten wir x ∈ α. Also haben wir x, y, z ∈ α. In α ist ∈ eine Ordnung. Aus der Transitivität von ∈ (als Ordnung) folgt x ∈ z.

6. Jedes x ∈ X sei transitiv. Zu zeigen ist, dass ⋃ X transitiv ist. Sei y ∈ ⋃ X, d.h. y ∈ x ∈ X. Da x transitiv ist, gilt y ⊆ x, also y ⊆ ⋃ X. Damit ist auch ⋃ X transitiv. Falls X eine Menge ist, so ist ⋃ X eine Menge (ZFC).

Definition (natürliche Zahlen) Wir definieren 0 = ∅, 1 = 0 ∪ {0} = ∅ ∪ {∅} = {∅}, 2 = 1 ∪ {1} = {∅, {∅}}, 3 = 2 ∪ {2} = {∅, {∅}, {∅, {∅}}} und so weiter... (Lustiger: {} statt ∅: 4 = {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}) Weiterhin definieren wir ω = {0, 1, 2, 3, ...}. Diese Menge existiert nach ZFC. Wenn α eine Ordinalzahl ist, so ist α + 1 = α ∪ {α} wieder eine Ordinalzahl. ω ist die erste unendliche Ordinalzahl. (Die Existenz ist durch das Unendlichkeitsaxiom gesichert.) ω enthält alle endlichen Ordinalzahlen. Die endlichen Ordinalzahlen sind in der Mengenlehre die natürlichen Zahlen.

Lemma 5.5. (13.2) Seien α, β ∈ On.

1. α ∈ β ⇔ α ⊂ β

2. Es gilt entweder α ∈ β oder α = β oder β ∈ α.

Beweis:

1. (a) ⇒ Diese Richtung ist klar, weil β transitiv ist und α ≠ β durch das Fundierungsaxiom gilt.

(b) ⇐ Es gelte α ⊂ β. Dann ist β \ α nicht leer. Sei γ das kleinste Element in β \ α. (γ existiert, da ∈ eine Wohlordnungauf β ist.) Wir zeigen α = γ, denn dann erhalten wir α ∈ β. Wir nutzen aus, dass zwei Mengen genau dann gleich sind, wenn sie dieselben Elemente besitzen (Extensionalitätsaxiom in ZF). Sei δ ∈ γ ∈ β. Wegen der Transitivitität von β gilt δ ∈ β. Wegen der Wahl von γ (kleinstes Element aus β \ α) folgt δ ∈ α. Somit haben wir γ ⊆ α. Sei δ ∈ α ⊆ β. Da ∈ eine lineare Ordnung auf β ist, gilt γ ∈ δ, γ = δ oder γ ⊆ δ. Wenn γ ∈ δ, so haben wir γ ∈ α, da α transitiv ist. Dies ist ein Widerspruch zur Wahl von γ ∈ β \ α. Wenn γ = δ, so erhalten wir ebenfalls γ ∈ α. Also muss γ ∋ δ gelten, d.h. α ⊆ γ.

2. α ∩ β ⊆ β ist eine Ordinalzahl. Mit 1. gilt also α ∩ β = β oder α ∩ β ∈ β.

Wegen α ∩ β ⊆ α erhalten wir analog α ∩ β = α oder α ∩ β ∈ α.

Aus α ∩ β = β folgt β ⊆ α und nach 1. dann β = α oder β ∈ α.

Aus α ∩ β = α folgt α ⊆ β und nach 1. dann α = β oder α ∈ β.

Also haben wir β ∈ α oder α = β oder α ∈ β oder (α ∩ β ∈ α und α ∩ β ∈ β). Im letzten Fall erhielten wir jedoch α ∩ β ∈ α ∩ β, was einen Widerspruch zur Irreflexivität von ∈ darstellte. Man beachte, dass sich die verbleibenden 3 Fälle gegenseitig ausschließen, da ∈ transitiv und irreflexiv ist.

Definition (Vergleichen von Ordinalzahlen) Für alle Ordinalzahlen α, β definieren wir

1. α < β, wenn α ∈ β.

2. α ≤ β, wenn α < β oder α = β. Bemerkung

1. On hat keine absteigenden ∈-Folgen.

Somit ist ∈ eine Wohlordnung, wenn die Abschnittsbedingung gilt.

2. α + 1 = α ∪ {α} ist in On der direkte Nachfolge von α. Wenn nun α < β, so folgt α ∈ β und α ⊂ β, also α ∪ {α} ⊆ β, d.h. α + 1 ≤ β.

3. 0 = ∅ ist die kleinste Ordinalzahl, da ∅ ⊆ α für alle α ∈ On. Also haben wir ∅ ∈ α für α ≠ 0 nach Lemma 13.2.

4. Ein Anfang von On ist 0 < 1 < 2 < ... < ω < ω + 1 < .... Lemma 5.6. (13.3)

1. Eine Ordinalzahl ist genau die Menge ihrer Abschnitte geordnet durch ⊆. Es gilt α_{β} = On_{β} = β für β ∈ α ∈ On.

2. ⟨On, <⟩ ist eine Wohlordnung.

3. Jede echte transitive Teilmenge von On ist eine Ordinalzahl.

4. Die Vereinigung einer echten Teilmenge von On ist eine Ordinalzahl. Beweis:

1. Siehe Kapitel 12, Bemerkungen 4 und 5.

Wenn β ∈ α ∈ On, dann β ⊂ α, also α_{β} = {γ ∈ α|γ ∈ β} = α ∩ β = β. On_{β} = {γ ∈ On|γ ∈ β} = β.

2. Wegen 1. Genügt On der Abschnittsbedingung. Damit ist On eine Wohlordnung.

3. Sei X ⊂ On eine echte transitive Teilmenge. Sei α ∈ On minimal in On \ X. Wir zeigen α = X. Wenn β ∈ α, dann β ∈ X, da α minimal in On \ X gewählt wurde. Wenn β ∈ X, so folgt β ∈ α: Sonst hätten wir α ∈ β oder α = β. α = β ∈ X ist unmöglich, da α ∈ On \ X. α ∈ β ∈ X impliziert α ∈ X, weil X transitiv ist. Damit erhalten wir auch hier einen Widerspruch.

4. X ist eine Menge von transitiven Mengen. Nach den obigen Bemerkungen ist also ⋃ X eine transitive Teilmenge von On und nach 3. eine Ordinalzahl.

Bemerkung ⟨On, <⟩ ist eine Wohlordnung. Wenn β ∈ On, so gilt β ⊆ On, da β eine Menge von Ordinalzahlen ist. On ist keine Menge und keine Ordinalzahl, sonst hätten wir On ∈ On, was einen Widerspruch zum Fundierungsaxiom, also ist On eine echte Klasse.

Vorlesung am 30.01.2008

Definition (Transfinite Induktion (1)) Sei X ∈ On oder X = On und P eine Eigenschaft von Ordinalzahlen. Für jedes α ∈ X gelte:

1. Wenn P (β) für alle β < α, dann P (α)

Dann gilt P für alle α ∈ X.

Definition (Transfinite Rekursion) Sei X ∈ On oder X = On, W eine Klasse und F eine Funktion, die jeder Funktion auf einem α aus X in W wieder einen Wert aus W zuordnet. Dann existiert eindeutig bestimmt eine Funktion f : X → W mit f(α) = F (f)(α) für alle α ∈ X.

Definition (Limeszahl, Nachfolgerzahl) α ∈ On heißt Limeszahl, wenn α die Vereinigung aller kleineren Ordinalzahlen ist. Sonst heißt α Nachfolgerzahl.

Lemma 5.7. (13.4)

1. α ∈ On ist genau dann Nachfolgerzahl, wenn α = β + 1 für ein β ∈ On gilt.

2. 0 ist die kleinste Limeszahl.

3. ω ist die nächstgrößere und gleichzeit die kleinste unendliche Limeszahl.

Beweis:

1. Wenn α = β +1 = β ∪{β}, so gilt ⋃_{γ∈α} γ = ⋃_{γ∈β} γ ∪β = β ≠ α. Damit ist α keine Limeszahl und damit Nachfolgerzahl im Sinne der Definition.

Seien ⋃_{γ∈α} γ ≠ α und β ∈ α \ ⋃_{γ∈α} γ.

Dann folgt für γ ∈ α, dass β ∉ γ, d.h. β ⊄ γ. Damit erhalten wir γ ≤ β für alle γ ∈ α. Also ist β größtes Element von α, d.h. α = β ∪ {α}.

2. 0 = ∅ = ⋃_{α∈∅} α

3. ω = {0} ∪ {n + 1|n ∈ ℕ}

Transfinite Induktion (2) Seien X ∈ On oder X = On und P sei eine Eigenschaft für Ordinalzahlen. Es gelte für alle α ∈ X :

1. Wenn α die Eigenschaft P besitzt, so auch α + 1.

2. Wenn α eine Limeszahl ist und die Eigenschaft für alle δ < α gilt, so gilt sie auch für α.

Dann gilt P für alle α ∈ X.

Bemerkung Der Teil der Aussage über Limeszahlen kann noch in den Induktionsanfang (d.h. für die Limeszahl 0) und den Schritt für unendliche Ordinalzahlen unterteilt werden.

Lemma 5.8. In jedem Isomorphietyp von wohlgeordneten Mengen gibt es genau eine Ordnungszahl. Nach AC lässt sich jede Menge wohlordnen, d.h. sie lässt sich mit Ordinalzahlen indizieren.

Beweis: Beweis der Eindeutigkeit Sei f : α ≅ β ein Ordnungsisomorphismus und α, β ∈ On. Wir nehmen an, dass α ≠ β gelte. Nach Lemma 13.2 haben α < β oder α = β oder β < α. Sei o.B.d.A. α < β. (Den Fall β < α behandeln wir analog.) Dann ist α ein echtes Anfangsstück von β (δ ∈ γ ∈ α ⇒ δ ∈ α). f wäre also Ordnungsisomorphismus von α in einen Abschnitt von α, was einen Widerspruch zu 12.1 darstellte.

Lemma 5.9. (13.5) Sei ⟨X, <⟩ eine Wohlordnung und f : X → On derart, dass für alle a ∈ X die Ordnung ⟨X_{a}, <⟩ isomorph zu der Ordinalzahl f(a) ist. Dann existiert ein Ordnungsisomorphismus von ⟨X, <⟩ auf ein Anfangsstück von ⟨On, <⟩. Dabei gilt f(X) = On, falls X keine Menge ist.

Beweis: Die Abbildung f ist eine Einbettung von ⟨X, <⟩ in ⟨On, <⟩: c < b in X ⇔ X_{c} < X_{b} ⇔ f(c) ist Isomorph zu einem Abschnitt von f(b) Es bleibt zu zeigen, dass f(X) ein Anfangsstück von On ist. Wenn f(X) = On gilt, sind wir fertig. Sonst gilt On \ f(X) ≠ ∅. Sei β das kleinste Element in On \ f(X). Behauptung: β = f(X), d.h. ⟨X, <⟩ ˆ=β Wir haben β ⊆ f(X) durch das bereits bekannte Minimalitätsargument. (Gäbe es α ∈ β \ f(X), dann hätten wir α ∉ f(X) und α < β, was einen Widerspruch zur Minimalität von β darstellt.) Wenn f(X) ⊃ β gelten würde, so hätten wir α ∈ f(X) \ β. Es kann nicht β = α ∈ f(X) gelten, da wir dann sofort einen Widerspruch zur Wahl von β hätten. Im Fall von α > β in f(X), existierte a ∈ X mit f(a) = α. Der Isomorphismus α ≅ ⟨X_{a}, <⟩, der nach Voraussetzung existiert, würde denn ein b ∈ X_{a} mit β ≅ ⟨X_{b}, <⟩ liefern. (β < α heißt β ist Abschnitt von α.) Dann wäre β ≅ f(b), d.h. β = f(b), d.h. β ∈ f(X), was einen Widerspruch zur Annahme darstellt. Es bliebe somit nur noch α < β, d.h. α ∈ β, was einen Widerspruch zu α ∈ f(X) \ β darstellt. Zuletzt zeigen wir noch den zweiten Teil des Lemmas: Nach dem mengentheoretischen Ersetzungsaxiom gilt für die Bijektion f: X ist genau dann eine Menge, wenn f(X) eine Menge ist. Es folgt also, dass ⟨X, <⟩ genau dann eine Klasse ist, wenn es zu ⟨On, <⟩ isomorph ist.

Satz 5.4. (13.6)

1. Jede wohlgeordnete Menge ist zu genau einer Ordinalzahl isomorph.

2. Jede Wohlordnung, die keine Menge ist, ist zu On isomorph.

Beweis:

1. Sei ⟨X, <⟩ eine wohlgeordnete Menge.

Annahme: ⟨X, <⟩ ist nicht zu einer Ordinalzahl isomorph.

Nach Lemma 13.5 existiert ein kleinstes a ∈ X, sodass ⟨X_{a}, <⟩ nicht zu einer Ordinalzahl isomorph ist. Aber jeder echte Abschnitt von ⟨X_{a}, <⟩ ist zu einer Ordinalzahl isomorph. Das widerspricht 13.5. Damit ist jede wohlgeordnete Menge zu einer Ordinalzahl isomorph.

2. Sei X eine echte Klasse.

Dann ist jedes X_{a} (durch die Abschnittsbedingung für Wohlordnungen) eine Menge. Damit ist jeder Abschnitt von X zu einer Ordinalzahl isomorph. 13.5. zeigt, dass ⟨X, <⟩ isomorph zu einer Ordinalzahl oder On ist. Da das Bild eine echte Klasse sein muss, kommt nur On in Frage.

Korollar 5.1. (13.7) Wenn X und Y Wohlordnungen sind, so ist X in Y oder Y in X zu einem Anfangsstück isomorph.

5.14 Kardinalzahlen

Definition (Gleichmächtigkeit von Mengen) Zwei Mengen sind gleichmächtig, wenn man sie durch eine Bijektion aufeinander abbilden kann.

Definition (Kardinalzahl) Eine Kardinalzahl ist eine Ordinalzahl, die zu keiner kleineren Ordinalzahl gleichmächtig ist.

Bemerkung Die Kardinalzahlen sind die kleinsten Ordinalzahlen in einer Gleichmächtigkeitsklasse.

Beispiel (Kardinalzahlen)

1. 0, 1, 2, ..., ω sind Kardinalzahlen.

2. ω + 1 ist keine Ordinalzahl:

Es existiert die Bijektion f(α) = \{ \begin{matrix}0 , & α = ω \\ α + 1, & α ∈ ω \end{matrix}

Bemerkung Wenn wir AC voraussetzen, so lässt sich jede Menge A mit einer Wohlordnung versehen. Nach Satz 13.6. ist dann ⟨A, <⟩ zu einer Ordinalzahl isomorph, d.h. wenn wir AC annehmen, dann existiert für jede Menge A eine gleichmächtige Ordinalzahl.

Definition (Mächtigkeit einer Menge) |A| ist die kleinste Kardinalzahl, die gleichmächtig zu A ist.

Definition (Klasse der (unendlichen) Kardinalzahlen) Wir definieren mit Cn die Klasse der Kardinalzahlen und mit Cn^{∞} die Klasse der unendlichen Kardinalzahlen.

Bemerkung Wegen Cn^{∞} ⊆ Cn ⊆ On ist Cn^{∞} wohlgeordnet. Nach Theorem 13.6 ist ⟨Cn^{∞}, <⟩ isomorph zu ⟨On, <⟩. (Cn^{∞} kann nicht isomorph zu einer Ordinalzahl sein, da Cn^{∞} unbeschränkt ist.)

Vorlesung am 04.02.2008

Definition (ℵ_{α}) ℵ_{α} mit α ∈ On bezeichnet die Kardinalzahl, die in der Wohlordnung der unendlichenen Kardinalzahlen die α-te Zahl ist. Mit ℵ_{α+1} bezeichnen wir den Nachfolger von ℵ_{α}.

Bemerkung

1. ℵ_{0} ist ω.

2. Für α < β gilt ℵ_{α} < ℵ_{β}.

3. Transfinite Induktion und Rekursion ist für Cn und Cn^{∞} möglich.

4. Für κ ∈ C_{n} schreiben wir |A| = κ, wenn A und κ gleichmächtig sind.

Definition (Ordnung der Kardinalzahlen) Für λ, κ ∈ C_{n} gilt λ < κ, wenn λ ∈ κ, d.h. es gilt λ < κ im Sinne der Ordnung der Ordinalzahlen. Lemma 5.10. (14.1) Es gibt genau dann eine Injektion f : X → Y, wenn |X| ≤ |Y |. Beweis:

1. ⇐ Wir haben

\xymatrix{X \ar[d]_{g} & Y \ar[d]^{h} \\ |X| \ar@{^{(}->}[r]_{r} & |Y |}

wobei g und h Bijektionen sind. Demnach müssen wir nur die Injektion r finden, welche durch die Identität gegeben ist. Wir erhalten die gesuchte Bijektion f durch f = h^{−1} ∘ r ∘ g.

2. ⇒ Wir betrachten

[figure: X; g; f; Y; h; |X|; |Y |; κ; λ]

wobei g und h Bijektionen sind. Damit ist r = h ∘ f ∘ g^{−1} eine Injektion von |X| nach |Y |. O.B.d.A. sei also κ = |X| = X und λ = |Y | = Y. Wir zeigen nun κ ≤ λ. Nach Theorem 13.6 existiert ein Ordnungsisomorphismus von f(κ) auf eine Ordinalzahl α. Wir haben also j : f(κ) ⟶^{∼} α. Als Ordinalzahlen sind α und λ vergleichbar. Falls α ≤ λ, so ist die Behauptung erfüllt, da κ = |f(κ)| = α ≤ λ. Der Fall λ < α tritt nicht ein, da man sonst die Einbettung f ∘ j^{−1} von α in α_{λ} = λ ⊇ f(κ), d.h. eine Einbettung in ein echtes Anfangsstück hätte.

Definition (Nachfolger einer Kardinalzahl) Für κ ∈ Cn ist κ^{+} der Nachfolger von κ.

Bemerkung 1. Jede unendliche Kardinalzahl ist eine Limesordinalzahl.

2. Kardinalzahlen ℵ_{α+1} heißen Nachfolgerkardinalzahlen.

3. Kardinalzahlen ℵ_{δ}, wobei δ Limesordinalzahlen sind, heißen Limeskardinalzahlen. (0 ist eine limesordinalzahl, also ist ω = ℵ_{0} eine Limeskardinalzahl.)

Definition Seien κ, λ ∈ Cn. Dann definieren wir

1. κ + λ = |κ ˙∪λ|

2. κ · λ = |κ × λ|

3. κ^{λ} = |^{λ}κ|, κ^{0} = 1

Erklärungen

1. κ ˙∪λ ist die Vereinigung von disjunkten Kopien von κ und λ, z.B. κ ˙∪λ = (λ×{0})∪(κ×{1}). |κ ˙∪λ| hängt nicht von der der Wahl der speziellen disjunkten Kopien ab.

2. κ × λ ist das kartesische Produkt.

3. ^{λ}κ ist die Menge aller Funktionen von λ in κ. Lemma 5.11. (14.2) Analog zu den natürlichen Zahlen gelten die folgenden Gesetze: Seien κ, λ, μ ∈ Cn.

1. (Cn, +) ist ein kommutatives Monoid mit neutralem Element 0.

2. Wenn κ ≤ λ, so gilt κ + μ ≤ λ + μ.

3. (Cn, ·) ist ein kommutatives Monoid mit neutralem Element 1.

4. κ(λ + μ) = κλ + κμ

5. Wenn κ ≤ λ, so gilt κμ ≤ λμ.

6. κ · 0 = 0 · κ = 0

7. κ^{λ+μ} = κ^{λ} · κ^{μ}

8. κ^{λ·μ} = (κ^{λ})^{μ}

9. (κ · λ)^{μ} = κ^{μ} · λ^{μ}

10. Wenn κ ≤ λ und μ > 0, so gilt μ^{κ} ≤ μ^{λ} und κ^{μ} ≤ λ^{μ}.

11. Es gilt κ^{0} = 1. Speziell gilt auch 0^{0} = 1.

12. κ^{1} = κ

13. Wenn κ ≠ 0, so gilt 0^{κ} = 0.

14. Wenn κ ≥ 2, so gilt κ + κ ≤ κ · κ. Beweis:

1. Folgt direkt aus der Definition.

2. Wenn κ ≤ λ, d.h. κ ⊆ λ, dann gilt (κ × {0}) ∪ (μ × {1}) ⊆ (λ × {0}) ∪ (μ × {1}).

3. Klar.

4. κ × ((λ × {0}) ∪ (μ × {1})) = (κ × (λ × {0})) ∪ (κ × (μ × {1}))

5. Wenn κ ≤ λ, d.h. κ ⊆ λ, dann gilt κ × μ ⊆ λ × μ.

6. ∅ × κ = ∅ = κ × ∅

7. ^{(λ×{0})∪(μ×{1})}κ =^{λ×{0}} κ ×^{μ×{1}} κ Wir verwenden dabei die Bijektion f ↦ (f|_{λ×{0}}, f|_{μ×{1}}).

8. Es ist ^{λ×μ}κ ⟷^{1:1} ^{μ}(^{λ}κ) zu zeigen.

Sei f ∈^{λ×μ} κ, d.h. f = {((α, β), f(α, β))|α ∈ λ, β ∈ μ}.

Nun verwenden wir die Bijektion f ↦ {(β, {α, f(α, β)|α ∈ λ})|β ∈ μ} ∈^{μ} (^{λ}κ).

9. Zu zeigen ist ^{μ}κ × λ ⟷^{1:1} ^{μ}κ ×^{μ} λ.

Sei f = {(β, (f_{0}(β), f_{1}(β)))|β ∈ μ, f_{0}(β) ∈ κ, f_{1}(β) ∈ λ} ∈^{μ} (κ × λ).

Wir verwenden nun einfach die Bijektion f ↦ (f_{0}, f_{1}).

10. Sei κ ≤ λ und μ > 0.

Wir haben κ^{μ} ≤ λ^{μ}, da ^{μ}κ ⊆^{μ} λ.

Wir haben μ^{κ} ≤ μ^{λ}, da eine Injektion r :^{κ} μ →^{λ} μ existiert. Wir definieren f ↦ f^{∗} mit f^{∗} = f auf κ und f^{∗} = ∅ = 0 auf λ \ κ.

11. Definition.

12. Klar.

13. Wenn κ ≠ 0, so ^{κ}∅ = ∅.

14. (κ × {0}) ∪ (κ × {1}) ⊆ (κ × κ) für κ ≥ 2. Satz 5.5. (Hessenberg(14.3)) Wir haben λ · λ = λ für λ ∈ Cn^{∞}. Beweis: Wir führen eine Induktion über λ ∈ Cn^{∞} durch. Wir definieren auf λ × λ eine Ordnung durch:

1. (α, β) < (γ, δ), falls max{α, β} < max{γ, δ},

2. (α, β) < (γ, δ), falls max{α, β} = max{γ, δ} und α < γ,

3. (α, β) < (γ, δ), falls max{α, β} = max{γ, δ} und α = γ und β < δ. Wir werden hier nicht explizit beweisen, dass ⟨λ × λ, <⟩ wirklich eine Ordnung ist. Behauptung ⟨λ × λ, <⟩ ist eine wohlgeordnete Menge: λ × λ ist nach den Axiomen der Mengenlehre eine Menge. Weiterhin ist < eine lineare Ordnung (den Beweis dafür haben wir ja weggelassen ˆ ˆ ). Sei ∅ ≠ X ⊆ λ × λ. Es ist zu zeigen, dass X ein kleinstes Element enthält. Sei η die kleinste Ordinalzahl von {max{α, β}|(α, β) ∈ X}. γ sei die kleinste Ordinalzahl in Y = {α ∈ On|∃β : (α, β) ∈ X, max{α, β} = η}. δ sei die kleinste Ordinalzahl, so dass (γ, δ) ∈ X. ⇒ (γ, δ) ist nach Konstruktion das kleinste Element in X. Nun zur Induktion:

1. Induktionsanfang: ⟨ℵ_{0} × ℵ_{0}⟩ ≅ ℵ_{0} ist ein Ordnungsisomorphismus, da auf beiden Seiten jeder Abschnitt endlich ist.

Vorlesung am 06.02.2008

2. Induktionsschritt:

Es gelte κ · κ = κ für alle κ < λ.

Wir zeigen, dass jeder Abschnitt von λ × λ eine Mächtigkeit, die kleiner als λ ist, hat.

Sei (γ, δ) ∈ (λ × λ). Wir wählen ε, sodass ε = max{γ, δ, ℵ_{0}} + 1.

⇒ ε ∈ λ und (γ, δ) < (ε, ε) ⇒ (λ × λ)_{(γ,δ)} ≤ (ε × ε) ⇒ |(λ × λ)_{(γ,δ)}| ≤ |ε × ε| = |ε| · |ε| = |ε| < λ Also hat jeder Abschnitt von λ × λ eine Mächtigkeit, die kleiner als λ ist. ⇒ |λ × λ| ≤ λ ⇒ λ · λ = |λ × λ| ≤ λ λ ↪ λ × λ ⇒ λ · λ = |λ × λ| ≥ λ (Da ⟨λ × λ, <⟩ eine wohlgeordnete Menge ist, existiert nach Satz 13.6 eine Ordinalzahl α mit ⟨λ × λ, <⟩ ≅ α. Wir haben gezeigt: Jeder Abschnitt von α ist eine Ordinalzahl, die kleiner als α ist. ⇒ α ≤ λ. Wäre λ < α, so hätte der Abschnitt α_{λ} die Mächtigkeit λ.) ⇒ λ · λ = λ

Korollar 5.2. (14.4) Wenn κ, λ ∈ Cn^{∞}, so gilt κ + λ = κ · λ = max{κ, λ}. Beweis: O.B.d.A. κ ≤ λ ∈ Cn^{∞}. max{κ, λ} = λ ≤ κ + λ ≤ λ · λ = λ. Korollar 5.3. (14.5) Wenn λ ∈ Cn^{∞}, 0 < n < ω, so gilt λ + n = λ · n = λ^{n} = λ. Beweis: λ ≤ λ + n ≤ λ + λ = λ λ ≤ λ · n ≤ λ · λ = λ Weil n < ω gilt, folgt:

λ^{n} = λ^{n−1} · λ = \underbrace{λ · λ · ... · λ}_{n−mal} = \underbrace{λ · ... · λ}_{n−1−mal} = ... = λ

Definition (Potenzmenge) P (X) = {y|y ⊆ X} Nach dem Potenzmengenaxiom ist P (X) eine Menge, wenn X eine Menge ist.

Bemerkung Es gilt |X| ≤ |P (X)|, da X ↪ P (X), mit x ↦ {x}.

Vereinbarung In diesem letzten Kapitel sei X ↪ Y stats eine Injektion, d.h. eine Einbettung bezüglich der Sprache ohne nichtlogische Symbole. Wir schreiben X ≈ Y (oder vielleicht auch X ⟷^{1:1} Y) um die Existenz einer Bijektion darzustellen.

Bemerkung (Satz von Bernstein (ohne AC)) Wenn X ↪ Y und Y ↪ X, dann X ≈ Y (bzw. X ⟷^{1:1} Y). Beweis: Ohne AC: Kein Beweis. In dem Fall, dass wir AC zulassen können wir diesen Satz natürlich sofort aus unseren bisherigen Erkenntnissen herleiten.

Lemma 5.12. (14.6)

1. |P (X)| = 2^{|X|} für alle X.

2. Seien κ ∈ Cn und λ ∈ Cn^{∞}. Wenn 2 ≤ κ ≤ λ, so κ^{λ} = 2^{λ}.

Beweis:

1. Wenn Y ⊆ X, so sei ch_{Y} (x) = \{ \begin{matrix}1, & x ∈ Y \\ 0, & sonst \end{matrix}

⇒ Y ↦ ch_{Y} ist eine Bijektion zwischen P (X) und ^{X}2.

2. Aus 2 ≤ κ ≤ λ ≤ |P (λ)| = 2^{λ} folgt nach Lemma 14.2 (10): 2^{λ} ≤ κ^{λ} ≤ (2^{λ})^{λ}. Mit 14.2 (8) und 14.3 folgt (2^{λ})^{λ} = 2^{λ·λ} = 2^{λ}. Somit folgt die Behauptung.

Bemerkung Für endliche X gilt |X| < |P (X)|.

Satz 5.6. (G. Cantor (14.7)) 2^{κ} > κ für alle κ ∈ Cn.

Beweis: Es reicht |P (X)| > |X| zu zeigen. Wir wissen |P (X)| ≥ |X|. Bestünde die Gleichheit, so existierte eine Bijektion f : X → P (X). Wir betrachten Y = {x ∈ X|x ∉ f(x)} ⊆ X. Da f surjektiv ist, existiert ein y ∈ X, sodass f(y) = Y. Wir erhalten nun den Widerspruch y ∈ Y ⇔ y ∉ f(y) ⇔ y ∉ Y. (Die erste Äquivalenz folgt aus der Definition von Y und die zweite gilt wegen Y = f(y).) Somit kann die Gleichheit nicht gelten.

Bemerkung (Mächtigkeit der Zahlbereiche)

1. |ℕ| = ℵ_{0}

2. |ℤ| = |ℕ ˙∪{ℕ \ {0}}| = ℵ_{0} + ℵ_{0} = ℵ_{0}

3. |ℤ| ≤ |ℚ| ≤ |ℤ × ℤ| = ℵ_{0} · ℵ_{0} = ℵ_{0} = |ℤ| ⇒ |ℚ| = |ℤ| = ℵ_{0}

4. |ℝ| = 2^{ℵ_{0}} (Kontinuum)

5. |ℂ| = |ℝ × ℝ| = 2^{ℵ_{0}} · 2^{ℵ_{0}} = 2^{ℵ_{0}}

Bemerkung (Kontinuumshypothese) G. Cantor: 2^{ℵ_{0}} = ℵ_{1} (CH)

→ 1. Hilbertsches Problem. 1938: K. Gödel: Wenn ZFC konsistent, so ZFC+(GCH). 1963: Paul Cohen: Wenn ZFC konsistent, so ZFC+¬CH konsistent. GCH ist die Verallgemeinerung von CH: 2^{ℵ_{α}} = ℵ_{α+1}.

Lemma 5.13. (14.8) Seien κ, λ ∈ Cn und |X_{i}| ≤ λ für alle i < κ. Dann gilt | ⋃_{i<κ} X_{i}| ≤ κ · λ.

Beweis: Aus |X_{i}| ≤ λ = |{i} × λ| folgt | ⋃_{i<κ} X_{i}| ≤ | ⋃_{i<κ}({i} × λ)| = |κ × λ| = κ · λ. .

Definition Für jede Menge X und λ ∈ Cn sei ^{<λ}X die Vereinigung der Mengen ^{μ}X, wobei μ über alle Kardinalzahlen, die kleiner als λ sind, läuft. Statt ^{<ℵ_{0}}X wird häufig ^{<ω}X geschrieben. Ist κ eine Kardinalzahl, so sei κ^{<λ} = |^{<λ}κ|.

Bemerkung <ωX ist die Menge aller endlichen Folgen von Elementen aus X.

Lemma 5.14. (14.9) Für alle κ ∈ Cn^{∞} gilt κ^{<ℵ_{0}} = κ.

Beweis: Nach 14.5. gilt |^{n}κ| = κ^{n} = κ und nach 14.8. gilt κ^{<ℵ_{0}} = | ⋃_{n<ω} ^{n}κ| ≤ ℵ_{0} · κ = κ.

Korollar 5.4. (14.10) Sei L die elementare Sprache der Signatur σ. Dann gilt:

1. |L| = max{ℵ_{0}, |σ|} = |σ| + ℵ_{0}, wobei σ die Menge der nichtlogischen Symbole sei.

2. Ist C eine Menge neuer Konstantensymbole, so ist |L(C)| = |L| + |C|.

Beweis:

1. Eine L-Formel ist einen endliche Folge über dem gegebenen Alphabet A.

Wir haben |A| = κ = max{ℵ_{0}, |σ|}. Nach Lemma 14.9 gilt κ ≤ |L| ≤ κ^{<ℵ_{0}} = κ.

2. Folgt aus 1., da σ(L(C)) = σ(L) + C, d.h. |σ(L(C))| = |σ(L)| + |C|.

5.15 Kofinalität

Wie schnell kann man eine Kardinalzahl durchwandern? Für ℵ_{ω} benötigen wir ω-viele Schritte. Für ℵ_{1} benötigen wir ℵ_{1}-viele Schritte.

Vorlesung am 11.02.2008

Bemerkung (*) Für die Funktion f : ω → ℵ_{ω}, definiert durch f(i) = ℵ_{i}, gilt ⋃ im(f) = ⋃_{i<ω} f(i) = ℵ_{ω}. (**) Wenn f : α → ℵ_{1} mit ⋃ im(f) = ℵ_{1}, so gilt α ≥ ℵ_{1}. Wenn κ ∈ Cn^{∞} eine Limesordinalzahl ist, gilt stets κ = ⋃_{α<κ} α. Beweis: (Beweis von (**)) Wäre α < ℵ_{1}, dann gilt |α| ≤ ℵ_{0}. Für f(β) < ℵ_{1} gilt |f(β)| < ℵ_{1}. Wir haben also ⋃ im(f) = ℵ_{0} und |α| ≤ ℵ_{0} · ℵ_{0} = ℵ_{0}.

Definition (Kofinalität cf) Falls α keine Limesordinalzahl ist oder α = 0 gilt, so setzen wir cf(α) = 0. Für alle Limesordinalzahlen δ (außer 0) sei cf(δ) = min{β|∃f : β → δ : ⋃ im(f) = δ}. (f ist unbeschränkt.) cf(δ) existiert, da id : δ → δ die gewünschte Eigenschaft hat.

Bemerkung

1. cf(δ) ≤ δ

2. cf(ω) = ω, cf(ℵ_{ω}) = ω, cf(ℵ_{α+1}) = ℵ_{α+1}

(Beweis analog zum Beweis von (**).)

Bemerkung Für jede Limeszahl δ > 0 gilt

1. cf(δ) ist eine unendliche Kardinalzahl. Beweis:

Wenn cf(δ) keine Kardinalzahl wäre, hätten wir κ = |cf(δ)| < cf(δ). Wir wählen eine Bijektion g : κ → cf(δ) und f : cf(δ) → δ mit ⋃ im(f) = δ. Dann ist auch f ∘ g : κ → δ unbeschränkt im Widerspruch zu κ < cf(δ). Somit ist cf(δ) eine Kardinalzahl. Wir haben ℵ_{0} ≤ cf(δ), da endliche Vereinigungen von Ordinalzahlen α_{0}, ..., α_{n−1} < δ höchstens die Kardinalität von max{α_{0}, ..., α_{n−1}} + 1 < δ haben.

2. Man kann in der Deifnition von f fordern, dass f (schwach) monoton ist, d.h. f(α) ≤ f(β) für alle α < β. Beweis: Sei h : cf(δ) → δ unbeschränkt in δ. Wir definieren f(γ) = ⋃ im(h|_{γ+1}). Da cf(δ) eine unendliche Kardinalzahl und damit auch eine Limeskardinalzahl ist, gilt für γ < cf(δ) auch γ + 1 < cf(δ). Damit erhalten wir ⋃ im(h|_{γ+1}) < δ. Da h(γ) ≤ f(γ), folgt die Behauptung.

Definition Sei κ ∈ Cn^{∞}.

1. κ ist regulär, falls cf(κ) = κ.

2. κ ist singulär, falls cf(κ) < κ.

Beispiel ℵ_{0}, ℵ_{α+1} sind regulär und ℵ_{ω} ist singulär.

Bemerkung Singuläre Kardinalzahlen sind stets Limeskardinalzahlen. Es stellt sich die Frage, ob es reguläre Limeskardinalzahlen (auch schwach unerreichbare Kardinalzahlen genannt) gibt, die größer als ℵ_{0} sind. Man weiß jedoch, dass man aus ZFC die Aussage der Existenz dieser Limeskardinalzahlen nicht beweisen kann, wenn ZFC konsistent ist. Man nimmt häufig an, dass ZFC und die Existenzaussage konsistent sind.

Lemma 5.15. (15.1) Für jede Limesordinalzahl δ > 0 gilt:

1. cf(δ) ist eine reguläre Kardinalzahl.

2. cf(cf(δ)) = cf(δ)

3. Es gilt genau dann cf(δ) = δ, wenn δ eine reguläre Kardinalzahl ist.

Beweis:

1. 2. ⇒ 1., da cf(δ) eine unendliche Kardinalzahl ist.

2. 1. ⇒ 3. soll auch trivial sein.

3. 2.

Wäre cf(cf(δ))<cf(δ), gäbe es dennoch zwei unbeschränkte Funktionen g:cf(cf(δ))→cf(δ) und f(cf(δ)) → δ. f kann o.B.d.A. als (schwach) monoton angenommen werden. Wir zeigen, dass f∘g : cf(cf(δ)) → δ unbeschränkt in δ ist, was den gewünschten Widerspruch erzeugt. Sei β < δ beliebig. Dann existiert α_{0} < cf(δ) mit β < f(α) < cf(δ) für alle α ≥ α_{0}. Weiterhin existiert ein γ mit g(γ) ≥ α_{0}, d.h. f ∘ g(γ) ≥ β.

Lemma 5.16. (15.2) Für κ ∈ Cn^{∞} ist κ genau dann regulär, wenn ∀X(|X| < κ ∧ ∀y(y ∈ X → |y| < κ) → | ⋃ X| < κ) gilt.

Beweis:

1. ⇐

Wir zeigen cf(κ) = κ.

Sei β < κ und f : β → κ.

⇒ ⋃ im(f) < κ

⇒ β < cf(κ)

⇒ κ ≤ cf(κ)

⇒ κ = cf(κ)

⇒ κ ist regulär.

2. ⇒

Seien κ regulär und X mit μ = |X| < κ, |y| < κ für alle y ∈ X gegeben. Zu zeigen ist | ⋃ X| < κ.

Da κ regulär ist, gilt μ < κ = cf(κ). Seien g : μ → X eine Bijektion und f(β) = |g(β)|. Damit gilt f(β) ≤ |X| < κ.

Wegen μ < cf(κ) gilt ⋃ im(f) < κ. Als Supremum (kleinste(!) obere Schranke) einer Menge von Kardinalzahlen ist ν = ⋃ im(f) eine Kardinalzahl. Wenn y ∈ X, so gilt y = g(β) für ein β ∈ μ. Damit haben wir |y| = f(β) ≤ ν, d.h. es existiert eine Kardinalzahl ν < κ, sodass |y| ≤ ν für alle y ∈ X.

Sei λ = max{μ, ν}. Dann gilt λ ≤ κ und | ⋃ X| ≤ λ · λ = λ < κ.

Definition

1. ∑_{i∈I} κ_{i} = | ⋃_{i∈I} κ_{i} × {i}|

2. ∏_{i∈I} κ_{i} = |×_{i∈I}κ_{i}|

Vorlesung am 13.02.2008

Lemma 5.17. (Ungleichung von Zermelo und König (15.3)) Sei I ≠ ∅ und (κ_{i})_{i∈I}, (μ_{i})_{i∈I} seien Familien von Kardinalzahlen mit κ_{i} < μ_{i} für i ∈ I. Dann gilt ∑_{i∈I} κ_{i} < ∏_{i∈I} μ_{i}.

Beweis: Wir definieren eine Injektion f : ⋃_{i∈I} κ_{i} × {i} → ×_{i∈I}μ_{i}.

Für α ∈ κ_{i_{0}} sei f(α, i) = g_{α,i_{0}} ∈ ×_{i∈I}μ_{i} mit g_{α,i_{0}}(i) = \{ \begin{matrix}κ_{i}, & i ≠ i_{0} \\ α , & i = i_{0} \end{matrix} .

Damit erhalten wir die ≤-Relation. Zu zeigen bleibt noch, dass die Gleichheit nicht gelten kann, d.h. es ist zu zeigen, dass die Mengen nicht gleichmächtig sind. Sei f : ⋃_{i∈I}{κ_{i} × {i}|i ∈ I} → ×_{i∈I}μ_{i}. Wir zeigen, dass f nicht surjektiv ist.

Wir definieren g ∈ ×_{i∈I}μ_{i} durch g(i) = min\{α ∈ μ_{i}|α ∉ \underbrace{\{h(i)|h ∈ \underbrace{f(κ_{i} × \{i\})}_{Y_{i}}\}}_{X_{i}}\}.

Mit Y_{i} = f(κ_{i} × {i}) ergibt sich wegen |κ_{i} × {i}| = κ_{i} < μ_{i} auch |Y_{i}| ≤ κ_{i} < μ_{i}. Dann erhalten wir |X_{i}| ≤ κ_{i} < μ_{i}, also μ_{i} \ X_{i} ≠ ∅, d.h. g ∉ im(f).

Satz 5.7. (15.4) Für alle κ ∈ Cn^{∞} gilt 1. κ < κ^{cf(κ)}

2. cf(2^{κ}) > κ Beweis:

1. 1. ⇒ 2. Wenn cf(2^{κ}) ≤ κ wäre, so hätten wir nach 1. auch 2^{κ} < (2^{κ})^{cf(2^{κ})} ≤ (2^{κ})^{κ}) = 2^{κ·κ} = 2^{κ}. Dies ist ein Widerspruch.

2. 1.

Falls κ regulär ist so gilt κ = cf(κ) und damit κ^{cf(κ)} = κ^{κ} ≥ 2^{κ} > κ. Sei κ also singulär. Wir haben κ = ℵ_{α}, wobei α eine Limesordinalzahl ist. Wenn μ < ℵ_{α}, so gilt auch μ^{+} < ℵ_{α}. (μ^{+} ist die kleinste Kardinalzahl, die größer als μ ist.) Jetz sei f : cf(ℵ_{α}) → ℵ_{α} unbeschränkt in ℵ_{α}. Es gilt |f(β)|^{+} < ℵ_{α}. Also nimmt f o.B.d.A. nur Kardinalzahlen als Werte an.

(a) ℵ_{α} = ⋃_{β<cf(ℵ_{α})} f(β)

Dies folgt direkt aus der Definition der Kofinalität cf(ℵ_{α}).

(b) | ⋃_{β<cf(ℵ_{α})} f(β)| ≤ ∑_{β∈cf(ℵ_{α})} f(β)

(c) ∑_{β∈cf(ℵ_{α})} f(β) < ∏_{β<cf(ℵ_{α})} ℵ_{α} Diese Ungleichung ist lediglich eine Anwendung der Ungleichung von Zermelo und König.

(d) ∏_{β<cf(ℵ_{α})} ℵ_{α} = |×_{β∈cf(ℵ_{α})}ℵ_{α}| = ℵ_{α}^{cf(ℵ_{α})} Diese Gleichungen sind inzwischen ebenfalls trivial.

Zu zeigen ist also lediglich (b). Wir müssen dafür nur eine Injektion h : ⋃_{β<cf(ℵ_{α})} f(β) → ⋃_{β<cf(ℵ_{α})} f(β) × {β} finden. Dafür wählen wir h(γ) = (γ, β), wobei β minimal mit γ ∈ f(β) gewählt wird.

Korollar 5.5. (15.5)

1. ℵ_{ω} < ℵ_{ω}^{ℵ_{0}} Dies ist eine Anwendung von Satz 15.4, Aussage 1 mit κ = ℵ_{0}.

2. (a) 2^{ℵ_{0}} ≠ ℵ_{ω} (b) 2^{ℵ_{1}} ≠ ℵ_{ω}

(c) 2^{ℵ_{1}} ≠ ℵ_{ℵ_{1}} Diese Aussagen folgen aus Satz 15.4, Aussage 2:

(a) Würde 2^{ℵ_{0}} = ℵ_{ω} gelten, so hätten wir cf(2^{ℵ_{0}}) > ℵ_{0} = cf(ℵ_{ω}) = cf(2^{ℵ_{0}}).

(b) Würde 2^{ℵ_{1}} = ℵ_{ω} gelten, so hätten wir cf(2^{ℵ_{1}}) > ℵ_{0} = cf(ℵ_{ω}) = cf(2^{ℵ_{1}}).

(c) Würde 2^{ℵ_{1}} = ℵ_{ℵ_{1}} gelten, so hätten wir cf(2^{ℵ_{1}}) > ℵ_{1} = cf(ℵ_{ℵ_{1}}) = cf(2^{ℵ_{1}}).

5.16 Das Zermelo-Fraenkelsche Axiomensystem (ZF)

Definition (Extensionalitätsaxiom, Aussonderungsaxiom)

1. Extensionalitätsaxiom (Ext)

∀xy(∀z(z ∈ x ↔ z ∈ y) → x = y)

2. Schema der Ausonderungsaxiome (Aus) Für jedes φ(z, \overline{x}) der Sprache der Mengenlehre gibt es ∀\overline{x}∀x∃y∀z(z ∈ y ↔ z ∈ x ∧ φ(z, \overline{x})). Dieses Axiom vermeidet die Russellsche Antinomie: Für eine Menge x existiert y = {z ∈ x|z ∉ z}: Falls y ∈ y, so erhalten wir y ∈ x und y ∉ y, was einen Widerspruch darstellt. Falls y ∉ y, so haben wir y ∉ x oder y ∈ y. Letzteres war ausgeschlossen, also haben wir y ∉ x.

Lemma 5.18. (16.1) Für alle x gilt {z ∈ x|z ∉ z} ∉ x. Weiterhin folgt die Existenzs von ∅, x ∩ y und x ∉ y. Wenn eine Menge x existiert, dann erhalten wir die Existenz der leeren Menge ∅_{x} = {z ∈ x|z ≠ z} durch das Aussonderungsaxiom. Die Eindeutigkeit der leeren Menge folgt durch das Extensionalitätsaxiom. Weiterhin gilt x ∩ y = {z ∈ x|z ∈ y} und \y = {z ∈ x|z ∉ y}. Wir haben genau dann x = ∅, wenn ¬∃z(z ∈ x).

Definition Wir definieren ⋂ X durch ⋂ ∅ = ∅ und ⋂ X = {z|∀x(x ∈ X → z ∈ x)}.

Definition (Vereinigungsaxiome)

1. ∀xy∃w∀z(z ∈ x ∨ z ∈ y → z ∈ w)

Hieraus folgt mit Hilfe des Aussonderungsaxioms die Existenz von x ∪ y = {z|z ∈ x ∨ z ∈ y}.

2. ∀X∃y∀xz(x ∈ X ∧ z ∈ x → z ∈ y) Durch das Aussonderungsaxiom folgt die Existenz von ⋃ X = {z|∃x(x ∈ X ∧ z ∈ x)}.

Definition (Paarmengenaxiom, Potenzmengenaxiom)

1. Paarmengenaxiom ∀xy∃z(x ∈ z ∧ y ∈ z) Damit haben wir die Existenz von {x, y} = {z|z = x ∨ z = y}.

2. Potenzmengenaxiom ∀x∃y∀z(z ⊆ x → z ∈ y) Mit dem Aussonderungsaxiom existieren die Mengen P (x) = {z|z ⊆ x}, {x} = {z ∈ P (x)|z = x} und {x, y} = {x} ∪ {y}.

Definition (Unendlichkeitsaxiom (Inf)) Mengen x mit der Eigenschaft ∅ ∈ x ∧ ∀z(z ∈ x → z ∪ {z} ∈ x) nennt man induktiv. Nach dem Unendlichkeitsaxiom existiert eine induktive Menge ω_{0}. Mit dem Aussonderungsaxiom erhalten wir die Existenz von ω durch ω = {z ∈ ω_{0}|∀w, w induktiv → z ∈ w}.

Lemma 5.19. (16.2) ω ist induktiv.

Beweis: Trivial.

Definition (Ersetzungsaxiom) Für alle \overline{x} definieren wir die folgende Ersetzungsregel: Wenn es zu jedem x genau ein y mit φ(x, y, \overline{x}) gibt, so existiert zu jedem u ein v, dass die Bilder y der x ∈ u mit φ(x, y, \overline{x}) enthält. ∀\overline{x}(∀x∃!yφ(x, y, \overline{x}) → ∀u∃v∀xy(x ∈ u ∧ φ(x, y, \overline{x}) → y ∈ v)) Nach dem Aussonderungsaxiom existiert zu jedem \overline{x} und u die Menge \{y|∃x(x ∈ u ∧ φ(x, y, \overline{x}))\}.

Definition (Fundierungsaxiom) Jede nichtleere Menge besitzt ien ∈-minimales Element. ∀X(X ≠ ∅ → ∃x(x ∈ X ∧ ¬∃y(y ∈ X ∧ y ∈ x))) ⇒ Es existieren keine ∈-Kreise.

Definition (ZF) Mit ZF bezeichnen wir die Menge dieser Axiome.

Index

Σ-Beweis, 16 äquivalent

elementar, 41 logisch, 12

ableitbar

Aussagenlogik, 16 Abschnitt, 66

Bedingung, 66 Abschnittsbedingung, 66 Abtrennungsregel, 16 allgemeingültig

Prädikatenlogik, 32 Alphabet

Prädikatenlogik, 26 Anfangsstück, 8, 66

echtes, 8 Atomformeln

Prädikatenlogik, 27 aufzählbar

rekursiv, 60 Ausonderungsaxiom, 84 Aussage

Prädikatenlogik, 29 Aussagenlogik, 7

Alphabet, 7 Aussagenvariablen, 7 Axiome, 16 Beweis, 16 Disjunktive Normalform, 14 erfüllbar, 11 Erfüllbarkeit

Formelmengen, 15 Formelmenge, 7 Grundzeichen, 7 Hilfszeichen, 7 inkonsistent, 19 Konjunktive Normalform, 14 Konnektoren, 7 konsistent, 19 Kontradiktion, 11 Schlussregel, 16 Semantik, 10 Sprache, 7 Tautologie, 11 Vollständigkeitssatz, 21 widerspruchsfrei, 19 widerspruchsvoll, 19 Wort, 7 Aussagenvariablen, 7 Automorphismus, 25 axiomatisierbar, 39 endlich, 39 rekursiv, 62

Axiome Aussagenlogik, 16

Belegung, 10

Beweis

Aussagenlogik, 16 bijektiv, 24 Boolesche Funktion, 15 Boolsche Kombination

Prädikatenlogik, 33

Deductions Theorem, 17 deduktiver Abschluss, 15 Prädikatenlogik, 37

definierbar, 40

Disjunktive Normalform Aussagenlogik, 14 Prädikatenlogik, 33

disjunktive pränexe Normalform, 35

Einbettung, 24

elementar, 52 elementar, 39

äquivalent, 41 axiomatisierbar, 39 Einbettung, 52 Unterstruktur, 52 Elementare Logik, 23

Funktionssymbole, 23 Homomorphismus, 24 Konstantensymbole, 23 Relationssymbole, 23 Signatur, 23 Stellenzahl, 23 Struktur, 23 erfüllbar

Prädikatenlogik, 32, 37 erfüllbar in M

Prädikatenlogik, 32 Erfüllbarkeit

Aussagenlogik

Formelmengen, 15 Erfüllbarkeitsproblem, 12 Ersetzungsaxiom, 85 existentiell, 36 Extensionalitätsaxiom, 84

Folgennummer, 59

Anfangsstuck, 60 Folgennummern

Menge, 59 Formel

Aussagenlogik, 7 Eindeutigkeit, 9 Teil-, 10

Formeln

Prädikatenlogik, 27 freies Vorkommen, 28 Fundierungsaxiom, 85 Funktion

rekursiv, 55

repräsentierbar, 61 repräsentiert durch

Term, 61 repräsentiert durch Formel, 61

Funktionssymbole Elementare Logik, 23

gültig

Prädikatenlogik, 32 Gültigkeit

L_{M}-Aussagen

Prädikatenlogik, 31 Aussagen

Prädikatenlogik, 30 gebundenes Vorkommen, 28 gleichmächtig, 74 Grundaussagen, 10

Hüllenoperator, 15 Halbordnung, 46 Henkin-Erfüllungsmenge, 48 homomorphes Bild, 24 Homomorphismus

Elementare Logik, 24

Prädikatenlogik 1. Stufe, 24

Induktion Formelaufbau, 8

Funktionsdefinition, 9 induktiv

Menge, 85 injektiv, 24 inkonsistent

Aussagenlogik, 19 Prädikatenlogik, 45

Isomorphietyp, 25 Isomorphismus, 25

Kardinalzahl, 74 Klasse aller, 74 Klasse aller unendlichen, 74 regulär, 81 schwach unerreichbar, 81 singulär, 81

Kardinalzahlen

Nachfolger, 76 kardinalzahlen Limes, 76 kartesisches Produkt Struktur, 26

Kette, 65

Klammernsparen Regeln, 10

Klasse, 65

Kardinalzahlen, 74 unendliche, 74 Ordinalzahlen, 69

Kofinalität, 80 Koinzidenzlemma

Prädikatenlogik, 29 Komplexitätsklasse, 12 Konjunktive Normalform Aussagenlogik, 14 Prädikatenlogik, 33

konjunktive pränexe Normalform, 35 konsistent

Aussagenlogik, 19

maximal

Prädikatenlogik, 45 Prädikatenlogik, 45 Konstantenerweiterung, 31 Konstantensymbole

Elementare Logik, 23 konstanter Term, 29 Kontradiktion

Aussagenlogik, 11 kontradiktorisch

Prädikatenlogik, 32

Limeskardinalzahlen, 76

Limeszahl, 72

lineare Ordnung, 65 Literal, 14 logisch äquivalent, 12

Prädikatenlogik, 32 logische Zeichen

Prädikatenlogik, 26

Matrix

pränexe Normalform, 35 maximal Konsistent

Prädikatenlogik, 45 Menge

induktiv, 85 wohlgeordnet, 66

Modell, 15

Prädikatenlogik, 37 Modus Ponens, 16 Monomorphismus, 24

Nachfolgerkardinalzahl, 76 Nachfolgerzahl, 72 nichtlogische Zeichen

Prädikatenlogik, 26 Normalform

disjunktiv Aussagenlogik, 14 Prädikatenlogik, 33

konjunktiv Aussagenlogik, 14 Prädikatenlogik, 33

pränex, 35 Nummeral, 61

Oberstruktur, 25 Ordinalzahl, 69

Klasse aller, 69 Limeszahl, 72 Nachfolgerzahl, 72

Ordnung, 65 linear, 65 partiell, 65 total, 65 Wohl-, 66

Paarmengenaxiom, 84 partielle Ordnung, 65 Potenzmengenaxiom, 84 Prädikantenlogik

pränexe Normalform, 35

Matrix, 35 Prädikat

rekursiv, 56 repräsentiert durch, 61 reprasentierbar, 61

Prädikatenlogik, 26 Äquivalenz, 37 allgemeingültig, 32 Alphabet, 26

Substitution, 27 Atomformeln, 27 Aussage, 29 Aussagenmenge

vollständig, 39 Boolsche Kombination, 33 deduktiver Abschluss, 37 Disjunktive Normalform, 33 disjunktive Normalform

pränex, 35 erfüllbar, 32 erfüllbar in M, 32 Folgerung, 37 Formeln, 27 gültig, 32 Gültigkeit

L_{M}-Aussagen, 31 Aussagen, 30

inkonsistent, 45 Koinzidenzlemma, 29 Konjunktive Normalform, 33 konjunktive Normalform

pränex, 35 konsistent, 45

maximal, 45 kontradiktorisch, 32 logisch äquivalent, 32 logische Zeichen, 26 maximal konsistent, 45 Modell, 37 nichtlogische Zeichen, 26 Normalform

pränex, 35 pränexe Normalform

disjunktiv, 35

existentiell, 36

konjunktiv, 35

universiell, 36 quantorenfrei, 35 Tautologie, 34 Term, 26 Theorie, 38

vollständig, 39 vollständig

Aussagenmenge, 39 Theorie, 39

Wert L_{M}-Term, 31 Term, 30

widerspruchsfrei, 45

widerspruchsvoll, 45 Prädikatenlogik 1. Stufe

Homomorphismus, 24 Struktur, 23

pränexe Normalform, 35 disjunktiv, 35 existentiell, 36 konjunktiv, 35 Matrix, 35 universiell, 36

Pradikatenlogik erfüllbar, 37

quantorenfrei, 35

Realisierung, 15 Redukt

Struktu, 26 regulär

Kardinalzahl, 81 rekursiv

aufzählbar, 60 Funktion, 55

induktiv definiert, 60 Prädikat, 56

rekursiv axiomatisierbar, 62 Relationssymbole

Elementare Logik, 23 repräsentierbar

Funktion, 61 reprasentierbar

Prädikat, 61 Russellsche Antinomie, 66

Schlussregel

Aussagenlogik, 16 Semantik

Aussagenlogik, 10 Sequenzennummer, 59 Signatur

Elementare Logik, 23 singulär

Kardinalzahl, 81 Stellenzahl

Elementare Logik, 23 Struktur

Elementare Logik, 23 kartesisches Produkt, 26 Oberstruktur, 25 Prädikatenlogik 1. Stufe, 23 Redukt, 26 Unterstruktur, 25

elementar, 52 Substitution, 10 Prädikatenlogik, 29 Alphabet, 27

surjektiv, 24

Tautologie Aussagenlogik, 11 Prädikatenlogik, 34

Teilformel, 10

Term

Prädikatenlogik, 26 Theorie

Prädikatenlogik, 38 vollständig, 39 totale Ordnung, 65 transitiv, 69

Unendlichkeitsaxiom, 85 universiell, 36 Unterstruktur, 25

Variablenkollision, 29 Vereinigungsaxiom, 84 vollständig, 20

Aussagenmenge, 39 Theorie, 39 Vollständigkeitssatz

Aussagenlogik, 21

Wahrheitswert, 10 widerspruchsfrei

Aussagenlogik, 19 Prädikatenlogik, 45

widerspruchsvoll Aussagenlogik, 19 Prädikatenlogik, 45

Wirkungsbereich

Quantoren, 28 wohlgeordnete Menge, 66 Wohlordnung, 66 Wort, 7

leer, 7

Zorn’s Lemma, 46