3

Suppose I have a statement $S$ along with two contidtional proofs:

  1. A proof that the Riemann hypothesis implies $S$, and
  2. Another proof that the negation of the Riemann hypothesis also implies $S$.

Can we say I proved $S$? Or did I leave out the possibility that the Riemann hypothesis is undecidable? Also it would bw interesting to know about instances of this (one might call it "undecidability dilemma").

Dominic van der Zypen
  • 2,740
  • 3
    Maybe this depends more on Excluded Middle. This is widely used in papers. – joro Mar 26 '16 at 08:40
  • @joro : are you saying that we need first a proof that $P \lor \lnot P$ ? for example, if instead of the RH we were considering the sentence "$P_{s_0} : \zeta(s)$ has a zero at $s=s_0$" then it is clear that for any fixed $s_0 \in \mathbb{C}$ : $P_{s_0}\lor \lnot P_{s_0}$ (why ? because $\zeta(s)$ is meromorphic ? because we have an algorithm for localizing the zeros of $\zeta$ ? ...) – reuns Mar 26 '16 at 21:43
  • but the sentence "$S_\sigma $ : $\zeta(s)$ has no zero for $Re(s) > \sigma$" is maybe undecidable. hence, if we had a proof of $(S_\sigma \lor \lnot S_\sigma) \implies P$, would we have a proof of $P$ ? – reuns Mar 26 '16 at 21:45
  • If my memory serves me, some highly nontrivial result was proved exactly this way. Maybe some expert in number theory reading this post knows the details. – Martín-Blas Pérez Pinilla Mar 31 '16 at 16:57

3 Answers3

7

Even if $P$ is independent of your base theory $T$, this is still a valid proof (assuming classical logic, as mentioned by joro).

Given any model of $T\cup\{P\}$, we know that $Q$ holds by the first proof. Given any model of $T\cup\{\lnot P\}$, we know that $Q$ holds by the second proof. In any model of $T$ either $P$ holds or $\lnot P$ holds. So in every model of $T$ we know that $Q$ holds. Therefore $T$ proves $Q$.

And of course this is a long way for a short drink of water. We can take a shorter, syntactic route. $T$ proves that: $P\rightarrow Q$ and $\lnot P\rightarrow Q$, therefore it proves that $P\lor\lnot P\rightarrow Q$, and therefore $T$ proves $Q$.

Asaf Karagila
  • 393,674
6

Maybe what you are confused about is the following:

If you showed that a proof of the Riemann hypothesis would give you $S$ and that a proof of the negation of the Riemann hypothesis would also give $S$, then you cannot conclude that $S$ is true.

Asvin
  • 8,229
  • 3
    You don't say why "you cannot conclude that $S$ is true" (which really is the question asked). As far as I understand Asaf's answer tells the opposite, so you need to explain more. Or I'm missing something. –  Mar 26 '16 at 11:33
  • The problem is that the two cases I have listed don't cover all possibilities. If RH were undecidable, then the above statement is vacuous and you cannot drive any conclusion about S. – Asvin Mar 26 '16 at 11:35
  • 1
    Well ok, but what about Asaf's answer? –  Mar 26 '16 at 11:38
  • 3
    The difference is that he is talking about the truth value of RH, I am talking about the truth value there exists a proof of RH and the truth value of these exists a proof of Negation of RH. These are different things. – Asvin Mar 26 '16 at 11:39
  • 2
    @Loïc: The point is that if the Riemann hypothesis is independent (of $T$) then it has neither a proof nor a disproof. So the implications are both vacuous and you can't use them to deduce $S$. In contrast if you said that you have a proof for RH, then you can prove $S$; and if there does not exist a proof for RH, then you can also prove $S$... then you fallback to my answer. – Asaf Karagila Mar 26 '16 at 12:28
  • 1
    Also, it might worth pointing out that as far as RH goes, it is equivalent to a $\Pi_1$ statement in PA; so if it is not true, its negation is a true $\Sigma_1$ statement, and thus provable from PA. It does not mean that ZFC must prove RH; but it means that if you don't have a proof or disproof, then it has to be the case that RH is true. – Asaf Karagila Mar 26 '16 at 12:36
  • @AsafKaragila - I don't have any background in logic or model theory so I am way out of my element here but doesn't what you just asserted imply that a proof that RH is independent of ZFC would constitute a proof of RH? (If yes, it even seemed like you are saying you can replace ZFC with PA in that statement??) – Ben Blum-Smith Mar 26 '16 at 14:17
  • @benblumsmith: Almost. If you cannot refute it in PA (or ZFC), then it is necessarily true in the standard model (and therefore true in the sense that RH should be true or false). The point is that if its negation is true, then this fact is in fact provable from PA. So an independence can only occur if the failure is in some nonstandard model. You could also check this question and its answers: http://mathoverflow.net/questions/79685/can-the-riemann-hypothesis-be-undecidable – Asaf Karagila Mar 26 '16 at 14:23
  • Ok, thank you all for the clarifications. –  Mar 26 '16 at 14:46
  • Good point Ashwin. I think I understood Asaf's answer, but your considerations made me less sure... – Dominic van der Zypen Mar 27 '16 at 07:36
1

Decidability has nothing to do with it. Issues of decidability in the context of classical logic involve propositions that cannot be proved from the axiomatic system you are working in. For example if you work in ZFC you can't prove either the continuum hypothesis or its negation (by the work of Goedel and Cohen).

In classical logic "P or not P" is always true and therefore your $S$ is indeed proved to be true.

The intuitionists will not accept your argument but then again there are many arguments they won't accept, such as the proof of the extreme value theorem.

Mikhail Katz
  • 42,112
  • 3
  • 66
  • 131