Revisions to What are some proofs of Godel's Theorem which are *essentially different* from the original proof?

replaced the dead link

Source Link

edited May 15, 2022 at 9:10

4.7k
4
35
40

To give an example of what I mean: The Godel/Rosser proof (see http://www.jstor.org/pss/2269059 for an exposition) shows that any consistent sufficiently strong axiomatizable theory is incomplete. The proof uses a substantial amount of recursion theory: the representability of primitive recursive functions and the diagonal lemma (roughly the same as Kleene's Recursion Theorem) are essential ingredients. The second incompleteness theorem - that no consistent sufficiently strong axiomatizable theory can prove its own consistency - is essentially a corollary to this proof, and a rather natural one at that. On the other hand, in 2000 Hilary Putnam published (http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.ndjfl/1027953483 https://doi.org/10.1305/ndjfl/1027953483) an alternate proof of Godel's first incompleteness theorem, due to Saul Kripke around 1984. This proof uses much less recursion theory, instead relying on some elementary model theory of nonstandard models of arithmetic. The theorem proven is slightly weaker, since Kripke's proof requires $\Sigma^0_2$-soundness, which is stronger than mere consistency (although still weaker than Godel's original assumption of $\omega$-consistency).

The only other potential example of such an essentially different proof that I know of is the proof(s) by Jech and Woodin (see http://andrescaicedo.files.wordpress.com/2010/11/2ndincompleteness1.pdf https://andrescaicedo.files.wordpress.com/2010/11/2ndincompleteness1.pdf), but I don't understand that proof at a level such that I would be comfortable saying that it is in fact an essentially different proof. It seems to me to be rather similar to the original proof. Perhaps someone can enlighten me?

To give an example of what I mean: The Godel/Rosser proof (see http://www.jstor.org/pss/2269059 for an exposition) shows that any consistent sufficiently strong axiomatizable theory is incomplete. The proof uses a substantial amount of recursion theory: the representability of primitive recursive functions and the diagonal lemma (roughly the same as Kleene's Recursion Theorem) are essential ingredients. The second incompleteness theorem - that no consistent sufficiently strong axiomatizable theory can prove its own consistency - is essentially a corollary to this proof, and a rather natural one at that. On the other hand, in 2000 Hilary Putnam published (http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.ndjfl/1027953483) an alternate proof of Godel's first incompleteness theorem, due to Saul Kripke around 1984. This proof uses much less recursion theory, instead relying on some elementary model theory of nonstandard models of arithmetic. The theorem proven is slightly weaker, since Kripke's proof requires $\Sigma^0_2$-soundness, which is stronger than mere consistency (although still weaker than Godel's original assumption of $\omega$-consistency).

The only other potential example of such an essentially different proof that I know of is the proof(s) by Jech and Woodin (see http://andrescaicedo.files.wordpress.com/2010/11/2ndincompleteness1.pdf), but I don't understand that proof at a level such that I would be comfortable saying that it is in fact an essentially different proof. It seems to me to be rather similar to the original proof. Perhaps someone can enlighten me?

To give an example of what I mean: The Godel/Rosser proof (see http://www.jstor.org/pss/2269059 for an exposition) shows that any consistent sufficiently strong axiomatizable theory is incomplete. The proof uses a substantial amount of recursion theory: the representability of primitive recursive functions and the diagonal lemma (roughly the same as Kleene's Recursion Theorem) are essential ingredients. The second incompleteness theorem - that no consistent sufficiently strong axiomatizable theory can prove its own consistency - is essentially a corollary to this proof, and a rather natural one at that. On the other hand, in 2000 Hilary Putnam published (https://doi.org/10.1305/ndjfl/1027953483) an alternate proof of Godel's first incompleteness theorem, due to Saul Kripke around 1984. This proof uses much less recursion theory, instead relying on some elementary model theory of nonstandard models of arithmetic. The theorem proven is slightly weaker, since Kripke's proof requires $\Sigma^0_2$-soundness, which is stronger than mere consistency (although still weaker than Godel's original assumption of $\omega$-consistency).

The only other potential example of such an essentially different proof that I know of is the proof(s) by Jech and Woodin (see https://andrescaicedo.files.wordpress.com/2010/11/2ndincompleteness1.pdf), but I don't understand that proof at a level such that I would be comfortable saying that it is in fact an essentially different proof. It seems to me to be rather similar to the original proof. Perhaps someone can enlighten me?