| ← | Table of contents | → |
We have already done some proofs of statements that start with universal quantifiers. For example, we proved that, for every integer n, n2 ≥ n. The idea is to ask somebody else to select an arbitrary value that has the required characteristics, and to prove the claim for that arbitrary value. It is important to understand that the word arbitrary, in this context, means that any value meeting the requirements might be selected. Somebody else is making the selection. You cannot choose the value yourself.
This is closely related to algorithms that solve problems with input. Suppose your goal is to write a program that reads a positive integer and tells whether that integer is prime. The program must work for any positive integer at all, since the input will be chosen by the user, not by the program.
Theorem. For every positive integer n, n2 + n is even.
Proof. Select an arbitrary positive integer n. We proceed by cases.
Case 1. (n is even). The product of two even numbers is even, so n2 is also even. But then n2 + n is the sum of two even numbers, which is even.
Case 2. (n is odd). The product of two odd numbers is odd, so n2 is also odd. But then n2 + n is the sum of two odd numbers, which is always even.
♦