Constructive Versus Existential Proofs

Constructive Versus Existential Proofs

Constructive Proofs

How would you prove 299 + 1 is a composite number? You would exhibit a factorization:

299 + 1 = (233)3 + 1 =(233 + 1)((233)2 - 233 + 1).

In other words, to prove 299 + 1 is composite we constructed a factorization. Not surprisingly, we call such a proof constructive.

q

Example: Pythagorean Triples

A Pythagorean triple is a triple of positive integers (a, b, c) that satisfies the equation a2 + b2 = c2. For example, (3, 4, 5) is a Pythagorean triple since 32 + 42 = 52. Are there more? Yes, there are infinitely more, just take multiples of (3,4, 5): (3k, 4k, 5k) where k can be any positve integer. We call something like (3k, 4k, 5k) a one parameter family of solutions. There is one parameter, namely k. Are there more solutions? Yes.

Theorem. There is a two parameter family of Pythagorean triples.

Proof. (We construct the solution.) Let a = u2 - v2 and b = 2 u v where u and v are positive integers with u > v. Then a2 + b2 = (u2-v2)2 + (2uv)2 = u4 - 2 u2v2 + v4 + 4 u2v2 = u4 + 2u2v2 + v4 = (u2 + v2)2. Thus, (u2 - v2, 2 u v, u2 + v2), for u > v, is two parameter family of Pythagorean triples.

q

Example: Rational Number

Theorem. There is a rational number that lies strictly between the square root of 10100 and the square root of 10100+1.

Proof. The square root of 10 100 is 10 50. After a little bit of trial and error, we let x = 10 50 + 10 -51, which is clearly a rational number bigger than the squre root of 10 100. To prove that x is less than the square root of 10100+1, we compute

x2 = (10 50 + 10 -51)2 = 10 100 + (2) 10 -1 + 10 -102

which is clearly less than 10100+1.

q

Existential Proofs

Sometimes it is possible to prove the existence of something mathematical without actually constructing it. Why would you want to do this? Well, it could be that you just cannot think of a constructive proof, or that a constructive proof is very long and tedious. In any case, existential proofs are another valuble technique in proofs. Let's look at a familiar example from the calculus.

An Example from Calculus

First let's recall the Intermedaite Value and Mean Value Theorems:

Intermediate Value Theorem. If a real valued funtion f is continuous on the closed interval [a, b] and if N is a number strictly between f(a) and f(b), then there exists a number c in (a, b) such that f(c) = N.

Mean Value Theorem. If a real valued function f is continuous on the closed interval [a, b] and f is differentiable on the open interval (a, b) then there is a number c in (a, b) such that f'(c) = (f(b) - f(a))/(b-a). We can use the Mean Value Theorem to prove that certain polynomials do not have more than one real root. (A root of a polynomial p(x) is a number c such that p(c) = 0.)

Theorem. The polynomial p(x) = x3 + x - 1 has exactly one real root.

Proof. The proof is in two parts.

Part 1. (Direct Existential Proof.) First we will prove p(x) has one real root. We appeal to the Intermediate Value Theorem with a = 0 and b = 1: p(0) = - 1 < 0 and p(1) = 1 > 0. Since 0 (N = 0) is between -1 (=p(0)) and 1 (=p(1)), we may conclude that there is a real number c, between 0 and 1, for which p(c) = 0.

Part 2. (Proof by Contradiction.) Now we will prove that p(x) has only one root. Assume to the contrary that p(x) has more than one root. Let's suppose two distinct roots c1 and c2, so p(c1) = p(c2) = 0. Then by appealing to the Mean Value Theorem, there must be a number c between c1 and c2 for which p'(c) = (p(c2) - p(c1))/(c2 - c1) = 0. But a direct calculation shows that p'(x) = 3x2 + 1, which can never be zero since x2 >= 0 for all real numbers x. The contradiction completes the proof.

q

Example: Continuous Motion

Here is an example where we appeal to the Mean Value Theorem to obtain the existence of something.

Theorem. If an object is traveling in a straight line with a differentiable position function s(t), where t denotes the time variable, for t between a and b, then there is a time t0, between a and b where the instantanious velocity at t = to is equal to the average velocity over the entire path.

Proof. The velocity function is the derivative of the position function v(t) = s'(t). According to the Mean Value Theorem, there is a value t = t0 between a and b where v(t0) = s'(t0) = (s(b) - s(a))/(b-a) = average velocity over the path.

q

Exercises

Prove each of the following.

  1. 425650925 - 1 is a composite number. (Constructive proof.)

  2. There is a rational number that lies strictly between 19 100 - 1 and 19 100. (Constructive proof.)

  3. sqrt(2) + sqrt(3) is an algebraic number. (See the section on Unwinding Defintions (Getting Started) for the definition of an algebraic number.) (Hint: First compute (sqrt(2) + sqrt(3))2.) (Constructive proof.)

  4. Suppose f(x) is a real valued differentiable function (of real numbers) with f(1) = -1 and f(2) = -2, then there is a value of x = x0, between 1 and -2 such that the y-intercept of the tangent line to the curve at x = x0 is equal to f(t0) + t0. (Existential proof--use the Mean Value Theorem).

Next==>Counter Examples

<==Back To Unwinding Definitions (Getting Started)

Back to Proofs