How to Prove That There’s No Proof
You can’t prove Cantor’s Continuum Hypothesis, and neither its negation.
Gödel’s incompleteness theorem shows that such statements will always exist, no matter how strong your axioms. Reason enough to take a closer look at how to prove that there’s no proof.
Is there a proof that there are only finitely many prime numbers? Certainly not! After all, Euclid taught us in his Elements that there are infinitely many prime numbers. As no theorem can be both true and false, we cannot give a proof that there are only finitely many prime numbers.
So one way to show that there is no proof of a certain theorem is to just find a proof for its negation: We know that there is no proof that the number π is rational because mathematicians have found several proofs showing that it is irrational. We know that there can’t be a 1-to-1-correspondence between the natural numbers and the real numbers because Cantor proved that there are more reals than naturals.
But why should you care about the non-existence of certain proofs when you can just prove the negation? You should care because of Gödel’s first incompleteness theorem.
Mathematics proceeds from axioms to theorems by proof. Gödel showed that if we start from axioms that are strong enough to carry out some elementary arithmetic, then there must be a statement independent of our axioms. This means that neither the statement nor its negation is provable from the axioms.
One of the most remarkable examples of this phenomenon is Cantor’s Continuum Hypothesis: The standard Zermelo-Fraenkel axioms of set theory can neither prove the continuum hypothesis nor its negation.
But how do we know that we can’t prove the continuum hypothesis? That is: How do we prove that there’s no proof?
The Parallel Postulate in Geometry
Let’s have a look at an example with a history of more than 2000 years.
Euclid postulated five axioms for geometry in his Elements: First, you can draw a straight line from any point to any point. Second, you can indefinitely extend any straight line in each direction. Third, given a point and a radius, you can draw a circle. And fourth, all right angles are equal to each other.
The most interesting of Euclid’s axioms is, however, the fifth. It’s the so-called parallel postulate:
That, if a straight line falling on two straight lines makes the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which are the angles less than the two right angles. (Euclid’s Elements, Book I, Postulate 5)
Essentially, the parallel postulate states that two lines that are not parallel must intersect eventually.
For thousands of years, mathematicians tried to prove that the first four axioms imply the parallel postulate. Why? As always, infinity complicates things. Euclid’s definition of parallel straight lines is this:
Parallel straight lines are straight lines which, being in the same plane and being produced indefinitely in both directions, do not meet one another in either direction. (Euclid’s Elements, Book I, Definition 23)
For ancient mathematicians, claiming that two lines are parallel, therefore, implied that they will not even intersect at infinity. However, those mathematicians were also aware that there are lines that do meet at infinity: the so-called asymptotes.
The parallel postulate makes claims about how straight lines behave at infinity and was, therefore, not considered to be self-evident. And if a mathematical claim isn’t self-evident, then it requires a proof. However, every attempt to prove the parallel postulate from Euclid’s first four axioms of geometry was doomed to fail.
Non-Euclidean geometry was discovered in the 19th century and drastically changed our understanding of the parallel postulate.
Mathematicians found geometries in which the first four of Euclid’s axioms are true but the parallel postulate fails. Eugenio Beltrami was the first mathematician to do so, although his contemporaries failed to see the importance of his work. Beltrami was a pioneer in non-euclidean geometry.
How do these non-euclidean geometries imply that there is no proof of the parallel postulate? If there was such a proof, then every model of the first four postulates would be a model of the parallel postulate. But that’s not the case. So there can’t be a proof.
Proofs & models: a case study in logic
But how does all this work formally? How can we give a full mathematical proof? That’s where mathematical logic comes into play. Classical propositional logic can be axiomatised by just three axioms and one rule for all propositions p and q:
- Axiom 1. p → (q → p).
- Axiom 2. (p → (q → r)) → ( (p → q) → (p → r)).
- Axiom 3. ¬¬p → p.
- Deduction Rule: Modus Ponens. From ‘p’ and ‘p → q’, deduce ‘q’.
The third axiom is also called the law of double negation elimination, and it is equivalent to the more famous law of excluded middle ‘p ∨ ¬p.’
These few axioms and rules are all we need to prove all propositional tautologies of classical logic. No matter how complicated the tautology, there will be a proof! Imagine you want to prove the tautology that ‘(q → p) → (q → p).’ That works like this:
- Instance of Axiom 1. p → (q → p).
- Instance of Axiom 2. (p → (q → p)) → ((p → q) → (p → q)).
- Modus Ponens on lines 1,2: (p → q) → (p → q).
And there we are. We proved the tautology in just three steps!
While such a formal proof may seem cumbersome and tedious, formal proof systems are indispensable for mathematical logic because they provide a way to treat proofs as mathematical objects.
Now, you might wonder: Do we really need all those three axioms for classical logic? Couldn’t we prove the law of double negation elimination from the first two axioms and the deduction rule?
Just as in the case of Euclid’s parallel postulate, this is impossible. But how can we show that? The trick is to find a model for propositional logic that satisfies the first two axioms and the deduction rule but not the third.
So let’s invent such a model. We will consider three truth values: true T, false F and intermediate I. In our model, every proposition will have one of these three truth values. The truth value of more complex propositions can then be calculated using the truth table in the photo.
The truth value of ¬p is defined as the truth value of ‘p → F’.
For example, if the truth value of p is I, then the truth value of ¬p must be ‘I → F’. According to the table, that’s F. So if p is intermediate, then ¬p is false.
Can we show that this model satisfies the first two axioms and the deduction rule but not the third?
To see that the rule of modus ponens is true in our model, assume that both ‘p’ and ‘p → q’ have truth value T. We have to show that ‘q’, as well, has truth value T. Imagine that ‘q’ does not have truth value T but rather truth value I or F. If it has value I, then ‘p → q’ has value I. And if it has value F, then ‘p → q’ has value F. Both contradict our assumption that ‘p → q’ has truth value T. Therefore, ‘q’ must have truth-value T as well.
This shows that the deduction rule is true in our model. Whenever ‘p → q’ and ‘p’ are true, then ‘q’ must be true as well.
What about the axioms? The first axiom, ‘p → (q → p)’, can be shown true in the model as follows.
If ‘p’ has truth-value T, then ‘q → p’ has truth-value T (no matter what ‘q’ has, check the table!) — but then ‘p → (q → p)’ will be true T.
If ‘p’ has truth-value I, then ‘q → p’ will have truth-value either I or T (that’s the second column of the truth table). But then it follows that ‘p → (q → p)’ will be true T because that’s just ‘I → I’ or ‘I → T’.
Finally, if ‘p’ has truth-value F, then ‘p → (q → p)’ is of the form ‘F → (q → p)’. According to the truth table, that’s always true.
The second axiom can be shown true in a similar way but no worries, I am not going to bore you with that!
What’s interesting, however, is that the law of double negation elimination fails in this model. It’s not the case that ‘¬¬p → p’!
Why not? Whenever ‘p’ has truth-value I, then ‘¬p’ is F and ‘¬¬p’ must be T. So ‘¬¬p → p’ is ‘T → I’ but that’s just I.
So ‘¬¬p → p’ is not a tautology in this model: there are instances in which it is not true. For this reason, also the law of excluded middle must fail in our model.
So what have we got? We have shown that the law of double negation elimination or the law of excluded middle are necessary axioms for classical propositional logic!
Just like as in the case of geometry, the other axioms do not suffice to prove that double negation elimination must be added. This independence result shows that we must have a law of double negation elimination.
Conclusion
Logicians use models and formal proofs to reason about whether or not some sentence can be proved from others. I just presented you a tiny example above but essentially the same ideas, though much more intricate, are used to prove the independence of the continuum hypothesis and other fascinating results in mathematical logic.
For more on the continuum hypothesis, take a look here. Or click here for more on the law of excluded middle. More stories can be found on my profile.
