A Simplified Explanation of Gödel’s Incompleteness Proof:
Part 5

Getting a number relationship to correspond to the concept of substitution

Page last updated 15 May 2021

First we give an example of substitution, using the sentence {x + 2}. Suppose we substitute the x by 8, and that gives us the sentence {8 + 2}. That is one particular example of substitution. What we want is a completely general expression, and we can call it Substitution.

This expression will take two values, one for the sentence to be substituted, the other for the number that we’re going to use for the substitution. That means it will have two free variables. Instead of just calling it Substitution, we can call it Substitution (Sentence, Number).

If we fill in particular values for Sentence, and Number, and if the Sentence has only one free variable, then we’ll get a specific substitution. For our example, if we have:

Substitution ({x + 2}, 8)

then the value of that is:

{8 + 2}.

You can see that Substitution is a function – it takes one value and gives another value. This is a simple substitution function, but as given it is not defined what happens if the sentence has, for example, two free variables, such as the sentence {x + y + 2}.

In fact, for our purpose, we only need to work with sentences that have just one free variable. But the Substitution function will still work with a sentence with two free variables. All we have to do is to define the Substitution function so that if there’s more than one free variable, it will only substitute one of the free variables – we might specify that it takes the free variable that’s the first in alphabetical order. That would mean that Substitution ({x + y + 2}, 8) will give the sentence {8 + y + 2}, since x comes before y in alphabetical order. So that if you needed to substitute both variables of a sentence with two free variables, you simply use the Substitution function twice.

Considerations of Language and Meta-language

You will come across the term ‘meta-language’ in discussions about proofs of incompleteness. This is because any such proof makes assertions in one language about a formal language. The language that talks about another language, and makes statements about another language is called a meta-language. The language that is talked about may be called a ‘sub-language’, or an ‘object-language’.

Because the meta-language has to be able to refer to every symbol of the sub-language, there will be a variable of the meta-language whose domain (the set of allowable values of the variable) is the set of all combinations of symbols of the sub-language (including ‘combinations’ that are actually just single symbols). For this reason, no variable of the sub-language can also be a variable in the meta-language, because then it would be both a variable and a member of the domain of the variable at the same time, which would be absurd.

The Substitution function can lead to some confusion. A function always gives a specific value. In the above, Substitution ({x + y + 2}, 8) gives the specific value as the sentence {8 + y + 2}. But from another point of view, {8 + y + 2} is not a particular value, since y is a free variable, which means that the entire expression {8 + y + 2} is not a particular value.

The point that must be grasped here is that y is only a variable in the formal language, and it’s not a variable in the meta-language that we are talking in. The language of the Substitution function is a language that is a different language to the formal sentence that we’re applying the substitution to. The language of the Substitution function makes statements about the formal language, so the language of the Substitution function is the meta-language.

And we call the formal language (the language that is talked about) the sub-language. From the point of view of the meta-language and the Substitution function, the values that it takes for Sentence and Number are simply symbols of the sub-language to be manipulated. So as far as the meta-language is concerned, {8 + y + 2} is just a combination of symbols, and it sees y as just another symbol of the sub-language, not as one of its own variables.

It is important to remember that the Substitution function can take all different sorts of symbols as its values, not just number values. The value for Sentence can be any combination of symbols of the formal language.

Now, you should recall that for any combination of symbols of the formal language there is a matching Gödel number. That means for valid values of Sentence and Number in Substitution (Sentence, Number), there is a matching Gödel number for the value for Sentence and a matching Gödel number for the value for Number. If you can define the Substitution function you should also be able to define another function that takes the matching Gödel numbers, and which mirrors the Substitution function exactly.

I’m going to call that function the G‑Substitution function. This function takes two number values, and so it will have two variables. So we can also call it G‑Substitution (Number1, Number2).

I’ll demonstrate how it works by an example. I’m going to use the sentence {x + 2} again. As before, we look up the definition of the symbols and the matching numbers, and we get the sequence of numbers, 4, 6, 7, 9, and 12, which gives the Gödel number 2⁴, 3⁶, 5⁷, 7⁹, 11¹², which is 115406992465420745187078750000 (here we take the number 9 to match to the symbol 2 of the formal system). So:

GN({x + 2}) = 11540699246​5420745187078750000

That gives us our first number, which is Number1.

Now, we are going to substitute the x of {x + 2} by 8. Suppose that the matching code for 8 is 10, and that gives the value of GN(8) as 2¹⁰. That gives GN(8) = 2¹⁰ = 1024, and that is our second number – Number2.

When we substitute the x of {x + 2} by 8 we get {8 + 2}, and the matching sequence of numbers for {8 + 2} is 4, 10, 7, 9, and 12. And the Gödel number for that is given as:

GN({8 + 2} = 2⁴  · 3¹⁰ · 5⁷ · 7⁹ · 11¹² = 93479663896990​80360153378750000.

Now suppose that we have Substitution ({x + 2}, 8). We know that this gives the result {8 + 2}. The matching number function, which is G‑Substitution will take the matching Gödel number values. The matching Gödel numbers are:

GN({x + 2}) = 11540699246​5420745187078750000,

and

GN(8) = 1024.

We put these values into the function G‑Substitution for Number1 and Number2. That can be written as:

G‑Substitution (115406992​465420745187078750000, 1024).

If it’s all done correctly, and if I had defined the G‑Substitution function properly, then you could give me those two numbers, and I could work out the value of G‑Substitution (11540699246​5420745187078750000, 1024)

The answer has to be some number, and I could find that answer without working out what the matching formal language equivalents of the numbers are. In fact, I could do it without knowing anything at all about the formal language at all, since all I’m doing is manipulating numbers, and coming up with the correct answer of 934796638969908​0360153378750000.

Then, and only then, if I wanted to, I could decode the number 934796638969908​0360153378750000, and work out that the matching formal sentence was {8 + 2}. So purely by working with numbers, you can get the desired result.

You might wonder, since G‑Substitution is a number relationship, what happens if you put in a number value that isn’t the Gödel number of any formal sentence. If you put in a number which isn’t a Gödel number for a sentence, then the G‑Substitution function simply gives the value that you put in for Number1. The same would happen if Number1 was the Gödel number of a nonsense sentence – a sentence that only uses the alphabet of the formal sentence, but which isn’t put together according to the rules – in English we’d call it a nonsensical sentence.

And the same would apply if you put in a number value for Number2 that isn’t the Gödel number of a number – the G‑Substitution function would simply give the value that you put in for Number1. And again, that’s the way it should be, since you can’t substitute variables of a formal sentence by anything other than a number value.

As was the case for Part 4: Creating a special number relationship, the exact definitions that Gödel used for his G‑substitution function aren’t really that important. Because it wouldn’t matter if he’d made some error in his definitions, in principle there must be a precise definition of substitution of a variable of a formal sentence by a number value. And that means that there must also be a precise definition that gives the matching transformation of the matching Gödel numbers of the sentence and the number – and which gives the Gödel number for the formal sentence that you’d get if you substituted the free variable of the sentence by the number. So there has to be some number relationship that actually is the G‑Substitution function.