by Scott Hoge
(Click here to download this essay)

Mathematics is distinguished from many other disciplines by its claims to certain knowledge. While life may roam on distant planets and matter may be made of strings, we know for a fact that seven circles touch, that π is greater than 3, and that there are infinitely many prime numbers. From the beginning, the ancient Greeks were impressed by the harmony of mathematical relations, and the philosopher Bertrand Russell described mathematics as possessing "not only truth, but supreme beauty -- a beauty cold and austere, like that of a sculpture... sublimely pure, and capable of a stern perfection as only the greatest art can show." Immanuel Kant spent decades attempting to bring all irrefutable knowledge, including mathematics, into a coherent system in which we could say, once and for all, what human beings knew and could know about the universe.

It begins with the elementary study of shapes and numerical relationships and progresses to the analysis of the most profoundly complex curves, symmetries, and fields. We've discovered algebra, geometry, trigonometry, calculus, differential equations, variational calculus, tensor calculus, topology, group theory, ring theory, field theory, Galois theory, and even more. There is literally no end to the advancement of mathematics -- we could go on forever.

Axioms, Inferences, and Mathematical Truth

So how is it that mathematicians discover these subjects? The answer turns out to be charmingly simple: mathematics deals with what we call propositions or statements. They are written in a logical language consisting of special symbols used to denote ordinary concepts, such as generalizations about entire groups of entities and statements of the existence of objects with certain properties:


. . . . . . .

  'For all x, it is true that'


. . . . . . .

  'There exists an x such that'


. . . . . . .

  'There exists a unique x such that'


. . . . . . .

  'Property P applies to x'

. . . . . . .


. . . . . . .



. . . . . . .


. . . . . . .



. . . . . . .

  'It can be proven that'

Pr(a, b)

. . . . . . .

  'a is a proof of b'

This language allows even the most complicated statements to be written concisely to the occasional benefit of the reader's comprehension. An example of a symbolic proposition is:

x (x is prime → ∃y (y is prime x < y)). . . . . . ."For every prime, there is a larger prime"

In mathematics, we begin with a handful of propositions called axioms, whose truth we postulate as self-evident. Axioms are the 'starting point' in mathematics and serve as the foundation for all the mathematical knowledge that follows from them. This knowledge is obtained by purely logical inference in a clear and incontrovertible way. For example, the axioms of arithmetic (called the Peano axioms) are:

     A1. 0 is a number.
     A2. ∀x (x is a number → ∃!y (y is a number y is the successor of x)).
     A3. ~∃x (0 is the successor of x).
     A4. ∀xyz ((z is the successor of x z is the successor of y) → x = y).
     A5. (P(0) xy ((x, y are numbers P(x) y is the successor of x) → P(y))) → ∀x (x is a number → P(x)).

Stated in English, they would be:

     A1. 0 is a number.
     A2. Every number has a unique successor (2 is the successor of 1, and so on).
     A3. There is no number whose successor is 0.
     A4. No two numbers have the same successor.
     A5. Any property that applies to 0 and to the successor of any number that has the property, applies to all numbers.

The final axiom is called the Axiom of Induction. From these axioms and with the aid of rules of inference, we may derive what are called theorems, propositions whose truth depends on the truth of the axioms. Rules of inference are methods of straightforward logical deduction. In virtue of their form, they always lead to true statements, provided that the axioms or premises of the inference are themselves true. A few rules of inference are:

     From PQ and QR we may deduce PR.
     From PQ we may deduce ~Q → ~P.
     From P Q and ~P we may deduce Q.

There are many others not listed. It follows from A1 and A2 above by a rule of inference that 0 has a successor, which we call 1. By the same inference, 1 has a successor called 2, and by axiom A4, there is no number whose successor is both 1 and 2. We may proceed with these deductions until we have until we obtain deep and signficiant knowledge about the properties of numbers, and by this method alone, there is no limit to the number of facts we can prove. With the aid of more elaborate axiomatic systems, such as that of Zermelo-Fraenkel set theory, we may deduce all of the mathematics taught in schools today.

