| ← | Table of contents | → |
Typically, to prove that something exists, you say what it is. Doing that is called a constructive existence proof. Here is an example.
Theorem. There exists a positive integer x that is equal to the sum of the positive integers that are less than x.
Proof. Choose x = 3. Notice that 3 = 2 + 1, so 3 is equal to the sum of the positive integers that are less than 3.
♦
Not every existence proof actually supplies a value. Here is an example of a nonconstructive proof.
Definition. A number x is rational if there exist integers a and b, where b ≠ 0, so that x = a/b. For example, 1/3, 2/10 and 10/3 are all rational numbers. A number is irrational if it is not rational.
Theorem, There exist two irrational numbers x and y (not necessarily different) so that xy is rational.
Later we prove that √2 is irrational. We assume that is true. The proof is by cases.
Case 1 (√2√2 is rational). Let x = √2 and y = √2. Notice that both x and y are irrational and, in this case, xy is rational.
Case 2 (√2√2 is irrational). Let x = √2√2 and y = √2. Then
| xy | = | (√2√2)√2 |
| = | √2√2√2 | |
| = | √22 | |
| = | 2 |
♦
Notice that, even after doing this proof, we cannot identify a single choice of values for x and y.
Nonconstructive proofs have some surprising uses in algorithms. For example, a positive integer n is composite if there exist positive integers a and b where a ≠ 1, b ≠ 1 and ab = n. For example 10 is composite because (2)(5) = 10. The obvious way to demonstrate that a number is composite is to find suitable numbers a and b, and you would expect an algorithm that checks whether a number is composite would search for a and b. But the best algorithms for determining whether a number is composite are able to come up with the answer (yes or no) without finding factors. They do a nonconstructive proof that the factors exist! It is conjectured that any algorithm that actually finds the factors must be much slower than those efficient nonconstructive algorithms.