Mathematische Logik (Erste Auflage): Errata

Dies ist die aktuelle Fehlerliste von Mathematische Logik. Mathematik Kompakt. Birkhäuser, 2010. Erste Auflage.

Hinweise auf Fehler verdanke ich Hans Adler, Philipp Bamberger, Franz Baumdicker, Simon Börger, Juan-Diego Caycedo, Matthias Fetzer, Martin Hils, Mohsen Khani, Michael Maier, Amador Martin Pizarro, Heike Mildenberger, Aaron Puchert, Luca Motto Ros und Katrin Tent.

• Seite vii, vorletzter Paragraph. Es muß heißen: … wird aber auch im vierten Kapitel verwendet…

• Seite 6, Hilfsatz 1.2. Der letzte Satz des Beweises wird besser ersetzt durch: Wenn φ = (ψ_{1} ∧ ψ_{2}) und φ′ = (ψ′_{1} ∧ ψ′_{2}), ist ψ_{1} Anfangsstück von ψ′_{1} oder umgekehrt, woraus nach Induktionsannahme folgt, daß beide gleich sind. Also muß ψ_{2} ein echtes Anfangsstück von ψ′_{2} sein. Das widerspricht der Induktionsannahme.

• Seite 7, Aufgabe 4. Die Behauptung, insbesondere Teil a) stimmt nicht, wenn L Funktionszeichen enthält.

• Seite 12, Aufgabe 6. Es muß heißen p(X_{1}, …, X_{n}) ∈ ℤ[X_{1}, …, X_{n}].

• Seite 14, Lemma über die Axiome der Gleichheit. In allen Formeln außer im Reflexivitätsaxiom fehlen Klammern nach den Allquantoren. Das Symmetrieaxiom muß zum Beispiel so lauten: ∀x, y (x ≐ y → y ≐ x).

• Seite 16, Aufgabe 11. Ein Beispiel für eine Formel, die immer den Wahrheitswert F hat, ist (p ∧ ¬ p), und nicht etwa (p ∧ ¬ q).

• Seite 16. Die Formeln in Aufgabe 12 sind ⋁_{i=1}^{N} k_{i} und ⋀_{i=1}^{N} d_{i}.

• Seite 16. Der erste Satz von Aufgabe 13 muß lauten: Zeigen Sie, daß {∧, ¬ } ein vollständiges Junktorensystem ist.

• Seite 17. Nach „Die eine Richtung ist leicht zu zeigen:“ sollte besser stehen Die Menge der allgemeingültigen Formeln enthält wegen der Lemmata in Abschnitt 3 die Axiome B1, B2, B3 und ist unter den Regeln B4 und B5 abgeschlossen. Also sind alle beweisbaren Formeln allgemeingültig. Der Beweis der Umkehrung macht den Rest des Abschnitts aus.

• Seite 19. Der Satz in Zeile 8 Zusammen mit … sollte besser so weitergehen: den ∀–Quantorenaxiomen ∀y_{i}, …, y_{n} φ(x_{1}, …, x_{i−1}, y_{i}, …, y_{n}) → ∀y_{i+1}, …, y_{n} φ(x_{1}, …, x_{i}, y_{i+1} …, y_{n}), (i = 1, …, n), und Aussagenlogik ergibt sich ⊢_{L} φ(x_{1}, …, x_{n}).

• Seite 19. Im Absatz nach dem Beweis von Lemma 4.2, sollte es besser heißen: 4.1 (1).

• Seite 20, letzter Teil von \underline{Schritt 1}. Es muß dort heißen: Wenn wir so fortfahren, erhalten wir eine widerspruchsfreie Henkintheorie T^{+} = ⋃_{i∈ℕ} T_{i} mit Konstantenmenge C = ⋃_{i∈ℕ} C_{i}.

• Seite 21. Am Anfang von \underline{Schritt 3} muß es heißen: ist T^{∗} das vollständige Diagramm von 𝔄 statt ist T^{∗} das vollständige Diagramm von 𝔄^{∗}. Im Beweis der Eindeutigkeit sollte man den Isomorphismus F nennen, nicht f.

