Indirect Proof

From ProofWiki
Jump to: navigation, search

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