Indirect Argument: Contradiction and Contraposition

Method of Proof by Contradiction

  1. Suppose the statement to be proved is false.
  2. Show that this supposition leads logically to its contradiction.
  3. Conclude that therefore the original statement must be true.

Example: Prove that there are an infinite number of integers.

Proof:

  1. Suppose that there are only finite many integers.
  2. Then there must be a largest, say N.
    Then, " n Î Z, n < N.
    Now, N + 1 is an integer because N is an integer and 1 is an integer and Z is closed under addition.
    But N + 1 > N ®¬ [This contradicts our assumption that N is the largest integer.]
  3. Hence our original statement must be true. 

Note: the numbering is just for comparison; leave them out when writing your proofs.

 

Example: Prove that the negative of any irrational number is irrational.

Symbolically: " x Î Â x is irrational ® -x is irrational.

Proof: Suppose not. $ x Î Â such that x is irrational Ù - x is rational.

- x rational means

–x = p/q, 

where p, q Î Z, q ¹ 0.

 

  x = –p/q,

a quotient of integers.

So x is rational. ®¬

[Hence out supposition is false and the given statement is true.]

Method of Proof by Contraposition

Given the statement "x Î D, P(x) ® Q(x)

  1. Replace P(x) ® Q(x) with its contrapositive.
    We have: "x Î D, ~ Q(x) ® ~ P(x).
  2. Prove this statement (usually directly).

Example: Prove " n Î Z, n2 is even ® n is even.

Proof (by contrapositive):

Suppose " n Î Z, ~(n is even) ® ~(n2 is even). Which can be written as

" n Î Z, n is odd ® n2 is odd.

Let n Î Z be odd, then n = 2k + 1, k Î Z.

n2 = (2k + 1)2

= 4k2 + 4k + 1 

 

= 2(2k2 + 2k) + 1,

let k1 = 2k2 + 2k Î Z.

So n2 = 2k1 + 1, k1 Î Z. Hence n2 is odd. 

Proof (by contradiction):

Suppose that " n Î Z, n2 is even ® n is even, is false. That is

$ n Î Z such that  n2 is even Ù n is odd. Now since n is odd, n = 2k + 1, k Î Z.

n2 = (2k + 1)2

= 4k2 + 4k + 1 

 

= 2(2k2 + 2k) + 1,

let k1 = 2k2 + 2k Î Z.

So n2 = 2k1 + 1, k1 Î Z. Hence n2 is odd. ®¬

[This contradicts the assumption that n2 is even. \ the original statement is true.]