Gödel Numbering

I was first introduced to Gödel’s incompleteness theorems when I was doing my master’s degree when one of my apartment mates suggested that I should read Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter. When I read the book, I was immediately hooked. However, to be frank, I did not understand that Hofstadter was actually addressing the issue of consciousness in the book. It was only later, when I was doing my degree in theology that I re-read the book and things began to fall into place.

While the ideas of the book have swirled around in the back burner of my mind ever since, it was only recently, when someone asked for a simple explanation of the theorems, that my attention once more went to Gödel’s groundbreaking accomplishments.

Prior to the publication of Gödel’s theorems, mathematicians like David Hilbert were bent on developing a self-contained, consistent, and complete body of mathematics. His goal was to produce a body of mathematics in which every statement could be proven true or false using a finite number of steps such that no statement could be proven both true and false. One of the foundational works that lay behind Hilbert’s program was the Principia Mathematica (PM) by Alfred North Whitehead and Bertrand Russell. This magnum opus had lofty goals, stated as follows:

1. “to analyse to the greatest possible extent the ideas and methods of mathematical logic and to minimise the number of primitive notions, axioms, and inference rules.” This meant that they wanted as few axioms and rules as possible that would lead to as many results as possible.
2. “to precisely express mathematical propositions in symbolic logic using the most convenient notation that precise expression allows.” This meant that they wanted a concise and coherent set of symbols that would be able to express all possible logic statements without any ambiguity or confusion.
3. “to solve the paradoxes that plagued logic and set theory at the turn of the 20th century, like Russell’s paradox.” This meant that they wanted a system in which paradoxes would be impossible to express. In particular, Russell’s paradox is stated as follows: Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition entails that it is a member of itself; yet, if it is a member of itself, then it is not a member of itself, since it is the set of all sets that are not members of themselves. The resulting contradiction is Russell’s paradox. There is a more common statement of this. On an island, there is a barber who cuts the hair of every person who does not cut their own hair. Does the barber cut his/her hair or not? If he/she cuts his/her hair, then by definition, he/she should not be cutting his/her hair.

In PM, Whitehead and Russell intended to formulate a system of logic in which formulations such as Russell’s paradox would be impossible.

However, just a few years after PM was published, Gödel came along and demonstrated that such paradoxes are possible within the logical system used by PM. Not only that, but Gödel demonstrated that any sufficiently powerful logical system will contain truthful statements that cannot be proven true within the system as well as statements whose truth values cannot be determined from within the system. This shattered Hilbert’s dream of developing a mathematical system that was complete and consistent.

Gödel’s genius was developing a system by which he could correlate statements about a mathematical system to statements within the mathematical system. The centerpiece of this is the process of Gödel numbering, which eventually allows a mathematical system to talk about itself. Since the process of Gödel numbering is not something us commoners would normally think of, I will address the set up of the numbering system in this post and leave the explanation of how Gödel used this system to frame self-referential statements for the next post.

Gödel begins by assigning a Gödel number to each of the symbols used to make mathematical statements.

Each of the symbols x, y, z, etc. are assigned prime numbers greater than 12. Hence, we get the Gödel number of x is 13, of y is 17, and of z is 19. You will have noticed that the only numeral in the table is the one for zero. Under the zero is what indicates ‘the successor of’, which might be obscure to most readers. This simply tells us what the next number is. Hence, s0 is the successor of 0 and, therefore, represents 1; ss0 is the successor of the successor of 0 and, therefore, represents 2; and sss0 is the successor of the successor of the successor of 0 and, therefore, represents 3.

Now, let us consider the statement 1 = 1. First, this would have translated to s0 = s0, a statement that contains five symbols. From the table they correspond to 7, 6, 5, 7, 6. Gödel needs to be able to map this statement, now coded as a sequence of Gödel numbers to a unique number. So, he takes the first five prime numbers 2, 3, 5, 7, and 11. Then he evaluates 2⁷×3⁶×5⁵×7⁷×11⁶ = 425,431,762,237,666,800,000. Yes, the system of Gödel numbering yields extremely large numbers. And we are nowhere close to being done!

Now, the prime factorization of any natural number is unique except for the order of the factors. If we insist on writing the factors in the order of the primes, then the factorization is unique. This means that the number 425,431,762,237,666,800,000, which has the prime factorization of 2⁷×3⁶×5⁵×7⁷×11⁶, necessarily represents the statement 1 = 1.

If we continue in this way, every mathematical statement can first be reduced to a sequence of Gödel numbers and then to a single (large) number whose ordered prime factorization is the sequence of Gödel numbers. This creates a map between every mathematical statement and a unique number.

Suppose, for example, we are given the coded number 13, 891, 649, 379, 189, 120. We can factorize this number to obtain 13, 891, 649, 379, 189, 120 = 2⁷×3⁶×5¹×7⁵×11⁶. Hence, 13, 891, 649, 379, 189, 120 is the code for the sequence of Gödel numbers (7, 6, 1, 5, 6). From the table above we can see that this sequence of Gödel numbers represents the mathematical statement 1 ~= 0.

Now, since every number has a unique ordered prime factorization, it follows that every number can be ‘decoded’ to represent a unique sequence of Gödel numbers, which in turn can be further ‘decoded’ to represent a unique mathematical string.

With this method Gödel successfully created a one to one map between mathematical strings and numbers. Once this has been done we encounter an interesting situation. Every number can now be considered as the number itself or as Gödel coded mathematical string. Hence, it now becomes possible to make the mathematical strings contain self referential aspects. That is, the numbers, being mathematical strings, can be made to refer to themselves. Of course, since the coded Gödel numbers themselves are large, the self-referentially coded Gödel numbers will be even larger. Yet, even if we cannot actually calculate the values of the self-referentially coded Gödel numbers, we know that each mathematical string has a unique coded Gödel number. This is the power of the numbering system that Gödel introduced. We will consider that in the next post.