Gödel's Incompleteness Theorems and the Limits of Mathematical Logic

Gödel's Incompleteness Theorems and the Limits of Mathematical Logic

By Raheel Sultan, L6N

Towards the end of the 19th century, mathematicians began to uncover inconsistencies within the foundations of logic.

Set theory was in its infancy at the time, and a complete definition of a set had not been universally agreed upon. One attempt came from Gottlob Frege, who proposed in his book, Die Grundlagen der Arithmetik, a list of rules outlining the behaviour of sets. These rules were constructive, in that the only set explicitly stated to exist was the empty set, and the rest of the rules described how sets were constructed from other ones. His fifth rule asserted that a set exists containing all objects satisfying a given property. For instance, such a property may be that a set contains the number 1; Frege’s fifth rule then implies that there exists a set of all sets which contain the number 1. This seemingly innocuous rule was the source of a paradox, as uncovered by Bertrand Russell. The paradox is as follows:

“Let R be the set of sets which do not contain themselves. Does R contain itself?”

If R contains itself, then, by definition, it is a member of the set of sets which do not contain themselves. Hence, R does not contain itself. If R does not contain itself, then it must be a member of the set of sets which do not contain themselves. This set is itself R, so R contains itself. In either case, we obtain a contradiction. Frege’s system of logic was thus invalidated by a single question. This raised the worrisome prospect that other fields rested on logically shaky grounds: might number theory, or calculus, be shown wrong at some later date? Could all mathematical research to date be rendered useless?

David Hilbert challenged the world to answer this question at his address to the International Congress of Mathematicians in 1900. He sought a list of axioms which could be used to encode mathematics, as well as a proof of their consistency (an inconsistent system is one which can produce a contradiction). In Hilbert’s philosophy of formalism, all of mathematics could be reduced to manipulating symbols on a page - only in this way could we be free of doubt over deductive errors made by the human mind. Crucial to this way of thinking was the necessity that proofs be written in finitely many steps, and utilise finitely many axioms. Georg Cantor had already exposed the counterintuitive nature of infinity through his work on infinite sets; to Hilbert, the assumption that infinities existed required its own justification, and hence could not be used in a direct proof of consistency. Perhaps naïvely, he staunchly believed that a consistency proof was inevitable. In response to a common attitude towards the natural sciences at the time, “ignoramus et ignorabimus” (We do not know and we will not know), Hilbert concluded his 1900 address with the words which would ultimately be inscribed on his gravestone: “Wir müssen wissen - wir werden wissen.” (We must know - we will know.)

Several steps would be taken towards a resolution of Hilbert’s programme over the next few decades, most notably in Whitehead and Russell’s Principia Mathematica (not to be confused with Isaac Newton’s book of a similar name). Ultimately the goal was shown to be impossible by an Austrian logician by the name of Kurt Gödel.

Before discussing his eponymous Incompleteness Theorems, we must describe first-order and second-order logic. In line with Hilbert’s ideals of purely symbolic reasoning, both systems consist of a set of symbols (the syntax), and a set of rules for manipulating them. These symbols represent logical implication (\(\rightarrow\)), logical ‘and’ (\( \land \)), ‘or’ (\(\lor\)), ‘not’ (\(\lnot\)) and ‘equals’ (\(=\)). There are also the symbols ‘for all’ (\(\forall\)) and ‘there exists’ (\(\exists\)), collectively called quantifiers, as well as symbols for functions, constants and variables.

Suppose we wanted to represent the statement, “All integers are either even or odd,” in one of these systems. One way to rephrase this is to say, “For all integers \(x\), there exists an integer \(n\) such that either \(x=2n\) or \(x=2n+1\).” We would write this as follows:

$$\forall x\, \exists n\,(x=2n\lor x=2n+1)$$

Notice that there is no symbol for either \(x\) or \(n\) being an integer. In first-order logic, the quantifiers are taken to range over all possible constants, and we choose to interpret these constants as integers. In second-order logic, the quantifiers can range over predicates in addition to constants. A predicate is a statement which can be either true or false, depending on the input value. One predicate is “\(n\) is a prime number.” If we denote this predicate as \(P(n)\), then we have that \(P(3)\) is true, but \(P(4)\) is false.

