How do we prove that something is unprovable?

Solution 1:

When we say that a statement is 'unprovable', we mean that it is unprovable from the axioms of a particular theory.

Here's a nice concrete example. Euclid's Elements, the prototypical example of axiomatic mathematics, begins by stating the following five axioms:

Any two points can be joined by a straight line

Any finite straight line segment can be extended to form an infinite straight line.

For any point $P$ and choice of radius $r$ we can form a circle centred at $P$ of radius $r$

All right angles are equal to one another.

[The parallel postulate:] If $L$ is a straight line and $P$ is a point not on the line $L$ then there is at most one line $L'$ that passes through $P$ and is parallel to $L$.

Euclid proceeds to derive much of classical plane geometry from these five axioms. This is an important point. After these axioms have been stated, Euclid makes no further appeal to our natural intuition for the concepts of 'line', 'point' and 'angle', but only gives proofs that can be deduced from the five axioms alone.

It is conceivable that you could come up with your own theory with 'points' and 'lines' that do not resemble points and lines at all. But if you could show that your 'points' and 'lines' obey the five axioms of Euclid, then you could interpret all of his theorems in your new theory.

In the two thousand years following the publication of the Elements, one major question that arose was: do we need the fifth axiom? The fifth axiom - known as the parallel postulate - seems less intuitively obvious than the other four: if we could find a way of deducing the fifth axiom from the first four then it would become superfluous and we could leave it out.

