Theorie/Erster Stufe/Ableitbar/Aufzählbar axiomatisierbar/Aufzählbar/Fakt/Beweis/Aufgabe/Lösung

Es sei ${}\Gamma$ eine ${}R$-aufzählbare Satzmenge, die ${}T$ axiomatisiert, und es sei ${}\alpha _{n}$, ${}n\in \mathbb {N} _{+}$, eine ${}R$-Aufzählung von ${}\Gamma$. Es sei ${}\beta _{n}$, ${}n\in \mathbb {N} _{+}$, eine ${}R$-Aufzählung der prädikatenlogischen Tautologien aus ${}L^{S}$. Wenn ein Satz ${}\gamma$ aus ${}\Gamma$ ableitbar ist, so gibt es eine endliche Auswahl ${}\alpha _{1},\ldots ,\alpha _{n}$ aus ${}\Gamma$ (bzw. aus der gewählten Aufzählung) derart, dass

$\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \gamma$

eine prädikatenlogische Tautologie ist. Daher leistet das folgende Verfahren, bei dem ${}n$ wächst, das Gewünschte: Für jedes ${}n$ notiert man die Tautologien ${}\beta _{1},\ldots ,\beta _{n}$ in der Form

${}\beta _{i}=\delta _{1}\wedge \ldots \wedge \delta _{s}\rightarrow \epsilon \,.$

Wenn ${}\beta _{i}$ überhaupt diese Form besitzt, so ist diese eindeutig bestimmt. Danach überprüft man für jedes ${}i\leq n$, ob alle ${}\delta _{1},\ldots ,\delta _{s}$ zu ${}\{\alpha _{1},\ldots ,\alpha _{n}\}$ gehören. Falls ja, und wenn ${}\epsilon$ ein Satz ist, so wird ${}\epsilon$ notiert. Danach geht man zum nächsten ${}i$. Wenn man ${}i=n$, erreicht hat, so geht man zu ${}n+1$, wobei man aber wieder bei ${}i=1$ anfängt.

Zur gelösten Aufgabe