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.

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?

share|improve this question
    
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. –  MJD Mar 12 at 15:48
1  
$\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. –  Quincunx Mar 12 at 18:08
    
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. –  thethuthinnang Mar 13 at 0:12

5 Answers 5

up vote 10 down vote accepted

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.

share|improve this answer
    
This is a special case of proof by cases. –  thethuthinnang Mar 13 at 15:19

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.

share|improve this answer

"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$ ?

share|improve this answer
2  
"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$) –  JiK Mar 12 at 16:04

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

share|improve this answer
3  
I understood nothing. –  Anonymous Pi Mar 12 at 18:59

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.

share|improve this answer

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.