Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying an undergraduate text about math logic. The proofs of the two Godel's incompleteness theorems are not completely formal: they are admittedly simpler that the real proofs. For what I understood, I deduce the two theorems are valid for both classical and intuitionistic logic.

Is my deduction correct?

share|improve this question

1 Answer 1

up vote 13 down vote accepted

The usual proof of Gödel's First Incompleteness Theorem is entirely constructive. We don't have to rely on excluded middle, or have to rely on proving an existential quantification for which we can't produce a witness. For recall: the proof consists in (a) giving a recipe which takes a suitable specification of a sufficiently strong theory $T$ and constructs a certain sentence $G_T$ and then (b) showing $G_T$ is undecidable in that theory. The construction of $G_T$ is clever though simple when you see how, and involves no infinitary ideas. The proof of undecidability involves a pair of reductios, but both of the non-contentious type [like "Suppose $T \vdash G_T$: then contradiction; so $T \nvdash G_T$"]. So overall the proof is intuitionistically acceptable.

The usual proof of the Second Incompleteness Theorem then consists, at heart, in showing that the proof of the First Theorem can be coded up in arithmetic. Again it's all constructive, and so is intuitionistically acceptable.

share|improve this answer
Historically this is the strength of the incompleteness theorems. They are foundationally indisputable in this sense. They don't appeal to set theory, nor to LEM. Just the natural numbers. –  Asaf Karagila Jul 21 '13 at 7:02
Yes indeed: @AsafKaragila's observation is exactly right. –  Peter Smith Jul 21 '13 at 7:37
I know, I made a footnote to your answer which is really a footnote, rather than a full answer with the classical P. Smith preface "This answer is really just a footnote to ...'s answer" ;-) –  Asaf Karagila Jul 21 '13 at 7:43
Poeple sometimes say that infinities are the troublemakers, which seems to be impecise in light of this answer. Or are there still infinities involved in this proof, which, if left out, would invalidate Godel's theorems? –  mcb Mar 25 at 15:08
Do "people sometimes say that infinities are the troublemakers" with respect to Gödelian incompleteness? Really? Which infinities?? –  Peter Smith Mar 25 at 19:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.