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

Page last updated 28 Dec 2022

Now printer friendly: this guide has now been set up for easy printing so that readers can also access the information in paper format.

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.

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.

Simple primitive recursive functions include the addition function x + y, the multiplier function x · y and the exponential function x^y. 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.