Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it possible to prove that you can't prove some theorem? For example: Prove that you can't prove the Riemann hypothesis. I have a feeling it's not possible but I want to know for sure. Thanks in advance

share|improve this question
    
    
Besides the usual examples in ZF mentioned in the answers, if you have access to a university library, you may want to look for the following paper by Stephen G. Simpson: "Unprovable theorems and fast-growing functions" in pp. 359-394 of the book "Logic and Combinatorics", Contemporary Mathematics, Volume 65, American Mathematical Society, 1987. The book in general, and that paper specifically, deals with examples of results that cannot be proved in the usual theories where you'd formulate/investigate them. Also, take a look at Harvey Friedman's page; he has worked extensively on this topic. –  Andres Caicedo Oct 7 '12 at 15:57
    
@Andres My post here contains a link to the full text of Simpson's article. –  Bill Dubuque Oct 7 '12 at 16:48
    
I think using the word theorem in the first place implies that a proof exists. –  wim Oct 8 '12 at 0:59

6 Answers 6

up vote 3 down vote accepted

Probably the term you're looking for is undecidable: we say a conjecture is undecidable, relative to some formal system, if neither it or its negation can be proven within that system.

Yes, it is possible to prove something undecidable, and it has been done (not with the Riemann hypothesis in particular, of course, but with other conjectures).

  • Goodstein's theorem is not decidable in Peano arithmetic (though it is provable in ZFC set theory).

  • The continuum hypothesis is known to be undecidable in ZFC set theory. In 1940, Kurt Gödel proved that the continuum hypothesis cannot be refuted from the ZFC axioms; in 1963, Paul Cohen proved that it cannot be proven from those axioms either.

  • In fact, Gödel proved in 1931 that for any formal system rich enough to intepret Peano arithmetic, there is a proposition that cannot be proven or refuted in that system. Moreover his proof is constructive: for any system you devise that includes natural number arithmetic as we know it, I can give you a specific proposition that is undecidable in that system.

share|improve this answer

I suppose it has been proved that neither the continuum hypothesis nor its negative can be proved from the ZFC. Hence, yes, it is possible to prove that something cannot be proved.

share|improve this answer
2  
PA has nothing to do with CH. –  Asaf Karagila Oct 7 '12 at 21:46
    
JohnB probably meant to say ZFC, or the axioms of set theory. –  MikeC Oct 7 '12 at 22:52
    
Sorry, it's several years now that I read about it. Thanks for correcting. –  JohnB Oct 8 '12 at 5:34

From the time of Euclid on, there was interest in showing that Euclid's Fifth Postulate follows from the rest of Euclid's axioms. (Roughly speaking, the Fifth Postulate says that through a given point there is a unique line parallel to a given line.)

Finally, in the $1830$'s, Bolyai and Lobachevsky independently showed that the Fifth Postulate does not follow from the rest, by discovering hyperbolic geometry. To use modern language, they found a model of the remaining axioms in which the Parallel Postulate fails.

The work of Bolyai and Lobachevsky is, arguably, the first independence result. It may have helped to change the notion of what one means by an axiomatic system.

share|improve this answer

Another simple example. In the theory of groups, it is impossible to prove the commutative law. To see this, we exhibit a non-commutative group.

In your example, it probably is technically senseless to say "the Riemann Hypothesis is not provable". Instead you include the axiom system you have in mind, for example maybe you want to say "the Riemann Hypothesis is unprovabie from the Zermelo-Frenkel axioms of set theory".

share|improve this answer

If I understand you correctly then yes.

Of course, the very word "theorem" cannot be used here because the word theorem itself means a proven result. What you meant probably was do their exist assertions regarding which it can be proven that they are not provable within the confines of our mathematical axioms. Yes there do. For example you can't prove the axiom of choice in Zermelo Fraenkel set theory.

share|improve this answer
    
About the use of the word "theorem" see my answer to the link in the comment to the main question: math.stackexchange.com/questions/183980/… –  Asaf Karagila Oct 7 '12 at 14:54
    
Thanks for the link. –  Shahab Oct 7 '12 at 15:02

Yes. Godel's incompleteness theorem tells us that if a theory (collection of axioms) is "simple enough" to describe then it cannot prove or disprove everything, unless it is inconsistent.

Where simple enough means that we can write a computer program which will tell us whether or not something is an axiom in our theory or not.

In addition Godel's completeness theorem tells us that if a theory is consistent then it has a model. If we have a theory $T$ and we can find a model of $T$ where $\varphi$ holds, and another model where $\lnot\varphi$ holds, then we have proved that we cannot prove $\varphi$ from the axioms of $T$.

Such method was used to show that the continuum hypothesis cannot be proved from the axioms of ZFC; and that the axiom of choice cannot be proved nor disproved from the axioms of ZF.

One simpler example for this is that you cannot prove solely from the properties of a field that there exists a square root for the number $2$. In the field $\mathbb Q$ such number does not exist, whereas in $\mathbb R$ it does.

share|improve this answer
    
Can you give some reference to the proof that it cannot be proven that an arbitrary field will have a square root for 1+1 or not? Thanks. –  Shahab Oct 7 '12 at 14:40
2  
@Shahab: Yes. The Greeks proved that $\sqrt 2\notin\mathbb Q$; whereas $\sqrt2\in\mathbb C$ since it is the root of the polynomial $x^2-2$. –  Asaf Karagila Oct 7 '12 at 14:42
2  
If something is provable then it is true in all models. $\mathbb{Q}$ is a model of the theory of fields and does not have $\sqrt{2}$, so the existence of $\sqrt{2}$ cannot be proved. –  Zhen Lin Oct 7 '12 at 14:46
2  
@Shahab: If you could prove that $\sqrt 2$ exists, it would be true in $\mathbb Q$; if you could prove it doesn't exist it would be true in $\mathbb C$. –  Asaf Karagila Oct 7 '12 at 14:46
    
yes, I just got it. Thanks. –  Shahab Oct 7 '12 at 14:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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