Mathematical Logic Quarterly 58 (4-5):307-316 (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
|
Keywords | The Incompleteness Theorems Berry's Paradox Kolmogorov Complexity |
Categories | (categorize this paper) |
DOI | 10.1002/malq.201110067 |
Options |
![]() ![]() ![]() ![]() |
Download options
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.
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I.K. Gödel - 1931 - Monatshefte für Mathematik 38 (1):173--198.
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 Constructivity and the Rosser Property: A Closer Look at Some Gödelean Proofs.Saeed Salehi & Payam Seraji - 2018 - Annals of Pure and Applied Logic 169 (10):971-980.
On the Diagonal Lemma of Gödel and Carnap.Saeed Salehi - 2020 - Bulletin of Symbolic Logic 26 (1):80-88.
Rosser-Type Undecidable Sentences Based on Yablo’s Paradox.Taishi Kurahashi - 2014 - Journal of Philosophical Logic 43 (5):999-1017.
Liar-Type Paradoxes and the Incompleteness Phenomena.Makoto Kikuchi & Taishi Kurahashi - 2016 - Journal of Philosophical Logic 45 (4):381-398.
View all 7 citations / Add more citations
Similar books and articles
The Surprise Examination Paradox and the Second Incompleteness Theorem.Shira Kritchman & Ran Raz - unknown
Mathematical Realism and Gödel's Incompleteness Theorems.Richard Tieszen - 1994 - Philosophia Mathematica 2 (3):177-201.
On the Incompleteness Theorems.Henryk Kotlarski - 1994 - Journal of Symbolic Logic 59 (4):1414-1419.
Contemporary Perspectives on Hilbert's Second Problem and the Gödel Incompleteness Theorems.Harvey Friedman - manuscript
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.
Algorithmic Information Theory and Undecidability.Panu Raatikainen - 2000 - Synthese 123 (2):217-225.
Gödel's Incompleteness Theorems and Computer Science.Roman Murawski - 1997 - Foundations of Science 2 (1):123-135.
Computability and Logic.George Boolos, John Burgess, Richard P. & C. Jeffrey - 2002 - Cambridge University Press.
Incompleteness in a General Setting (Vol 13, Pg 21, 2007).John Bell - 2008 - Bulletin of Symbolic Logic 14 (1):21 - 30.
Consistency, Turing Computability and Gödel’s First Incompleteness Theorem.Robert F. Hadley - 2008 - Minds and Machines 18 (1):1-15.
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.
Analytics
Added to PP index
2013-10-31
Total views
53 ( #213,841 of 2,504,848 )
Recent downloads (6 months)
2 ( #277,627 of 2,504,848 )
2013-10-31
Total views
53 ( #213,841 of 2,504,848 )
Recent downloads (6 months)
2 ( #277,627 of 2,504,848 )
How can I increase my downloads?
Downloads