Mathematical Logic Quarterly 58 (4-5):307-316 (2012)

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
Keywords The Incompleteness Theorems  Berry's Paradox  Kolmogorov Complexity
Categories (categorize this paper)
DOI 10.1002/malq.201110067
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,775
Through your library

References found in this work BETA

Mathematical Logic as Based on the Theory of Types.Bertrand Russell - 1908 - American Journal of Mathematics 30 (3):222-262.
The Logic of Provability.George S. Boolos - 1993 - Cambridge University Press.
A Survey of Proof Theory.G. Kreisel - 1968 - Journal of Symbolic Logic 33 (3):321-388.
A Note on Boolos' Proof of the Incompleteness Theorem.Makoto Kikuchi - 1994 - Mathematical Logic Quarterly 40 (4):528-532.

View all 13 references / Add more references

Citations of this work BETA

Incompleteness Via Paradox and Completeness.Walter Dean - 2020 - Review of Symbolic Logic 13 (3):541-592.
On the Diagonal Lemma of Gödel and Carnap.Saeed Salehi - 2020 - Bulletin of Symbolic Logic 26 (1):80-88.
Liar-Type Paradoxes and the Incompleteness Phenomena.Makoto Kikuchi & Taishi Kurahashi - 2016 - Journal of Philosophical Logic 45 (4):381-398.
Rosser-Type Undecidable Sentences Based on Yablo’s Paradox.Taishi Kurahashi - 2014 - Journal of Philosophical Logic 43 (5):999-1017.

View all 6 citations / Add more citations

Similar books and articles

On the Incompleteness Theorems.Henryk Kotlarski - 1994 - Journal of Symbolic Logic 59 (4):1414-1419.
Computational Complexity and Godel's Incompleteness Theorem.Gregory J. Chaitin - 1970 - [Rio De Janeiro, Centro Técnico Científico, Pontifícia Universidade Católica Do Rio De Janeiro.
Gödel's Incompleteness Theorems and Computer Science.Roman Murawski - 1997 - Foundations of Science 2 (1):123-135.
Incompleteness in a General Setting (Vol 13, Pg 21, 2007).John Bell - 2008 - Bulletin of Symbolic Logic 14 (1):21 - 30.
On Formalization of Model-Theoretic Proofs of Gödel's Theorems.Makoto Kikuchi & Kazuyuki Tanaka - 1994 - Notre Dame Journal of Formal Logic 35 (3):403-412.
Gödel’s Incompleteness Theorems and Physics.Newton C. A. Da Costa - 2011 - Principia: An International Journal of Epistemology 15 (3):453-459.


Added to PP index

Total views
50 ( #206,319 of 2,432,671 )

Recent downloads (6 months)
1 ( #464,418 of 2,432,671 )

How can I increase my downloads?


My notes