• Seite 22. Nach Gleichung (2) fehlt ein ∈ T^{∗}. Es muß heißen:

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

• Seite 28. Im dritten und vierten Fall muß φ_{i} statt φ stehen.

• Seite 30. Am Anfang des Beweises des Interpolationssatzes schreibt man besser: Denn wenn φ_{1} ≻ β(c_{1}, …, c_{n}) und β(c_{1}, …, c_{n}) ≻ φ_{2} allgemeingültig sind, leistet δ = ∃x_{1}, …, x_{n} β(x_{1}, … x_{n}) das Verlangte.

• Seite 31. Im vierten Fall muß stehen Δ_{1} ∪ Δ_{2} ≻ (Γ′_{1} ∪ {φ_{i}}) ∪ Γ_{2}.

• Seite 32. Die letzte Formel von Aufgabe 28 muß richtig heißen:

T (P) ⊢ ∀x (P (x) ↔ π(x)).

• Seite 33. In der siebten und achten Zeile von unten sollte stehen:

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

• Seite 35. Im Beweis des Satzes von Herbrand muß es heißen: Nehmen wir umgekehrt an, daß

⋀_{i=1}^{N} ¬ ψ(t^{i}) = ¬ ψ(t_{1}^{1}, t_{2}^{1}, … t_{n}^{1}) ∧ ⋯ ∧ ¬ ψ(t_{1}^{N}, t_{2}^{N}, … t_{n}^{N})

• Seite 38, oben. Die erste Formel heißt richtig:

x_{1} ≐ f(c, g(x_{3}, x_{3}))

• Seite 39, Zeile 2: Es muß heißen:

Die Allgemeingültigkeit einer aussagenlogischen Formel f läßt sich feststellen, indem man überprüft, daß alle Belegungen der Variablen von f den Wahrheitswert W ergeben.

• Seite 39, Formel (7.2). Es muß heißen:

⋁_{C∈C} ⋀_{L∈C} L

• Seite 39, Ende des Paragraphen nach Formel (7.2). Es muß heißen:

Wir lassen auch die leere Klauselmenge zu, die nicht erfüllbar ist, und die leere Klausel, die immer den Wahrheitswert W hat.

• Seite 40. Überall muß C|p statt C|A stehen. Unten muß es richtig heißen Weil p in C|p = W und C|p = F nicht mehr vorkommt

• Seite 45. Das Lemma über die Existenz des direkten Produkts muß beginnen mit: Aus den Axiomen von ZFC folgt ….

• Seite 46. Es muß heißen

F = \{(u, z) | φ(u, z, \overline{w})\}.

• Seite 49, Aufgabe 37, Teil 2. Es muß heißen

β(2^{n_{1}} + ⋯ + 2^{n_{k}})

und

⋯ n_{−3} E_{β} n_{−2} E_{β} n_{−1} E_{β} n_{0}

• Seite 51, Definition von „transitiv “. Elemente statt Element.

• Seite 53, Lemma (2). Es muß heißen: der unmittelbare Nachfolger von n • Seite 53, Beweis des Lemmas. Besser wäre m ≤ n.^{10} 10 ist kein Exponent,

sondern verweist auf eine Fußnote.

• Seite 55, Beweis von 1. In der ersten Zeile soll es heißen: x < y ∈ S → x ∈ S • Seite 55, Beweis von 3. Es sollte besser heißen: 9.1 (1).

• Seite 57, Ende des Beweises von Lemma 10.1: Richtig ist F′ = f′ ∪ {(β, ∗) | α′ ≤ β}.

• Seite 59. Im Beweis des Lemmas muß stehen:

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

• Seite 60, Aufgabe 45: Es muß heißen α · 0 = 0.

• Seite 65, Zeile 11: Es muß heißen: Der folgende Satz wurde von Rosser. …

