Reductio Ad Absurdum
Contents |
Theorem
If, by making an assumption $\neg p$, we can infer a contradiction as a consequence, then we may infer $p$:
- $\left({\neg p \vdash \bot}\right) \vdash p$
or
- $\neg p \implies \bot \vdash p$
to which, via the rule of implication, it is equivalent.
It can alternatively be rendered:
- $\neg p \implies \left({q \land \neg q}\right) \vdash p$
from the definition of contradiction.
It can be written:
- $\displaystyle {\begin{array}{|c|} \hline \neg p \\ \vdots \\ \bot \\ \hline \end{array} \over p} \textrm{RAA}$
Its abbreviation in a tableau proof is $\textrm{RAA}$.
Proof
Proof by Natural deduction
First, from the Rule of Implication and Modus Ponendo Ponens we use the fact that:
- $\left({\neg p \vdash \bot}\right) \dashv \vdash \left({\neg p \implies \bot}\right)$
Then, by the tableau method:
| Line | Pool | Formula | Rule | Depends upon | |
|---|---|---|---|---|---|
| 1 | 1 | $\neg p \implies \bot$ | P | (None) | |
| 2 | 2 | $\neg p$ | A | (None) | |
| 3 | 1, 2 | $\bot$ | $\bot \mathcal E$ | 1, 2 | |
| 4 | 1 | $\neg \neg p$ | $\neg \mathcal I$ | 2-3 | |
| 5 | 4 | $p$ | $\neg \neg \mathcal E$ | (None) |
Thus:
- $\left ({\neg p \vdash \bot}\right) \vdash p$
$\blacksquare$
Proof by Truth Table
As can be seen by inspection, the truth values under the main connectives match for all models.
$\begin{array}{|cccc||c|} \hline \neg & p & \implies & \bot & p \\ \hline T & F & F & F & F \\ F & T & F & F & T \\ \hline \end{array}$
The expanded version:
$\begin{array}{|ccccccc||c|} \hline \neg & p & \implies & (q & \land & \neg & q) & p \\ \hline T & F & F & F & F & T & F & F \\ T & F & F & T & F & F & T & F \\ F & T & T & F & F & T & F & T \\ F & T & T & T & F & F & T & T \\ \hline \end{array}$
$\blacksquare$
Comment
It can be seen that this result depends on the rule of Double Negation Elimination.
As this depends on the Law of the Excluded Middle, it invalidates the Reductio Ad Absurdum from the intuitionist system.
Indirect Proof
This is also known as an indirect proof.
Let $P$ be a proposition which is to be proved.
An indirect proof of $P$ is a valid argument which takes as a premise the negation of $P$, and from it deduces a contradiction.
Also see
Because of their similarity in form, many authors treat the Reductio Ad Absurdum and the proof by contradiction as two aspects of the same thing.
From the point of view of purely classical logic, this is acceptable. However, in the context of intuitionistic logic, it is essential to bear in mind that only the proof by contradiction is valid.
Linguistic Note
Reductio ad absurdum is Latin for reduction to absurdity.
Sources
This is also known as:
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{I}: \S 3$
- E.J. Lemmon: Beginning Logic (1965): $\S 1.3$
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.12$
- Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.2$