Gödel's Incompleteness Theorem and the Mystery of Undecidable Statements

The Peano axioms give us an intuitively plausible account of the natural numbers. We start with 0 (A1), the first number (A3), count our way through unique numbers (A2), and reach all of them individually (A5). As we shall see, however, even our current system of arithmetic may not give us the full picture of mathematical truth that we seek. In fact, I will soon demonstrate that there are statements that can neither be proven nor disproven, which means that certain questions about numbers have been left unanswered.

But how? What alternate descriptions are left possible? We start with 0 and count our way up: it should be that simple, right? As luck would have it, there are unsettled questions, as Kurt Gödel showed in 1931. The formal statement of Gödel's Incompleteness Theorem, in his original manuscript, is,

"For every ω-consistent recursive class κ of formulas, there are recursive class-signs r such that neither ν Gen r nor Neg(ν Gen r) belong to Flg (κ)."

An English-translated implication of this is,

"There are statements about numbers that are neither provable nor disprovable."

There are two properties of an axiomatic system that allow us to demonstrate this: ω-consistency ('omega-consistency') and recursive axiomatizability. Later, I will explain what they are, but I will first remark that such properties of the system are needed in order to formulate a statement similar to,

"This statement is not provable."

We call this a self-referential statement. If we observe it closely, we will notice that if it were false, it would be provable, and therefore true. But it can't be false and true at the same time, so it can't be false to begin with. Therefore, it must be true -- but as it states, not provable by ordinary methods of inference.

Other self-referential statements lead to paradoxes. Consider, "This statement is false." It appears at first sight that if the statement is true, it must be false, and if it is false, it must be true. Which is it? Does the property we know as 'truth' apply to it? A similar quandary arises when we consider, "This statement is true." To decide on the truth of the statement, we have to know whether it's true to begin with. One might even ask: what is truth? A host of answers have been offered to these paradoxes and dilemmas, but no single one of them has been agreed upon.

In fact, "This statement is not provable" isn't exactly the statement of Gödel's Incompleteness Theorem! It is, however, frequently given as a metaphorical simplification. Due to paradoxes very similar to those mentioned, actual self-reference has been abolished from modern mathematics. Even so, a phenomenon I call endless reference to infinity still appears in mathematics. It is through this idea that Gödel's undecidable statement gains its uniquely elusive character.

How Endless Propositional Reference Leads to Unanswered Questions about Numbers

As we noted, true self-reference is not allowed in mathematics. Propositions such as "This statement is true" are never formulated. However, another kind of reference, endless reference, is still possible and allows for statements of the type:

The following is true → The following is true → The following is true → . . .

The truth values of the statements in this sequence could be T → T → T → ... or F → F → F → ... Curiously, the analogue of "This statement is false" is not paradoxical:

The following is false → The following is false → The following is false → . . .

Here, with the truth values T → F → T → F → ... or F → T → F → T → ... we would successfully avoid a contradiction. Now we may observe the true form of Gödel's undecidable statement:

The following is unprovable → The following is unprovable → The following is unprovable → . . .

or, to simplify,

G  −states unprovable→  G'  −states unprovable→  G''  −states unprovable→  . . .

where G, G', G'', ... comprise an infinite sequence of statements. I will show how this statement is constructed, but I will first give an outline of the proof. We will see in this outline how the two concepts of recursive axiomatizability and ω-consistency come into play.

The proof of Gödel's Incompleteness Theorem works like this: if G were provable, then recursive axiomatizability would allow us to translate the proof into a proof of G'. But since the unprovability of G' is just what G states, the proof of G would translate into the very proof whose nonexistence it purports to prove, resulting in inconsistency. Therefore, G can't be provable.