• Seite 65, Fußnote 19. Es muß heißen: Eigentlich müßte man statt Bew(⌜¬ R⌝, z) die Formel Bew(Neg(⌜R⌝), z) nehmen

• Seite 66, Aufgabe 48. Ersetze die Aufgabe durch das folgende:

Aufgabe 48. Angenommen ZFC ist konsistent, geben Sie eine konsistente Erweiterung von ZFC an, die die Inkonsistenz von ZFC, und damit auch ihre eigene Inkonsistenz, beweist. Es ist also denkbar, daß auch ZFC seine eigene Konsistenz beweist, ohne inkonsistent zu sein.

• Seite 71, Zeile -1 und Seite 72, Zeilen 8, -7. Hier sind die Hilfsregister der Kopiermaschinen gemeint.

• S.72, oben. Richtig ist: K^{R+1,1}H^{∗} (berechnet h(f_{1}(x), f_{2}(x)).

• Seite 72, Aufgabe 51. Es muß A = {0, 1, |} heißen.

• Seite 72, Aufgabe 53. Die Behauptung c) war inkorrekt. Ersetze die Aufgabe durch das folgende:

Aufgabe 53. Definiere die Funktionenfolge A_{0}, A_{1}, … durch A_{0}(x) = x + 1 und A_{a+1}(x) = A_{a}^{x+1}(1).

a) Zeigen Sie, daß jedes A_{n} primitiv rekursiv ist.

b) Begründen Sie, warum die (modifizierte) Ackermannfunktion A(x, a) = A_{a}(x) in einem intuitiven Sinn berechenbar ist. (Wir werden in Aufgabe 56 sehen, daß A rekursiv ist.)

c) Für jede primitiv rekursive Funktion f: ℕ^{n} → ℕ gibt es ein a, sodaß für alle x_{1}, …, x_{n}

f(x_{1}, …, x_{n}) ≤ A_{a}(∑_{i} x_{i}).

d) Die Ackermannfunktion ist nicht primitiv rekursiv.

Hinweis zu ??): Beweise zuerst, daß A in beiden Argumente streng monoton ist, und die Ungleichung A_{a}(A_{a+1}(x)) ≤ A_{a+2}(x). Dann zeigt man die Behauptung induktiv über den Aufbau primitiv rekursiver Funktionen. Zu ??): Man konstruiere aus A eine Funktion ℕ → ℕ, für die ??) nicht gilt.

• Seite 74, letzte Zeile vor Lemma 13.2: Verwende K_{._{=}0} statt K und K_{._{=}0}((x +

1) . − y) statt K_{._{=}0}(x + 1 . − y).

• Seite 76, Zeile 3: Es muß heißen:

p(x) = (x + 1)–te Primzahl • Seite 77: Es muß heißen: Schreibbefehl b = PUSH(r, l)

• Seite 78, Zeile -8: Es muß heißen:

Stop(m, k) ⟺ (m)_{(k)_{0}} = 0.

• Seite 79, Aufgabe 56. Eine Berechung a der Ackermannfunktion soll die fol-

genden Eigenschaften haben (siehe Korrektur der Aufgabe 53):

• Wenn (x, 0, z) in a vorkommt, ist z = x + 1.

• Wenn (0, y + 1, z) in a vorkommt, gehört (1, y, z) zu a.

• Wenn (x + 1, y + 1, z) in a vorkommt, dann gibt es ein w, sodaß (x, y +

1, w) und (w, y, z) zu a gehören.

• Seite 80, letzte Zeile im Beweis des Lemmas. Das soll sein:

f(x) = \begin{cases}(x)_{0} & wenn \overline{R}((x)_{0}, (x)_{1}) \\ r & sonst \end{cases}

• Seite 81, dritte und vierte Zeile im Beweis von Lemma 14.3. Das sollte sein:

g(\overline{x}) = μy (\overline{V} (\overline{x}, y) ∨ \overline{W} (\overline{x}, y))

für alle \overline{x} definiert. …

• Seite 81, Aufgabe 57.

