Indirect Proof

From ProofWiki
(Redirected from Definition:Indirect Proof)
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Indirect_Proof&oldid=688739"