# 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

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

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

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

### Proof by Contradiction

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

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

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

## Proof

For proofs, see:

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