← Table of contents →

Select a white background

Proving ∀x∃y P(x, y)

We will approach this from a constructive point of view. Given any x, the claim is that a y can be found (depending on x) so that P(x, y) is true. An obvious thing to do is to describe an algorithm that takes x as input and produces a suitable y as output.

Example

Definition.

Theorem. If a and b are integers where b > 0 then there exist integers q and r so that the following are both true.

(1) a = qb + r
(2) 0 ≤ r < b

Proof. All we need is an algorithm that takes a and b as inputs and produces q and r as output. For simplicity, we break the problem into two cases.

Case 1. (a ≥ 0). Consider the following algorithm. 

  r = a
  q = 0
  while (r < 0 or r ≥ b)
  {
    r = r - b
    q = q + 1
  }
Notice that a and b never change. They are the inputs. The final values of q and r are the outputs.

Claim 1. Each time the above algorithm reaches the beginning of the while-loop, variables q and r satisfy a = qb + r.

Proof of claim 1. The first time the while-statement is reached, r = a and q = 0. So qb + r = (0)b + a = a, and the claim is true the first time the top of the while-loop is reached.

Now our goal is to look at subsequent times the program reaches the top of the while-loop. It is enough to show that the loop body does not ruin the claim. That is, as long as the claim is true when we are at the beginning of the loop, it will be true again after doing the loop body and coming back around to the top of the loop.

So suppose that we are at the top of the while-loop, and have values q = k and r = m where

(1) a = kb + m
and we need to do the loop body. Doing the loop body once changes q and r so that r = m − b and q = k + 1. So the loop goes back to its top, and we find that

qb + r  =  (k+1)b + (m−b)
 =  kb + b + m − b (by algebra)
 =  kb + m (by algebra)
 =  a (by (1))

So claim 1 holds again. The claim is true initially and each time the loop body is done, the claim remains true. ♦

Claim 2. The loop eventually stops.

Proof of claim 2. Variable r starts at a nonnegative value, since a ≥ 0. Each time around the loop, r is decreased by b. Since the range of values of r (from 0 to b−1) for which the loop stops has b values in it, r cannot jump over that range. Eventually, we must encounter a value of r that stops the loop. ♦

Now we are ready to finish case 1. Look at the last time the loop reaches its top. We know, from claim 1, that

(2) a = qb + r.
Since this is the last time, the condition (r < 0 or r ≥ b) must be false (otherwise, the loop would go through again). That is,
(3) r ≥ 0 and r < b
The program stops with those values of q and r. Since facts (2) and (3) are the same as requirements (1) and (2) in the theorem, we are done.

Case 2. (a < 0). The proof is similar to the case 1. Consider the following algorithm. 

  r = a
  q = 0
  while (r < 0 or r ≥ b)
  {
    r = r + b
    q = q - 1
  }

Once again we claim that, each time the program reaches the top of the loop, a = qb + r. We have already verified that for the first time, since the initial values of q and r are the same as in the preceding case. So suppose that we reach the loop top with values q = k and r = m, where

(1) a = kb + m
After doing the loop body once, we end up with q = k − 1 and r = m + b. Notice that, when we reach the top of the loop the next time,

qb + r  =  (k−1)b + (m+b)
 =  kb − b + m + b (by algebra)
 =  kb + m (by algebra)
 =  a (by (1))

As before, equation a = qb + r holds every time the program is at the top of the loop. Also, we can see the the loop must eventually stop since r starts at a negative number a and increases by b each time. As before, r will eventually end up in the range from 0 to b − 1.

♦

There is nothing mysterious about the theorem that we have just proved. It is called the Division theorem. You have learned an algorithm, called long division, where you divide two integers. For example, dividing 100 by 3 looks like this. 

       33 R1
   3 |100
       9
       10
        9
        1
Dividing 100 by 3 gives a quotient of 33 and a remainder of 1. That is 100 = 33(3) + 1. The division theorem just says that, for any integers a and b, where b > 0, you can divide a by b, getting a quotient q and remainder r, so that a = qb + r and 0 ≤ r < b.

The long division algorithm is much faster than the algorithm given in our proof. But, for a proof, it does not matter how fast the algorithm is, as long as it gives an answer.

You probably did not learn about dividing a negative number by a positive number in elementary school. Try using our algorithm to divide −14 by 3. What are the quotient and remainder? Are the required equations satisfied?