Validity of proof by contradiction on the contrapositive

logicpropositional-calculussolution-verification

Given $a, b \in \mathbb{R},$ prove $ab = 0 \implies (a=0 \lor b=0).$

Is the following valid?


Proceed by contraposition. The contrapositive of $ab = 0 \implies (a=0 \lor b=0)$ is $(a \neq 0 \land b \neq 0) \implies ab \neq 0.$

Proceed by contradiction. Suppose $a \neq 0 \land b \neq 0$ and, for contradiction, assume that $ab = 0.$ Taking $(ab = 0) \times \frac1a$ gives $b = 0$, which contradicts the supposition that $b \neq 0.$ Therefore $ab \neq 0,$ thus $(a \neq 0 \land b \neq 0) \implies ab \neq 0.$

Therefore, by contraposition, $ab = 0 \implies (a=0 \lor b=0).$

Best Answer

Doing it as a proof by contradiction is completely unnecessary. You never use the assumption that $b\neq 0$ except to contradict your conclusion that $b=0$. In essence, you are doing a "fake proof by contradiction" of the contrapositive, by doing a contrapositive proof of the contrapositive. In fact, you are doing a direct proof in the first place!

Why do I say that? You start from $ab=0$. Then you say: "if $a\neq 0$, then multiplying by $\frac{1}{a}$ we conclude $b=0$"; fine up to here, but then you just use that conclusion to contradict your assumption that $b\neq 0$. Why bother? Just conclude that if $ab=0$ and $a\neq 0$ , then $b=0$...

And then you are done! Why? Because $P\vee Q$ is equivalent to $\neg P\implies Q$; so by proving that $\neg(a=0)\implies b=0$, you've actually proven that $(a=0)\vee (b=0)$... which is what you wanted to prove in the first place...

Or alternatively: assume $ab=0$. If $a=0$, you are done. If $a\neq 0$, then... and you put down your argument. So you've proven that either $a=0$ or $b=0$. No need for contrapositives, contradictions, or a double secret probation reversal...