EF Proof by contradiction

Section 6.9 Proof by contradiction

Fact 6.9.1.

For any logically false statement

e,

we have

s \to t \Leftrightarrow (s \land \neg t) \to e .

First,

s \to t

is false precisely when

s

is true and

t

is false. On the other hand,

(s \land \neg t) \to e

is false precisely when

s \land \neg t

is true, and

s \land \neg t

is true precisely when

s, \neg t

are both true, i.e. when

s

is true and

t

is false.

🔗

Procedure 6.9.2. Proof by contradiction.

🔗

🔗
To prove $P \Rightarrow Q,$ devise a false statement $E$ such that $(P \land \neg Q) \Rightarrow E .$
🔗
To prove $(\forall x) (P (x) \Rightarrow Q (x)),$ devise a predicate $E (x)$ such that $(\forall x) (\neg E (x))$ is true (i.e. $E (x)$ is false for all $x$ in the domain), but $(\forall x) [(P (x) \land \neg Q (x)) \Rightarrow E (x)] .$

🔗

Note 6.9.3.

🔗

Usually

E

is taken to be some variation of

C \land \neg C,

for some statement

C .

(See the Law of Contradiction, recorded as Basic Tautology 4 in Example 1.4.1.)

🔗

Worked Example 6.9.4.

🔗

Prove that

\sqrt{2}

is irrational.

Solution.

We want to prove the quantified conditional with domain the real numbers: for all

x,

x^{2} = 2

and

x > 0

then

x

is not rational.

Suppose that

x

is a real number such that

x^{2} = 2

and

x > 0 .

By contradiction, also assume that

x

is rational. We want this extra assumption to lead to a false statement. Now,

x

rational means

x = a / b

for some integers

a, b .

We may assume

a, b

are both positive, since

x > 0 .

We may also assume

a, b

have no common factors (i.e. fraction

a / b

is in lowest terms). Then,

\begin{aligned} x^{2} = 2 & \Rightarrow a^{2} = 2 b^{2}, \\ \Rightarrow a^{2} even, \\ \Rightarrow a even, \\ \Rightarrow a = 2 m, some m, \\ \Rightarrow 2 b^{2} = a^{2} = 4 m^{2}, \\ \Rightarrow b^{2} = 2 m^{2}, \\ \Rightarrow b^{2} even, \\ \Rightarrow b even . \end{aligned}

But if both

a, b

are even, then

a

and

b

are both divisible by

2 .

We have arrived at our contradiction:

a, b

have no common factor but

a, b

have a common factor of

2 .

That is, we have shown the following.

For all $x,$ if $((x^{2} = 2 and x > 0) and x not irrational)$ then (there exist positive integers $a, b$ such that $x = a / b$ and $a, b$ have no common divisor and $a, b$ have a common divisor).

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 6.9 Proof by contradiction

Fact 6.9.1.

Proof.

Procedure 6.9.2. Proof by contradiction.

Note 6.9.3.

Worked Example 6.9.4.

Checkpoint 6.9.5.