Logic and Language

Copyright   James R Meyer    2012 - 2023 https://www.jamesrmeyer.com

# A Step by Step Guide to Gödel’s Incompleteness Proof: 6: Relations of Natural Numbers 1 to 23

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.

Note that (provided you have JavaScript enabled) clicking on () will reveal further details, while clicking again will hide it.

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

## Gödel’s Relations 1- 45 of Natural Numbers

Note again that in Gödel’s paper the epsilon symbol ε is used in several definitions; the meaning of the term ε (see also Epsilon notation ε) is given by:

εx R(x, y) is a function with the free variable y, and whose value is the smallest number x for which the relation R(x, y) holds, and if there is no such smallest number, then the value of εx R(x, y) is 0.

In the section entitled “Relations 1-46 ” Gödel defines various relations/functions. The relations/functions 1-45 are all primitive recursive; relation 46 is not defined as primitive recursive. Note that while in modern terminology, all variables of a relation are normally enclosed after the relation name in brackets (e.g. Rel(x, y) ), Gödel often places variables before and after the relation name (e.g. x Rel y) ). The names are mainly abbreviations of German words, see notes at the foot of this page for the words and the English translations.

Some of these functions (nos. 3, 4, 5, 16, 30) are recursively defined in terms of the value of the function itself. For example, the function 4 is the factorial function mentioned in the previous page.

For most of the relations/functions, Gödel adds comments describing the relationship between symbol strings of the formal system that corresponds (by the Gödel numbering function) to the given relation between natural numbers. In the following, further notes are included to assist the reader. In these notes variables for symbols/symbol strings of the formal system P are represented by colored capital letters, e.g. X, Y. (Footnote: Note that these variables are in a language that is a meta-language to the formal system.)

It is crucial to remember that all these relations/functions are purely number-theoretic - that is, that they only refer to natural numbers and variables whose domain is natural numbers. It is important not to use intuition to jump to conclusions, nor to make assumptions about the corresponding relationships between symbol strings of the formal system. Any such correspondence must follow in a logical manner.

It should be noted that in some cases, a corresponding number is obtained not by the Gödel numbering function φ but by the ψ function (as referred to previously, see The Psi function). This does not present any problems, since given a number obtained via the ψ function for a symbol, one can always obtain the Gödel number by applying the Gödel numbering function φ to that single symbol. For example ψ(f ) = 3, and φ[ f ] = 23.

NB: when the term ‘symbol’ is used below, unless otherwise indicated, that can mean either a single basic symbol of the system P or a variable of the system P. Also note that some of the ‘formulas’ used in the examples are not actually proper formulas of the system P; this is only so that the examples are not overly long.

### Relations/functions 1-5: Basic Arithmetical Concepts.

These are basic arithmetical concepts, principally concerning properties of prime numbers. Since the Gödel numbering method is based on the fact that every natural number has a unique factorization into its constituent prime factors, these relations/functions underpin the subsequent relations and functions. The details of the definitions are given below; clicking “show” will show the details for that definition.

1. x/y   ()

This is a relation that asserts that y is divisible by x with no remainder .

e.g. the relation 72/6 applies, but 73/6 does not apply.

In Gödel’s paper…

2. Prim(x)   ()

This is a relation that asserts that x is a prime number. i.e: x is one of 2, 3, 5, 7, 11, 13, 17, 19, 23,

e.g. the relation Prim(7) applies, but Prim(8) does not apply.

In Gödel’s paper…

3. n Pr x   ()

This is a function whose value is the nth largest prime number that is a factor of x .

e.g. 4 Pr [ 23 · 3 · 53 · 74 · 11 · 133 ] = 7

(7 is the 4th largest prime factor of 23 · 3 · 53 · 74 · 11 · 133)

In Gödel’s paper…

4. n!   ()

This is the factorial function as mentioned previously in this guide. Its value is given by multiplying together n and all the natural numbers that are smaller than n (except zero).