Now, if ~G were provable, then G' would be provable, since ~G denies the statement that G' is unprovable. In that case, ω-consistency would allow us to backwardly translate the proof of G' into a proof of G, in which case both G and ~G would be provable -- another contradiction!

In conclusion, G must be neither provable nor disprovable.

The explanation given here works similarly to "This statement is not provable," only self-reference is replaced with endless reference, and two concepts (ω-consistency and recursive axiomatizability) are required to ensure that a proof of the first statement in the chain amounts to a proof of the next statement, and vice versa.

What are ω-consistency and recursive axiomatizability? In this essay, I will gloss over the definition of recursive axiomatizability, but I will again remark that it is needed for a translation theorem that would relate a proof of G to a proof of G'. While the concept of ω-consistency is intuitively plausible, ω-inconsistency is a bit tricky. It involves the notion of a number that is inductively accessible, or reachable, inside a theory, but unreachable outside the theory. I will discuss this later, but first I will describe this sequence of endless propositional reference in more detail.

In the first section, we saw how statements may be encoded with symbols. Mathematics is a very expansive discipline -- so expansive, in fact, that mathematics as a science can be studied within mathematics! The encoded statements are simply treated as mathematical objects, allowing us to make statements about statements. In doing so, we usually enclose them with quotation marks or brackets, to designate them as objects that a higher-order statement can be about. Thus, "The statement, 'A is not provable' is provable" can be written:

Pr [~ Pr A].

We obtain an endless string of propositions that claim the unprovability of the next in sequence by defining what is called a substitution (or arithmoquine) function. This function, which I will denote S, transforms a property into a statement that the symbol for the property has that property. In this way, direct self-reference is avoided, and endless reference is made possible. The effect of the substitution function on the property "x is prime," for example, is to create the statement, "The statement 'x is prime' is prime." Of course, statements can't be prime, unless encoded as numbers (and in Peano arithmetic, this can be done with a procedure called Gödel numbering) but the idea is that the substitution function replaces the free variable of a property -- in this case, x -- with the expression for that property, thereby allowing a property to refer to itself. A few examples of adjectives in everyday speech whose arithmoquines are true are: 'English,' 'four-syllable,' and 'twelve-letter.' Each property applies to the symbol for the property. When self-substituted, these adjectives become, "The word 'English' is English," "The term 'four-syllable' is four-syllable," and "The term 'twelve-letter' is twelve-letter."

To construct an endless reference to infinity within non-self-referential mathematics, we use the substitution function on a statement that itself contains the substitution function. This prepares the statement for an infinite substitution process. Gödel's undecidable statement, written in mathematical language, is:

[~ Pr S [~ Pr S x]]

When we continually perform the substitution operation on the statement in brackets, we obtain the logically equivalent statements:

[~ Pr [~ Pr S [~ Pr S x]]]
[~ Pr [~ Pr [~ Pr S [~ Pr S x]]]]
[~ Pr [~ Pr [~ Pr [~ Pr S [~ Pr S x]]]]]
                     .    .    .     

We'll give the name 'G' to the statement [~ Pr S [~ Pr S x]]. When expanded, it amounts to the endless reference we are looking for. With the two concepts of ω-consistency and recursive axiomatizability, we will now show that G is undecidable.

Earlier in this section, we noticed that truth isn't always preserved in endless reference. With statements such as:

The following is false → The following is false → The following is false → . . . ,

we might end up with truth values

T → F → T → F → . . .

If the truth values of statements in the above sequence alternate, how can we be sure that the provability values of the statements in

The following is unprovable → The following is unprovable → The following is unprovable → . . . , or
G  −states unprovable→  G'  −states unprovable→  G''  −states unprovable→  . . .

don't alternate as well? More specifically, how can we tell that the provability of the first statement amounts to the provability of the second statement, and vice versa? This is where we use recursive axiomatizability and ω-consistency.

