A common problem in mathematics is to prove the existence and uniqueness of a solution, element, object in a category, etc. The typical approach for such a proof is to establish the existence of the solution, then determine the uniqueness. In instances like this, uniqueness is often proved by assuming there are two solutions and concluding they are indeed equal.

Needle-in-a-haystack Heuristic

An alternative and often more constructive approach is to prove uniqueness first, then prove existence - we call this the needle-in-the-haystack heuristic because it is much easier to find a needle in a haystack when you first prove you know where it will be if it is there at all.¹

We give a basic example from elementary mathematics.

If we chose to write the theorem in the traditional manner and introduce the existence first, then we would have begun with a rather unpredictable beginning:

Let $\displaystyle x=\frac{b_2-b_1}{m_1-m_2}$ .

Furthermore, to prove the uniqueness of a solution by means of assuming there are two solutions can be a misleading approach for some problems. For example, the intersection of $f(x)=x^2-8x$ with $g(x)=-3x-4$ is unique, but given two solutions $(x_1,y_1)$ , $(x_2,y_2)$ , it becomes rather difficult to conclude $(x_1,y_1)=(x_2,y_2)$ directly. With the needle-in-the-haystack heuristic one begins the proof by showing the only solution is $(4,-16)$ , if there is a solution. Thus we never compare two systems of equations in several variables.

When to use the heuristic

When an existence and uniqueness is claimed where there are accompanying equations or structures that must be satisfied by the solution, it is often possible to apply the heuristic. Often such problems can be worded as two sets intersecting at a single point. If the possible point of intersection is characterized before we know the intersection is non-empty, then we have an immediate candidate with which we may prove the intersection is non-empty.

When not to use the heuristic

There are, however, many examples where the traditional approach of establishing existence first is preferable. For instance, in a proof that every integer has a unique factorization, establishing some factorization exists is nearly trivial: choose a prime $p$ which divides $n$ , then by induction choose a prime factorization $q_1\cdots q_s$ of $n/p$ , and then $n=p q_1\cdots q_s$ is a prime factorization of $n$ . However, establishing the uniqueness of a prime factorization is a far more delicate matter.

The heuristic applies best when the definition of the solution, element, or object in question is not immediately presentable from the definition. When a definition provides a blue-print for establishing existence then the traditional method may be preferable.

Footnotes

... all.¹

This terminology is due to F. R. Beyl