📂Set Theory

Mathematical Logic Proof by Contradiction

Law ¹

$$ (p \land \lnot q) \to c \iff p \to q $$

---

• $c$ implies a contradiction.

Explanation

Reductio ad absurdum or proof by contradiction is a proof technique that is widely used throughout mathematics. However, those who encounter this method for the first time may find the term unfamiliar and may resist it. Or there might be people who, although they have become accustomed to it, do not understand how it works.

Let’s try to understand proof by contradiction by reading the following:

• (1) The conclusion $q$ is either true or false. This is obvious due to the law of the excluded middle².
• (2) However, if $\lnot q$ is true and leads to a contradiction, we can at least conclude that $\lnot q$ cannot be true.
• (3) As stated in (1), since $q$ is either true or false, if $\lnot q$ is false, then $q$ must be true.
• (4) Therefore, $p \to q$.

If this is difficult to understand, let’s check with an example unrelated to math:

• $p$: I have two arms.
• $q$: I have at least one arm.
• $p \to q$: If I have two arms, I have at least one.

At first glance, disregarding the fact that it’s a proof by contradiction, it seems too apparent. If I don’t have at least one arm, how can I have two? But this obvious logic is exactly what proof by contradiction is:

• First, let’s deny the conclusion $q$ and assume that I have no arms.
• But according to the assumption $p$, I have two arms, which is a contradiction.
• Thus, the assumption that I have no arms, $\lnot q$, must be incorrect. Of course, this is when the assumption that I have two arms, $p$, stands, hence $p \to q$.

Proof

$$ \begin{align*} (p \land \lnot q) \to c \iff & \lnot ( p \land \lnot q ) \lor c \\ \iff & \lnot (p \land \lnot q) \\ \iff & \lnot p \lor q \\ \iff & p \to q \end{align*} $$

■