161
$\begingroup$

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.

$\endgroup$
  • 12
    $\begingroup$ I was just thinking of preparing a talk on this very subject... $\endgroup$ – Stefan Mesken Nov 23 '16 at 12:06
  • 3
    $\begingroup$ "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. " Not at all. Often axioms are found to be redundant: Hilbert's axiom "$a \implies a$" was found to be redundant (in other words, it was provable from other axioms). Happens all the time. $\endgroup$ – DanielV Nov 23 '16 at 12:32
  • 7
    $\begingroup$ While logic is a rich subject, it tends to be very shallow in the parts where laypeople think there is depth (e.g. the notion of "axiom"). Most of the ideas you have about logic are not actually about logic, but instead ideas about philosophy or pedagogy $\endgroup$ – user14972 Nov 23 '16 at 15:18
  • 2
    $\begingroup$ Stefan's answer has identified that the main issue is your understanding of "unprovable", which is always relative. See math.stackexchange.com/a/1643073 for a brief outline of some points I wish to highlight, and math.stackexchange.com/a/1808558 for a little more on foundational aspects. $\endgroup$ – user21820 Nov 25 '16 at 7:02
  • 1
    $\begingroup$ 'Theorem" has 2 different meanings. In the usual language, it means "a proposition (of some importance) for which someone has given have an acceptable proof". It is a result obtained by people. In logic, it is a well-formed formula which happens to be true in some theory. When talking about "provability", you are in the second context; so theorem exists even without written proof, without the exsitence of proof, - and even without anybody stating them. $\endgroup$ – Michel Billaud Nov 25 '16 at 10:01
157
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ Nice answer. Do you want to add a few words about the third version of the parallel postulate, in which there are no parallel lines? $\endgroup$ – Scott Nov 23 '16 at 16:54
  • 2
    $\begingroup$ I learned a lot from all answers and I can't resist to emphasize that marking this answer as accepted doesn't imply undervaluing other ones $\endgroup$ – polfosol Nov 24 '16 at 7:08
  • 6
    $\begingroup$ It isn't quite true that Euclid proved his theorems from those 5 axioms alone. Over the years, mathematicians have identified several other assumptions he made without realizing it. These additional assumptions are also axioms of Euclidean geometry. One such assumption is that a line separates a plane into two halves, such that any line connecting points in one half with points in the other must intersect the first line. $\endgroup$ – Paul Sinclair Nov 24 '16 at 14:44
  • 2
    $\begingroup$ @HenningMakholm SGA/EGA make heavy use of Grothendieck universes, which can't be shown to exist in ZFC alone. Now, much of the material in SGA/EGA can be developed in ZFC, but the convenience of the Grothendieck universes approach makes me uneasy of claiming that ZFC is a foundation for all mathematics. $\endgroup$ – John Gowers Nov 24 '16 at 16:28
  • 2
    $\begingroup$ @JohnGowers: Grothendieck universes don’t need to be viewed as outside or beyond ZFC — they can reasonably be seen as just an extra existence assumption, the basic framework still remains ZFC. I work in type theory and constructive maths, so I’m a big proponent of alternatives, but I don’t think there’s any problem in saying that ZFC’s a satisfactory foundation for the vast majority of current mathematics (including EGA, SGA etc). $\endgroup$ – Peter LeFanu Lumsdaine Nov 28 '16 at 11:22
69
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ @polfosol Well, because the truth of a given statement - unless implied by your axioms - is debatable. You are free to add this true statement to your axioms (and we regularly do that), but to other people the negation may seem to be true and they might decide to accept that as an axiom. $\endgroup$ – Stefan Mesken Nov 23 '16 at 12:59
  • 1
    $\begingroup$ @polfosol I myself don't consider any statement to be true (in an absolute sense) - at least I think I don't. Rather I work under the reasonable assumption that they are not self-contradictory and try to figure out what their consequences are. $\endgroup$ – Stefan Mesken Nov 23 '16 at 13:00
  • 1
    $\begingroup$ @polfosol Because - thus far - set theory has been most successful (or unfortunate - depending on your point of view) in determining natural, unprovable statements. However, there are other examples. See for example Goodstein's Theorem. $\endgroup$ – Stefan Mesken Nov 23 '16 at 13:10
  • 1
    $\begingroup$ When you consider whether A is a "natural" set of axioms, what do you mean by "natural"? $\endgroup$ – Matt Gutting Nov 23 '16 at 14:34
  • 3
    $\begingroup$ @Stefan Strictly speaking, other theories have been much more successful than set theory for determining natural unprovable statements. For example, the statement '$G$ is abelian' is undecidable in the theory of groups. The point is that when we say undecidable, we usually mean undecidable in set theory , so the natural examples will also come from set theory. $\endgroup$ – John Gowers Nov 23 '16 at 15:15
