Theorie/Erster Stufe/Ableitbar/Aufzählbar, vollständig, widerspruchsfrei/Entscheidbar/Fakt/Beweis

Beweis

Nach Fakt bedeutet die aufzählbare Axiomatisierbarkeit, dass schon die Theorie selbst aufzählbar ist. Es sei also aufzählbar, vollständig und widerspruchsfrei, und sei , , eine Aufzählung von . Es sei ein Satz. Wegen der Widerspruchsfreiheit und der Vollständigkeit gilt entweder oder . Daher kommt entweder oder in der Aufzählung von vor. Bei ist und bei ist .