Answer to Question #198663 in Discrete Mathematics for Parth Godhani

Question

What are the two types of indirect proofs? Explain through an example for each type.

Answer 1

Proof of the Contrapositive:

The contrapositive of the statement P⇒Q is ¬Q⇒¬P.

Example: If ab is even then either a or b is even.

Assume both a and b are odd. Since the product of odd numbers is odd, ab is odd.

Proof by Contradiction:

To prove a sentence P by contradiction we assume ¬P and derive a statement that is known to be false.

Example: There are infinitely many primes.

Assume there are only finitely many primes $p_1,...,p_k$ . Let $n=p_1...p_k+1$ . Since $n\ge2$ , n is divisible by some prime, say $p_i$ . Then $p_i|(p_1...p_i...p_k)$ , so $p_i|(n-p_i...p_k)$ .

Since $n-p_i...p_k$ , there is a contradiction $p_i|1$ .