Beweis
Es sei eine
-aufzählbare
Satzmenge, die axiomatisiert, und es sei
, ,
eine -Aufzählung von . Es sei
, ,
eine -Aufzählung der prädikatenlogischen Tautologien aus . Wenn ein Satz aus ableitbar ist, so gibt es eine endliche Auswahl aus
(bzw. aus der gewählten Aufzählung)
derart, dass
-
eine prädikatenlogische Tautologie ist. Daher leistet das folgende Verfahren, bei dem wächst, das Gewünschte: Für jedes notiert man die Tautologien in der Form
-
Wenn überhaupt diese Form besitzt, so ist diese eindeutig bestimmt. Danach überprüft man für jedes
,
ob alle zu gehören. Falls ja, und wenn ein Satz ist, so wird notiert. Danach geht man zum nächsten . Wenn man
,
erreicht hat, so geht man zu , wobei man aber wieder bei
anfängt.