Copyright © James R Meyer 2012 - 2016 www.jamesrmeyer.com
Note: Full functionality of this web page requires JavaScript to be enabled in your browser.
Several incompleteness proofs, like Gödel’s proof, claim to prove incompleteness of a formal language system and also claim that there is a formula of the formal system that is ‘true’ but unprovable in the formal system. These proofs all have obvious errors of logic, or make unfounded assumptions, or both. A brief synopsis of the types of errors in such proofs is given Errors in incompleteness proofs: here. Papers demonstrating the flaws in these proofs are now available, as follows:
There are also papers on the errors in three different proofs of incompleteness where the authors claim that the proof must be correct because it has been ‘checked’ by computer software:
Brief details about the papers are given below:
There is also a web page on the errors in four different proofs of what is called the ‘Diagonal Lemma’ (see The Diagonal Lemma). The Diagonal Lemma uses an unfounded assumption to make it appear that a formal system can reference itself; once that is done, an incompleteness proof based on that is easily accomplished.
Similar assumptions are also used by Scott Aaronson, an Associate Professor in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology, in two different “proofs” of incompleteness. The proofs are examined on the webpage The Halting Problem and Incompleteness Proofs.
I also now have a page to deal with incompleteness proofs that are so obviously flawed that it is not worth devoting a web page to them, you can see them at Yet Another Flawed Incompleteness Proof.
This paper deals with an incompleteness proof that is found in the Second Edition of a book by Peter Smith, called “An Introduction to Gödel’s Theorems” (Footnote: Peter Smith. An Introduction to Gödel’s Theorems. Cambridge University Press, 2006.
ISBN: 9780521857840 See An Introduction to Gödel’s Theorems: Details.
Note: Smith has a downloadable PDF on his website, Gödel Without (Too Many) Tears which covers much of the same material as the book, but it skips over the crucial technical details, so it cannot be recommended as a substitute for the book.) (For the paper that refers to the First Edition (2007) see A Fundamental Flaw in an Incompleteness Proof by Peter Smith (v1) ). Smith makes the elementary error of the illegal substitution of a variable, as well as several erroneous assumptions (see Error of illegal substitution: here for a brief description of Smith’s principal error). Several authors have used the same basis as Smith for their proofs of incompleteness and the error can readily be demonstrated in the same way as the demonstration of the error in Peter Smith’s book. Among such proofs are:
See also the two ‘computer verified’ proofs below by Harrison and O’Connor which also rely on the same error of substitution.
This paper deals with incompleteness proofs and related proofs that are to be found in two papers by Stephen Kleene. (Footnote: S. C. Kleene. General recursive functions of natural numbers. Mathematische Annalen, 112: pp 727-742, 1936. Not available free online, except at sci hub, http://sci-hub.bz/ or http://sci-hub.cc/.) (Footnote: S. C. Kleene. Recursive predicates and quantifiers.
Transactions of the American Mathematical Society, 53: pp 41-73, 1943. Available online Recursive Predicates And Quantifiers: here PDF.) Kleene’s errors are the error of using an unproven assumption, the error of language confusion, and the error of illegal substitution of variables (see Error of unproven assumption: here, Error of language confusion: here and Error of illegal substitution: here for a brief description of the errors).
This paper deals with incompleteness proofs that can be found in several papers by Gregory Chaitin. (Footnote: G. J. Chaitin. Computational Complexity And Gödel’s Incompleteness Theorem.
ACM SIGACT News, 9: pp 11-12, 1971. Available online Computational Complexity: here PDF.) (Footnote: G. J. Chaitin. Information-theoretic computational complexity.
IEEE Transactions on Information Theory, IT-20: pp 10-15, 1974. Available online Information-theoretic computational complexity: here.) (Footnote: G. J. Chaitin. Information-Theoretic Limitations Of Formal Systems.
Journal of the ACM, 21: pp 403-424, 1974. Available online Information Theoretic Incompleteness of Formal systems: here PDF.) (Footnote: G. J. Chaitin. Algorithmic Information Theory.
IBM Journal of Research and Development, 21: pp 350-359, 1977. Available online Algorithmic Information Theory: here PDF.) (Footnote: G. J. Chaitin. Information Theoretic Incompleteness.
Applied Mathematics and Computation, 52: pp 83-101, 1992. Available online Information Theoretic Incompleteness: here PDF.) Chaitin’s error is that he bases his proofs on an unproven assertion (see Error of unproven assumption: here for a brief description of the error).
This paper deals with an incompleteness proof in a paper by George Boolos. (Footnote: G Boolos. A New Proof of the Gödel’s Incompleteness Theorem.
Notices of the American Mathematical Society, 1989, v36 pp 388-390.)
Boolos’s error is that he bases his proofs on an unproven assertion (see Error of unproven assumption: here for a brief description of the error).
This paper deals with an incompleteness proof that is found in a paper by Stanisław Świerczkowski, called “Finite sets and Gödel’s incompleteness theorems”. (Footnote: Świerczkowski. Finite sets and Gödel’s incompleteness theorems.
Polska Akademia Nauk, Instytut Matematyczny, vol. 422, 2003. Available online Świerczkowski, Finite sets and Gödel’s incompleteness theorems: here PDF.) Świerczkowski’s proof fails to make a clear distinction between when an expression is intended to represent an expression of the formal system, and when it is itself actually an expression of the formal system. This results in the bizarre claim that expressions of the formal system can refer to symbols of the meta-language, even though by definition the formal system can only refer to its own symbols. A logical analysis demonstrates that Świerczkowski’s ‘proof’ of this bizarre claim has no logical validity.
Lawrence Paulson has published some papers claiming a machine assisted proof
of incompleteness that is based on Świerczkowski’s paper. (Footnote: L. Paulson. A Machine Assisted Proof of Gödel’s Incompleteness Theorems for the Theory of
Hereditarily Finite Sets.
The Review of Symbolic Logic (2013), 1–15. Available online A Machine-Assisted Proof Of Gödel’s Incompleteness Theorems: here PDF.) (Footnote: L. Paulson. Gödel’s Incompleteness Theorems (Machine Code), Nov, 2013. Available online Gödel’s Incompleteness Theorems, Machine Code: here PDF.) Paulson’s computer code is flawed in the same way as Świerczkowski’s proof.
This paper deals with an incompleteness proof that is found in a book by John Harrison, called “Handbook of Practical Logic and Automated Reasoning”. (Footnote: J. Harrison. Handbook of Practical Logic and Automated Reasoning. Cambridge University Press, 2009.
ISBN: 9780521899574 (eBook format: ISBN: 9780511508653) Handbook of Practical Logic and Automated Reasoning: Details.) Harrison’s proof relies on the same illogical substitution of variables by values outside their allowable domain that is found in the proof by Peter Smith, see above.
This paper deals with an incompleteness proof that is found in an article by Russell O’Connor, called “Essential Incompleteness of Arithmetic Verified by Coq”. (Footnote: R. O’Connor. Essential In completeness of Arithmetic Verified by Coq., 2005. Available online Incompleteness of Arithmetic Verified by Coq: here.) (Footnote: R. O’Connor. Incompleteness & Completeness, 2009. Available online Incompleteness & Completeness: here PDF.) O’Connor’s proof relies on the same illogical substitution of variables by values outside their allowable domain that is found in the proof by Peter Smith, see above.
This paper deals with an incompleteness proof that is found in a book by Natarajan Shankar, called “Metamathematics, Machines, and Gödel’s proof.”. (Footnote: N. Shankar. Metamathematics, Machines, and Gödel’s Proof. Cambridge University Press, 1997.
ISBN: 9780521585330 Metamathematics, Machines, and Gödel’s Proof: Details.) The error in Shankar’s proof occurs when he uses a non-variable value where there should be a variable value.
Footnotes:
Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked (comments will be checked before appearing on this site). Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - this will only be used to notify you of replies to your comments - it will never be used for any other purpose, will never be displayed and does not require verification. Comments are common to the entire website, so please indicate what section of the site you are commenting on.
If you cannot see any comments below, it may be that a plug-in on your browser is blocking Disqus comments from loading. Avast anti-virus in particular is known to do this, especially with Internet Explorer and Safari. See Disqus Browser plug-in/extension conflicts or Why isn’t the comment box loading?.
Please wait for comments to load …
There is a new addition to the page Yet another flawed incompleteness proof, where Berto’s proof of incompleteness in his book There’s something about Gödel comes under scrutiny.
I found that making, adding or deleting footnotes in the traditional manner proved to be a major pain. So I developed a different system for footnotes which makes inserting or changing footnotes a doddle. You can check it out at Easy Footnotes for Web Pages (Accessibility friendly).
I have now added a new section to my paper on Russell O’Connor’s claim of a computer verified incompleteness proof. This shows that the flaw in the proof arises from a reliance on definitions that include unacceptable assumptions - assumptions that are not actually checked by the computer code. See also the new page Representability.
There is now a new page on Chaitin’s Constant (Chaitin’s Omega), which demonstrates that Chaitin has failed to prove that it is actually algorithmically irreducible.
Flawed proofs of the Diagonal Lemma by Panu Raatikainen and Vann McGee have been added to the Diagonal Lemma web page.
16th Mar 2015 Bishops Dancing with Pixies?
23rd Feb 2015 Artificial Intelligence
31 Mar 2015 Cranks and Crackpots
For convenience, there are now two pages on this site with links to various material relating to Gödel and the Incompleteness Theorem
– a page with general links:
– and a page relating specifically to the Gödel mind-machine debate:
All pages on this website are printer friendly, and will print the main content in a convenient format. Note that the margins are set by your browser print settings.
Note: for some browsers JavaScript must be enabled for this to operate correctly.
Comments on this site are welcome, please see the comment section.
Please note that this web site, like any other is a collection of various statements. Not all of this web site is intended to be factual. Some of it is personal opinion or interpretation.
If you prefer to ask me directly about the material on this site, please send me an e-mail with your query, and I will attempt to reply promptly.
Feedback about site design would also be appreciated so that I can improve the site.
Copyright © James R Meyer 2012 - 2016
www.jamesrmeyer.com