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

# A Simplified Explanation of Gödel’s proof - Part 3

## 3: Gödel’s special numbering system

Page last updated 15 May 2021

Gödel’s numbering system is a way of representing any sentence of the formal language by a number. But not only sentences. Any sequence of symbols of the alphabet of the formal system can have a corresponding number. And every proof sequence of sentences of the formal language can also be represented as a number (a proof sequence is a list of all the sentences that go together to make a proof of some sentence).

The Gödel numbering system is a one-to-one function. That simply means that it takes in one value, which is some combination of symbols of the formal language, and puts out another value, which is a number. Every combination of symbols is matched to a unique number, so that no two combinations can have the same number, and no two numbers can match to the same combination.

The way that it works is by a two-step process.

The first step is to take every symbol of the formal language and you define that a specific number is to be associated to every symbol, so that no two formal symbols are associated with the same number.

For example, suppose we take the sentence **{x + y}**, and we match numbers to the symbols.

We might define:

- the opening bracket symbol ‘
**{**’ to match to**4**, - the symbol
*‘*to match to**x**’**6**, - the symbol ‘
**+**’ to**7**, - the symbol
*‘*to**y**’**8**, - and the closing bracket symbol ‘
**}**’ to**12**.

That gives you the sequence of numbers, **4**, **6**, **7**, **8**, and **12**. But **4**, **6**, **7**, **8**, **12** is only a sequence of numbers and isn’t actually a number itself, so there’s a bit more to be done. We need to be able to make this sequence into a number, and we’ve to do that without losing any information, so that you can always convert the number back into the formal sentence.

It isn’t sufficient to take the numbers and put them together to make the **467812**, because that method can lose information. You can’t say whether the original sequence was **46**, **7**, **81**, **2**, or **4**, **67**, **8**, **1**, **2** or **4**, **6**, **78**, **12** or some other sequence.

To be sure that you can always get back the original information that you started with, Gödel devised a way of converting these sequences of numbers into numbers in a way that retains all the original information. The reverse process can be applied in order to retrieve the original information.

Gödel’s encoding system uses prime numbers (prime numbers are numbers that can only be divided by themselves and by one without leaving a remainder).

Gödel’s system takes the prime numbers in order, so that for example, to encode a sequence of five numbers, we start off with the first five prime numbers – which are **2**, **3**, **5**, **7** and **11**.

We now encode our sample sequence, which is **4**, **6**, **7**, **8**, **12** as follows:

Multiply the first prime, which is **2**, by itself **4** times. We use **4** times because **4** is the first number in our sequence. We call this raising **2** to the power of **4** and we denote this as **2 ^{4}**.

Then for the next prime number, which is **3**, we multiply it by itself by **6** times, **6** being by the next number in our sequence. This is called raising **3** to the power of **6**, and we denote this by **3 ^{6}**.

Do the same with the rest of the numbers. This give us

**2 ^{4}**,

**3**,

^{6}**5**,

^{7}**7**,

^{8}**11**,

^{12}

where each bit works out as

**16**, **729**, **78125**, **5764801** and **3138428376721**.

Then we multiply these all together. We can denote that by **2 ^{4} · 3^{6} · 5^{7} · 7^{8} · 11^{12}** and that gives

**16486713209345820741011250000**. That is the matching Gödel number for the sentence

**{x + y}**.

Given a Gödel number, you can always reverse the process. So, given the number **16486713209345820741011250000**, first divide by the first prime number, which is **2**. Keep dividing by **2** until you don’t get an even division and you end up with a remainder, as follows:

**16486713209345820741011250000** divided by **2** gives:

**8243356604672910370505625000**

**8243356604672910370505625000** divided by **2** gives:

**4121678302336455185252812500**

**4121678302336455185252812500** divided by **2** gives:

**2060839151168227592626406250**

**2060839151168227592626406250** divided by **2** gives:

**1030419575584113796313203125**

**1030419575584113796313203125** divided by **2** gives:

**515209787792056898156601562**, with remainder **1**.

This gives the information about how many **2**s were multiplied by each other originally, which was **4**.

We repeat the process with the next prime number, until we get no remainder at all. And this will give you the information that originally we multiplied **2** by itself **4** times, **3** by itself **6** times, **5** by itself **7** times, **7** by itself **8** times, and **11** by itself **12** times. We can write that as **2 ^{4} · 3^{6} · 5^{7} · 7^{8} · 11^{12}**. That means our original number sequence was

**4**,

**6**,

**7**,

**8**,

**12**.

And that means that, given the definition of which symbol matches to which number, that we can tell that we started with **{x + y}**. This means that this method of encoding gives a unique number that retains all the original information of any combination of symbols of the formal language.

That’s all there is to Gödel’s method of encoding the sentences of the formal language. For the full details of the actual Gödel numbering function that Gödel used, please see Gödel proof guide - the Gödel numbering function.

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

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