Recursive axiomatizability refers to a property of the system by which its axioms can be generated according to a certain kind of algorithm. I will not reveal in this essay what algorithms are permissible, but this property of the system allows us to translate a proof of G into a proof of G' -- more specifically, it allows us to deduce from the provability of the first statement, the provability of the provability of the second statement. In symbols, the translation theorem given by recursive axiomatizability tells us that

Pr(y, [~ Pr S [~ Pr S x]]) implies Pr [Pr(y, [~ Pr S [~ Pr S x]])]
~ Pr(y, [~ Pr S [~ Pr S x]]) implies Pr [~ Pr(y, [~ Pr S [~ Pr S x]])]

This gives us the first step. If G were provable, then by the translation theorem, the proof of G would translate into a proof of G'. But the unprovability of G' is just what G states. In that case, G' would be both provable and disprovable, a contradiction, and since by assumption of consistency we cannot have a contradiction, G cannot be proven.

Now, for the next step: we must use ω-consistency to show that the provability of G' would imply the provability of G. We saw earlier that ω-consistency essentially means that every number in the system is 'reachable' outside the system in addition to inside. Formally, it means that if, for any property P,

Pr [P(1)], Pr [P(2)], Pr [P(3)], . . .

then it cannot be that

Pr [∃x ~P(x)],

where 1, 2, 3, ... include only the translated numerals from numbers outside the system. This sounds intuitively plausible: if, by counting, we can 'reach' only numbers with the property P, then we should never be able to reach a number with the property ~P. However, as I will show in the next section, it is logically possible to construct an ω-inconsistent theory by adding a new number and allowing it to play the role of a 'reachable' number that is technically unreachable.

Suppose now that G were disprovable. In that case, G' would provable. We first note that if nothing proves G, then by the translation theorem, nothing will translate into a proof of G', and although (as we shall see) G' might still be provable in the system of G, there is no translated proof of G' from outside the system of G. But if G' is provable, as disproving G would imply, then we would end up with a proof of G' that could not be reached and translated from outside the system of G, contradicting our assumption that the system of G is ω-consistent. Therefore, G cannot be disproven either.

Since G, the first statement in the infinite sequence, cannot be proven or disproven, it is undecidable. This concludes the proof.

*     *     *

Curiously, what would happen if we removed the requirement of recursive axiomatizability? If we did, we could add as many new axioms as we wanted to, and if we carried out this process infinitely, we could make every statement decidable, completing the system. Gödel's theorem, in that case, would not restrict us from judging every statement 'true' or 'false,' as the translation theorem would no longer apply. It may be asked, however, whether these new axioms would really be true.

It has been shown that Gödel's theorem can be proven on the assumption of consistency alone. The proof is slightly more complicated, but still readable, and is called the Gödel-Rosser Theorem. I will not touch on it here, but it can be found in more advanced literature, such as First Order Mathematical Logic by Angelo Margaris.

On the Possible Existence of 'Supernatural Numbers'

When we relax the requirement of recursive axiomatizability, we may begin adding new axioms in a way that completes a system. As we have seen, we can consistently add either G or ~G as an axiom. Many mathematicians have agreed that G is, Platonically speaking, a true statement, as its falsity would imply its provability, and therefore its truth. We must remember, however, that Gödel's theorem is founded on endless reference, and that the truth value of G could turn out to be independent of the truth value of its statement of reference, G'.

Even so, if we added ~G, the consistency of the system in which G' is formulated would be destroyed. This is the basis of Gödel's second incompleteness theorem, according to which the consistency of arithmetic as a formal system cannot be proven within arithmetic. If ~G turned out to be true, then neither in arithmetic nor in its modern extension, Zermelo-Fraenkel set theory, would we be able to formulate a consistent representation of the theory under study. In a sense, mathematics would not even be able to reflect upon itself as an axiomatic system without facing contradictions.

The addition of ~G as an axiom to arithmetic would result in ω-inconsistency and the existence of a supernatural number, a number that is allegedly higher than every number that can be counted to, and that encodes a proof of G'. If we chose, we could call this number 'x.'

