Gödel Numbering And Incompleteness

Gödel Numbering And Incompleteness

Author: Ken Wais

Keywords: Incompleteness Theorem (ITH), Gödel, sentential variables, numerical variables, predicate variables, Truth Functional Logic (TFL)

Kurt Gödel in his 1931 paper entitled: On formally undecidable propositions of Principia Mathematica and related systems spawn the Incompleteness Theorem of Mathematical Logic and created a wonderful way to test the validity of any logical construction called Gödel Numbering.  I would like to illustrate how this system of mapping logical constructions to integer numbers is made.

I believe that ITH is only valid in the TFL system of Mathematical Logic, and is not applicable to alternative systems like Modal Logic. I won’t discuss these alternative systems in this essay, but I must point out that the symbology of Modal Logic goes beyond that of TFL logic and this makes it incompatible with Gödel numbering.  Nevertheless, students of logic should understand the linchpin of Gödel’s analysis.  With that said let’s get started.

Introduction

Gödel believed he discovered in his ITH construction that if we create a system of logical deduction it would be either incomplete or inconsistent.  But there was a problem with showing this by using the methods of mathematical logic.  If we use the system to talk about the system you would be uncertain when you were talking about the system or just inside the system itself.  Then Gödel hit on the idea of grafting all the symbology of TFL onto a new system of integers.  In this way, we could manipulate the numbers themselves once generated and see if they preserved the relations in the TFL system.  If they didn’t and contradictions were found we could conclude the TFL system itself, was flawed.  Now let’s see how this system of numbering TFL constructions works.

Gödel Numbering

Let’s take a simple logical implication in TFL. First, we give the simple English statement, and then we will state it in symbolic terms:

There is a number x such that x =x.

