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