Odd proof method

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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.