To state this symbolically we must first introduce the symbols of logic and specifically quantificational logic for the above example.  Each symbol has a Gödel number.  There are 10 constant symbols used in Gödel numbering. Below is a transformation table for these symbols.

 Symbol Gödel Number Value , 10 Punctuation ) 9 Punctuation ( 8 Punctuation S 7 The successor of a number 0 6 Zero = 5 Equality Ǝ 4 Existential quantifier meaning a symbol that states there exists V 2 Or ⊃ 3 If-Then ~ 1 Not

Let’s restate the implication above along with its symbolic equivalent.

There is a number x such that x =x

(Ǝ)x (x=x)

We are almost ready to write the above statement’s Gödel number but first we have to state some of the rules Gödel specified for transforming numerical, sentential and predicate variables.  The transformation table above lists only the operational symbols. The statement contains both predicate and sentential variables.  So, what are they?  A sentential variable is a symbol that can represent a sentence like: A man is a man.  If we take A man is a man = t, then t is a sentential variable. Symbolically, it would be written A=A.  A numerical variable is any integer, so x could be 2, 4, or 2037, etc.  A predicate variable assigns a property to a symbol like prime, composite, less than, greater than.  Each of these three variables has a rule to transform them into Gödel numbers.

1.     Numerical variables like a, b, c, d etc must be a prime number greater than 10.

2.     Sentential variables like A v B, or P ⊃ Q, ~P, must be the square of a prime number greater than 10.

3.     Predicate variables like T is prime, D is less than, must the cube of prime numbers greater than 10.

When we generate our Gödel number, must be an odd prime number ordered in succession.  It doesn’t have to be 10 prime numbers. But whatever the number, they must be odd and prime.

Now, we can put it all together and one-by-one list the Gödel number for every symbol in the statement: (Ǝ)x (x=x).

( =8

Ǝ =4

)=9

x = 11 (since it’s a numeric)

( =8

x = 11

= is 5

x = 11

) = 9

Listing the string from left to right we have 8 4 9 11 8 11 5 11 9 as the Gödel number, but this isn’t the end.  You see, Gödel wanted to completely arithmetized the construction of logical statements and thereby provide a way to convert from the symbology of logic to a calculus of arithmetic.  In so doing logical propositions (statements) would be invertible with Gödel numbers.  One system could be turned into another and vice versa.  The reasons for doing this will become clear after we complete this example. The string above could be converted into one integer with just a one more rule.  The first 9 prime numbers in succession could be raised to the power of their Gödel numbers and multiplied together.  Notice the emphasis on succession and this is important.  Let’s do this with all 9 Gödel numbers we generated.  Here they are below:

28 34 59 711 118 1311 175 1911 239

Next to get one integer we multiply the string above.  The final number is (thanks to my computer’s calculator of course) 9.165……e + 72, that is 9 x 1072 approximately.  An enormous number no doubt.  What is important about this calculation is any part of it can be retrieved from the final number by dividing out that portion.  For instance the portion that codes (Ǝ)x and is a product itself, could be extracted by dividing out everything starting with 118 going forward to 239.  This means that first 4 symbols are derivable from the entire Gödel number.  This form of number encoding is powerful and has been used in recursive number theory.  Not every number integer is a Gödel number.  As an example let’s take at random 1048576 (actually it’s not random because I chose it to illustrate the point). 1048576 = 220 = 210 x 210.  The Gödel number for the exponent 10 transforms to , thus 210 x 210 is , , In this case 1048576 is not a Gödel number because it not the result of successive prime numbers, and it can be seen in the symbolic translation that it is making no interpretable reference.[i]

With the calculus of Gödel numbers explained we can ask the following question:

What does the mapping of Gödel numbers to the propositions of logic mean?

At the beginning we noted that theorizing in a system of logic with the symbols of that logic could lead to confusion on what was being examined.  So, we found a way via Gödel numbering, to avoid this problem. What was created is called a Meta-Mathematics.  We are now analyzing if Gödel numbers once created can be related to show that they are a consistent and complete description of the logical system they describe.  We’ve already seen that some Gödel numbers don’t trace back to logical statements.  Here is where Gödel began to see that some of his numbers might show a crack in the dam, speaking metaphorically.

First, we must understand what is meant by Meta-Mathematics. This hyphenated word simply means a way of analyzing mathematical descriptions from outside the system of mathematics.  For example take the standard equation for the Taylor series expansion in integral calculus shown below:

e^x = 1 + x/1! + x^2/2! + x^3/3! + ..... - ∞ < x < + ∞

We could plug in values for x and churn out the results for the transcendental number e for any given x. In some cases the function would converge to a number in other cases like using complex numbers for the x power that e is raised to, it would not. If we describe what this function is and why the right-hand side of the equation generates e^x  we are depicting the function itself and not just using it to calculate values of its input x.  Furthermore, if we described the transcendental e and how raising it to powers of x can be approximated as convergent or divergent in the Taylor Series we are again not using the function but describing what the function is. We are not just doing mathematics here, but explaining the mathematics.  We are one step beyond mathematics or to use the Greek word meta which means beyond. So, a meta-mathematical study is analyzing something contained within it.  This is what Gödel was intending to do, to Mathematical Logic when he created his numbering system.

Now we can show how Gödel showed inconsistency and incompleteness in his theorem.  With the background given it isn't very hard to see how he arrived at this conclusion.  Suppose we have Gödel number Z that when decoded is the following proposition:

There exists a Gödel number Z.

And suppose we have a Gödel number Y that when decoded is the following proposition:

Gödel number Z is not a Gödel number.

The statements have valid Gödel numbers Z and Y, but one is a contradiction of the other and vice versa.  But through the calculus of converting the statements to symbolic logic and then to Gödel numbers we find they are both true Gödel numbers.  If this is case then the arithmetic of Gödel numbering has led us to an irresolvable contradiction.  It has shown that while the calculus works, i.e. it generates Gödel numbers, they can contradict themselves and the system of generating these numbers must be somehow unfinished or incomplete.  For a system of Logic such as an arithmetical system to be complete, every number it generates must be contained within the system.  But clearly Z above can’t be in the system and out of at the same time, thus the system of Gödel numbering is incomplete.  With this comment we end our survey of Gödel numbering.

References

1.     Gödel, Kurt. "On formally undecidable propositions of Principia Mathematica and related systems." IBM Research. IBM, 27 Nov. 2000. Web. 12 Sep. 2012. 1931 Gödel Paper

2.     Ernest, Nagel & Newman, James. Gödel's Proof. : New York University Press, 1958. Print.

3.      Sakharov, Alex and Weisstein, Eric W. "Gödel Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GoedelNumber.html

[i] Throughout this paper I use the terms statement and proposition interchangeably.