Premium
On proofs of the incompleteness theorems based on Berry's paradox by Vopěnka, Chaitin, and Boolos
Author(s) -
Kikuchi Makoto,
Kurahashi Taishi,
Sakai Hiroshi
Publication year - 2012
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201110067
Subject(s) - mathematical proof , mathematics , diagonal , argument (complex analysis) , completeness (order theory) , discrete mathematics , analytic proof , extension (predicate logic) , cantor's diagonal argument , calculus (dental) , pure mathematics , algebra over a field , computer science , mathematical analysis , programming language , medicine , biochemistry , chemistry , geometry , dentistry , cantor set
By formalizing Berry's paradox, Vopěnka, Chaitin, Boolos and others proved the incompleteness theorems without using the diagonal argument. In this paper, we shall examine these proofs closely and show their relationships. Firstly, we shall show that we can use the diagonal argument for proofs of the incompleteness theorems based on Berry's paradox. Then, we shall show that an extension of Boolos' proof can be considered as a special case of Chaitin's proof by defining a suitable Kolmogorov complexity. We shall show also that Vopěnka's proof can be reformulated in arithmetic by using the arithmetized completeness theorem.