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

#
A Step by Step Guide to Gödel’s Incompleteness Proof:

6: Gödel’s Relations of Natural Numbers 1 to 23

## Page Contents

Page last updated 14 May 2021

Note that (provided you have JavaScript enabled) clicking on (show hide ) will reveal further details, while clicking again will hide it. Also, clicking on (show Gödel’s hide Gödel’s ) will reveal relevant parts of Gödel’s text (shown in green), while clicking again will hide it.

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] = 2**.

^{3}

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

### 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

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

#### 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**

#### 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 **∀**

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

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

Relations 18. **Typ _{1}′(x)** and 19.

**Typ**correspond to the assertion that a particular combination of symbols is a string of the formal system.

_{n}(x)

18. **Typ _{1}′(x) ** 19.

**Typ**( hide show)

_{n}(x)

#### 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)** ( hide show)

Footnotes:

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

A | Anzahl | = | number |

Aeq | Aequivalenz | = | equivalence |

Ax | Axiom | = | axiom |

B | Beweis | = | proof |

Bew | Beweisbar | = | provable |

Bw | Beweisfigur | = | proof-schema |

Con | Conjunktion | = | conjunction |

Dis | Disjunktion | = | disjunction |

E | Einklammern | = | include in brackets |

Elf | Elementarformel | = | elementary formula |

Ex | Existenz | = | existence |

Fl | unmittelbare Folge | = | immediate consequence |

Flg | Folgerungsmenge | = | set of consequences |

Form | Formel | = | formula |

Fr | frei | = | free |

FR | Reihe von Formeln | = | series of formulae |

Geb | gebunden | = | bound |

Gen | Generalisation | = | generalization |

Gl | Glied | = | term |

Imp | Implikation | = | implication |

l | Lange | = | length |

Neg | Negation | = | negation |

Op | Operation | = | operation |

Pr | Primzahl | = | prime number |

Prim | Primzahl | = | prime number |

R | Zahlenreihe | = | number series |

Sb | Substitution | = | substitution |

St | Stelle | = | place |

Su | Substitution | = | substitution |

Th | Typenerhohung | = | type-lift |

Typ | Typ | = | type |

Var | Variable | = | variable |

Wid | Widerspruchsfreiheit | = | consistency |

Z | Zahlzeichen | = | number-symbol |

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.

Derogatory comments.

Long-winded comments.

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 usernames for one person.

Users, who, when shown their point is wrong, immediately claim that they just wrote it wrong 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.

Note: a password enables editing of comments, an email enables notification of replies