The death of logical certainty

Early twentieth century hopes dashed on the rocks of paradox

At the dawn of the twentieth century, there were high hopes that the newly developed formal logic, combined with rigorous mathematics, could establish a wide range of truths with logical and philosophical certainty. As is common in the history of philosophy, these hopes did not materialise. Yet the reasons remain worth understanding as the failure was due to explicit internal system limitations more than external critiques.

New forms of logic and mathematics had been invented in the late nineteenth century that promised to provide a rigorous foundation to knowledge. Core developers of these approaches, especially Gottlob Frege and Geog Cantor, had produced well worked through systems that formally based mathematics on pure logic. By the end of the 1930s, however, mathematicians and logicians had discovered three core results that placed clear limitations on our ability to ground general truth in formal logic.

These results have long been taken to place limits on certain types of human knowledge, especially the applicability of proofs. However, they also provide some useful insights into why we need to be humble about our knowledge more generally. To see this, we will cover each of the three results in turn.

A mathematical paradox

In 1910, Bertrand Russell and Alfred Whitehead began publishing Principia Mathematica - their “monumental but little read classic” that sought to ground mathematics in formal logic. Stretching in the original to almost 2000 pages of dense notation, the sheer size of the book gave considerable weight to this conclusion.¹ However, the complexity of the work was necessitated by a flaw that Russell found in the previous work of Frege and Cantor - and is now known as Russell’s Paradox.

The initial project, as advanced especially by Frege, relied on some simple and intuitive ideas. We need to cover a couple of definitions first. In mathematics, a set is simply a collection of things, which could be physical, abstract or even other sets. In logic, the focus is on the properties that things have - colour, temperature, size, whether a prime number, etc. There is an intuitive and natural connection between these two concepts:

For any well-defined property, there is a set that contains all (and only) the things that have that property.

This principle allowed a clear, intuitive and non-arbitrary connection between mathematics and logic. However, Russell realised that it does not hold universally as there is at least one well-defined property for which there cannot be a corresponding set. The problem arises if we consider the set of all things with the following property: it is not a member of itself.²

This is now called the Russell Set, that is the set of all sets that are not members of themselves. And it immediately generates a paradox: if it is a member of itself, then by definition it is not a member of itself - and vice versa.

If this is too abstract, Russell himself noted a real life illustration of the same idea. Imagine there is a town with a single barber in it. Now we could plausibly say that the barber is the person who shaves all of the people in the town, and only those people, who do not shave themselves. However, this raises the question of whether this barber shaves himself? Assuming he isn’t a modern hipster with a full beard, it turns out the question is unanswerable and therefore definition describes an impossible situation. This is despite it being easy to understand and intuitively plausible.

To avoid this paradox, Russell and Whitehead introduces a separate theory of types to avoid the problems with intuitive notions of sets. The fact that this somewhat arbitrary approach was necessary and took nearly 2000 pages to ground basic mathematics in pure logic suggested there were severe limitations to their project and the thesis they were attempting to demonstrate.

Proof versus truth

More devastating to the broader project was a result published by Kurt Gödel in 1931 and which is now known as Gödel’s Theorem.³ To understand the result, and its broader importance, it is useful to understand how modern formal logic works. Put simply, it defines very precise languages using a limited set of symbols, no ambiguity and clear rules about what statements are allowable within the language or not. The only allowable statements are those that can be derived from other statements (or core assumptions) via a limited set of rules. These derivations are what we call proofs.

The attempt to ground all of mathematics in formal logic assumed that proof within logic could establish truth, and prove all mathematical truths. Gödel, however, showed how we could, within a standard logical language that included basic mathematics, always construct a statement that could not be provable (or disprovable) but that we would nevertheless say is true. In other words, truth transcends provability.

The ‘Gödel Statement’ is, perhaps unsurprisingly, rather similar to Russell’s Set. It is one that essentially claimed about itself that "This statement is not provable." The problem is that if the Gödel Statement is provable, then we can prove that it isn’t provable - which is a contradiction and the whole logic falls apart. So it cannot be provable, but that means it is true.⁴

Gödel therefore showed that proof, at least via logic within a formal language, cannot capture what we would describe as the complete truth about the world - even as it relates to the language being used. Given all the mechanisms that formal languages rely on can be found within normal human languages (albeit without the precision) then this limitation applies beyond the artificial world of pure formal logic and mathematics. The extent to which it holds is not so clear, but it should give us some pause as to how reliable our conclusions might be when we think we have proven something.

From proof to computation

The third result is in many ways a corollary of Gödel’s work but it is worth particular note given our modern algorithmic world.⁵ In 1937, Allan Turing published a result that extended the concept of undecidability inherent in Gödel’s approach to the nascent field of computation and algorithms.

Turing showed that, for any general computational algorithm, there will be some problem that it cannot solve. The specific result is now known as the Halting Problem as it is based on using the algorithm to determine whether specific programs complete (halt) or continue indefinitely. The core move in the proof may not be surprising as - to simplify - it involves defining a program that does the opposite of what it is asked to do.

The lesson of the Halting Problem is well-embedded in modern day computation - we rely on a range of algorithms that operate in parallel with different domains and put in many safeguards to stop algorithms going haywire. All this is necessary as a universal algorithm is not possible.

However, the philosophical implications are less well understood. If no general algorithm can exist that can solve any arbitrary problems, it should call into question our common algorithmic approaches to knowledge and action - as well as put a real limit on the likelihood of the AI singularity.

Humility and the limits of representations

To summarise, we have seen that intuitive connections between mathematics and logic end in paradox; formal proof can never fully capture truth; and that no general computational algorithm is possible that could (even in principle) solve any problem. These seem, at least to me, to be all clear evidence that knowledge is hard and our attempts will fall short of what we hope. In other words, they are good evidence for epistemic humility.

What is intriguing about these results is that the limitations all arise from the basic rules or mechanics within the logic or mathematics being constructed. To be able to capture, reason with and expand our knowledge about the world, we (humans) need to construct languages or systems to represent our knowledge. However, in each of these results the basic mechanics of the language or system can be shown to prevent a complete representation of what we wanted to capture. To put this core point differently, our systems of representing knowledge are restricted and can only provide a partial picture of the world.

For reference, each of these results were inspired by a very old puzzle called the Liar Paradox, which has been discussed since (at least) the Ancient Greeks. That in itself is a subject with a vast literature and requires a separate post at a later date.

1. Notably, Russell apparently estimated that only 6 people every read the whole text in his lifetime. See https://writings.stephenwolfram.com/2010/11/100-years-since-principia-mathematica/

2. It might seem odd that a set could be a member of itself. However, consider the set of hot things. If we treat the full collection of hot things as itself a thing (or an entity) then that collection (set) is obviously also hot.

3. Strictly speaking, there are two theorems that are often not distinguished. The distinction is not relevant here.

4. This is the standard interpretation, although there are alternative views. All of the alternatives accept the result establishes a version of the limitation covered in the next paragraph - so we can justify glossing over these details.

5. I should note that Alonzo Church published a similar result prior to Turing, but it focused on mathematics rather than computation.