From a certain point of view, there is no need for the current section. If we are proving an existential statement we are disproving some universal statement. (Which has already been discussed.) Similarly, if we are trying to disprove an existential statement, then we are actually proving a related universal statement. Nevertheless, sometimes the way a theorem is stated emphasizes the existence question over the corresponding universal — and so people talk about proving and disproving existential statements as a separate issue from universal statements.

Proofs of existential questions come in two basic varieties: constructive and non-constructive. Constructive proofs are conceptually the easier of the two — you actually name an example that shows the existential question is true. For example:

A non-constructive existence proof is trickier. One approach is to argue by contradiction — if the thing we're seeking doesn't exist that will lead to an absurdity. Another approach is to outline a search algorithm for the desired item and provide an argument as to why it cannot fail!

A particularly neat approach is to argue using dilemma. This is my favorite non-constructive existential theorem/proof.

Many existential proofs involve a property of the natural numbers known as the well-ordering principle. The well-ordering principle is sometimes abbreviated WOP. If a set has WOP it doesn't mean that the set is ordered in a particularly good way, but rather that its subsets are like wells — the kind one hoists water out of with a bucket on a rope. You needn't be concerned with WOP in general at this point, but notice that the subsets of the natural numbers have a particularly nice property — any non-empty set of natural numbers must have a least element (much like every water well has a bottom).

Because the natural numbers have the well-ordering principle we can prove that there is a least natural number with property X by simply finding any natural number with property X — by doing that we've shown that the set of natural numbers with property X is non-empty and that's the only hypothesis the WOP needs.

For example, in the exercises in Section 3.5 we introduced vampire numbers. A vampire number is a \(2n\) digit number \(v\) that factors as \(v=xy\) where \(x\) and \(y\) are \(n\) digit numbers and the digits of \(v\) are the union of the digits in \(x\) and \(y\) in some order. The numbers \(x\) and \(y\) are known as the “fangs” of \(v\). To eliminate trivial cases, pairs of trailing zeros are disallowed.

This is quite an interesting situation in that we know there is a smallest 6-digit vampire number without having any idea what it is!

There are quite a few occasions when we need to prove statements involving the unique existence quantifier (\(\exists !\)). In such instances we need to do just a little bit more work. We need to show existence — either constructively or non-constructively — and we also need to show uniqueness. To give an example of a unique existence proof we'll return to a concept first discussed in Section 1.5 and finish-up some business that was glossed-over there.

Recall the Euclidean algorithm that was used to calculate the greatest common divisor of two integers \(a\) and \(b\) (which we denote \(\gcd{a}{b}\)). There is a rather important question concerning algorithms known as the “halting problem.” Does the program eventually halt, or does it get stuck in an infinite loop? We know that the Euclidean algorithm halts (and outputs the correct result) because we know the following unique existence result. \begin{equation*} \forall a, b \in \Integers^+, \, \exists ! \, d \in \Integers^+ \; \mbox{such that} \, d=\gcd{a}{b} \end{equation*}

Now, before we can prove this result, we'll need a precise definition for \(\gcd{a}{b}\). Firstly, a gcd must be a common divisor which means it needs to divide both \(a\) and \(b\). Secondly, among all the common divisors, it must be the largest. This second point is usually addressed by requiring that every other common divisor divides the gcd. Finally we should note that a gcd is always positive, for whenever a number divides another number so does its negative, and whichever of those two is positive will clearly be the greater! This allows us to extend the definition of gcd to all integers, but things are conceptually easier if we keep our attention restricted to the positive integers.

Armed with this definition, let's return our attention to proving the unique existence of the gcd. The uniqueness part is easier so we'll do that first. We argue by contradiction. Suppose that there were two different numbers \(d\) and \(d'\) satisfying the definition of \(\gcd{a}{b}\). Put \(d'\) in the place of \(c\) in the definition to see that \(d' \divides d\). Similarly, we can deduce that \(d \divides d'\) and if two numbers each divide into the other, they must be equal. This is a contradiction since we assumed \(d\) and \(d'\) were different.

For the existence part we'll need to define a set — known as the \(\Integers\)-module generated by \(a\) and \(b\) — that consists of all numbers of the form \(xa+yb\) where \(x\) and \(y\) range over the integers.

\(\Integers\)\(\Integers\)\(21\)\(15\)\(21x+15y\)\((x,y)\)

This set has a very nice geometric character that often doesn't receive the attention it deserves. Every element of a \(\Integers\)-module generated by two numbers (\(15\) and \(21\) in the example) corresponds to a point in the Euclidean plane. As indicated in <<Unresolved xref, reference "fig_zmodule"; check spelling or use "provisional" attribute>> there is a dividing line between the positive and negative elements in a \(\Integers\)-module. It is also easy to see that there are many repetitions of the same value at different points in the plane.

In thinking about this \(\Integers\)-module, and perusing <<Unresolved xref, reference "fig_zmodule"; check spelling or use "provisional" attribute>>, you may have noticed that the smallest positive number in the \(\Integers\)-module is 3. If you hadn't noticed that, look back and verify that fact now.

What we've just observed is a particular instance of a general result.