Gödel Numbering: Encoding Logic into Numbers

Gödel Numbering And Incompleteness

Author: Robleh 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,  he created 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 ITH doesn't apply 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.  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 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 means 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, or greater than.  Each of these three variables has a rule to transform it into a Gödel number.

 

1.     Numerical variables like a, b, c, d, etc. must be prime numbers 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, it 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 arithmetize 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 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:

2⁸ 3⁴ 5⁹ 7¹¹ 11⁸ 13¹¹ 17⁵ 19¹¹ 23⁹

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 10⁷² approximately.  An enormous number, no doubt.  What is important about this calculation is that 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 11⁸ going forward to 23⁹.  This means that the 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 integer is a Gödel number.  As an example, let’s take at random 1048576  it’s not random because I chose it to illustrate the point). 1048576 = 2²⁰ = 2¹⁰ x 2¹⁰.  The Gödel number for the exponent 10 transforms to, thus 2¹⁰ x 2¹⁰ is,  In this case, 1048576 is not a Gödel number because it is not the result of successive prime numbers, and it can be seen in the symbolic translation that it is making no interpretable reference.[i] 

How Gödel Numbering In Meta-Mathematics Leads to Contradiction.

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 about what was being examined.  So, we found a way via Gödel numbering to avoid this problem. What was created is called Meta-Mathematics.  We are now analyzing whether 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.  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 intended to do, in Mathematical Logic, when he created his numbering system.

Now we can show how Gödel illustrated 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.  Through the calculus of converting the statements to symbolic logic and then to Gödel numbers, we find that they are both true Gödel numbers.  If this is the case, then the arithmetic of Gödel numbering has led us to an irresolvable contradiction.  It has been 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 Z above can’t be in the system and out of the system 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. https://mathworld.wolfram.com/GoedelNumber.html