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.

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?

share|improve this question
add comment

3 Answers 3

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.