How do we prove that something is unprovable?

Question

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 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.

Answer 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.

Answer 3

Your question is partially based on an error of terminology. We don't speak of unprovable theorems - as you say, being a theorem implies having a proof. The correct thing to speak of is unprovable statements or unprovable assertions.

That said, it is possible for a statement to be a theorem in one context but not in another, in which case you could say that, in the second context, it is an unprovable theorem. Example: All proofs of the Pythagorean Theorem rely essentially on the Parallel Postulate; so if you try to prove what you can in geometry with the Parallel Postulate omitted (this is called 'absolute geometry'), then the Pythagorean Theorem becomes an unprovable theorem within that context. (this is about the only situation where I think the phrase 'unprovable theorem' is the natural choice)

Answer 4

You have already received some excellent responses, but I just wanted to clarify a few things that I feel may have not received the attention that they require.

For instance, you mentioned

[...] definitions, axioms, conjectures, lemmas and theorems.

It is important to realize that when setting up a mathematical theory, there are really only two things that matter:

1. Statements we define to be true (or, equivalently, false).
2. All other statements, that can either be true or false, or neither; these require a proof.

Definitions and axioms are both a form of type 1. They are quite closely related as axioms usually define some important concept and definitions usually specify that we call $Z$ a zork if and only if $Z$ has certain properties. For example, consider the statments

Every natural number $n$ has a successor $S(n)$.

An even number is of the form $2n$, for some $n \in \mathbb N$.

Are thesee definitions of the successor function and even numbers, respectively? Or are they axioms in a theory about natural numbers?

Similarly the distinction between theorems, conjectures, lemmas etc. is mostly an emotional distinction: they help the reader of a book or article distinguish between the "important" results and the statements that are more like tools and need to be proven only to get an interesting result.

Now on to (un)provable. There are formal definitions of a proof in mathematical logic, but let's not go into them. The main point is that a proof is a logical sequence of steps, starting from the assumptions of a theorem (or lemma, or conjecture, ...), ending with the conclusion of the theorem, and where every step is justified either by an axiom or by a previously proven theorem:

Theorem: (If conditions then) conclusion

Note that the conditions part can be omitted if the conclusion is always true (a tautology).

The "proof" for an axiom is then quite trivial: there are no preconditions and the single step of the proof consists of invoking the axiom.

For a lot of statements, we can usually show that they are true or false, given some set of axioms (and we usually include a set of proven theorems as well that we agree on, for example, you don't invoke Peano's axioms every time you prove something about a natural number). Showing that the theorem is false usually involves finding a counter example, or - more formally - showing that the "anti"theorem

Theorem: (If conditions then) not (conclusion)

is true, again by a proof in which each step is nicely justified.

So for example, we can prove the theorem "6 is even" to be true as follows:

• $6 = 2 \cdot 3$
• So $6 = 2 \cdot n$ for $n = 3$.
• This satisfies the definition of an even number (or, if you have set up things that way: This is an even number by the axiom "Even number").

Similarly we can prove that 7 is not even by showing that there is no number $n$ such that $7 = 2 \cdot n$ (the only solution is $n = 3.5$ and that is not a natural number).

However, suppose that I want to prove "4 is a nortial number". Is that theorem true or false in our simple theory with one axiom about even numbers? No matter what way you invoke the axiom, or any theorem you can prove from it, you cannot show that 4 is a nortial number. However, similarly you cannot prove that "4 is not a nortial number" so the theorem can also not be false. Clearly, your theory does not have enough axioms to be able to reach either conclusion. This is what we mean by "an unprovable statement".

Answer 5

"Too obvious" doesn't exist in mathematics, we choose to agree about some axioms to build a theory. Axioms mustn't imply each other and mustn't be contradictory.

If a theorem cannot be proven nor denied by the axioms that means it goes beyond boundaries of that theory. So you can join that theorem as another axiom to build more complex theory, or you can join its negation as an axiom to build another theory

In addition, how can be proven that a theorem isn't implied nor denied by axioms?? That would be something like if you don't get contradiction by joining the theorem nor by joining its negation to the set of axioms. Just pass trough whole set of objects you use in the theory... :P

Answer 6

A theory is created from building blocks called axioms which are accepted to be true. The axioms need not and cannot be proven (not because they are "too obvious", but because they are independent of the other axioms). Anyway, you have to prove that the set of axioms forming your theory is not contradictory.

Since Gödel, we know that a (rich) theory cannot prove all the logical propositions expressible in its frame, so that some propositions will require extra axioms, hence a stronger theory, to become theorems.

Simplistically speaking, propositions can be shown "unprovable" when their meaning is equivalent to "I am not provable in the frame of the theory". Then if they were provable, they would not be provable, and conversely.

Answer 7

It can make sense to call something an "unprovable theorem" if what is meant is that the theorem is unprovable in a given formal system or from a given set of axioms. For instance Gödel's formal statement which informally said "I cannot be proven" is unprovable in the formal system he used, but he also proved it using more powerful, informal tools - thus making it a theorem.

Answer 8

The most common way (AFAIK) to establish $A \not \vdash B$ is to find some statement $X$ such that:

• $A,~X \vdash \lnot B$
• $A \land X$ is consistent

Then you can conclude $A \not \vdash B$ because constructively if $A \vdash B$ then $A ,~ X \vdash B$ then $A ,~ X \vdash B \land \lnot B$ which contradicts the assumption that $A \land X$ are consistent.

For example, if you wanted to show that from "$n$ is divisible by $3$" you cannot prove "$n$ is divisible by $6$" you do the obvious thing of pointing out the $X$ of $n = 9$. Since

• $3|n , ~ n = 9 \vdash \lnot 6|n$
• $(3|n) \land (n = 9)$ is consistent

So $3|n \not \vdash 6|n$. This simple approach can get very complex, mainly because establishing $A \land X$ as being consistent can be extremely demanding, usually an informal model theoretic approach is used for this.

---

It is also a well known way to establish undecidability, if you can find $X_1$ and $X_2$ such that:

• $A, ~ X_1 \vdash B$
• $A, ~ X_2 \vdash \lnot B$
• $A \land X_1$ is consistent
• $A \land X_2$ is consistent

Then for the same reason $A \not \vdash B$ and $A \not \vdash \lnot B$, so $B$ is independent of $A$.