[figure]

Mathematisches Institut der Universität Bonn Abt. für Grundlagenforschung der Mathematik

Prof. Dr. Peter Koepke

Einführung in die Mathematische Logik WS 2000/2001

Übungsaufgaben, Folge 8, Abgabe: 14.12.2000 in der Vorlesung

Aufgabe 1 Es sei L = (I, J, K, t) eine formale Spache, j ∈ J mit t(j) = 1 und k ∈ K. Zeigen Sie:

(a) ḟ_{j} ˙(v̇_{0}˙) ∉ Tm(L).

(b) ˙∀ ċ_{k} v̇_{0} ≐ ḟ_{j}ċ_{k} ∉ Fml(L).

Für die nächsten Aufgaben fixieren wir ein paar Sprechweisen. Es sei A ein Alphabet. ϱ heißt Regel über A, falls es ein n = n_{ϱ} ∈ ℕ gibt mit ϱ ⊆ (A^{∗})^{n}×A^{∗}. Statt ϱ((w_{1}, …, w_{n}), w) schreiben wir auch

ϱ: \frac{w_{1}, …, w_{n}}{w}

und sagen: Bei Input w_{1}, …, w_{n} produziert ϱ das Wort w. Im Fall n_{ϱ} = 0 gilt ϱ ⊆ A^{∗} und wir nennen ϱ eine Anfangsregel. Eine Menge 𝒦 heißt Kalkül über A, falls jedes Element von 𝒦 eine Regel über A ist. Das Erzeugnis Erz(𝒦) von 𝒦 die ⊆-kleinste Menge mit

∀ϱ ∈ 𝒦 ∀w_{1}, …, w_{n_{ϱ}}, w ∈ A^{∗}
((w_{1} ∈ Erz(𝒦) ∧ … ∧ w_{n} ∈ Erz(𝒦) ∧ ϱ((w_{1}, …, w_{n_{ϱ}}), w)) ⟶ w ∈ Erz(𝒦)).

Aufgabe 2 (a) Zeigen Sie folgendes Induktionsschema: Es sei ϕ(x) eine ∈-Formel und es gelte ∀ϱ ∈ 𝒦 ∀w_{1}, …, w_{n_{ϱ}}, w ∈ Erz(𝒦) ((ϕ(w_{1}) ∧ … ∧ ϕ(w_{n_{ϱ}}) ∧ ϱ((w_{1}, …, w_{n_{ϱ}}), w)) ⟶ ϕ(w)).

Dann gilt: ∀w ∈ Erz(𝒦) ϕ(w).

(b) Es seien w_{1}, …, w_{N}, w ∈ A^{∗}. Die Sequenz (w_{1}, …, w_{N}) heißt Ableitung für w, falls gilt:

• w_{N} = w;

• ∀k ≤ N ∃ϱ ∈ 𝒦 ∃i_{1}, …, i_{n_{ϱ}} < k ϱ((w_{i_{1}}, …, w_{i_{nϱ}}), w_{k}). Zeigen Sie Erz(𝒦) = {w ∈ A^{∗} | w hat eine Ableitung}.

Wir sagen, der Kalkül 𝒦 hat eindeutige Zerlegung, falls sich jedes w ∈ Erz(𝒦) auf genau eine Weise produzieren läßt, genauer, falls gilt:

∀w ∈ Erz(𝒦) ∀ϱ_{0}, ϱ_{1} ∈ 𝒦 ∀w_{1}^{0}, …, w_{n_{ϱ_{0}}}^{0}, w_{1}^{1}, …, w_{n_{ϱ_{1}}}^{1} ∈ Erz(𝒦)
((ϱ_{0}((w_{1}^{0}, …, w_{n_{ϱ_{0}}}^{0}), w) ∧ ϱ_{1}((w_{1}^{1}, …, w_{n_{ϱ_{1}}}^{1}), w))
⟶ (ϱ_{0} = ϱ_{1} ∧ w_{1}^{0} = w_{1}^{1} ∧ … ∧ w_{n_{ϱ_{0}}}^{0} = w_{n_{ϱ_{1}}}^{1})).

Aufgabe 3 Geben Sie über dem Alphabet A_{L} einen Kalkül 𝒦_{L} an, der eindeutige Zerlegung hat und für den Erz(𝒦_{L}) = Fml(L) gilt.

Aufgabe 4 Es sei 𝒦 ein Kalkül, der eindeutige Zerlegung hat. Beweisen Sie folgenden Rekursionssatz: Für jedes ϱ ∈ 𝒦 sei G_{ϱ}: V^{n_{ϱ}+1} → V. Dann existiert genau eine Funktion H: Erz(𝒦) → V mit folgender Eigenschaft:

∀ϱ ∈ 𝒦 ∀w_{1}, …, w_{n_{ϱ}}, w ∈ Erz(𝒦)
(ϱ((w_{1}, …, w_{n_{ϱ}}), w) ⟶ H(w) = G_{ϱ}(H(w_{1}), …, H(w_{n_{ϱ}}), w)).

Tipp: Setzen Sie E_{N} :≡ {w ∈ Erz(𝒦) | w hat eine Ableitung von höchstens Länge N}. Definieren Sie dann H_{N}: E_{N} → V mit H_{N} ↾ E_{N−1} = H_{N−1} geeignet, indem Sie ausnutzen, dass jedes w ∈ E_{N} \E_{N−1} auf eindeutige Weise durch eine Regel ϱ mit Input aus E_{N−1} produziert wird. Setzen Sie dann H :≡ ⋃_{N∈ℕ} H_{N}.