Prelude
It was a dark and stormy night.
As Ludwig, a tall, dour looking man with perpetually tousled hair, stepped out of his favorite coffee shop in old Vienna, the proprietor urgently seized his elbow, imploring, “Here, please take this.”
“What is it?” inquired Ludwig.
“A lantern,” answered the proprietor.
With a wry, resigned smirk Ludwig replied, “You know that I’m blind, and have no use for a lantern, whether it is dark out or light.”
“Yes, of course,” said the proprietor, “But take it anyway so at least nobody runs into you.”
Obligingly, Ludwig took the lantern, tipped his cap, and went on his way.
Meanwhile, Kurt, a man slight of build and tentative of gait, meticulously groomed and thickly spectacled, meandered a nearby park in deep contemplation, hardly cognizant of the rain, etching a path that kept looping back upon itself in strange fashion.
As Ludwig entered the park (his favorite route home), he felt the sudden jolt that unmistakably signifies being bumped into. From the low collisional force and lack of warning, Ludwig discerned the other man’s slightness of build and softness of gait.
Annoyed but unharmed, Ludwig snipped, “Is that you, Kurt? Watch out where you’re going! Didn’t you see my lantern?”
“I’m very sorry, Ludwig, but your candle has extinguished.”
“No eye has seen, nor ear heard, nor the human heart conceived, what God has prepared for those who love him.”
1 Corinthians 2:9, NRSV-CI
Mathematics in Crisis
At the turn of the twentieth century, mathematics found itself mired in a foundational crisis. Recent advances, while exhilarating, left it riddled with contradictions, manifest as lacerations from playing around with sharp objects like infinities larger than infinity, infinitesimals vanishing into singularity, and self-referencing sets.
Mathematical systems that contain internal contradictions are entirely useless, and so it seemed to many that death by a thousand cuts was imminent.
The situation came to a head in the form of “Russell’s Paradox,” named after the famous mathematician and popular philosopher Bertrand Russell. Russell’s Paradox relates to the concept of sets, which are simply groupings of items that share a common property. Examples include the set of all prime numbers, the set of all red things, and the set of all my golf trophies (be aware that a set can be empty).
Russell’s Paradox involved sets whose members can themselves be sets. If a set can be in a set, what happens if a set is a member of itself? To analyze this strange situation, consider two types of sets: a ‘normal’ set that does not include itself as a member, and a ‘self-containing’ set that does include itself.
The paradox comes out when you try to group all normal sets. Let’s call S the set of all normal sets. Then ask yourself, is S a normal set? Let’s think it through. Since all normal sets belong to S, if S is a normal set then S should be a member of itself. But if S is a member of itself, then S is by definition a self-containing set, and not a normal set at all. But if S is not a normal set, then S cannot be a member of itself because S includes only normal sets, which immediately kicks S back out, making S a normal set again. And so on. We are left with an unending recursive loop and an internal contradiction that cannot be resolved.[1]
Something had to be done before all of mathematics disappeared in a puff of logic.
Un-Triumphant Triumvirate
The best thinkers advocated a one-two punch approach to eradicating the emergent storm of contradictions. First, a coherent and robust, yet minimum, set of axioms (or assumptions) must be developed. Second, those axioms must be coupled with a set of precise rules and unambiguous expressions. This, they thought, would erect a fortress that paradox could not breach.
Russell, alongside Alfred North Whitehead, ambitiously attacked the problem head on in their three-volume tome, Principia Mathematica. While not quite reaching the goal of dispatching all paradox, their work served to inspire other mathematicians, logicians, and philosophers to take up the sword for their own run at slaying the dragon.
Ludwig Wittgenstein, an Austrian philosopher and paramour of Vienna, was one such would-be knight. Wittgenstein sought to close Russell’s logical loopholes in his skinny-but-dense singular work, Tractatus Logico-Philosophicus (discussed further here).
Taken together, the contributions of Russell and Whitehead on the one hand and Wittgenstein on the other occupied the collective imagination of an elite philosophical group known as the Vienna Circle. Unified around developing a philosophy of science, the Vienna Circle proselytized empiricism, which they considered objective and natural, while criticizing metaphysics, which they considered subjective and supernatural.
The Vienna Circle believed that anything that can be known will be known only through observation and measurement, and that delving into higher meaning is useless because understanding higher meaning is impossibly beyond reach.
Distilled down, the foundational beliefs undergirding the efforts of Russell, Wittgenstein, and the Vienna Circle, amounted to:
(1) paradox is merely an artifact resulting from wordplay and the impreciseness of language; and
(2) self-reference is a particularly nasty source of ambiguity and should be disallowed by fiat, decreeing that a thing cannot simultaneously be itself and refer to itself.
Unbeknownst to any of them at the time (and unappreciated by some of them even after it happened), the seeds of their own unraveling were already sown. For around the periphery of the Vienna Circle, barely noticed, lurked the unassuming yet deadly-precise logic of Kurt Gödel. As we will see, not only did Gödel’s efforts topple the foundation of their beliefs, he wrought this destruction from the best of intentions–only trying to help.
Completing Incompleteness
In the midst of this percolating intellectual activity, the German mathematician David Hilbert entered the fray, resolved to defend and uphold the foundations of mathematics. Like the others, Hilbert believed the victory would come in the form of a finite and complete set of axioms. Unlike the others, Hilbert knew that the victory would not be final unless there was a rigorous proof that the axioms in fact produced a system that was complete and consistent.
In mathematics and logic, consistency of a system means that, for any proposition in the system, both the proposition and its negation cannot both be true. In other words, in a consistent system, x = 0 and x ≠ 0 cannot both be proven.
Whereas consistency meant the absence of contradictions, completeness meant that all true propositions in the system are provable. In other words, in a complete system all truth is discoverable.
Hilbert’s dream was for the system of arithmetic to be proven both complete (all truth is provable) and consistent (no internal contradictions), and Gödel sought to make that dream a reality.
As a warm-up, stretching his formalism muscles so to speak, Gödel began working on the Hilbert problem by attempting to prove the completeness and consistency of simple logic. Simple logic is essentially all the propositions that can be formulated using and, or, not, if/then, and so on. For example, the following statement is a well-formed and true proposition in simple logic:
if A is true, then the statement ‘A or B’ is true.
Gödel saw simple logic as a trivial system that quickly reduces to tautological statements, and so it was unremarkable that he was able to demonstrate it to be both consistent and complete. What was remarkable was how exacting and complex the proof ended up needing to be.
Undaunted and armed with a few new tricks, Gödel proceeded to tackle the system of formal arithmetic head on. Unlike simple logic, formal arithmetic embodied a truly complex and non-trivial system. If ever the proverbial irresistible force collided with the proverbial immovable object, this was the time.
To spare the gory detail, suffice it to say that the full force of Gödel’s logic failed to prove the completeness and consistency of formal arithmetic. However, all was not lost because the collision created an altogether unexpected result.
As the dust settled, Gödel’s masterwork slowly came into focus: two theorems more eternal than marble monuments, each driving a stake through the heart of Hilbert’s dream by utterly refuting its underlying premise. Today they are called Gödel’s incompleteness theorems.
In the first incompleteness theorem, Gödel proved that any consistent system with a definable set of axioms capable of expressing a non-trival system like formal arithmetic can never be complete. In other words, within formal arithmetic (or any other non-trivial logical system) it is possible to construct a statement that is true but that cannot be proven.
Gödel’s second incompleteness theorem proved that one of those unprovable truths is the system’s own consistency. In other words, don’t even try to prove consistency, it cannot be done.
Hilbert’s dream, Russell’s magnum opus, and Wittgenstein’s philosophy all disappeared in two swift strokes.
Paradox Found
Even today, roughly 90 years later, people are still uncovering the implications of Gödel’s incompleteness theorems. One startling but unavoidable implication is that all consistent and non-trivial systems of logic will necessarily produce contradictions that cannot be resolved.
I’ll say that again in another way, and in bold italics to grab your attention:
Gödel’s incompleteness theorems proved that paradoxes are not merely an artifact of imperfectly defined axioms (as Russel thought), or even the innate imprecision and ambiguity of language (as Wittgenstein thought), but are instead a necessary feature of logic systems.
Gödel demonstrated the utopian vision of a paradox-free logic system to be a mirage. To add insult to injury, Gödel accomplished this feat by utilizing self-reference, that paradox-producing disallowed demon of mathematical mischief. And he did it in a way that paradoxically avoided paradox.
The details of Gödel’s proofs, while beautiful to behold in their breathtaking complexity and precision (not unlike an M.C. Escher print), are maddeningly difficult to penetrate, and thus are well beyond the scope of this blog.[2]
However, that does not mean their essence is out of reach, and indeed in many ways that essence is surprisingly intuitive. As Douglas Hofstadter observed:
“Merely from knowing the [Gödel] formula’s meaning, one can infer its truth or falsity without any effort to derive it in the old-fashioned way, which requires one to trudge methodically ‘upwards’ from the axioms. This is not just peculiar; it is astonishing. Normally, one cannot merely look at what a mathematical conjecture says and simply appeal to the content of that statement on its own to deduce whether the statement is true or false.”
Douglas Hofstadter, I Am a Strange Loop, pages 169-170
What Hofstadter referred to as the ‘Gödel formula’ is a way of using numbers to encode statements about number systems so that you can explore the meaning of the statements just by performing number operations. The key was coming up with a number that stood for a particular self-referential proposition, namely:
‘This statement cannot be proven in the system.’
As Gödel designed it, the number that encoded this statement could not be false, because if it was false then it could be proven, and provable statements cannot be false. The only alternative is for the statement to be true, thus resulting in a consistent system containing a proposition known to be true and yet unprovable.
Stop for a moment to think about what Gödel did. He deployed the power of self-reference on two different levels, first encoding statements about a number system into the system itself, and then constructing a statement that concerned the provability of itself.
What emerged from this double loop was the realization that the only non-paradoxical way to view logic systems required those systems to include paradoxes.
Mind blown. Twice.
Strange Loops in a Strange Land
Hofstadster coined the term ‘strange loop’ in his Pulitzer Prize-winning book, Gödel, Escher, Bach: An Eternal Golden Braid, to refer to concepts like Gödel’s formula. In fact, we have already encountered at least one other strange loop in this post–Russell’s Paradox.
A strange loop is simply an occurrence of self-reference that results in a contradiction, or paradox. Take, for example, the following sentence:
‘This sentence is false.’
The statement refers to itself in a way that, if it was a true statement, then it would be false; but if it was false, then it would be true. You will sometimes hear the particular example referred to as the liar’s paradox.
Such statements are strange loops because they loop back on themselves in a way that leads to a paradoxical result.
More abstractly, a strange loop can be defined as a hierarchy of levels each relationally linked to at least one other such that starting at any level and following the links will result in arriving back at the starting point. The hierarchy of a strange loop can be described as ‘tangled’ in the sense that every level is both higher and lower than every other level.
As an example, see the M.C. Escher print in Figure 2, depicting an impossible strange-looped staircase.
Figure 2: M.C. Esher’s lithograph, Ascending and Descending
Like the stairs in Figure 2, when navigating a strange loop, you can get to every level (even all the way back to the starting level) by moving ‘down’ the hierarchical stack; and you can get to every level (even all the way back to the starting level) by moving ‘up’ the stack.
Hofstadter saw strange loops in not just riddles, Gödel’s formula, and Escher’s works, but also in J.S. Bach compositions, DNA replication, and the emergence of consciousness.
Because strange loops allow going up by going down and going down by going up, cause-and-effect relationships end up being flipped on their head, making it seem like the chicken hatches back into the egg.
No wonder the likes of Russell and Wittgenstein wanted to banish them.
“Paradoxes, in the technical sense, are those catastrophes of reason whereby the mind is compelled by logic itself to draw contradictory conclusions. Many are of the self-referential variety.”
Rebecca Goldstein, Incompleteness, p. 49
Paradox can throw the mind into an infinite loop, perhaps revealing that the ability to deal with paradox and to look outside the system to recognize truth is a non-algorithmic function, but more on that in Part 2.
Whack-a-Mole
Gödel’s work demonstrated that trying to banish strange loops is a game of whack-a-mole. You can get rid of your current pesky problem, but a new one will always pop up. You can eliminate Russell’s Paradox in set theory by imposing a rule that sets cannot contain sets, thereby enforcing an orderly and untangled hierarchy that will never loop back on itself. But this does not get rid of the incompleteness issue generally, because Gödel’s theorems work on systems with any set of axioms.
No matter how many new rules you add in an attempt to ‘fix’ the system (even if you find one of those pesky unprovable truths and add it by axiom), the result is a new system with a new set of axioms that, by Gödel’s first incompleteness theorem, is also incomplete.
There is just no way around the persistent existence of unprovable truths, and, by Gödel’s second incompleteness theorem, the reality that the consistency of the system itself is one of those unprovable truths.
What made Gödel’s strange loop so brilliant was that it was not properly a paradox. Even though the Gödel formula is self-referential, it is not contradictory because the loop stops when you get to the interpretation that the statement is true but unprovable.
The philosophical implication of the incompleteness theorems is that there exist truths that you cannot “get to the truth of” without going outside of the system–without going beyond.
If that last bit makes you squirm, try this on for size.
Since it is impossible to formally prove the consistency of an arithmetic or logical system within that system, and consistency means that the rules of a system cannot derive a contradiction, then the absence of paradox would seem to prove internal consistency in the system, even though we know that cannot happen.
Thus, the only way to demonstrate the consistency of a system is by showing that paradoxes do not occur, which runs afoul of Gödel’s results. The upshot is that, not only is a consistent system of logic or mathematics capable of producing paradoxes, it must produce paradoxes or will cease to be consistent.
Let’s repeat that one more time.
The complete absence of paradox means consistency is provable, which contradicts Gödel’s consistency theorem. Therefore, paradox is necessarily present, and can only be resolved from ‘outside’ the system.
Any attempt to fix the system from within by removing paradox is doomed to failure, akin to Quixotically tilting at windmills, or for that matter, whacking moles.
Coexist
Whereas Wittgenstein and company thought that incompleteness derived from correctable limitations and flaws in language and syntax, Gödel showed that incompleteness exists as a very consequence of consistency. It’s a feature, not a bug!
Gödel’s results were difficult to swallow for those who saw paradox as a nuisance, a nagging problem signifying nothing but the failure to apply sufficient rigor. These ‘objectivist’ types seemed to accept as a matter of faith that paradox was nothing more than a glitch needing to be fixed, removed, or ignored.
Why such knee-jerk revulsion to paradox? Can’t we all just get along?
Perhaps it is simply the very human desire for certainty. Or maybe it is a matter of pride in defending the capacity of human reason. Possibly it is that paradox threatens the belief that the secrets of the universe are fully knowable. Or is it fear that confronting paradox means confronting the potential of a higher meaning and greater purpose?
From the point of view of the objectivists, the drive to remove the possibility of paradox seems to originate from the same place as the desire to remove God from the equation of life. Believing there is no God means being free from accountability to a higher purpose, and the ability to remain intellectually consistent without running afoul of what God has in mind.
Faith in God obliges me to pay attention to God’s purpose while constantly struggling with what that purpose means for my life.
Subordinating my own desires and judgments to God’s puts me in jeopardy of living a lie whenever my own devices are at odds with God’s. Perhaps the revulsion we feel when encountering paradox reveals an intuitive understanding that confronting it will mean admitting our own limitations–that there are things beyond our immediate and ultimate grasp.
For the sake of holding on to the illusion that we are in control–of clinging to the idea that existence extends only to what is knowable–we are not just willing but inclined to deny the existence of something greater, something beyond our capacity for reason and logic to fully understand.
In the frantic attempt to preserve the freedom to act on our own, we become slaves to our own desires, which prevents us from becoming what God intended.
[1] A fun example similar to Russell’s Paradox is the set of all adjectives that are self-describing as compared to the set of all adjectives that are not self-describing. The adjective ‘monosyllabic’ is not self-describing, whereas ‘multisyllabic’ is. What about the adjective ‘non-self-descriptive’?
[2] Perhaps the best and most thorough explanation of Gödel’s proofs is set forth in Douglas Hofstadter’s book Gödel, Escher, Bach: An Eternal Golden Braid.