But how could an 'unreachable number' like x exist without violating the axiom of induction? If the numbers 1, 2, 3, ... don't encode proofs of G', then by induction, wouldn't x inherit the property of not being a proof? If you couldn't count to x, how could it inherit the inductive property of being a number that you can count to?

The answer, as I've hinted earlier, is that you could count to x, but only in the theory to which x belonged as a reachable number. In that theory, the supernatural number x would play the role of a mysterious constant that attained inductive accessibility by functioning like a variable. The proof it encoded would possess all of the properties of a normal proof, or so we are told: it would begin with premises, proceed with inferences, and end in a conclusion. Outside the theory, the x would just be an x. It would be a letter with two intersecting marks. You wouldn't be able to count to it, because the symbol x doesn't appear in the number sequence. It is by acting as variables that new constants added to a theory are able to inherit properties of its already-existing objects and make possible both ω-inconsistency and the existence of supernatural numbers.

By adding x to the theory, however, we would destroy the consistency of not only the same theory, formulated within itself, but also of the old theory without the axiom ~G. Near the beginning of the previous section, I explained that any proof of G would translate into the very object whose nonexistence it would prove, effectively proving itself nonexistent in the act of existing. The same would be true of a proof of G'. In the system of ~G, x would simply exist, but in the system of G', x would both exist and not exist.

Additional Comments on Endless Reference

In response to this essay, several have challenged the validity of the interpretation of G as a statement that begins an endless reference on the grounds that G and G' are identical statements. They have argued that since G' is simply the Gödel number of G and is identical in syntax to G, it is really the same statement as G, and that G should be interpreted as self-referential, not endlessly referential. In response to these objections, I will clarify both the meaning of endless reference and my position on the issue of whether G and G' are basically identical.

First, we remember that ZFC contains an infinite number of nested reflections of its own theory:

ZFC > ZFC' > ZFC'' > ...

The actual expansion of G by the substitution function S takes place as follows:

     G1  −states unprovable→  G'0
     G2  −states unprovable→  G'1  −states unprovable→  G''0
     . . .


     G0G1G2 ↔ . . .
     G'0G'1G'2 ↔ . . .
     G''0G''1G''2 ↔ . . .

are all provable in their respective theories. To obtain the infinite sequence

G  −states unprovable→  G'  −states unprovable→  G''  −states unprovable→  . . .

we define an equivalence class for each nested theory ZFC(n) in which G0, G1, G2, ... are identified as logically equivalent statements. We then define 'states unprovable' to mean that a proposition in one class states the unprovability of a proposition in the next class.

In this way, we capture the idea of endless reference:

The following is unprovable: The following is unprovable: The following is unprovable: . . .

Even without these definitions, all we really need are G, G', and G'' to ask about the truth of ~G. In this essay, I have been careful not to deny that the sequence above might ultimately be founded on self-reference, that G, G', G'', ... are essentially identical, and that G is Platonically true. However, by treating G, G', and G'' as logically independent statements we have made a startling case for the possibility that ~G is true. It remains to be seen how the controversy will settle.

Further Speculations

A few have attempted to draw implications from Gödel's Incompleteness Theorem about the nature of the mind, the universe, and human knowledge. A number of startling hypotheses are that human knowledge is essentially limited, that the ability to perceive truth in Gödel's undecidable statement is unique to humans and is not shared by robots, and even that no ultimate theory of the universe will ever be found. Stuart Hameroff and Roger Penrose have been working on a theory of consciousness in which microtubules in the brain are thought to facilitate quantum effects that allow human beings to transcend artificial intelligence in grasping the truth of Gödel's undecidable statement. At this time, I do not espouse any of these claims, but I do feel that incompleteness and undecidability are subjects worthy of investigation in the philosophy of knowledge.

Send me mail

Back to My Essays

View my Guestbook

Online Degree Programs