godel part 5 - i've got your number godel

Godel links: Part 1 | Part 2 | Part 3 | Part 4 | Part 5 | Part 6 | Part 7

And deeper we go. Now that we have an outline of how Godel attacks the formal systems, we need to figure out how he made G, the theorem. The trick here is how to write it. We have to use formal mathematical language and we have to make it reference itself. This is tricky. Just understanding what Godel does here is tricky. And it is this bit that gets me lost every time. Let’s start.

Godel starts by defining his formal system. To do this he defines his symbols, defines his rules for combining the symbols into well formed phrases (phrases which by definition can be constructed within the formal system), a special set of axiomatic well formed phrases (starter phrases if you will), and a process by which well formed phrases can be manipulated to produce other well formed phrases. Ultimately a set of well formed phrases will represent a proof of a theorem, with the last well formed phrase denoting the final theorem to be proved. Note we have no issues with the axiomatic statements here that we had with Euclid, because they don’t inherently mean anything yet. They are just a string of symbols. Godel will in fact have some idea of what these symbols mean because he has to be sure that they can be ultimately interpreted as being arithmetic. So in the back of his head some symbols already mean if….then…, and, or, “all”, “some”, etc.

Once this is done Godel does something ingenious. He assigns another set of symbols to the symbols he has already created. Not just any symbol. Numbers. By assigning numbers to the symbols he can translate a given well formed phrase into a long number. This number means the same thing as the well formed phrase. All he is doing here is encoding his phrases. But what it will allow him to do is actually perform arithmetic on the numbers themselves. In this way he will be able to accomplish self referencing. But let’s not get ahead of ourselves. The actual rules for numbering are amazingly brilliant and hard to understand. It’s not important for us. Let’s show an example of what this numbering could look like to give a better idea of what he did (the actual numbering scheme is off to the right).

Symbol	Godel #	Meaning
~	1	Not
→	2	If…then…
x	3	Variable
=	4	Equals
0	5	Zero
s	6	Successor of
(	7	Punctuation
)	8	Punctuation
‘	9	Prime

Now a basic formal structure lesson so we can write some well formed phrases and also understand what it is we are ultimately writing in a arithmetical aspect. Parentheses represents all (as in all variables x…). Successor simply means the next natural number (the successor of 1 is 2). The prime symbol, ‘, allows us to differentiate between two different variables (x and x’). We can put these symbols together to write arithmetical statements. For example, (x)F(x) means “All variables ‘x’ have the property F”. Let’s take another and Godel number it. I’m going to name this phrase ‘wfp1’ (for well formed phrase 1)

wfp1: (x) (x’) ((s(x) = s(x’)) → (x = x’)

This says “for all x and all x’, the successor of x equals the successor of x’ if x equals x’”. In other words if the next natural number of one number equals the next natural number of another number, then the two numbers must be the same number. Simple statement. Let’s Godel number wfp1. And let’s introduce the notation to denote the ‘Godelling’ of a phrase, GN(phrase). In this case GN(wfp1) equals,

73873987767384673988234398

Simple huh? Note how this is a two way affair. I can easily take a number and figure out what the well formed phrase is as well. The only thing left is to define a way to denote the end of a phrase and the beginning of a new phrase. Because if we GN() a lot of phrases then we get a long string of numbers with no idea where one phrase ends and the next begins. To do this we add a 0 in between the phrases. So performing a Godel numbering on 2 phrases would result in a number like this; “…439807387…”. We use 0 because then the long number representing many phrases is itself a number we can perform arithmetic on.

Now let’s discuss how we can get self referencing out of this. Because Godel was careful to number his symbols in a specific way, he ultimately ends up with numbers that allow him to do something very interesting. Let’s say we have a phrase (wfp1) that logically leads to another (wfp2) by way of a proof. In other words, by using the formal system rules we can get wfp2 from wfp1. With Godel’s special numbering scheme he could also describe that process using the Godel numbers for those phrases and performing a purely arithmetical maneuver on them.

For example, suppose GN(wfp1) = 317 and GN(wfp2) = 195589. We could show that getting to wfp2 from wfp1 can be done by using the formal system rules or we can get there by multiplying GN(wfp1) by 617. The two maneuvers are identical in nature. This is not exactly what Godel did but the concept is correct.

What Godel was able to show was that those sequences of well formed phrases that constituted valid proofs, had numbers that all bore a similar arithmetical property. For example they all could be even or they all could be prime numbers. In fact the feature was much more complicated than that. It follows that all valid theorems (the last well formed phrase in the proof) had an arithmetical property. We won’t prove that but it’s not hard to see that it likely is true. Hopefully you can see what he’s doing here. Theorems here have some ability to speak to their own provability. Speak about themselves if you will.

So Godel has basically (I’ll use the author’s phrase) conjured up an arithmetical property of numbers, let’s call it Pr(n), that denotes whether the well formed phrase, when converted into a Godel number, is a provable or not. Notice that Pr(x) here is very similar to the F symbol we defined above. When we wrote (x)F(x) to mean that all variables x have the property F, we can also write (x)Pr(x) to mean all variables x have the property that they are provable.

I also want you to remember these statements we are making aren’t necessarily true or false as they stand. For example s(x)=s(0) which says the successor of x equals the successor or 0. Clearly this is neither true or false. If x = 1 then it is true. For all other x’s it is false. It’s just a propositional statement

Now let’s lastly focus on Pr(x). Remember for all well formed phrases, p, we have some Godel number GN(p), a natural number. Theorems are a special subset of all well formed phrases; namely the provable propositions within the formal system. And given any natural number, n, it may or may not be true that it corresponds to a provable theorem in the formal system. For any theorem p of the system, we know it has a Godel number GN(p). And sticking this number into the Pr(x) attribute we know that Pr(GN(p)) = TRUE. Just know that Pr(x) is complicated so we won’t talk about it, but Godel defined it. But Pr(x) is a bit odd isn’t it? It kind of has two meanings. On one level it is an arithmetical property. Let’s say it means a number being even (in our fake case). Easy to check if a number is even. Pr(8) = TRUE. But it also has this other meaning. Namely, converting 8 into a well formed phrase by definition will give us a provable theorem within the formal system. Okay I’m done with this point.

Okay one last thing before we stop. Godel implicitly invokes the Diagonal Lemma. He actually proves a specific case of it for his theorem but in our case we’ll use the Lemma. When we put a number ‘into’ F(x) we create a new well formed phrase. If we turn that into a Godel number then that number will equal the number we put into F(x). Specifically,

n = GN(F(n))

Once again – The Diagonal Lemma says that for all properties F(x), there exists a number in well formed phrase lexicon such that the Godel number of that property equals the natural number version of what you put into F(x). However! Note that the n on the left side is a natural number. The number on the right side is a well formed phrase. When we don’t specify what n is and use a variable we just use ‘x’. But when we specify what x is we need to do it within the rules of the formal system. How do you write a number as a phrase? Well 3 would look like this

s(s(s(0)))

The successor of the successor of the successor of the number 0. Okay? This is important because we are switching between purely arithmetical propositions and actual natural numbers and arithmetical operations. Just keep that in mind.

Okay let’s stop. Before we go over too much. We are actually very close and we will seal up the deal in the next post.