Mathematicians tried for millennia to find a way of deducing the parallel postulate from the first four axioms (and I'm sure there are cranks who are still trying to do so now), but were unable to. Gradually, they started to get the feeling that it might be impossible to prove the parallel postulate from the first four axioms. But how do you prove that something is unprovable?

The right approach was found independently by Lobachevsky and Bolyai (and possibly Gauss) in the nineteenth century. They took the first four axioms and replaced the fifth with the following:

[Hyperbolic parallel postulate:] If $L$ is a straight line and $P$ is a point not on the line $L$ then there are at least two lines that pass through $P$ and are parallel to $L$.

This axiom is clearly incompatible with the original parallel postulate. The remarkable thing is that there is a geometrical theory in which the first four axioms and the modified parallel postulate are true.

The theory is called hyperbolic geometry and it deals with points and lines inscribed on the surface of a hyperboloid:

In the bottom right of the image above, you can see a pair of hyperbolic parallel lines. Notice that they diverge from one another.

The first four axioms hold (and you can check this), but now if $L$ is a line and $P$ is a point not on $L$ then there are infinitely many lines parallel to $L$ passing through $P$. So the original parallel postulate does not hold.

This now allows us to prove very quickly that it is impossible to prove the parallel postulate from the other four axioms: indeed, suppose there were such a proof. Since the first four axioms are true in hyperbolic geometry, our proof would induce a proof of the parallel postulate in the setting of hyperbolic geometry. But the parallel postulate is not true in hyperbolic geometry, so this is absurd.

This is a major method for showing that statements are unprovable in various theories. Indeed, a theorem of Gödel (Gödel's completeness theorem) tells us that if a statement $s$ in the language of some axiomatic theory $\mathbb T$ is unprovable then there is always some structure that satisfies the axioms of $\mathbb T$ in which $s$ is false. So showing that $s$ is unprovable often amounts to finding such a structure.

It is also possible to show that things are unprovable using a direct combinatorial argument on the axioms and deduction rules you are allowed in your logic. I won't go into that here.

You're probably interested in things like Gödel's incompleteness theorem, that say that there are statements that are unprovable in a particular theory called ZFC set theory, which is often used as the foundation of all mathematics (note: there is in fact plenty of mathematics that cannot be expressed in ZFC, so all isn't really correct here). This situation is not at all different from the geometrical example I gave above:

If a particular statement is neither provable nor disprovable from the axioms of all mathematics it means that there are two structures out there, both of which interpret the axioms of all mathematics, in one of which the statement is true and in the other of which the statement is false.

Sometimes we have explicit examples: one important problem at the turn of the century was the Continuum Hypothesis. The problem was solved in two steps:

• Gödel gave a structure satisfying the axioms of ZFC set theory in which the Continuum Hypothesis was true.
• Later, Cohen gave a structure satisfying the axioms of ZFC set theory in which the Continuum Hypothesis was false.

Between them, these results show that the Continuum Hypothesis is in fact neither provable nor disprovable in ZFC set theory.

Solution 2:

First of all in the following answer I allowed myself (contrary to my general nature) to focus my efforts on simplicity, rather than formal correctness.

In general, I think that the way we teach the concept of axioms is rather unfortunate. While traditionally axioms were thought of as statements that are - in some philosophical way - obviously true and don't need further justifications, this view has shifted a lot in the last century or so. Rather than thinking of axioms as obvious truths think of them as statements that we declare to be true. Let $\mathcal A$ be a set of axioms. We can now ask a bunch of questions about $\mathcal A$.

• Is $\mathcal A$ self-contradictory? I.e. does there exist a proof (<- this needs to be formalized, but for the sake of simplicity just think of your informal notion of proofs) - starting from formulas in $\mathcal A$ that leads to a contradiction? If that's the case, then $\mathcal A$ was poorly chosen. If all the statements in $\mathcal A$ should be true (in a philosophical sense), then they cannot lead to a contradiction. So our first requirement is that $\mathcal A$ - should it represent a collection of true statements - is not self-contradictory.
• Does $\mathcal A$ prove interesting statements? Take for example $\mathcal A$ as the axioms of set theory (e.g. $\mathcal A = \operatorname{ZFC}$). In this case we can prove all sorts of interesting mathematical statements. In fact, it seems reasonable that every mathematical theorem that can be proved by the usual style of informal proofs, can be formally proved from $\mathcal A$. This is one of the reasons, the axioms of set theory have been so successful.
• Is $\mathcal A$ a natural set of axioms? ...
• ...
• Is there a statement $\phi$ which $\mathcal A$ does not decide? I.e. is there a statement $\phi$ such that there is no proof of $\phi$ or $\neg \phi$ starting from $\mathcal A$?

The last point is what we mean when we say that $\phi$ is unprovable from $\mathcal A$. And if $\mathcal A$ is our background theory, say $\mathcal A = \operatorname{ZFC}$, we just say that $\phi$ is unprovable.

By a very general theorem of Kurt Gödel, any natural set of axioms $\mathcal A$ has statements that are unprovable from it. In fact, the statement "$\mathcal A$ is not self-contradictory" is not provable from $\mathcal A$. So, while natural sets of axioms $\mathcal A$ are not self-contradictory - they themselves cannot prove this fact. This is rather unfortunate and demonstrates that David Hilbert's program on the foundation of mathematics - in its original form - is impossible. The natural workaround is something contrary to the general nature of mathematics - a leap of faith: If $\mathcal A$ is a sufficiently natural set of axioms (or otherwise certified), we believe that it is consistent (or - if you're more like me - you assume it is consistent until you see a reason not to).

This is - for example - the case for $\mathcal A = \operatorname{ZFC}$ and for the remainder of my answer, I will restrict myself to this scenario. Now that we know that $\mathcal A$ does not decide all statements (and arguably does not prove some true statements - like its consistency), a new question arises:

• Does $\operatorname{ZFC}$ decide all mathematical statements? In other words: Is there a question about typical mathematical objects that $\operatorname{ZFC}$ does not answer?

The - to some people unfortunate - answer is yes and the most famous example is

$\operatorname{ZFC}$ does not decide how many real numbers there are.

Actually proving this fact, took mathematicians (logicians) many decades. At the end of this effort, however, we not only had a way to prove this single statement, but we actually obtained a very general method to prove the independence of many statements (the so-called method of forcing, introduced by Paul Cohen in 1963).

The idea - roughly speaking - is as follows: Let $\phi$ be a statement, say

$\phi \equiv$ "there is no infinity strictly between the infinity of $\mathbb N$ and of $\mathbb R$"

Let $\mathcal M$ be a model of $\operatorname{ZFC}$. Starting from $\mathcal M$ we would like to construct new models $\mathcal M_{\phi}$ and $\mathcal M_{\neg \phi}$ of $\operatorname{ZFC}$ such that $\mathcal M_{\phi} \models \phi$ and $\mathcal M_{\neg \phi} \models \neg \phi$ (i.e. $\phi$ is true in $\mathcal M_{\phi}$ and $\phi$ is false in $\mathcal M_{\neg \phi}$). If this is possible, then this proves that $\phi$ is not decided by $\operatorname{ZFC}$. Why is that?

Well, if it were decided by $\operatorname{ZFC}$, then there would be a proof of $\phi$ or a proof of $\neg \phi$. Let us say that $\phi$ has a proof (the other case is the same). Then, by soundness of our proofs, any model that satisfies $\operatorname{ZFC}$ must satisfy $\phi$, so there cannot be a model $\mathcal M_{\neg \phi}$ as above.