Theorie/Erster Stufe/Ableitbar/Aufzählbar axiomatisierbar/Aufzählbar/Fakt/Beweis

Beweis

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.