e.g. 4! = 4 · 3 · 2 · 1

In Gödel’s paper…

5. Pr(n)   ()

This is a function whose value is the nth largest prime number.

e.g. Pr(5) = 11 (the 5th largest prime is 11; the four smaller primes are 2, 3, 5 and 7)

In Gödel’s paper…

### Relations/functions 6-23: Relations/functions that correspond to the construction of symbol strings

We now move from basic arithmetical definitions to the definition of functions that correspond to operations on symbols and symbol strings of the formal system - and to the definition of relations that correspond to assertions regarding symbol strings of the formal system.

The formulas of the formal system are combinations of the symbols of the system that satisfy certain conditions. One of the goals of these relations and functions is to lead to the definition of relation 23, which corresponds to the assertion that a given symbol string is a formula of the formal system.

It will be noted that the functions/relations are presented here in a different order to that given by Gödel; here they are grouped according to their similarity and purpose.

#### Functions 6, 7, 9: Basic string operations

These are basic functions that correspond to:

6. n Gl x: the operation of obtaining the symbol at a particular position in a symbol string

7. l(x): the operation of counting the number of symbols in a symbol string

9. R(x): the operation of obtaining the Gödel number of a single symbol

6. n Gl x   ()

This is a function which is defined in terms of the function n Pr x above, and gives the value of the smallest factor of the exponent of the nth largest prime in the number x.

e.g. 5 Gl [ 23 · 33 · 51 · 711 · 1119 · 133 ] = 19 (the 5th largest prime in x is 11, and its exponent is 19)

If x is the Gödel number of the formula X, i.e: x = φ[  X  ], then n Gl x corresponds to:

the symbol at the nth position in the symbol string X

e.g. if X = ff 0(y1), then x = φ[  X ] = 23 · 33 · 51 · 711 · 1119 · 133

then 5 Gl [ 23 · 33 · 51 · 711 · 1119 · 133 ] = 19 to correspond to:

the operation of obtaining the 5th symbol of the symbol string ff0(y1), which is y1

where 19 = ψ[ y1 ].

In Gödel’s paper…

7. l(x)   ()

This is a function whose value is the number of unique prime factors in x.

e.g. l(23 · 33 · 53 · 71) = 4 (there are only four unique prime factors: 2357).

If x is the Gödel number of the formula X, i.e: x = φ[ X ], then l(x) corresponds to:

the operation of counting the number of individual symbols/variables in the formula X

e.g. if X = fff 0, then x = φ[ X ] = 23 · 33 · 51 · 71, then

l(23 · 33 · 51 · 71) = 4 corresponds to:

the operation of counting the number of symbols in fff0, which is 4.

In Gödel’s paper…

9. R(x)   ()

This is a function which raises 2 to the power of x, e.g. R(19) = 219

So R(x) = φ[ X ]

where x = ψ[ X ] (as given by ψ - the Psi function - the function that assigns a unique number to a symbol X of the formal system), and where X is a single symbol or a variable of the formal system P .

