On proofs of the incompleteness theorems based on Berry's paradox by Vopěnka, Chaitin, and Boolos
Makoto Kikuchi, Taishi Kurahashi, Hiroshi Sakai · Mathematical logic quarterly · 2012
Abstract 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.