Gödel Without Tears - Or Not?
Peter Smith is a prominent apologist for Gödel’s incompleteness proof. He has written several versions of his own “proof” of incompleteness. All of his accounts include the same fundamental error. The most detailed account is to be found in his book, ‘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. ) which I have analyzed in depth in my paper A Fundamental Flaw in an Incompleteness Proof by Peter Smith. If you want to investigate Smith’s claims in depth, I would recommend that you follow the book and my analysis of it.
However, Smith also has a downloadable version available at Logic Matters: Gödel Without (Too Many) Tears, which he says is a cut-down version of the book. Many people will use this version rather than buying the book, and in fact Smith states that thousands of this version have been downloaded. This is the reason I have decided to make an analysis of that version available here, for those who do not want to buy Smith’s book.
Readers should be aware, that while Smith’s argument in the downloadable version is essentially the same as that expounded in his book, in the downloadable version a lot of details are omitted, or glossed over. However, this lack of detail is not the cause of the error shown below - it is also evident in the detailed version in Smith’s book.
Smith’s “Theorem” 31
The key place where the crucial error occurs is in Smith’s “proof” is in his “Theorem” 31, which Smith states as follows: (Footnote:
The terms that Smith uses are as follows:
p.r. function: a primitive recursive number-theoretic function.
LA: A language system that can express p.r. functions.
wff: A well formed formula in that language.
g.n.: A Gödel number of an expression of the language LA.
n: The number n in the format of the language LA (Note: the initial n should appear with a bar over it. If no bar is showing, your browser is not displaying the content as intended. Perhaps you have the CSS styling turned off in your browser).
Theorem 31: There is a p.r. function diag(n) which, when applied to a number n which is the g.n. of some LA wff with one free variable, yields the g.n. of that wff ’s diagonalization, and yields n otherwise.
Proof: Consider this procedure. Try treating n as a g.n., and seek to decode it. If you don’t get an expression with one free variable, return n. Otherwise you get a wff φ and can form the wff φ( n ), which is its diagonalization. Then work out the g.n. of this result to compute diag(n). This procedure doesn’t involve any unbounded searches. So we again will be able to program the procedure using just ‘for’ loops. Hence diag is a p.r. function.
So what Smith is saying in his “proof” above is this:
If n is the Gödel number of a valid formula φ with one free variable, then diag(n) is the Gödel number of φ( n ). In other words, Smith’s claim is that:
diag(n) = g.n.[φ( n )]
Yes, this is a recursive function. But it is most certainly not a primitive recursive function, since a primitive recursive function is necessarily number-theoretic. And regardless of the terminology, the entire point of the reference to primitive recursion is supposedly that any primitive recursive expression can be expressed in the language of the formal system LA which can only deal with numerical expressions.
As defined by Smith, diag(n) cannot be a primitive recursive function, since it is defined in terms of the Gödel numbering function, which is a function of the meta-language and cannot be expressed in the formal language (see The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System).
Does it matter? Yes, it does. Because further on, in the “proof” of Theorem 33, Smith refers to an expression:
Prf (m, diag(n))
But although he has already defined Prf as a primitive recursive number-theoretic function, his “proof” requires that the entire expression Prf (m, diag(n)) can be expressed in the language LA, which it clearly can’t, since it is not a number-theoretic expression.
Note that I have not attempted to discuss Smith’s error in his cut-down downloadable version in any more detail, simply because that version omits quite a lot of detail anyway. Since the error is essentially the same as in Smith’s book, if you want to see a fully detailed analysis of Smith’s error please see the paper A Fundamental Flaw in an Incompleteness Proof by Peter Smith.
Smith’s “proof” is fatally flawed, since the error of assuming that an expression is a number-theoretic expression when it clearly isn’t completely undermines the entire argument. The error is the same error as in Smith’s book An Introduction to Gödel’s Theorems, and there is a much more detailed analysis of that error in the paper A Fundamental Flaw in an Incompleteness Proof by Peter Smith.
In fact this type of error crops up in numerous attempted incompleteness proofs, see Errors in Incompleteness Proofs and Analyses of Incompleteness Proofs. If you want to ask Peter Smith about the error in his proof, send him an email at peter email@example.com. If you get an interesting reply, please let me know.
As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Frivolous, irrelevant comments.
Comments devoid of logical basis.
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.
Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous usernames for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it wrong and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.
Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.
Note: a password enables editing of comments, an email enables notification of replies