Direct Proof

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

A direct proof of "if P then Q" starts by assuming P is true, then deduces Q through a chain of logical steps. Each step follows from definitions, axioms, or previously proven results. No detours, no contradictions: just a straight line from hypothesis to conclusion.

Structure of a direct proof

Every direct proof has three parts: (1) state what you are proving, (2) assume the hypothesis, (3) derive the conclusion using definitions and known results. The chain must be gap-free: each step must follow logically from what came before.

Scheme

; Direct proof: the sum of two even numbers is even.
;
; Claim: If a and b are even, then a + b is even.
; Proof: Assume a and b are even.
;   By definition, a = 2k for some integer k, b = 2m for some integer m.
;   Then a + b = 2k + 2m = 2(k + m).
;   Since k + m is an integer, a + b is even. QED.

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

; Check the claim on examples
(define (check a b)
  (display a) (display " + ") (display b)
  (display " = ") (display (+ a b))
  (display " even? ") (display (even? (+ a b)))
  (newline))

(check 4 6)
(check 10 22)
(check 0 8)
(check 2 2)
; Every sum of two evens is even.

Example: product of rationals is rational

Claim: if a and b are rational, then a * b is rational. Proof: a rational number is p/q where p, q are integers and q is not zero. If a = p/q and b = r/s, then a * b = (p * r)/(q * s). Since p*r and q*s are integers and q*s is not zero, the product is rational.

Scheme

; Direct proof: product of rationals is rational.
; We represent a rational as a pair (numerator . denominator).

(define (make-rat p q) (cons p q))
(define (numer r) (car r))
(define (denom r) (cdr r))

(define (rat-multiply a b)
  (make-rat (* (numer a) (numer b))
            (* (denom a) (denom b))))

(define (show-rat r)
  (display (numer r)) (display "/") (display (denom r)))

(define a (make-rat 2 3))   ; 2/3
(define b (make-rat 5 7))   ; 5/7

(display "a = ") (show-rat a) (newline)
(display "b = ") (show-rat b) (newline)
(display "a * b = ") (show-rat (rat-multiply a b)) (newline)
; (2*5)/(3*7) = 10/21 — integer over nonzero integer — rational.

(define c (make-rat 3 4))
(define d (make-rat 8 9))
(display "c * d = ") (show-rat (rat-multiply c d))
; 24/36 = 2/3 — still rational.

Writing direct proofs

The skill is turning definitions into equations you can manipulate. "Even" means 2k. "Rational" means p/q. "Divides" means a = b*k. Every direct proof starts the same way: unpack the definitions, do the algebra, repack into the conclusion's definition.

Scheme

; Direct proof: if a divides b and b divides c, then a divides c.
; "a divides b" means b = a*k for some integer k.

(define (divides? a b) (= 0 (modulo b a)))

; Proof: assume a|b and b|c.
; Then b = a*k and c = b*m for integers k, m.
; So c = (a*k)*m = a*(k*m).
; Since k*m is an integer, a divides c. QED.

(display "3|6? ") (display (divides? 3 6)) (newline)
(display "6|24? ") (display (divides? 6 24)) (newline)
(display "3|24? ") (display (divides? 3 24)) (newline)
; Transitivity: 3|6 and 6|24 implies 3|24.

(display "5|15? ") (display (divides? 5 15)) (newline)
(display "15|45? ") (display (divides? 15 45)) (newline)
(display "5|45? ") (display (divides? 5 45))

Neighbors

✎ Proofs Ch.1 — the logical foundations that justify each step
✎ Proofs Ch.3 — what to do when direct proof is hard

← Statements and Logic by june.kim Contrapositive and Contradiction →