Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Prepcourse Mathematics - Basics - Propositional Logic

Indirect Proof

[previous page] [next page] [table of contents][page overview]
In order to show that a premise $ V$ implies an assertion $ B$ ( $ V \Longrightarrow B$), one can deduce a contradiction by assuming that $ V$ is true while $ B$ is false, which then implies a false statement $ F$, particularly with $ F = \lnot V$ or $ F=B$:

$\displaystyle V\land(\lnot B)\,\Longrightarrow\,F \,, $

In particular, we note that the equivalences

$\displaystyle B = (\lnot B \Longrightarrow F) \,=\,(\lnot B\Rightarrow B) $

hold if no premises are made.
(Authors: Höllig/Knesch/Apprich/Abele)
The implication

$\displaystyle V \land (\lnot B)\,\Longrightarrow\,F $

is equivalent to

$\displaystyle \lnot(V\land(\lnot B)) \lor F = (\lnot V) \lor B \lor F \,. $

If the implication is true, i.e. if it follows from valid mathematical laws, then the assertion $ B$ must be true, since $ \lnot V$ is false and $ F$ is either false or equal to $ B$.
(Authors: Höllig/Hörner/Abele)
As an example of the indirect method of proof we will show that $ \sqrt{2}$ is an irrational number, i.e. it cannot be represented as a fraction.

Assume that assertion $ B$ is false, so

$\displaystyle \lnot B:\ \sqrt{2} = \frac{p}{q}$   with$\displaystyle \ p,q\in\mathbb{N},\,\operatorname{gcd}(p,q)=1 \,. $

(The abbreviation $ \operatorname{gcd}$ denotes the greatest common divisor.)

By squaring and subsequent multiplication with $ q^2$, our initial assumption implies that

$\displaystyle 2q^2 = p^2 \,, $

so $ p^2$ and thus $ p$ must be even. In particular, there exists a $ r\in\mathbb{N}$ such that $ p=2r$. Since then

$\displaystyle q^2 = 2r^2 \quad , $

$ q$ must be even as well, thus $ \operatorname{gcd}(p,q) = 2$. Yet this contradicts the assumption that $ p$ and $ q$ are coprime (cf. $ \operatorname{gcd}(p,q)=1$), so

$\displaystyle (\lnot B) \Longrightarrow B \,. $

Consequently, assertion $ B$ must be true.
(Authors: Höllig/Knesch/Abele)
[previous page] [next page] [table of contents][page overview]
  automatically generated 9/18/2007