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

Creating a special number relationship

Page last updated 15 May 2021

By the previous part, Part 3: Gödel’s special numbering system, we know that for any combination of formal language symbols there’s a matching number. We’re going to call that number the matching Gödel number. So for any formal sentence there’s a matching Gödel number. And if there’s a formal proof that proves that sentence, then there must also be a matching Gödel number for that proof.

From Part 2: Formal Language Systems, we know that there’s a definite relationship between that proof and the sentence that it proves. We also know that that relationship can be completely and precisely defined. It may be a very complex relationship, but it can always be completely defined, since it can be broken down into simple steps, even if there are a large number of those simple steps. Each of those simple steps is a simple relationship between formal language sentences.

In Gödel’s paper, the idea is that, for every single one of those simple steps - which is a relationship between formal sentences - you can define a corresponding relationship between the numbers that are the matching Gödel numbers for those formal sentences – so that for every single simple step of any formal proof there is a single matching number relationship.

And if all those single number relationships can be put together in some way, you end up with another single number relationship, which is the relationship between the Gödel number of a formal sentence and the Gödel number of the proof that proves that sentence.

Up to this point, we have been talking in very general terms. Now we need to get into it a bit deeper.

We now need to use various symbols to make what we are saying more manageable. Some people find it hard to understand symbols, but it is actually very simple. A symbol can be considered as a name for something, and we use these names so that our expressions do not become too cumbersome.

We can use symbols as names for some particular thing, which might be a number. If I say ‘Bagpuss and Rover’, when Bagpuss and Rover are names for particular animals, that’s basically no different to saying ‘6 and 11’, where 6 and 11 are names for particular numbers. I could call Bagpuss A, and Rover B, and when I say ‘A and B’, it’s the same as saying ‘Bagpuss and Rover’ – as long as it is defined somewhere what A and B stand for.

We can also have names for variables. If I say, ‘a cat and a dog’, that’s basically no different to saying ‘a number x and a number ’y. And that’s really no different to saying ‘x and y’ – provided I’ve already said that x and y are variables for numbers.

The definition of what constitutes a step of a proof can be defined in general terms, so that basically I can say:

‘P is the proof of the sentence S’.

In that expression P and S are variables – variables for formal sentences.

Given any two formal sentences, I can substitute them for P and S, and I get a proposition that is either correct or incorrect.

Suppose P is {x + 3}, and S is {2 + y }.

That gives the expression, ‘{x + 3} is the proof of {2 + y }’.

Now that proposition is obviously wrong, but it serves to illustrate the principle – we end up with a proposition.

Now, instead of referring to the Gödel numbering system by simply saying ‘the Gödel numbering system’ we give the Gödel numbering system a shorter name, which is GN. When we write GN(F ) that just means that F is a free variable – the free variable of the Gödel numbering system. It’s a variable that can take the value of any formal symbol sentence.

The example formal sentence that we used earlier was {x + y } and its matching Gödel number was 16486713209345820741011250000.

So, given the sentence {x + y }, we can write the expression GN({x + y }).

That expression GN({x + y }) represents the Gödel number of the sentence {x + y }, which is the number 16486713209345820741011250000.

So we can say that:

GN({x + y }) = 16486713209345820741011250000.

The name GN(F ) is simply a general name that we’ve chosen for the Gödel number that matches to the formal sentence F. And in exactly the same way, we could put it another way simply by using different names. For example, we could say that GN(Formal Sentence) is a name for the Gödel number that matches to the formal sentence that we represent by the variable Formal Sentence.

Now, as we saw earlier, we can have a relationship between a formal sentence and a formal proof. If we use the names P and S as names for variables for formal symbol sentences, then the relationship we’re interested in is the relationship:

‘P is the proof of the sentence S’

Since there are matching Gödel numbers for P and S, then there’s also a matching relationship between the Gödel numbers for the formal proof P and the formal sentence S. And we can write down that relationship as:

‘GN(P) is the G‑proof of GN(S)’.

Now we have to be careful not to get confused. That does not mean that GN(P) proves GN(S).

G‑proof is only a name for a relationship. GN(P) and GN(S) are only numbers, and a number can’t actually be a proof of another number. Although we used the name G‑proof for the relationship between the numbers GN(P) and GN(S), we could have used any name. We use the name G‑proof so that it is easier to remember what it stands for.

G‑proof is a particular number relationship that corresponds to the relationship between the formal sentences P and S. That means that ‘GN(P) is the G‑proof of GN(S)’ is a relationship that corresponds to the expression ‘P is the proof of the sentence S’.

Because G‑proof is a general number relationship, we could substitute any number for the variables into the relationship. So we can have ‘3178934… is the G‑proof of 43476234…’

And this can be either correct or incorrect, since the matching formal sequence for 3178934… is either the proof of the formal sentence that matches to 43476234…or it isn’t.

Now, if the formal language is fully definable, then the general relationship between a formal proof and the formal sentence that it proves is fully definable. Gödel actually wrote out a detailed definition of the G‑proof relationship that he used in his paper for a particular formal system. That definition is quite long and complex. But in principle, if the Gödel numbering system is a completely accurate representation of the formal language, then the Gödel number of that formal proof and the Gödel number of that formal sentence must also have a matching number relationship that can be completely defined. And that actually is the number relationship that we have called G‑proof. That means that the exact definitions that Gödel used to generate his G‑proof relationship aren’t really that important. Even if he’d made a mistake in his definitions, in principle the definitions can be precisely made, and there must be some number relationship that actually is this G‑proof.