It is important to clarify the difference between a logical system, such as first-order logic, and a theory. By itself, a logical system has no functions, no constants and no predicates. It can only prove general statements such as: “If \(P \rightarrow Q\), then \(\lnot Q\rightarrow \lnot P\).” Logical systems have axioms, but these axioms govern the general process of logical deduction. In contrast, a theory characterises a specific mathematical object, such as the integers. The function symbols represent functions of the integers, such as addition, and the axioms relate specifically to integers and their operations. We therefore have notions of first-order theories and second-order theories - theories constructed on top of first-order logic and second-order logic respectively.

Given a consistent theory, it is possible to find a mathematical object that satisfies the axioms of the theory; such a mathematical object is called a model. Theories can have multiple models if the axioms do not specify enough properties. An example of this would be a theory which postulates the existence of the constants 0 and 1, and the addition and multiplication functions with the usual properties. This theory could have the integers as a model, as well as the real numbers. Any proof inside a theory must be true in all its models. Therefore, any statement which is true in some models, but not in others, cannot be proven either true or false in the theory. If every statement can be proven either true or false, the theory is called complete. It turns out that in first-order logic, if a statement is true in every model of a theory, then that statement can be proven using the axioms of the theory. This result is known as Gödel’s Completeness Theorem. Note that the word ‘complete’ has been used with two meanings: a theory can be complete, and first-order logic is complete. Gödel’s Completeness Theorem is a large part of the reason why most mathematics is done using first-order logic - a semantic (non-symbolic) proof entails the existence of a syntactic proof, relieving the need to write down both.

In response to Hilbert’s programme, mathematicians tried to find a complete theory of the arithmetic of the natural numbers using finitely many axioms. It was thought that this would be the first step towards formalising other areas, such as calculus and topology. Gödel’s First Incompleteness Theorem states that this is not possible, and a sketch of its proof is given in the following paragraphs. As an overview, we first show that every statement can be given a unique number known as a Gödel number. Then we argue that we can express provability in terms of arithmetic by using these Gödel numbers. Finally, we construct a statement which shows itself to be unprovable.

Suppose that we have a theory of arithmetic of the natural numbers, and that it has finitely many symbols. We form infinitely many variables by using one symbol, \(x\), and adding an asterisk to create more variables of the form \(x^*\), \(x^{**}\), and so on. Our function symbols will be addition, multiplication, and succession, denoted by \(S(x)\). We interpret \(S(x)\) as \(x+1\). It is possible to assign a two-digit string to each of these symbols, from 10 to 24. The Gödel number of an expression, \(G(A)\), is the number obtained by concatenating these strings in the order they appear in the expression \(A\). For example, if we assign 10 to the constant \(0\), 11 to the \(+\) symbol, 12 to the \(=\) symbol, 13 to the \((\) symbol and 14 to the \()\) symbol, the statement \((0+0)=0\) would receive a Gödel number of 13101110141210. We will also want to form Gödel numbers of proofs; proofs are lists of statements where each statement follows from ones before it. To form the Gödel number of a list of statements in a proof, we concatenate the Gödel numbers of all the individual statements, separated by the unused string 25.

Every axiom of the theory can be represented by a predicate on the Gödel numbers of lists of statements. For example, if we have an axiom which, given the statements \(A\) and \(A \rightarrow B\), lets us conclude \(B\), we can create a predicate \(P(x,x^*)\) which is true whenever \(x=G(A,A\rightarrow B)\), and \(x^*=G(A, A\rightarrow B, B)\). A statement is provable exactly when it can be reached by a series of axiomatic deductions, so these predicates encode whether a statement is provable. The key point of this is that the provability of an arbitrary statement can be expressed purely in terms of arithmetic. Since the theory operates on arithmetic, we can use the theory to reason about itself. It is this self-referential property which enables the proof of the First Incompleteness Theorem.

To finish off the argument, given a predicate \(P\), let \(Q(G(P))\) be the predicate expressing that \(P(G(P))\) has no proof. Consider \(Q(G(Q))\). This statement asserts that the statement \(Q(G(Q))\) does not have a proof - it asserts that it is unprovable. If it is true, there must be unprovable statements within our theory, and so our theory is incomplete. If it is false, then it is not unprovable, and so it has a proof. However, if a false statement has a proof, the theory is inconsistent. Therefore, no finitistic theory of arithmetic can be both complete and consistent.

