14
$\begingroup$

I read on the wikipedia article for the Riemann Hypothesis that some theorems have been proved by assuming the hypothesis to be true and then false and proving the certain theorem from both cases. I.e. proving $P\Rightarrow Q$ and $\neg P\Rightarrow Q$ and then infering $Q$.

This method made me curious about another possible method. What if you prove $P \Leftrightarrow Q$ and then $\neg P \Rightarrow Q$, doesn't that prove both $P$ and $Q$? Is that logically sound? If so it would be an interesting proof method because if I proved $P \Leftrightarrow Q$ I would've thought nothing more could be gleaned from the relation of their truth values, but if this is true checking $\neg P\Rightarrow Q$ could prove both theorems.

If this makes any sense are there any examples of any proofs like this?

|cite|improve this question
$\endgroup$
  • $\begingroup$ It's fairly common to use $(\lnot P\implies P)\implies P$ (or the reverse, $(P\implies\lnot P)\implies\lnot P$), but I'm not sure if you would consider that to be an example of the method you describe. But it's what you get if you take $Q=P$ in your method. $\endgroup$ – MJD Mar 12 '14 at 15:48
  • 1
    $\begingroup$ $\neg P\Rightarrow Q = \neg\neg(\neg P\Rightarrow Q) = \neg(\neg P\land\neg Q) = P\lor Q$. This means that either $P$ or $Q$ is true, so because $P\Leftrightarrow Q$, both must be true. $\endgroup$ – Justin Mar 12 '14 at 18:08
  • $\begingroup$ I believe that any proof that uses this strategy (the first listed) can be simplified (i.e. removing the dead logic (analogous to dead code in programming)). I would like to see a simple demonstration of this strategy. $\endgroup$ – AbleArcher Mar 13 '14 at 0:12
9
$\begingroup$

This is a standard method of proof called proof by cases (or proof by exhaustion). It works for any finite number of cases. Suppose you know that $P_1$ or $P_2$ or ... $P_n$ must be true, i.e. at least one of the $P_i$ is true. If you can prove that $Q$ is true in each case (assuming each of the $P_i$ in turn is true), then $Q$ must be true.

In your example, you have two cases: (1) RH is true, (2) RH is false.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is a special case of proof by cases. $\endgroup$ – AbleArcher Mar 13 '14 at 15:19
5
$\begingroup$

This proposal seems like an amazingly roundabout method of proof. The theorems that led to this question use RH (and $\neg$ RH) in important but not critical ways. For example, we need to bound the growth of some function; both RH and $\neg$ RH provide different ways to bound that growth. If we could find a way to bound the growth using neither, then we would have a proof independent of RH.

|cite|improve this answer
$\endgroup$
4
$\begingroup$

"Formally" it works.

From the two proofs [in all the argument, I left implicit a "common set" of assumptions : $\Gamma$] :

$\vdash P \rightarrow Q$

and

$\vdash \lnot P \rightarrow Q$

by the tautology :

$\vdash (P \rightarrow Q) \rightarrow [(\lnot P \rightarrow Q) \rightarrow Q]$

we may have, by modus ponens twice :

$\vdash Q$.

Now, with the additional proof :

$\vdash Q \rightarrow P$

with the above result, by modus ponens, we may conclude also :

$\vdash P$.

The only doubt I have is : why, in general, we may expect taht it is "easier" to produce three proofs (of $P \rightarrow Q$, $\lnot P \rightarrow Q$ and $Q \rightarrow P$) instead of two : $\vdash Q$ and $\vdash P$ ?

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ "The only doubt I have is : why, in general, we may expect taht it is "easier" to produce three proofs (of $P \rightarrow Q$, $\lnot P \rightarrow Q$ and $Q \rightarrow P$) instead of two : $\vdash Q$ and $\vdash P$?" Well, the interest in the question starts from the fact that it is sometimes easier to produce two proofs ($P\rightarrow Q$ and $\lnot P \rightarrow Q$) instead of one ($\vdash Q$) $\endgroup$ – JiK Mar 12 '14 at 16:04
1
$\begingroup$

If (p⇔q), then (p→q), as well as (q→p). Thus, if (p⇔q), and ($\lnot$p→q), since [(p→q)→(($\lnot$p→q)→q)] is a theorem or axiom in any complete system of propositional calculus, we can obtain "q". Since we have (q→p) and "q", we can also obtain "p" by detachment. Therefore, if (p⇔q) and ($\lnot$p→q), then, yes, it comes as valid to infer both "p" and "q".

Or, in Polish notation:

If Epq, then Cpq, as well as Cqp. Thus, if Epq, and CNpq, since CCpqCCNpqq is a theorem or axiom in any complete system of propositional calculus, we can obtain "q". Since we have Cqp and q we can also obtain "p" by detachment. Therefore, if Epq and CNpq, then, yes, it comes as valid to infer both "p" and "q".

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ I understood nothing. $\endgroup$ – Anonymous Pi Mar 12 '14 at 18:59
0
$\begingroup$

A standard example of this method of proof would be to show something like this

Theorem: The square of every non-zero real number is greater than $0$.

Let's say you have already proved that the product of two positive numbers is positive.

Then (using the letters in the original question) : $P$ is the statement "$x$ is positive" and $Q$ is the statement "$x^2$ is greater than 0".

Now "$P \implies Q$" is a special case of your earlier theorem, so you know it's true.

To prove "$\lnot P \implies Q$", you could use the commutativity of multiplication.

Say $y$ is negative. Then there is some positive number x so that $y = (-1)x$.

Then $y^2 = (-1)x(-1)x = (-1)(-1)(x^2) = x^2$. Since $x^2$ is positive, you've proved that $y^2$ is positive.

So, in this case, you've proved that $P \implies Q$ and $\lnot P \implies Q$. Therefore, $Q$ is true.

Sorry, though, I don't have a proof of the Riemann Hypothesis.

I use this example in my discrete math classes as an example of proof by cases.

|cite|improve this answer
$\endgroup$

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.