27
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ +1 and thanks for an easy to follow example of unprovable theorems. Is it worked out somewhere? $\endgroup$ – draks ... Mar 15 '17 at 6:52
13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What is a nortial number? $\endgroup$ – Ole Petersen Nov 28 '16 at 9:36
  • $\begingroup$ I have no idea :) $\endgroup$ – CompuChip Nov 28 '16 at 9:56
  • $\begingroup$ Your answer is pretty good, but like many others, you overlook the importance of "undefined concepts" in definitions. In set theory, what is an element? Does an element exist? What is "membership"? In geometry, we have a choice of a new undefined concept, "sense" referring to clockwise or counterclockwise, or creating a new axiom related to a line partitioning the real projective plane. When you try to define an undefined concept, you generally do so in other terms that lead back to the thing you are trying to define. $\endgroup$ – richard1941 Nov 29 '16 at 19:31
9
$\begingroup$

"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

$\endgroup$
  • 6
    $\begingroup$ "we choose to agree about some axioms to build a theory." To be historically accurate, we usually know the theorems we want to prove long before anyone proposes a set of axioms to support them, for almost any theory you will ever find. "Axioms mustn't imply each other and mustn't be contradictory." Axioms often are found to imply each other, but fortunately are not often found to be contradictory. $\endgroup$ – DanielV Nov 23 '16 at 13:09
  • $\begingroup$ @DanielV You're right, this was said for an imagined perfectly defined theory. And of course we choose axioms so to satisfy a wanted purpose $\endgroup$ – Djura Marinkov Nov 23 '16 at 14:51
  • $\begingroup$ Note that In set theory we prove that Zermelo's and axiom of choice are equivenent; each implies the other. $\endgroup$ – richard1941 Nov 29 '16 at 19:38
  • $\begingroup$ +1 how large will these sets of theorems grow when you keep on joining theorems that are currently beyond the boundaries? $\endgroup$ – draks ... Mar 15 '17 at 6:50
  • $\begingroup$ @draks... I guess as large as your imagination reaches $\endgroup$ – Djura Marinkov Mar 21 '17 at 12:08
6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ There are rich and complete theories - take for example the theory of $H_{\omega_{1}}$. The point of Gödel's theorem is, that those cannot be recursively enumerable. $\endgroup$ – Stefan Mesken Nov 23 '16 at 22:18
  • $\begingroup$ @Stefan: I don't think that this is on the level that the OP expects. $\endgroup$ – Yves Daoust Nov 23 '16 at 22:20
  • 2
    $\begingroup$ Sure. The reason for my comment is that people often get Gödel's Incompleteness Theorem wrong - which trained me to be very sensitive about its statement (-; $\endgroup$ – Stefan Mesken Nov 23 '16 at 22:23
  • $\begingroup$ Off topic a bit, but is there a minimal axiomatic structure that contains unprovable statements? is there a maximally complex axiomatic structure that contains NO unprovable statements? $\endgroup$ – richard1941 Nov 29 '16 at 19:40
  • $\begingroup$ @richard1941 I think you would want to examine philosophy.stackexchange.com/questions/15525/… carefully. And then try to prove maximality or minimality. Since all of the systems I know of are amenable to various axiomatic formulations; you probably need to specify minimal and maximal. $\endgroup$ – rrogers Nov 30 '16 at 18:40
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There is some circularity in this answer. The claim "$A \land X$ is consistent" is equivalent to claiming the unprovability of inconsistencies. This is unavoidable. Unprovability, like many other things in logic, is never created, only propagated. $\endgroup$ – DanielV Oct 12 '18 at 11:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.