There are theories of arithmetic which are incomplete but can still produce much of number theory. Peano arithmetic, invented by Giuseppe Peano, is a first-order theory, but it contains statements which are unprovable. By Gödel’s Completeness Theorem, it has several models. A modified version of this, second-order Peano arithmetic, only has one model. However, since the Completeness Theorem does not apply to second-order logic, there are statements which are true about its model which second-order Peano arithmetic is incapable of proving.

This was a serious, though not fatal, blow to Hilbert’s programme. By itself, Gödel’s First Incompleteness Theorem does not preclude a proof of the consistency of the axioms of arithmetic; it merely shows that if the axioms are consistent, they must be incomplete. It was the second of the Incompleteness Theorems which suggested that no consistency proof exists. This theorem states that no theory powerful enough to encode arithmetic is capable of proving its own consistency. No proof outline will be given, but the method is similar to that of the first theorem.

A natural question is why we would be concerned with a system proving its own consistency - an inconsistent theory can prove anything (the principle of explosion), so, given that it can express arithmetic, it can certainly prove its own consistency. To answer this, suppose we had a finitistic proof of Peano arithmetic. As this proof does not make any appeal to infinity, it should be possible to translate the proof into Peano arithmetic. However, Gödel’s Second Incompleteness Theorem rules this out, meaning no such proof can exist. Any system capable of proving that Peano arithmetic is consistent must assume at least as much as Peano arithmetic does, thus casting doubt upon the consistency of the system used to prove it. This system would itself require another system to prove its consistency, and so on.

It would therefore seem that Gödel’s Second Incompleteness Theorem destroyed Hilbert’s vision of a finitistic proof of the consistency of arithmetic. This statement is not entirely true, as it comes with two caveats.

Firstly, the above argument rests on the assumption that any finitistic proof can be translated into Peano arithmetic. Although the method used in the Incompleteness Theorems’ proofs demonstrate that arithmetic is sufficiently powerful to express much of logic, there is a certain amount of reasoning on the meta-mathematical level (reasoning about theories, rather than inside of them) which it is incapable of encoding. We therefore cannot rule out the possibility that a finitistic consistency proof exists which is not definable in terms of arithmetic.

Secondly, it is unclear what exactly is meant by ‘finitistic’. David Hilbert never gave a clear definition; his speech in 1900 was primarily intended as a direction in which mathematics should progress over the course of the next century, rather than a series of explicit conjectures. One ambiguous proof came from Gerhard Gentzen, who in 1936 published a consistency proof utilising induction over infinite ordered sets (ordinals). The infinite ordinals which he used can be phrased in terms of finite objects, but there is no consensus on whether this constitutes a finitistic method.

At least for now, we must contend with the unknowability of the consistency of mathematics. There can be no canonical set of axioms from which we can deduce all truths. This does, however, allow for several, equally valid axiom systems.

The standard axioms in mathematical use are Zermelo-Fraenkel set theory with the axiom of choice, abbreviated to ZFC. Like Frege’s system before it, ZFC governs which sets exist and can be constructed. As a first-order theory, ZFC is incomplete - it contains statements which can neither be proven true nor false. One such statement is the continuum hypothesis. It is widely known that the size of the set of real numbers is a ‘bigger infinity’ than the size of the set of natural numbers, in the sense that it is impossible to pair up the elements of each without having real numbers left over. The continuum hypothesis claims that there is no infinity smaller than that of the reals, but larger than that of the natural numbers. Since there is no proof or disproof of the continuum hypothesis, we are free to create an axiom stating that it is true, or that it is false. Doing so yields two different set theories, both of which are true in just as valid a sense as ZFC is.

There may be no solution to Hilbert’s programme. Perhaps he was foolish to assume that one single set of axioms could conquer all of mathematics. Yet contemplating the idea has revealed the existence of several parallel but independent axiomatic systems - a multiverse of mathematicses, each one of which as real as any other.