6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Related: math.stackexchange.com/questions/183980/… $\endgroup$ – Asaf Karagila Oct 7 '12 at 14:53
  • $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Oct 7 '12 at 15:57
  • $\begingroup$ @Andres My post here contains a link to the full text of Simpson's article. $\endgroup$ – Bill Dubuque Oct 7 '12 at 16:48
  • $\begingroup$ I think using the word theorem in the first place implies that a proof exists. $\endgroup$ – wim Oct 8 '12 at 0:59
  • 2
    $\begingroup$ A theorem is not simply "provable" or "unprovable". It is always provable or unprovable relative to some set of axioms. Every theorem is provable if we take the theorem itself as an axiom. In some cases, when a theorem was not provable from a certain set of axioms, mathematicians simply assumed more axioms so that the theorem could be proved. $\endgroup$ – Carl Mummert May 29 '15 at 13:35
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Forcing_%28mathematics%29 looks like a technique for that $\endgroup$ – Ciro Santilli 新疆改造中心法轮功六四事件 May 4 '16 at 9:14
  • 1
    $\begingroup$ Important caveat: CH is independent of ZFC if ZFC is consistent. The reason this is important is that if you ever manage to prove in ZFC under no assumptions that some statement of ZFC is not provable, then you can also prove a contradiction in ZFC, and this fact is in fact witnessed by a program that maps any proof of the former into a proof of the latter! Similarly the Godel's incompleteness theorem as stated here is missing the same crucial condition. $\endgroup$ – user21820 Feb 13 '17 at 5:10
  • 1
    $\begingroup$ @user21820: Understood, though I'm tempted to counter by asking why you presume that ZFC is my preferred metasystem. If I'm living in e.g. Tarski-Groethendieck set theory, then I can just say "ZFC has models satisfying CH and models satisfying ¬CH" without qualifiers. But your point, that we can only prove consistency results for a (sufficiently interesting) formal system via a stronger formal system, is well taken. $\endgroup$ – user43623 Feb 24 '17 at 22:12
  • 1
    $\begingroup$ Oh I don't intend to imply that ZFC is your preferred meta-system; it isn't mine for that matter. It's just that current convention is to use ZFC as the meta-system. Also, while you are right that you could just work in a strong enough meta-system to be able to prove directly that CH is independent of ZFC, I feel you should state it in your post, because it's much more than assuming Con(ZFC). In any case, my caveat remains pertinent to your statement of Godel's incompleteness theorem, since as stated it applies to the meta-system itself, yielding a contradiction. $\endgroup$ – user21820 Feb 25 '17 at 6:23
14
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
7
$\begingroup$

Yes. Gödel's incompleteness theorem tells us that if a theory (collection of axioms) is "simple enough" and it can describe elementary arithmetic, 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 Gödel'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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shahab Oct 7 '12 at 14:40
  • 2
    $\begingroup$ @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$. $\endgroup$ – Asaf Karagila Oct 7 '12 at 14:42
  • 2
    $\begingroup$ 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. $\endgroup$ – Zhen Lin Oct 7 '12 at 14:46
  • 2
    $\begingroup$ @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$. $\endgroup$ – Asaf Karagila Oct 7 '12 at 14:46
  • $\begingroup$ yes, I just got it. Thanks. $\endgroup$ – Shahab Oct 7 '12 at 14:47
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – Asaf Karagila Oct 7 '12 at 14:54
  • $\begingroup$ Your last sentence is incorrect if you're working in ZFC, unless ZFC is itself inconsistent. See my comment. In particular, if ZFC proves "ZF does not prove AC" then ZFC proves "ZF is consistent" and hence by Godel's L you also get that ZFC proves "ZFC is consistent" and then by Lob's theorem you get that ZFC proves a contradiction. $\endgroup$ – user21820 Feb 13 '17 at 5:44
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ PA has nothing to do with CH. $\endgroup$ – Asaf Karagila Oct 7 '12 at 21:46
  • $\begingroup$ JohnB probably meant to say ZFC, or the axioms of set theory. $\endgroup$ – MikeC Oct 7 '12 at 22:52
  • $\begingroup$ Sorry, it's several years now that I read about it. Thanks for correcting. $\endgroup$ – JohnB Oct 8 '12 at 5:34
  • $\begingroup$ So many answerers here are making the same error... See my comment. $\endgroup$ – user21820 Feb 13 '17 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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