Arithmetische Satzmenge/Repräsentierungen/Fixpunktsatz/Fakt/Beweis/Aufgabe/Lösung

Wir betrachten die Abbildung

F : ℕ \times ℕ ⟶ ℕ, (m, n) ⟼ F (m, n),

die durch

F (m, n) := {\begin{matrix} G N (α (n)), falls m die G N eines α \in L_{1}^{A r} ist, \\ 0 sonst, \end{matrix}

festgelegt ist. Bei der Berechnung von $F$ wird also zuerst geschaut, ob das erste Argument, also $m$ , die Gödelnummer eines arithmetischen Ausdrucks mit genau einer freien Variablen ist. Falls nicht, so ist $F (m, n) = 0$ , unabhängig von $n$ . Falls ja, so ist also $m = G N (α)$ mit $α \in L_{1}^{A r}$ . In diesem Ausdruck wird dann die einzige freie Variable durch das zweite Argument der Abbildung, also $n$ , ersetzt, wobei man einen Satz $α (n)$ erhält. Dessen Gödelnummer ist nach Definition der Wert der Abbildung $F (m, n)$ . In diesem Fall ist also $F (m, n) = G N (α (n))$ . Diese Erläuterungen zeigen zugleich, dass $F$ berechenbar ist.
Da $Γ$ nach Voraussetzung Repräsentierungen erlaubt, gibt es einen Ausdruck $φ (x, y, z)$ mit drei freien Variablen, der diese Abbildung repräsentiert. D.h. es gilt für jede Belegung der Variablen mit natürlichen Zahlen $m, n, k$ die Beziehungen (wir können annehmen, dass $Γ$ widerspruchsfrei ist, da andernfalls das Resultat trivial ist)

F (m, n) = k genau dann, wenn Γ ⊢ φ (m, n, k),

F (m, n) ≠ k genau dann, wenn Γ ⊢ \neg φ (m, n, k)

und (für jede Belegung $m, n$ für $x$ und $y$ )

Γ ⊢ \exists! z φ (m, n, z) .

Den Fixpunkt zu einem vorgegebenen $α \in L_{1}^{A r}$ erhalten wir nun durch eine trickreiche Anwendung von $φ$ . Wir setzen

s := \forall z (φ (x, x, z) \to α (z)) .

Der Ausdruck $s$ besitzt die Gödelnummer $G N (s)$ . Wir behaupten nun, dass der Satz

q := s \frac{G N (s)}{x} = \forall z (φ (G N (s), G N (s), z) \to α (z))

die zu beweisende Ableitungsbeziehung $Γ ⊢ q \leftrightarrow α (G N (q))$ erfüllt.
Der Ausdruck $s$ besitzt die einzige freie Variable $x$ , daher gilt

F (G N (s), G N (s)) = G N (s \frac{G N (s)}{x}) = G N (q) .

Aufgrund der Repräsentierungseigenschaft ist daher

Γ ⊢ φ (G N (s), G N (s), G N (q)) .

Aus der Allaussage $q$ erhält man durch Spezialisierung (man ersetzt die Variable $z$ durch den Term $G N (q)$ )

⊢ q \to (φ (G N (s), G N (s), G N (q)) \to α (G N (q))) .

Da das Antezedens der rechten Implikation aus $Γ$ ableitbar ist, folgt

Γ ⊢ q \to α (G N (q)) .

Dies besagt also die Ableitbarkeit der Hinrichtung.

Die aufgrund der Repräsentierbarkeit oben angeführte eindeutige Existenzaussage führt zu

Γ ⊢ \forall z (φ (G N (s), G N (s), z) \to (z = G N (q))) .

Durch Substitution ergibt sich

⊢ (z = G N (q)) \to (α (G N (q)) \to α (z))

und somit nach einer prädikatenlogischen Umformulierung

Γ ⊢ \forall z (φ (G N (s), G N (s), z) \land α (G N (q)) \to α (z)) .

Da hierbei $α (G N (q))$ keine freie Variablen besitzt, ist auch

Γ ⊢ α (G N (q)) \to (\forall z (φ (G N (s), G N (s), z) \to α (z))),

und das Sukzedens ist gerade

q

, sodass auch die Rückrichtung ableitbar ist.

Zur gelösten Aufgabe