Godel Numbering

Godel "numbering": The goal is to provide a unique and decodable number for every possible well formed sentence (according to a bunch of rules of syntax) in a formal language (like algebra or logic). (I have no idea how much of this you already know!)

The reason for the goal is something like it would be nice to be able to treat any well formed sentence (wff or well formed formula - academics like to call these "woofs" :) as part of any other wff (so long as the rules syntax rules for creating wffs are followed). Think of a snake eating its own tail. Since one of the allowed things in an algebra wff is a number, if every wff has a number standing for it, the wff can be represented in other wffs by its number.

Godel wanted to do some proofs which required this.

So we need, and Godel needed, a unique number for each wff in a language. With me so far? Probably or you wouldn't have asked about the numbering?!

What Godel did that solved this problem was to assign to every character allowable in the wffs (according to the syntax rules) a number, a huge number built up from multiplying together pre-chosen prime numbers.

Now prime numbers are special in the following way: Every number in existence can be factored down to the set of primes which when multiplied together create that number. A prime number cannot be factored further down than itself and 1. (That's its definition in fact!)

So if every character in a wff (like the equal sign, every digit, the plus sign, etc.) has a prime number assigned to it ... hold on there is a step missing...

Also assign each position in the wff a prime number. The first position from the left can be a 2, the second can be a 3, the third can be a 5, the forth a 7, etc. (Note these are the primes from lowest upwards.)

Now let's say the first character was a left bracket. And let's say that left brackets wherever they occur are assigned the prime number 11 (I'm guessing!) So what you do is take the position prime number (in this case 2 since it is the first character in the wff) and place it to the power of the character prime number, like this:


See? That will be a unique prime number in and of itself. Now do this for each character in the wff, and then multiply them all together, like (for totally made up example):

 character number:  11    7     2     17     29     5      13   etc   
  position number: 2  x  3  x  5  x  7  x  11  x  13  x  17  x  etc

The final number (huge) is the product of all of these, and will therefore be factorable back into these components uniquely, and so it can stand as a code (or Godel number) for the wff. Do you see why?

(I hope I haven't done your homework assignment for you!) Please only learn about these concepts from me. Don't quote them at all! I might have this slightly wrong!

Note that Godel didn't prove the impossiblity of truth. He showed that any system powerful enough to do algebra in was also powerful enough to derive a wff that says of itself that it is false. So if the wff is actually false, then no such wff should be derivable. But since it was derived, it must be true, in which case it would be false, etc.

Did you ever see the old Star Trek episode where Harry Mudd was trying to mess up an android's head by telling him the liar's paradox. "Everything I say to you is false." Godel derived this sort of sentence from algebra using the Godel numbering!


Anthony's thoughts

Carolyn's Diary
[index]|[mail me]|[finale]