• 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 get back to the top of the page anytime, press the Home key.

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

A Step by Step Guide to Gödel’s Incompleteness Proof: 5: Primitive Recursive Relations

Page Contents

Primitive Recursion

Epsilon ε

P R Functions

P R Relations

Note that (provided you have JavaScript enabled) clicking on (hideshow) will reveal further details, while clicking again will hide it. Also, clicking on (hideshow Gödel’s) will reveal relevant parts of Gödel’s text (shown in green), while clicking again will hide it. Please note that older browsers may not display some symbols correctly.

(like this)

(like this)

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

Primitive Recursive Relations and Functions

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:

1. For given values of its free variables, every primitive recursive relation is provable, or else its negation is provable from the axioms of number theory, and
2. Every primitive recursive relation can be expressed in the formal system P.

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:

1. since a number-theoretic relation is a relation where the entities that the relation refers to are all natural numbers or variables for natural numbers, then there is a formula of the formal system that corresponds to that number-theoretic relation, and
2. given any primitive recursive relation with n free variables, there is always a corresponding formula in the formal system which also has n free variables - and it has the property that:
3. whenever the free variables of the primitive recursive relation are substituted by specific values, if the resulting relation is provable, then the corresponding formula of the formal system is also provable; if the negation of the resulting relation is provable, then the corresponding negation formula of the formal system is also provable.

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.

The Epsilon notation ε

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

Primitive Recursive Functions

A primitive recursive function can always be evaluated by a method that always has a finite number of precisely defined steps.

For example, the ‘factorial’ function is defined as:

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

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.

Primitive Recursive Relations

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.

Footnotes:

Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked. 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 - any address will do, it does not require verification. Your e-mail will only be used to notify you of replies to your comments - it will never be used for any other purpose and will not be displayed. If you cannot see any comments below, see Why isn’t the comment box loading?.

NEWS

Lebesgue Measure

There is now a new page on a contradiction in Lebesgue measure theory.

Illogical Assumptions

There is now a new page Halbach and Zhang’s Yablo without Gödel which analyzes the illogical assumptions used by Halbach and Zhang.

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.

Previous Blog Posts

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:

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.

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.