On proofs of the incompleteness theorems based on Berry's paradox by Vopěnka, Chaitin, and Boolos
A length diagonalization lemma is proved in the paper, and based on it some proofs for the first and second incompleteness theorems (of K. Gödel) are presented. This shows that the proofs of Boolos, Chaitin and Vopěnka, which are based on Berry's paradox (and do not use a diagonal argument), can be proved by a diagonal method. Also, a notion of Kolmogorov complexity is introduced in the paper which is based on the provability in an arithmetical theory rather than computability by some Turing machine. This enables the authors to obtain a Chaitin-like proof for the incompleteness phenomenon. Finally, Vopěnka's proof of the second incompleteness theorem, which was based on set-theoretic notions, is imported to arithmetical theories using the arithmetized completeness theorem.NEWLINENEWLINEThe paper is a good read and contains very interesting results. Unfortunately, there are several misprints and mistakes; also the English of the paper needs a major revision.
scientific article; zbMATH DE number 6081350