Questions: Proof by Exhaustion

Question 1

A proof by exhaustion of a statement about all one-digit prime numbers would require how many cases?

• A. 3
• B. 4
• C. 5
• D. 9

Answer: (B)

The one-digit primes are 2, 3, 5, and 7 — four numbers. A proof by exhaustion would verify the statement for each of these four cases. Since these are all the one-digit primes, the four cases are exhaustive. No other one-digit number is prime, so no other case needs checking.

Question 2

To prove a statement about most integers by exhaustion, you is expected to check infinitely many individual cases.

• T. True
• F. False

Answer: False

You can partition all integers into a finite number of categories. For example, every integer is either even or odd — that is two cases, not infinitely many. Proof by exhaustion over the cases 'even' and 'odd' covers all integers with just two sub-proofs. The trick is choosing categories that are exhaustive and that allow each sub-proof to go through.

Question 3

Prove by exhaustion that for any integer n with 1 ≤ n ≤ 4, the value n² ≤ 20.

Model answer: Case n=1: 1² = 1 ≤ 20. Case n=2: 2² = 4 ≤ 20. Case n=3: 3² = 9 ≤ 20. Case n=4: 4² = 16 ≤ 20. All four cases satisfy n² ≤ 20, and these are all integers in the range [1,4], so the statement is proven.

This is a pure exhaustion proof — the domain is finite (four integers), so you check each one. Every case satisfies the inequality, and no cases are missing. Note that n=5 would give 25 > 20, but n=5 is outside the stated domain, so it is irrelevant.