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,\dots ,{\alpha }_n$ aus $\Gamma$ (bzw. aus der gewählten Aufzählung) derart, dass

$⊢{\alpha }_1\wedge \dots \wedge {\alpha }_n\to \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,\dots ,{\beta }_n$ in der Form

${\beta }_i={\delta }_1\wedge \dots \wedge {\delta }_s\to ϵ.$

Wenn ${\beta }_i$ überhaupt diese Form besitzt, so ist diese eindeutig bestimmt. Danach überprüft man für jedes  $i\le n$,  ob alle ${\delta }_1,\dots ,{\delta }_s$ zu $\{{\alpha }_1,\dots ,{\alpha }_n\}$ gehören. Falls ja, und wenn $ϵ$ ein Satz ist, so wird $ϵ$ 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