Going Gödel-ian - I

Gödel’s Incompleteness Theorem is one of the most surprising results to come out of twentieth-century mathematical logic. In its most basic form, the theorem states that there exist mathematical statements that are true, but cannot be proven by the mathematical framework the statements are a part of. In this section of my essay, I intend to describe its history, since the context of mathematical formalism is important to understand its significance, and the basics of its derivation and meaning.

Gödel’s Incompleteness Theorem first appeared in 1931, at a time when the dominant drive in mathematics was the consolidation of mathematics to the most self-evident axioms and immediately apparent axioms; the idea was to avoid even the possibility of internally inconsistent systems and to prevent mathematics from being infected with shortcuts peculiar to human thought. One of the most famous attempts to create a strictly formal mathematical system—that is, a system with clearly defined axioms (statements accepted as true without proof) and clearly defined rules to go from axioms to theorems, that would then lead to a complete expression of all conceivable mathematics—was that of Bertrand Russell and Alfred Whitehead, in their Principia Mathematica. Their system was intended not just to express all mathematics, but also to eliminate self-reference, which they believed were the cause of paradoxes. Also relevant at the time was the attempt to solve Hilbert’s Second Problem: to show that arithmetic was consistent (that is, to show that it was impossible to prove both a statement and its opposite within a mathematical framework that expressed arithmetic). In this context, Gödel was looking into strictly formal systems and the idea of proving consistency and its close relative, completeness (a complete system is one in which all true statements can be proven from its axioms and rules of inference.), and it was in this search that he proved that a system cannot be both complete and consistent.

Gödel’s Incompleteness Theorem demonstrates that in any system with enough expressive power to express every truth about arithmetic (that is, its syntax is rich enough that statements as simple as “2 + 2 = 4” and as complex as “every even number greater than 4 is a sum of two prime numbers” can all be written using the same, unambiguous notation) can also express statements that, while indisputably true, can only be shown to be true through means of a logic external to the system itself. The specific statement he identifies may help clarify what I mean: Gödel himself offers the statement G, which roughly means “G is not provable within this formal system, G0” If G is false, then it can be proved, and is therefore true, which is a logical impossibility; if G is true, then it cannot be proven, and therefore the system, G0 is incomplete.

This statement on its own is not particularly compelling for demonstrating that G0 in particular and any candidate for a formal system in general are necessarily incomplete. There are two refutations to the Theorem: One that the formal system can be expanded to include G, and therefore be incomplete, and one that denies that G is even expressible, and is therefore irrelevant.

The first refutation to G, therefore, is to simply add it to G0 as an axiom, so that in addition to the premises already included, G would be true. Therefore, G would be provable within the context of that system, since it was one of the axioms. However, this approach fails, since the formal system in this case is no longer G0, but G0 + G, which I’ll refer to as G1. Though G, the statement itself, is no longer true and unprovable, a sort of sequel to G, which I’ll call G´ (pronounced “gee prime”) is true and unprovable. If G can be read as “G is unprovable within G0,” then G´ can be read as “G´ is unprovable within G1.” G´ can be added as an axiom, but this only creates the new formal system G2, and Gödel’s Incompleteness Theorem still applies: No matter how cleverly one attempts to incorporate G into a system, it will always be vulnerable to the creation of a new true but unprovable statement.

Or will it? The second refutation denies that G is, in fact, expressible at all, and that it is not an arithmetic truth, and therefore G0, a candidate for a complete formal system, still is complete, because it does not contain true statements that cannot be proven. This objection requires a more serious appraisal, and it is in fact the entire basis of Gödel’s Incompleteness Theorem itself: the Theorem consists of demonstrating that provability can be expressed using purely arithmetical rules.

The basic premise upon which the Theorem is developed is that statements within a formal system (such as “there is no such number as the greatest prime number” or “231 – 1 is a prime”) can be interpreted, via an isomorphism, into statements about the formal system (such as “this system is incomplete” or “0 = 0 is an axiom of this system”). An isomorphism is a relationship between two groups of objects that links one entity from one group, uniquely and reversibly, to one entity in the other group. For example, one possible isomorphism is from the group of positive integers (1, 2, 3, 4, 5, and so on) to the group of prime numbers (2, 3, 5, 7, 11, 13, and so on). One isomorphism could be the number 1 corresponds to the first prime, the number 2 corresponds to the second prime, and so on, and vice versa—the first prime corresponds to the first number.

The particular isomorphism Gödel set up was one between three-digit numbers and the syntax of a formal system: = could be assigned 101, the + sign could be assigned 202, the number 1 could be assigned the number 052, and so on until all the syntax is accounted for. Statements such as “1 + 1 = 2” could then be written by converting the assigned numbers into a prime factorization—that is, it would equal 2^52 • 3^202 • 5^52 • 7^101 • 1^153. One of the theorems in arithmetic is that every number can be uniquely factored into a product of primes, so any number can be converted into symbols: the isomorphism works both ways.

Gödel then showed that this isomorphism of numbers to symbols could be taken one step further: The rules of inference that characterized the system could be expressed as numerical rules. Since the formal systems of the day used typographical rules of inference that were essentially rules for transforming one legal statement into another by manipulating symbols. Since the rules were purely mechanical and typographical in nature, the isomorphism Gödel set up allowed them to be expressed as numerical transformations. From there, Gödel demonstrated that the provability of a number’s coded arithmetical statement is an intrinsic trait, just like whether or not it is even, a perfect square, or a prime, and furthermore that it could be determined in a finite amount of time. Provability is therefore expressible within the syntax of a formal system, and the statement G is inevitable—a true but unprovable statement must appear.

Gödel’s Incompleteness Theorem shows that for any meaningfully complex and useful mathematical system, it must either contain contradictions, or include statements that are true, but not simply the result of the rules of inference provided at the outset of the system. To show this, Gödel showed that a seemingly paradoxical and definitely self-referential statement could be expressed in a mathematical system, and that it can only be shown to be true by thinking in terms outside the realm of the system itself.