250 6 Korrektheit und Vollstandigkeit des Redehandlungskalkuls
(xvi) Wenn θ0, ..., θr-1 ∈ GTERMH, θ'0, ..., θ'r-1 ∈ GTERMH, fur alle i < r: rθi = θ'i^l ∈ X
und φ ∈ FUNK r-stellig, dann rφ(θ0, ., θr-1) = φ(θ'0, ., θ'r-ι)^l ∈ X, und
(xvii) Wenn θ0, ., θr-1 ∈ GTERMH, θ'0, ., θ'r-1 ∈ GTERMH, fur alle i < r: rθi = θ'i^l ∈ X
und Φ ∈ PRA r-stellig und rΦ(θ0, ., θr-1)^l ∈ X, dann rΦ(θ'0, ., θ'r-1)^l ∈ X.
Theorem 6-9. Hintikka-Obermengen fur konsistente L-Aussagenmengen
Wenn X ⊆ GFORM und X konsistent, dann gibt es ein Y ⊆ GFORMH, so dass
(i) Y ist eine Hintikka-Menge und
(ii) X ⊆ Y.
Beweis: Sei X ⊆ GFORM und X konsistent. Sei nun g eine Bijektion zwischen N und
GFORMH. Nun wird unter Ruckgriff auf g mit Hilfe der (Konversen der) Cantorschen
Paarungsfunktion C eine Aufzahlung der Γ ∈ GFORMH definiert, in der jede Aussage
abzahlbar unendlich oft als Wert auftritt.16 Sei dazu F = {(k, Γ) | Es gibt i, j ∈ N, k =
(i-+j) lζl j'ŋ ∙j und γ = g(j)}. Dann ist F eine Funktion von N nach GFORMH. Zunachst ist
Dom(F) ⊆ N. Sei nun k ∈ N. Dann gilt mit der Surjektivitat der CANTORschen Paarungs-
funktion und Dom(g) = N, dass es i, j ∈ N und Γ ∈ GFORMH gibt, so dass k =
(i+j) (il j'ŋ ∙j und γ = g(j). Also ist auch N ⊆ Dom(F) und damit insgesamt Dom(F) = N.
Nach den Definitionen von F und g gilt sodann Ran(F) ⊆ GFORMH. Seien nun (k, Γ), (k,
Γ*) ∈ F. Dann gibt es i, j und i', j' so dass (ij(2+j+-)+j = k = (i,+j7) <ζ+j'+1l+j' und Γ =
g(j) und Γ* = g(j'). Dann ist wegen der Injektivitat der Cantorschen Paarungsfunktion i
= i' und j = j' und damit mit der Injektivitat von g: Γ = g(j) = g(j') = Γ*. Sodann gilt fur al-
le l ∈ N und alle Γ ∈ GFORMH: Es gibt ein k > l, so dass F(k) = Γ. Sei namlich l ∈ N
und Γ ∈ GFORMH. Dann gibt es ein s ∈ N, so dass Γ = g(s). Dann ist l ≤ (l+s) (^+s+1)+s <
(l+1+s)∙(l+1+s+1)
+s und F (■
(l+1+s)∙(l+1+s+1)
+s) = g(s) = γ.
Nun wird unter Ruckgriff auf F eine Funktion G auf N definiert, mit der die gewunsch-
te Hintikka-Obermenge zu X erzeugt wird. Sei dazu G(0) = X. Fur alle k ∈ N sei nun
G(k+1) wie folgt bestimmt: Wenn F(k) ∈ G(k), dann:
16 Zur CANTORschen Paarungsfunktion C: N × N → N mit C(i, j) = (i + j) ∙ (i + j + 1)∕2+j siehe etwa
Deiser, O.: Mengenlehre, S. 112-113.