Indirect Proof

Theorem

Let $P$ be a proposition whose truth value is to be proved (either true or false).

There are two aspects to this:

Reductio Ad Absurdum

A reductio ad absurdum argument for the truth of $P$ is a valid argument which takes as a premise the negation of $P$, and from it deduces a contradiction:

$\neg P \implies \bot \vdash P$

Proof by Contradiction

A proof by contradiction argument for the falsehood of $P$ is a valid argument which takes $P$ as a premise, and from it directly deduces a contradiction:

$P \implies \bot \vdash \neg P$

Proof

For proofs, see:

• Reductio Ad Absurdum
• Proof by Contradiction.

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{I}: \S 3$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.12$