5
$\begingroup$

Suppose one wants to prove $P \implies Q$ by contradiction. In general, we will probably have the following, $P_1, \dots, P_n \implies Q$. Suppose we want to prove this by contradiction. Then is it better to get a contradiction via the following: $P_1, \dots, P_n, \neg Q\implies Q$? Or would is be better to get a contradiction via $P_1, \dots, P_n, \neg Q\implies \neg P_i$ for any $i \in \{1, \dots , n \}$? Is the second proof "stronger" than the first proof?

For the second proof, the assumption of $\neg Q$ could potentially come up with negations of all the $P_{i}$'s right?

3 Answers 3

8

More generally, if one wishes to prove $P \Rightarrow Q$ by contradiction (if $P$ is composed of many statements, just lump them all together as $P$), one seeks to show that assuming $P \wedge \neg Q$ causes one to conclude any false or contradictory statement. The conclusion need not have anything to do with the original $P$ and $Q$.

If assuming $P \wedge \neg Q$ causes you to conclude that $1 = 0$, then you have a successful proof of $P \Rightarrow Q$ by contradiction, even if $P$ and $Q$ have nothing to do with the natural numbers.

0

Yes, I agree. But since you are asking about which of the two is stronger. I think the answer is relative to the statement you wish to prove. But structure- wise, I think the first one is less tedious than the second because negating all P_i 's would require more time than just using all $P$ and $ \sim Q $ to prove that it is indeed $Q$.

0

In general, I think it would be easier to go for what Austin Mohr has suggested, e.g. show that $P \wedge \neg Q$ causes one to conclude a false or contradictory statement, and so therefore $P \implies Q$ must be true.

Here is an example of how this can be used:

Prove that in a commutative ring $S$, if $ab$ is a zero divisor then $a$ or $b$ is a zero divisor.

You want to prove $P \implies (Q \lor R)$. Assume that $P \wedge (\neg Q \wedge \neg R)$ is true, namely that $ab$ is a zero divisor and $a$ and $b$ are both not zero divisors. Then since $ab$ is a zero divisor, there exists $c \neq 0$ in $R$ such that $(ab)c = 0$. Now by the associative law this means $a(bc) = 0$. Now $a$ is not a zero divisor so we must have that $bc = 0$. However, $b,c \neq 0$ and so $b$ is a zero divisor of $c$ which contradicts our assumption on $b$. Similary one can derive a result that contradicts $a$ not being a zero divisor.

We have shown that $P \wedge (\neg Q \wedge \neg R)$ is ridiculous, so that $P \implies (Q \lor R)$ must be true.