“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 17375  


Abstract:  
he proofs of GÃÂ¨odel (1931), Rosser (1936), Kleene (first 1936 and second 1950), Chaitin (1970), and Boolos (1989) for the first incompleteness theorem are compared with each other, especially from the viewpoint of the second incompleteness theorem. It is shown that GÃÂ¨odelÃ¢??s (first incompleteness theorem) and KleeneÃ¢??s first theorems are equivalent with the second incompleteness theorem, RosserÃ¢??s and KleeneÃ¢??s second theorems do deliver the second incompleteness theorem, and BoolosÃ¢?? theorem is derived from the second incompleteness theorem in the standard way. It is also shown that none of RosserÃ¢??s, KleeneÃ¢??s second or BoolosÃ¢?? theorems is equivalent with the second incompleteness theorem, and ChaitinÃ¢??s incompleteness theorem neither delivers nor is derived from the second incompleteness theorem. We compare (the strength of) these six proofs with one another. After discussing some other proofs of GÃÂ¶del's First Incompleteness Theorem, namely the proofs of Rosser, Kleene, Chaitin and Boolos, we investigate whether these proofs of the first theorem also imply the second. It is shown that while the proofs of Rosser and Kleene imply the second theorem, the proofs of Chaitin and Boolos do not.
Download TeX format 

back to top 