Peter Smith’s Gödel Without (Too Many) Tears - Or Not?
Page last updated 09 Nov 2022
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 he has now made freely available as a downloadable PDF at Smith’s An Introduction to Gödel’s Theorems. I have analyzed the “proof” Smith presents in that book 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.
Smith also used to have a PDF freely available on his website entitled Gödel Without (Too Many) Tears. I see that now he has taken it off his site, and he wants you to pay for it at Amazon. I have a copy of it, if you want it for educational purposes (the copyright specifically permits copying for educational use) I can send you a copy, just ask through my email or in a comment with your email address (I will then remove that address). Smith says that it is a cut-down version of the book, and it covers much of the same material as the book, but it skips over the crucial technical details, so it cannot really be recommended as a substitute for the book. Many people will want to use this version rather than pay for the book. This is the reason I have decided to make an analysis of that version available here.
Readers should be aware, that while Smith’s argument in this cut-down version is essentially the same as that expounded in his book, in the cut-down 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 “diag ” function
The key place where the crucial error occurs is in Smith’s “proof” is in his “Theorem” 32, which Smith states as follows: (Footnote:
Smith sometimes changes his text and in doing so, may change the theorem numbers, so in a future edition of Smith’s text, the actual theorem number may be different. The terms that Smith uses are as follows:
p.r. function: a primitive recursive number-theoretic function.
L: 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 L.
n: The number n in the format of the language L (Note: n should appear with a bar over it where it occurs in φ( n ). If no bar is showing, it may be due to your browser).
Theorem 32: There is a p.r. function diag(n) which, when applied to a number n which is the g.n. of some L wff with one free variable, yields the g.n. of that wff ’s diagonalization, and yields 0 otherwise.
Proof: Try treating n as a g.n., and seek to decode it. If you don’t get an expression with one free variable, return 0. Otherwise you get a wff of the type φ(x) and can form the wff φ( n ), which is its diagonalization (since by assumption n is its g.n.). Then we work out the g.n. of this resulting wff to compute diag(n). This procedure doesn’t involve any unbounded searches. So we 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 L 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 L, which it clearly can’t, since it is not a number-theoretic expression.
Smith’s fudge asks you to believe that one can have two valid definitions of a function diag(n) , where one definition defines the function as having a particular property (primitive recursive) and the other definition defines the function as not having that property. It’s not what one might expect from someone who has written a book entitled “An Introduction to Formal Logic” . (Footnote: Peter Smith, An introduction to Formal Logic, Cambridge University Press, 2003.)
Note that I will not attempt to discuss Smith’s error in his cut-down 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 firstname.lastname@example.org. 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 user names for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it incorrectly 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.