e.g. if X = (, then x = ψ[ (  ] = 11, and

R(x) = 211 corresponds to:

the operation of obtaining the Gödel number of the symbol (, which is φ[ (  ] = R(ψ[ (  ]) = 211

In Gödel’s paper…

#### Function 8: Defining numbers that correspond to a concatenation of two strings

x * y corresponds to the operation of concatenating (joining together) two symbol strings.

8. x * y   ()

This function can be thought of as ‘shifting’ up the prime factors of the second number y. It is probably easiest to understand this function by an example.

[ 23 ] * [ 23 · 33 · 53 · 71 ] = 23 · 33 · 53 · 73 · 111

And *  y = φ[ XY ], where x = φ[ X ] and y = φ[ Y ]

i.e: φ[ X ]  *  φ[ Y ] = φ[ XY ]

that is, if x= φ[ X ] and x= φ[ Y ], then the function x  *  y corresponds to:

the operation of concatenating X and Y

where X and Y are symbol strings of the formal system P .

e.g. if X = f and Y = fff 0, then x = φ[ X ] = 23, and y = φ[ Y ] = 23 · 33 · 53 · 71

then 23 * 23 · 33 · 53 · 71 = 23 · 33 · 53 · 73 · 111 corresponds to:

the operation of concatenating the symbol strings f and fff 0 to give ffff 0.

In Gödel’s paper…

#### Functions 16, 17: Defining numbers that correspond to simple strings

These are functions that correspond to:

16. n N x: the operation of n repetitions of prefixing a symbol string by the symbol f

17. Z(n): the operation of n repetitions of prefixing the symbol 0 by the symbol f

16. n N x   ()

For this function,

0 N x = φ[ X ]

1 N x = φ[ fX ]

2 N x = φ[ ffX ]

n N x = φ[ fff…ffX ], where there are n occurrences of f

that is, if x = φ[ X ], then the value of n N x corresponds to:

the operation of prefixing n repeated occurrences of the symbol f in front of the symbol string X

e.g. if X is f 0, and φ[ f 0 ] = 23 · 31

then 3 N (23 · 31) = 23 · 33 · 53 · 73 · 111 corresponds to:

the operation of prefixing f0 by three instances of f, which gives ffff 0.

In Gödel’s paper…

17. Z(n)   ()

For this function,

Z(n) = n N R(1), and R(1) = 21, so

Z(n) = n N 21= φ[ fff…ff 0 ]

where there are n occurrences of f, since by the Gödel numbering function, 21 corresponds to the formal symbol for zero, which is 0. So the value of Z(n) corresponds to:

the operation of prefixing n repeated occurrences of the symbol f in front of the symbol 0

e.g. Z(5) = φ[ fffff 0 ] = 23 · 33 · 53 · 73 · 113 · 131 corresponds to:

the operation of obtaining the Gödel number of fffff 0

Note: Gödel is being rather disingenuous here in simply asserting that “Z(n) is the number-string for the number n”, without giving any further details. By that assertion he is asserting that Z(n) = φ[ n ], i.e: that Z(n) is the same as the Gödel numbering function for the number n. But the domain of the variable of the Gödel numbering function φ is all symbol strings of the formal system, whereas the domain of the function Z is the domain of natural numbers. To make the assertion means that the domain of the common variable n would have to be restricted to symbol strings of the format 0, f 0, ff 0, , and it would not be allowable, for example to have an equality between 5 and fffff 0, since if such equality were permissible, we would have φ[ 5 ] which is not a valid expression. Furthermore, the symbols for zero and the successor symbol for the formal system could be any symbols, for example, 3 and 7, which would rule out using the symbols 3 and 7 for three and seven, as is conventional for number-theoretic relations. Gödel’s stipulation requires that his number-theoretic relations must necessarily use precisely the same format for natural numbers as the formal system in question - which begs the question as to why the two systems should be interdependent in this manner. Gödel claims that any formal system (if it includes sufficient arithmetic) can be used in place of his system P - which means that the formal system, and the symbols it uses, must be independent of the meta-language. We will discuss this matter in more detail later when considering Gödel’s Proposition V.

In Gödel’s paper…

#### Functions 10, 13, 14, 15: Defining numbers that correspond to complex strings

These functions correspond to operations that build up more complex symbol strings from simpler ones. They correspond to:

10. E(x): the operation of putting brackets around a symbol string

13. Neg(x): the operation of creating the negation of a symbol string

14. x Dis y: the operation of joining two symbol strings by the ‘or’ symbol

15. x Gen y: the operation of prefixing a symbol string by a variable and the ‘for all’ symbol

10. E(x)   ()

This function can be thought of as multiplying the number x by an ‘initial’ 211, and ‘shifting’ each of the exponents of the prime factors of the number x up to the next largest prime, and then multiplying the result by a ‘final’ next largest prime with an exponent of 13. The exponent of the ‘initial’ 2 is 11, since 11 is the matching number for the opening bracket (11 = ψ[ (  ]), and the exponent of the ‘final’ prime is 13, since 13 is the matching number for the closing bracket (13 = ψ[ )  ]). It is probably easiest to understand this function by an example:

E(23 · 33 · 53 · 73 · 111) = 211 · 33 · 53 · 73 · 113 · 131 · 1713

In this example 17 is the additional ‘final’ next largest prime (with the exponent of 13).

Note that E(x) = φ[ ( X ) ]

where x = φ[ X ], and where X is a symbol string of the formal system P.

See Function 8, which gives that

φ[ ( X ) ] = φ[ ( ] * φ[ X ] * φ[ ) ]

that is, if x = φ[ X ] then the value of E(x) corresponds to:

the operation of putting brackets on either side of the symbol string X

e.g. if X = ffff 0, and φ[ ffff 0 ] = 23 · 33 · 53 · 73 · 111, then

E(x) = φ[ ( X ) ] = φ[ (ffff 0) ] = 211 · 33 · 53 · 73 · 113 · 13 · 1713 corresponds to:

the operation of enclosing the symbol string ffff 0 by brackets to give (ffff 0).

In Gödel’s paper…

13. Neg(x)   ()

This function can be thought of as multiplying the number x by an ‘initial’ 25 · 311, and ‘shifting’ each of the exponents of the prime factors of the number x up to the next largest prime, and then multiplying the result by a ‘final’ next largest prime with an exponent of 13. The exponent of the ‘initial’ 2 is 5, since 5 is the matching number for the negation symbol (5 = ψ[ ¬  ]), and the exponent of the ‘initial’ 3 is 11, since 11 is the matching number for the opening bracket (11 = ψ[ (  ]); the exponent of the ‘final’ prime is 13, since 13 is the matching number for the closing bracket (13 = ψ[ )  ]). It is probably easiest to understand this function by an example:

Neg(23 · 33 · 53 · 73 · 111) = 25 · 311 · 53 · 73 · 113 · 133 · 171 · 1913

In this example 19 is the additional ‘final’ next largest prime (with the exponent of 13).

And Neg(x) = φ[ ¬(X) ]

where X is a string of symbols of the formal system P, and ¬, ( and ) are symbols of the formal system P.

Function 8 above gives that

φ[ ¬ ] * φ[ ( ] * φ[ X ] * φ[ ) ]= φ[ ¬(X) ]

that is, if x = φ[ X ] then the value of Neg(x) corresponds to:

the operation of putting the symbol ¬ in front of the symbol string X

i.e: creating the negation of the formula X

e.g. if X = ffff 0, and φ[ ffff 0 ] = 23 · 33 · 53 · 73 · 111

then Neg(x) = φ[ ¬(ffff 0) ] = 25 · 311 · 53 · 73 · 113 · 133 · 171 · 1913 corresponds to:

the operation of enclosing the symbol string ffff 0 by brackets and prefixing that by the negation symbol to give ¬(ffff 0).

In Gödel’s paper…

14. x Dis y   ()

For this function,

x Dis y = φ[ (X) ∨ (Y) ]

where X and Y are symbol strings of the formal system P, and ∨ is a symbol of the formal system P.

Function 8 above gives that

φ[ (  ] * φ[ X ] * φ[ )  ] * φ[ ∨ ] * φ[ (  ] * φ[ Y ] * φ[ )  ] = φ[ (X) ∨ (Y) ]

that is, if x = φ[ X ] and y = φ[ Y ], then the value of x Dis y corresponds to:

the operation of concatenating the symbol string (X), the symbol , and the symbol string (Y).

i.e: creating a formula by joining two formulas by the ‘or’ symbol

e.g. if X = f 0, and φ[ f 0 ] = 23 · 31, and Y = ff 0, and φ[ ff 0 ] = 23 · 33 · 51, then

x Dis y = φ[ (f 0) ∨ (ff 0) ] = 211 · 33 · 51 · 713 · 117 · 1311 · 173 · 193 · 231 · 2913 corresponds to:

the operation of enclosing the symbol strings f 0 and ff 0 by brackets and interposing the symbol between them to give (f 0) ∨ (ff 0).

In Gödel’s paper…

15. x Gen y   ()

For this function,

x Gen y = φ[ X ∀ (Y) ]

where X and Y are symbol strings of the formal system P, and is a symbol of the formal system P.

Function 8 above gives that

φ[ X ] * φ[ ∀ ] * φ[ (  ] * φ[ Y ] * φ[ )  ] = φ[ X ∀ (Y) ]

that is, if x = φ[ X ] and y = φ[ Y ], then the value of x Gen y corresponds to:

the operation of concatenating the symbol string X, the symbol , and the symbol string (Y).

i.e: creating the generalization of a formula by prefixing it with a variable and the ‘For all ’ symbol (though note that in this function X is not restricted to being a variable - it can be any symbol string of the system P; the definition of what constitutes a variable is given by Relation 12) .

e.g. if X is a type 1 variable, and x = φ[ z1 ], and Y is some formula, where y = φ[ Y ], then

x Gen y = 223 · 39 · …    = 2ψ[ z1 ] · 3ψ[ ∀ ] · … corresponds to:

the operation of bracketing the formula Y and prefixing it by z1

In Gödel’s paper…

#### Relations 11, 12: Assertions regarding variables of the formal system

Relations 11. n Var x and 12. Var(x) correspond to the assertion that a particular symbol is a variable (reminder: we refer to a variable of the formal system as a ‘single’ symbol, although it is actually composed of two or more symbols).

11. n Var x   ()

This is a relation, which asserts that x = pn, where p is a prime number greater than 13.

e.g. the relation 1 Var 17 applies; 2 Var 232 applies; 2 Var 19 does not apply (since the exponent of 19 is not 2).

The relation n Var x is an assertion regarding natural numbers n and x, and corresponds to the assertion:

the symbol string X is a type n variable of the formal system P

where x = ψ[ X ].

Note that n Var x defines a correspondence to a variable of the formal system by the use of the ψ function rather than using the φ function directly. The n defines the type of the corresponding variable X.

e.g. if X is the variable x3 of the formal system, and ψ[ x3 ] = 17

then 3 Var 173 corresponds to:

the assertion that the symbol string x3 is a type 3 variable.

In Gödel’s paper…

12. Var(x)   ()

This is a relation whose definition follows directly from the previous relation (n Var x), i.e: it asserts that x = pn, where p is a prime number greater than 13, and n > 0.

The relation Var(x) is an assertion regarding a natural number x, and corresponds to the assertion:

the symbol string X is a variable of the formal system P

where x = ψ[ X ].

Similar to the definition for n Var x. Var(x) also defines a correspondence to a variable of the formal system by the use of the ψ function.

e.g. if X is the variable y2 of the formal system, and ψ[ y2 ] = 192, then Var 192 corresponds to:

the assertion that the symbol string y2 is a variable of the formal system P.

In Gödel’s paper…

#### Relations 18, 19: Assertions regarding Type n strings of the formal system

Relations 18. Typ1′(x) and 19. Typn(x) correspond to the assertion that a particular combination of symbols is a string of the formal system.

18. Typ1′(x)   19. Typn(x)   ()

Typ1′(x) is not used anywhere else, its only role is in the definition of the relation Typn(x).

Typn(x) asserts that either x = 23 · 33 · … · pq, or x = 2pn, where p, q and n must satisfy certain conditions.

Typ1′(x) asserts that either:

x = 23 · 33 · … · p1, where p is some prime number; this corresponds to:

X is a symbol string of the form 0, f 0, ff 0, fff 0, …,

where x = φ[ X ].

or

x = 23 · 33 · … · pq, where p is some prime number and q is some prime number greater than 13; this corresponds to:

X is a symbol string of the form x1, fx1, ffx1, fffx1, , or y1, fy1, ffy1, fffy1, , etc,

where x = φ[ X ].

For Typn(x), for the case when n = 1, the case is simply

Typ1(x) = Typ1′(x)

when n > 1, Typn(x) asserts that:

x = 2pn, or x = (2p)n, where p is some prime number greater than 13; this corresponds to:

X is a string of type n (which is the same as a variable of type n)

where x = φ[ X ].

See Type n string definition for the definition of a type n string/variable.

So, Typn(x) is an assertion regarding a natural number x, and corresponds to the assertion:

the symbol string X is a type n string of the formal system P

where x = φ[ X ].

In Gödel’s paper…

#### Relations 20 - 23: Assertions regarding formulas of the formal system

Relations 20. Elf(x) and 21. Op(x,y,z) correspond to the assertion that a particular combination of symbols is a particular type of formula of the formal system. FR(x) is a relation which corresponds, though not directly by Gödel numbering, to the notion of a series of formulas. These relations are not used elsewhere; their only purpose is for the definition of Form(x).

Relation 23. Form(x) corresponds to the assertion that a particular combination of symbols is a formula of the formal system. It is defined in terms of Elf(x), Op(x,y,z) and FR(x).

20. Elf(x)   21. Op(x,y,z)   22. FR(x)   23. Form(x)   ()

Elf(x) is a relation that corresponds to the assertion:

the symbol string X is an elementary formula of the formal system P.

where x = φ[ X ]. See elementary formula.

Op(x, y, z) is a relation that corresponds to the assertion:

the symbol string X of the formal system P is of the form

¬(Y), or

(Y) ∨ (Z), or

x∀(X),

where x = φ[ X ], y = φ[ Y ] and z = φ[ Z ] and Y and Z are symbol strings of the formal system P.

See the formulas following the section elementary formula.

FR(x) is a relation which asserts that:

x = 2φ[ X1 ] · 3φ[ X2 ] · 5φ[ X3 ] · … pφ[ Xn ]

x corresponds to a ‘series of formulas’ (which may be a ‘proof-schema’ ), in that the prime factors of x have exponents that are the Gödel numbers of formulas, where each formula is either an elementary formula or a formula built up from elementary formulas. See Formula definition for definition of a formula of the system P.

NB: It is important to observe that this is not a direct correspondence by Gödel numbering as in the previous relations - there is no symbol string of the formal system P where x = φ[ X ] - the exponents of the prime factors of x are Gödel numbers, rather than x itself being a Gödel number - in this case the number x does not correspond by Gödel numbering to a series of formulas nor to a proof schema of the formal system P, i.e:

x  ≠  φ (series of formulas of the formal system P).

x  ≠  φ (proof-schema of the formal system P).

For more on this, see Corresponding Relations in Part 4 of this guide.

Also note that where the function n Gl x occurs in the definition of FR(x), it does not correspond to giving a single symbol of the formal system, which was the case in the previous relations - it corresponds to giving a symbol string of the formal system P.

Form(x) is a relation which asserts that:

the symbol string X is a formula of the formal system P

where x = φ[ X ], and x is the exponent of the largest prime p in a number n, where:

x = 2φ[ Y1 ] · 3φ[ Y2 ] · 5φ[ Y3 ] · … pφ[ Ym ]

See Formula definition for definition of a formula of the system P.

In Gödel’s paper…

Below is a list of names used for various relations in the text, which are mostly abbreviations of German words; translations are provided below:

Interested in supporting this site?

You can help by sharing the site with others. You can also donate at where there are full details.

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

Based on HashOver Comment System by Jacob Barkdull

Copyright   James R Meyer   2012 - 2023
https://www.jamesrmeyer.com