A Simplified Explanation of
Gödel’s Incompleteness Proof:
Another Numbering System
Page last updated 15 May 2021
This is the point in Gödel’s proof where we need a new function that is similar to the Gödel numbering function. The Gödel numbering function is not a number relationship, since it refers to symbols of the formal language that aren’t numbers, such as the symbol for equals, the symbol for plus, and so on.
We might suppose that we say that we’re going to use the Gödel numbering function only for symbols of the formal language that actually are numbers. So, if we call the Gödel numbering function GN(x), we say that we can only substitute the x by symbols of the formal language that represent numbers.
However, that still doesn’t make GN(x) into a number relationship – because the actual definition of the Gödel numbering function still refers to symbols other than numbers. In order for his proof to work, Gödel needs a function that is similar to the GN(x) function, but which is a purely number relationship.
The idea is that this new function will only take number values for its free variable, and provided you’re only inputting numbers, and the function only results in number values, this new function can do exactly the same thing as the Gödel numbering function. Since this new function doesn’t refer to anything other than numbers, and variables for numbers, and is defined only in terms of numbers, then it is a number relationship.
We can call this new function anything we like, but I’m going to call it the Basic Numbering function, or BN for short, or BN(x), where x is its free variable. (Footnote: In Gödel’s original proof, Gödel calls this function Z(n) - it is his ‘relation’ 17.) That means that whenever we put in symbols that are the symbols for a number, this BN function gives us the correct Gödel number – so we can get a Gödel number for any number we want.
You might wonder what happens if we try to substitute the variable of BN(x) by a symbol that isn’t a number. The answer is simple – the definition of BN(x) does not include any reference to specific values that are not number values. So trying to substitute a non-number value wouldn’t make any sense. It would be like trying to use any foreign word in a language and expecting it to make sense. With this function BN(x), wherever it appears, it has to be the case that only numbers can be substituted for its free variable x.