Teil 1: Richtig ist: Zeigen Sie, daß die partiell rekursiven Funktionen genau die berechenbaren partiellen Funktionen sind. Teil 2: Es muß heißen: Wie muß man die Regeln R0 bis R3 modifizieren,…

• Seite 82, Aufgabe 61. Richtig ist:

φ_{e}^{m+n}(x_{1}, …, x_{m}, y_{1}, …, y_{n}) = φ_{s_{n}^{m}(e,x_{1},...,x_{m})}^{n}(y_{1}, …, y_{n}).

• Seite 87, Beweis von 16.2, erster Absatz. Richtig muß es heißen: Würde p auch bj + 1 teilen, für ein j ≠ i, wäre p ein Teiler von b(j − i) und daher auch von j − i.

• Seite 90, Zeile 8. Es muß heißen:

∃y_{1}, y_{2} (φ_{1}(y_{1}, x_{1}) ∧ φ_{2}(y_{2}, x_{1}) ∧ φ_{h}(x_{0}, y_{1}, y_{2}))

• Seite 93, Definition von Σ_{1}–Formel. Es muß dort heißen:

dabei ist t ein Term, der x nicht enthält,… • Seite 93, Beweis von 18.2. Der letzte Absatz sollte ersetzt werden durch:

Wenn 𝔑 ⊧ (∀x_{0} < x_{1}ψ)[a_{1}, …, a_{n}], ist 𝔑 ⊧ ψ[a_{0}, a_{1}, …, a_{n}], und daher nach Induktionsvoraussetzung Q^{∗} ⊢ ψ[Δ_{a_{0}}, Δ_{a_{1}}, …, Δ_{a_{n}}], für alle a_{0} < a_{1}. Wegen Q^{∗}3 folgt daraus

Q^{∗} ⊢ (∀x_{0} < x_{1}ψ)[Δ_{a_{1}}, …, Δ_{a_{n}}].

• Seite 94, oben. Es muß heißen:

\begin{aligned}R(a) & ⇒ & 𝔑 ⊧ φ(Δ_{a}) & ⇒ & Q^{∗} ⊢ φ(Δ_{a}) & ⇒ & T ⊢ φ(Δ_{a}) \\ ¬ R(a) & ⇒ & 𝔑 |̸= φ(Δ_{a}) & ⇒ & & & T ⊬ φ(Δ_{a}) \end{aligned} .

• Seite 94, Satz 18.4. Richtig ist

{⌜φ⌝ | φ allgemeingültige L–Formel}.

• Seite 94. In der Definition muß es heißen:

T ⊢ ∀x_{0} (x_{0} ≐ Δ_{a_{0}} ⟷ φ(x_{0}, Δ_{a_{1}}, …, Δ_{a_{n}}))

• Seite 97, Aufgabe 77. Ersetze monadische Formel zweiter Stufe durch zweitstufige Formel.

• Seite 99, Ungleichung (19.1). Richtig ist:

\underline{0} ≤ x.

• Seite 102. In der Definition muß es heißen:

P ⊢ φ ⟷ ¬ ψ

• Seite 103, Aufgabe 79, drittletzte Zeile. Es muß heißen: … die gleichen erststufigen Aussagen folgen wie aus. …

• Seite 104, oben. Es muß heißen:

B′(s, n) = ∀i < n(Ax(β′(s, i)) ∨ ∃j, k < i Reg(β′(s, i), β′(s, j), β′(s, k))),

und weiter unten: Aus dem Deduktionslemma folgt, daß Bew′ in 𝔑 die Menge der Gödelnummern der in P beweisbaren Aussagen definiert.

• Seite 105, Lemma 20.2. Im Beweis von L1 muß es heißen: Die Umkehrung gilt natürlich auch, weil P wahr ist.

• Seite 106, Folgerung aus dem Satz von Loeb. Es muß heißen:

P ⊢ Bew(Δ_{⌜ψ⌝}) → ψ ⇒ P ⊢ ψ

Stand: 14. März 2023 Martin Ziegler