How do we prove that something is unprovable?

I have read somewhere there are some theorems that are shown to be “unprovable”. It was a while ago and I don’t remember the details, and I suspect that this question might be the result of a total misunderstanding. By the way, I assume that unprovable theorem does exist. Please correct me if I am wrong and skip reading the rest.

As far as I know, the mathematical statements are categorized into: undefined concepts, definitions, axioms, conjectures, lemmas and theorems. There might be some other types that I am not aware of as an amateur math learner. In this categorization, an axiom is something that cannot be built upon other things and it is too obvious to be proved (is it?). So axioms are unprovable. A theorem or lemma is actually a conjecture that has been proved. So “a theorem that cannot be proved” sounds like a paradox.

I know that there are some statements that cannot be proved simply because they are wrong. I am not addressing them because they are not theorems. So what does it mean that a theorem is unprovable? Does it mean that it cannot be proved by current mathematical tools and it may be proved in the future by more advanced tools that are not discovered yet? So why don’t we call it a conjecture? If it cannot be proved at all, then it is better to call it an axiom.

Another question is, how can we be sure that a theorem cannot be proved? I am assuming the description might be some high level logic that is way above my understanding. So I would appreciate if you put it into simple words.

Edit- Thanks to a comment by @user21820 I just read two other interesting posts, this and this that are relevant to this question. I recommend everyone to take a look at them as well.

Answer

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:

Wikimedia image: a triangle and a pair of diverging parallel lines inscribed on 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 T is unprovable then there is always some structure that satisfies the axioms of 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.

Attribution
Source : Link , Question Author : polfosol , Answer Author : John Gowers

Leave a Comment