Contrapositive and Contradiction

Jim Hefferon · GFDL + CC BY-SA 2.5 · Introduction to Proofs

When a direct proof is hard, try an indirect route. Proof by contrapositive proves "if not Q then not P" instead of "if P then Q" (they are logically equivalent). Proof by contradiction assumes the negation and derives something impossible.

Proof by contrapositive

"If P then Q" is logically equivalent to "if not Q then not P." Sometimes the contrapositive direction is easier. Example: if n^2 is even, then n is even. Direct proof is awkward. Contrapositive: if n is odd, then n^2 is odd. That is straightforward algebra.

Scheme

; Contrapositive: "if n^2 is even then n is even"
; Equivalent to: "if n is odd then n^2 is odd"
;
; Proof: assume n is odd. Then n = 2k+1 for some integer k.
; n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.
; This is odd. QED.

(define (even? n) (= 0 (modulo n 2)))
(define (odd? n) (not (even? n)))

; Verify: odd n always gives odd n^2
(define (check n)
  (display "n=") (display n)
  (display " odd?=") (display (odd? n))
  (display "  n^2=") (display (* n n))
  (display " odd?=") (display (odd? (* n n)))
  (newline))

(check 1)
(check 3)
(check 5)
(check 7)
(check 9)
; Every odd n gives odd n^2. Contrapositive holds.

Proof by contradiction

To prove statement S, assume not-S and derive a contradiction (any statement that is both true and false). Since contradictions cannot exist, not-S must be false, so S is true. The classic example: the square root of 2 is irrational.

Scheme

; Proof by contradiction: sqrt(2) is irrational.
;
; Assume sqrt(2) = p/q in lowest terms (gcd(p,q) = 1).
; Then 2 = p^2/q^2, so p^2 = 2*q^2.
; So p^2 is even, so p is even (by contrapositive above).
; Write p = 2k. Then 4k^2 = 2q^2, so q^2 = 2k^2.
; So q^2 is even, so q is even.
; But then both p and q are even — contradicts gcd(p,q) = 1.
; Therefore sqrt(2) is irrational. QED.

; We can verify numerically: no fraction p/q equals sqrt(2)
(define (close-to-sqrt2? p q tolerance)
  (< (abs (- (* p p) (* 2 q q))) tolerance))

; Try to find p/q = sqrt(2) with small integers
(define (search limit)
  (define (try p q)
    (cond
      ((> p limit) (display "No exact fraction found."))
      ((> q limit) (try (+ p 1) 1))
      ((= (* p p) (* 2 q q))
       (display "Found: ") (display p) (display "/") (display q))
      (else (try p (+ q 1)))))
  (try 1 1))

(search 100)
; No integer pair works. The proof says none ever will.

When to use which

Use direct proof when the definitions unpack cleanly into algebra. Use contrapositive when the conclusion is easier to negate than to prove directly (especially "if even then even" patterns). Use contradiction when you need to prove something does not exist (irrationals, infinitely many primes).

Scheme

; Another contradiction proof: there are infinitely many primes.
;
; Assume there are finitely many: p1, p2, ..., pn.
; Let N = p1*p2*...*pn + 1.
; N is not divisible by any pi (remainder 1).
; So N is either prime or has a prime factor not in the list.
; Either way, the list is incomplete. Contradiction. QED.

(define (prime? n)
  (define (check d)
    (cond ((<= n 1) #f)
          ((> (* d d) n) #t)
          ((= 0 (modulo n d)) #f)
          (else (check (+ d 1)))))
  (check 2))

; Euclid's construction: multiply all known primes, add 1
(define primes (list 2 3 5 7 11 13))

(define product
  (let loop ((lst primes) (acc 1))
    (if (null? lst) acc
        (loop (cdr lst) (* acc (car lst))))))

(define N (+ product 1))
(display "Product + 1 = ") (display N) (newline)
(display "Is it prime? ") (display (prime? N)) (newline)
; 30031 = 59 * 509. Not prime, but 59 is not in our list.
; The list was incomplete, as the proof guarantees.

Neighbors

🔑 Logic Ch.5 — natural deduction formalizes these proof strategies
✎ Proofs Ch.2 — direct proof, the baseline technique

← Direct Proof by june.kim Mathematical Induction →