# Indirect Proof

## Theorem

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

An **indirect proof** has one of the following two argument forms:

### 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:

- If, by making an assumption $\neg \phi$, we can infer a contradiction as a consequence, then we may infer $\phi$.

- The conclusion $\phi$ does not depend upon the assumption $\neg \phi$.

### 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:

- If, by making an assumption $\phi$, we can infer a contradiction as a consequence, then we may infer $\neg \phi$.

- The conclusion $\neg \phi$ does not depend upon the assumption $\phi$.

## Proof

For proofs, see:

## Also defined as

In their handing of **Indirect Proof**, some sources do not spend much time on explaining the differences between what is defined here on $\mathsf{Pr} \infty \mathsf{fWiki}$ as:

- Proof by Contradiction: Assume the truth of the proposition, derive a contradiction, and hence deduce that the proposition must be false.

- Reductio ad Absurdum: Assume the negation of the proposition, derive a contradiction, and hence deduce that the proposition must have been true after all.

The former is accepted as a valid argument in general universally.

The latter requires the assumption of the Law of Excluded Middle.

The Law of Excluded Middle can be symbolised by the sequent:

- $\vdash p \lor \neg p$

## Sources

- 1964: Donald Kalish and Richard Montague:
*Logic: Techniques of Formal Reasoning*... (previous) ... (next): $\text{I}$: 'NOT' and 'IF': $\S 3$ - 1973: Irving M. Copi:
*Symbolic Logic*(4th ed.) ... (previous) ... (next): $3$: The Method of Deduction: $3.6$: The Rule of Indirect Proof - 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Appendix $\text{A}.5$: Theorems and Proofs - 1978: Thomas A. Whitelaw:
*An Introduction to Abstract Algebra*... (previous) ... (next): $\S 5$: Proof by contradiction - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**argument**:**2.** - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**indirect proof** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**argument**:**2.** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**indirect proof**