This page is keyboard accessible:
• Use Tab, Shift + Tab keys to traverse the main menu. To enter a sub-menu use the Right Arrow key. To leave a sub-menu use the Left Arrow or the Escape key.
• The Enter or the Space key opens the active menu item.
• To skip the menu and move to the main content, press Tab after the page loads to reveal a skip button.
• To get back to the top of the page anytime, press the Home key.
• For more information, click here: Accessibility   Close this tip.

Note: Full functionality of this web page requires JavaScript to be enabled in your browser.
 

Analyses of Incompleteness Proofs

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:

  1. A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF
  2. A Fundamental Flaw in Incompleteness Proofs by S. C. Kleene PDF
  3. A Fundamental Flaw in Incompleteness Proofs by Gregory Chaitin PDF
  4. A Fundamental Flaw in an Incompleteness Proof by George Boolos PDF
  5. A Fundamental Flaw in an Incompleteness Proof by Stanisław Świerczkowski PDF

 

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:

  1. An Error in a Computer Verified Proof of Incompleteness by John Harrison PDF
  2. An Error in a Computer Verified Proof of Incompleteness by Russell O’Connor PDF
  3. An Error in a Computer Verified Proof of Incompleteness by Natarajan Shankar PDF

 

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.

 

A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF

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:

  1. “Gödel’s Incompleteness Theorems”, by Raymond M Smullyan (Footnote: Raymond M Smullyan. Gödel’s Incompleteness Theorems. Oxford University Press, 1992.
    ISBN: 0195046722 See Gödel’s Incompleteness Theorems: Details.)
  2. “Recursion Theory for Metamathematics”, by Raymond M Smullyan (Footnote: Raymond M Smullyan. Recursion Theory for Metamathematics. Oxford University Press, 1993.
    ISBN: 9780195082326 See Recursion Theory for Metamathematics: Details.)
  3. “Computability and Logic”, by George Boolos (Footnote: G Boolos, J Burges, and R Jeffrey. Computability and Logic. Cambridge University Press, fifth edition, 2007.
    ISBN: 9780521877527 See Computability and Logic: Details.)
  4. “Gödel’s Theorem: An Incomplete Guide to its Use and Abuse”, by Torkel Franzén (Footnote: Torkel Franzén. Gödel’s Theorem: An Incomplete Guide to its Use and Abuse. A K Peters, 2005.
    ISBN: 1568812388 See Gödel’s Theorem: An Incomplete Guide to its Use and Abuse: Details.)
  5. “Lecture Notes: Aspects of Incompleteness”, by Per Lindström (Footnote: Per Lindström. Lecture Notes: Aspects of Incompleteness. Springer-Verlag, 1997.
    ISBN: 3540632131 Available online Aspects of Incompleteness: here.)
  6. “Sentences Undecidable in Formalized Arithmetic”, by Andrej Mostowski (Footnote: Andrej Mostowski. Sentences Undecidable in Formalized Arithmetic. Greenwood Press, 1982.
    ISBN: 9780313231513 See Sentences undecidable in formalized arithmetic: Details.)

See also the two ‘computer verified’ proofs below by Harrison and O’Connor which also rely on the same error of substitution.

 

A Fundamental Flaw in Incompleteness Proofs by S. C. Kleene PDF

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).

 

A Fundamental Flaw in Incompleteness Proofs by Gregory Chaitin PDF

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).

 

A Fundamental Flaw in an Incompleteness Proof by George Boolos PDF

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).

 

A Fundamental Flaw In An Incompleteness Proof by Stanisław Świerczkowski PDF

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.

 

An Error in a Computer Verified Proof of Incompleteness by John Harrison PDF

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.

 

An Error in a Computer Verified Proof of Incompleteness by Russell O’Connor PDF

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.

 

An Error in a Computer Verified Proof of Incompleteness by Natarajan Shankar PDF

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 …  

 

The Lighter Side

 

NEWS

There’s something about Gödel by Francesco Berto

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.

 

 

Easy Footnotes

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).

 

 

O’Connor’s “computer checked” proof

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.

 

 

New page on Chaitin’s Constant

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.

 

 

Updated: Diagonal Lemma

Flawed proofs of the Diagonal Lemma by Panu Raatikainen and Vann McGee have been added to the Diagonal Lemma web page.

Previous Blog Posts  

 

16th Mar 2015 Bishops Dancing with Pixies?

 

23rd Feb 2015 Artificial Intelligence

 

31 Mar 2015 Cranks and Crackpots

 

30 Apr 2015 The Chinese Room

 

Links  

 

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:

Gödel Links

 

– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines

 

Printer Friendly

 

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

 

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