On proofs of the incompleteness theorems based on Berry's paradox by Vopěnka, Chaitin, and Boolos
type: Item
instance of: scholarly article
title: On proofs of the incompleteness theorems based on Berry's paradox by Vopěnka, Chaitin, and Boolos
zbMATH Open document ID: 1257.03088
author: Makoto Kikuchi
author: Taishi Kurahashi
author: Hiroshi Sakai
publication date: 2012-09-12T00:00:00Z
Mathematics Subject Classification ID: 03F40
Mathematics Subject Classification ID: 03A05
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 6081350
zbMATH Keywords: incompleteness theorems
zbMATH Keywords: Berry's paradox
zbMATH Keywords: Kolmogorov complexity
MaRDI profile type: Publication
full work available at URL: malq.201110067
OpenAlex ID: W2078113475
cites work: Q4339021
cites work: Information-theoretic computation complexity
cites work: The Berry paradox
cites work: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
cites work: Q4001935
cites work: On Models Constructed by Means of the Arithmetized Completeness Theorem
cites work: On formalization of model-theoretic proofs of Gödel's theorems
cites work: A Note on Boolos' Proof of the Incompleteness Theorem
cites work: Kolmogorov complexity and the second incompleteness theorem
cites work: On the incompleteness theorems
cites work: The incompleteness theorems after 70 years
cites work: A survey of proof theory
cites work: The Surprise Examination Paradox and the Second Incompleteness Theorem
cites work: Q4337021
cites work: Recursive functions and metamathematics. Problems of completeness and decidability, Gödel's theorems
cites work: Classical recursion theory. The theory of functions and sets of natural numbers
cites work: The shortest definition of a number in Peano arithmetic
DOI: 10.1002/MALQ.201110067
published in: Mathematical Logic Quarterly (MLQ)
review text: 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.
reviewed by: Saeed Salehi
description: scientific article; zbMATH DE number 6081350