A second proof of Gödel’s theorem, and a proof of Gödel’s second theorem
A. W. Moore · 2022
Abstract This chapter presents a second proof of Gödel’s theorem, closer to Gödel’s own. It adopts a version of Peano Arithmetic, called PA, as a sample theory. PA can be shown to be both axiomatizable and sufficiently strong. Showing that PA is sufficiently strong requires giving a precise definition of what it is for membership of a set of natural numbers to be determined algorithmically. Three candidate definitions are outlined, one of which exploits the concept of a Turing machine. These definitions can be shown to be equivalent, and the thesis that any of them suffices, which is known as Church’s thesis, is introduced and thereafter presupposed. The proof of Gödel’s theorem in application to PA is then sketched. It involves exploiting a Gödel numbering and constructing a statement s in the language of PA which is true if and only if it doesn’t belong to PA. It can then be shown that, if PA is consistent, then s does not belong to PA; and that, if PA has a stronger property known as ω-consistency, which is a sort of soundness, then the negation of s does not belong to PA either; hence that PA is incomplete. Finally, a sketch is given of how reflection on this very proof yields a proof of Gödel’s second theorem in application to PA, which shows that PA doesn’t contain a statement corresponding to a statement of its own consistency.