2.2 Indirect proofs.

2.2 Indirect proofs

In many cases we prove that a conditional statement p→q is true without assuming that P is true and concluding that q is true. Such methods of proofs are called indirect proofs.

An extremely useful type of indirect proofs is known as “proofs by contraposition”. In this type we make use of the fact that p→q is equivalent to its contrapositive, ~q→~p.

2.2.1 Example

Prove (by contraposition) that if n is an integer and 3n+2 is odd then n is odd.

Solution

Let p(n) be the proposition “3n+2” is odd and q(n) be the proposition n is odd. The first step in the proof by contraposition is to assume ~q is true. Thus we assume that n is not odd i.e. n is even. By definition, n=2k, where k is an integer. It follows that

2.2 Indirect proofs.

Thus 3n+2=2m, where m=3k+1 is an integer.

Therefore 3n+2 is even i.e. 3n+2 is not odd.

This proves that ~p is true. Thus we have proved that p(n)→q(n) is true, or equivalently “If 3n+2 is odd then n is odd”.

Note that we cannot prove the statement using direct proofs (try!!).

2.2.2 Example

Prove that if n=ab, where a and b are positive integers, then (≤√n ˅ b≤√n).

Solution

A direct proof does not seem to go anywhere. Using a proof by contraposition. Assume that ~(a≤√n ˅ b≤√n) is true, i.e we assume that ~(a≤√n ) ˄ ⌉( b≤√n) is true. This implies that a>√n ˄ b>√n. Since a and b are positive integers we obtain that, ab>√n.√n=n. Thus ab≠n, or equivalently ab=n is false. Hence ~(ab=n) is true. Our proof by contraposition succeeded to prove the given statement.

2.2 Indirect proofs.

The second type of “indirect proofs” is called “proofs by contradiction”. Suppose we want to prove that a statement p is true and suppose that there exists a contradiction q such that ~p→ q is true. Because q is false and ~p→ q is true, we conclude that ~p is false i.e. p is true.

This method of proofs is called “proofs” by contradiction.

It is obviously another type of indirect proofs.

2.2.3 Definition

The real number r is rational if there exists integers p and q with q≠0 such that r=p/q.

A real number that is not rational is called irrational.

2.2.4 Example

Prove that √ 2 is irrational.

2.2 Indirect proofs.

Solution

We use “proofs by contradiction”. Assume that √2 is not irrational i.e. √2 is rational. We will prove that this assumption leads to a contradiction. Since √2 is rational then there exists integers a and b such that b≠0 and √2=a/b. We can assume without loss of generality that a and b have no common factor i.e. the fraction a/b is in its simplest form.

Squaring both sides of √2 =
Hence a² is even. Using the fact that “if a² is even then, a is even” we obtain that a is even. Thus a=2n, for some integer n. substituting in equation (2.1) we get
Dividing both sides by 2 gives

2.2 Indirect proofs.

Thus b² is even and hence b is also even. Since a and b are both even then 2 is a common factor of a and b. This contradicts the assumption that a and b have no common factor. Thus the assumption that √2 is rational leads to a contradiction and hence “√2 is rational” must be false. That is the statement √2 is irrational is true.

In the next example we prove a conditional proposition “p→q” using a proof by contradiction. To do that we assume that p and ~q are true. Then we use the steps from the proof of “ ~q→ ~p” to show that ~p is true. This leads to the contradiction p ˄ ⌉p.

2.2.5 Example

Prove by contradiction that “If 3n+2 is odd, then n is odd”.

Solution

Assume that 3n+2 is odd while n is even. Thus there exists an integer k such that n=2k. this gives


Where m is the integer 3k+2. Hence 3n+2 is even. Therefore we obtain the following obvious contradiction “3n+2 is odd and 3n+2” is even. Thus our assumption is false. This completes the proof by contradiction of the required statements.