Copyright © James R Meyer 2012 - 2016 www.jamesrmeyer.com
This guide is intended to assist in attaining a full understanding of Gödel’s proof. If there is any difficulty in following any part of the proof, please contact me and I will try to help. And if you have any suggestions as to how this guide might be improved, please contact me. This guide is intended to be read alongside the English translation of Gödel’s original proof which can be viewed online at English translation of Gödel’s original proof or as a PDF file at English translation of Gödel’s original proof, PDF fileGödel’s Proof - English translation.
In Gödel’s section ‘Recursive Relations’ , the first paragraph (beginning “We now introduce a parenthetic consideration…”) refers to recursive functions and relations of number-theory. Nowadays we call such functions and relations ‘primitive recursive’ functions and relations, rather than simply ‘recursive’ number-theoretic functions and relations.
Gödel’s primitive recursive functions and relations are all number-theoretic, that is, they are functions/relations where the entities that the function or relation refers to are all natural numbers, or variables for natural numbers (“A number-theoretic function is said to be recursively defined by the number-theoretic functions …”).
Gödel had two principal reasons for using primitive recursive relations:
Both of these properties are used in the proof of Gödel’s Proposition V (which we will come to later, see Part 8: Gödel’s Proposition V).
Primitive recursive relations (for given values of the free variables) are always provable from the axioms of number theory since a primitive recursive relation can always be calculated as being a correct or incorrect proposition, using the axioms of number theory, by a method that always has a finite number of precisely defined steps. (Footnote: Note: There are relations and functions that can be calculated by a finite number of steps, but which do not fall within the strict definition of primitive recursion. Gödel did not use such relations or functions in his proof.)
When it is asserted that every primitive recursive relation can be expressed in the formal system, what is being asserted is that:
In this guide we will not go into the details of Gödel’s definitions of primitive recursive relations; at this point it is sufficient to understand the principles of the main properties of primitive recursive relations/functions that is important. Gödel’s point is that the actual relations and functions 1-45 that he uses in his proof (and which you will find in Gödel’s paper under the heading ‘Relations 1-46’) can be shown to be primitive recursive.
Note: Gödel introduces the ε notation in this section, and the ε notation is used in subsequent sections:
εx R(x, y) is defined to be a function with one free variable y, and whose value is the smallest value of x for which the relation R(x, y) holds. If there is no such smallest number, then the value of εx R(x, y) is 0. The function εx R(x, y) is a primitive recursive function if the relation R(x, y) is primitive recursive and provided the relation R(x, y) includes an upper bound on the value of x.
A brief overview of primitive recursion is given below. If you wish to go into the details of the definition and treatment of primitive recursion, there are plenty of sources of such information available; the reason it is not included here is that such details will not significantly assist your understanding of the thrust of Gödel’s argument. (Footnote: You may read elsewhere that a comprehensive knowledge of the details of primitive recursion is essential to an understanding of Gödel’s paper, but this is not the case. In fact, if you arrive at a full understanding of the paper up to and including Gödel’s Proposition V, you will see that primitive recursion is a peripheral matter.)
A primitive recursive function can always be evaluated by a method that always has a finite number of precisely defined steps.
0! = 1
(n+1)! = (n+1) · n!
where · indicates multiplication.
The intention of the factorial function n! is that, for any natural number n, it gives the value of n multiplied by all the natural numbers less than n (except zero). For example,
1! = 1
2! = 2 · 1
3! = 3 · 2 · 1
4! = 4 · 3 · 2 · 1, and so on.
So when we have (n+1)! = (n+1) · n!, then that indicates that n! = n · (n-1)!, providing n-1 is greater than zero, so that:
(n+1)! = (n+1) · n! = (n+1) · n · (n-1)! (providing n, n-1, n-2, n-3, … are all greater than 0)
or we might say that:
n! = n · (n-1)! = n · (n-1) · (n-2) · (n-3) · … (again, providing n, n-1, n-2, n-3, … are all greater than 0)
For any value of n, the value of n! can be calculated by a simple method, like this:
1. Let w = n
2. Let y = n
3. y = y - 1
4. If y > 1 then w = y · w and return to step 3
5. Otherwise the value of n! is w
Suppose we use this method to calculate 4!
1. w = 4
2. y = 4
3. y = 3
4. y > 1 so w = 4 · 3
3. y = 2
4. y > 1 so w = 4 · 3 · 2
3. y = 1
4. Since y = 1, no return to step 3
5. 4! = w = 4 · 3 · 2
So, given any value of n, the value of the function n! can always be determined in a finite number of steps of calculation. We know that the calculation must stop at some point, since we must always reach the point where y = 1, and so n! is a primitive recursive function. This method could be made into a computer program, and every primitive recursive function can be calculated by a simple computer program (but you should be aware that there are functions that evaluate as natural numbers by computer programs, but which are not primitive recursive functions).
Simple primitive recursive functions include the addition function x + y, the multiplier function x · y and the exponential function xy. Gödel’s section ‘Recursive Relations’ introduces more complex primitive recursive functions which he defines in terms of simpler primitive recursive functions.
Gödel gives a precise definition of primitive recursive relations in terms of primitive recursive functions. The definitions are such that, for every primitive recursive relation, there is always a method with a finite number of steps that can calculate if the relation or its negation can be proved to follow from the axioms of number theory. For example, using the simple factorial function above, we could have the relation
x = (y + 3)!
Given any x and any y, it can be calculated, in a finite number of steps, if the relation is correct or incorrect for those values of x and y.
Simple primitive recursive relations include the ‘less than’ relation x < y and the equality relation x = y. Gödel’s section ‘Recursive Relations’ introduces more complex primitive recursive relations which he defines in terms of simpler primitive recursive functions and relations.
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.
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.
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