Some of the most useful and interesting existence theorems are "existence and uniqueness proofs''—they say that there is one and only one object with a specified property. The symbol $\exists !x P(x)$ stands for "there exists a unique $x$ satisfying $P(x)$,'' or "there is exactly one $x$ such that $P(x)$,'' or any equivalent formulation.

Example 2.5.1 (The universe is $\R$.) $\exists ! x\,(x^2+1=2x)$: This is true since $x=1$ is not only a solution, but the only solution. (Can you prove it?) $\square$

We can, of course, combine this quantifier with others.

Example 2.5.2 (The universe is $\Z$.) $\forall x\,\exists ! y\,(x< y< x+2)$: This is true since only $y=x+1$ satisfies the inequalities. $\square$

The quantifier $\exists !$ can be broken down into the "existence'' part and the "uniqueness'' part. In other words, $\exists x !\,P(x)$ says the same thing as $$ \bigl(\exists x\,P(x)\bigr)\, \land\,\bigl(\forall x\,\forall y\,(P(x)\land P(y)\implies x=y)\bigr) $$ The second part of this formula is the "uniqueness'' part; it says that any two elements that satisfy $P$ must, in fact, be the same. More often than not, we must prove existence and uniqueness separately; quite frequently, the uniqueness part is the easier of the two.

Example 2.5.3 (The universe is $\R$.) There is a unique function $f(x)$ such that $f'(x)=2x$ and $f(0)=3$.

Proof. Existence: $f(x)=x^2+3$ works.

Uniqueness: If $f_0(x)$ and $f_1(x)$ both satisfy these conditions, then $f_0'(x)=2x=f_1'(x)$, so they differ by a constant, i.e., there is a $C$ such that $f_0(x)=f_1(x)+C$. Hence, $3=f_0(0)=f_1(0)+C=3+C$. This gives $C=0$ and so $f_0(x)=f_1(x)$.$\qed$

Sometimes we can do both parts of an existence and uniqueness argument at the same time. This is usually accomplished by proving $\forall x\,(P(x)\iff x=x_0)$, where $x_0$ is some particular value.

Example 2.5.4 For every $x$ there exists a unique $y$ such that $(x+1)^2- x^2=2y-1$.

Proof. We do this in two ways—first we divide up the argument:

Existence: Let $y=x+1$; then $(x+1)^2-x^2=x^2+2x+1-x^2=2(x+1)-1=2y-1$.

Uniqueness: If $y_0$ and $y_1$ both satisfy the equation, then $2y_0+1=(x+1)^2-x^2=2y_1+1$, so $2y_0+1=2y_1+1$. Subtracting $1$ and canceling $2$ gives $y_0=y_1$.

We can also combine existence and uniqueness:

Note that $(x+1)^2-x^2 = x^2+2x+1 - x^2 = 2(x+1)-1$. Now $2y-1=2(x+1)-1$ if and only if $y=x+1$, which proves the result.

(We're cheating a little here. In fact, proving a statement of the form $(P(x)\iff x=x_0)$ often requires two proofs, one for each direction of the "$\iff$''. Sometimes, as in this case, the proof can be phrased so that the "if and only if'' is clear without two distinct proofs. In general, however, an existence and uniqueness proof is likely to require two proofs, whichever way you choose to divide the work.)$\qed$

Here is a familiar yet extraordinarily useful existence and uniqueness theorem, called the Division Algorithm. It says that if we divide one integer into another we end up with a unique quotient and remainder.

Theorem 2.5.5 If $a$ and $b$ are integers and $b$ is positive, then there are integers $q$ and $r$ such that $a=bq+r$ and $0\le r< b$. Furthermore, these numbers (called the quotient and remainder) are unique.

Proof. We begin with the existence part of the argument. We assume $a\ge 0$ and leave the case $a< 0$ for an exercise. We use induction on $a$, with $m=0$, and $k=b-1$. (Recall the use of $m$ and $k$ in the statement of the Induction Axiom in section 2.4.)

If $0\le a\le b-1$, then $a=b\cdot 0+a$; this establishes the basis of the induction. Now assume that $a\ge b$ and the result is true for $0,1,…, a-1$. Then $a-1\ge a-b\ge 0$, so there are numbers $q'$ and $r\in \{0,1,…, b-1\}$ such that $a-b=bq'+r$. Let $q=q'+1$; then $$ qb+r=(q'+1)b+r=q'b+r+b=(a-b)+b=a, $$ as desired. To show uniqueness, suppose $$ bq_1+r_1=a=bq_2+r_2, \quad \hbox{where}\quad 0\le r_1\le r_2< b. $$ Then $$ 0\le r_2-r_1< b-0=b, $$ because $r_2< b$ and $r_1\ge 0$. We also have $$ b(q_1-q_2)=bq_1-bq_2=r_2-r_1, $$ which gives $$ 0\le b(q_1-q_2)< b. $$ Canceling the $b$'s gives $$ 0 \le q_1-q_2< 1, $$ i.e. $q_1-q_2=0$, or $q_1=q_2$. This, in turn, implies $0=r_2-r_1$, i.e., $r_1=r_2$. Note that the uniqueness portion of the proof does not use the hypothesis that $a\ge0$, so all that remains is to show existence for $a< 0$ (exercise 7). $\qed$

You may object that this is an awful lot of work for such an "obvious'' result. But this result almost certainly seems obvious because it is so familiar—you know by experience that you can always get a quotient and remainder. Yet pressed to explain how you know that no matter how you do it, you always get the same remainder, you would probably find yourself at something of a loss. As we set out to establish a body of true mathematical facts, it is important to have complete confidence that the foundation is solid. Many a convincing proof has turned out to be wrong; the first place to look for a mistake is always the line that says "now, it is obvious that …''

Corollary 2.5.6 Using the above notation, $b\vert a$ if and only if $r=0$.

Proof. See exercise 8.$\qed$

Example 2.5.7 Suppose $a=11$ and $b=3$. You undoubtedly know how to find the quotient $q$: divide $a$ by $b$ and round down: $\lfloor 11/3\rfloor=3$ (the notation $\lfloor x \rfloor$ indicates the floor function, or the greatest integer function, that is, the "round down to the nearest integer'' function). Now $bq=9$ and $r=2$, giving $11=3\cdot 3 +2$. This also works when $a< 0$, say $a=-11$ and $b=3$: $\lfloor -11/3\rfloor = \lfloor -3.66\ldots\rfloor = -4$, so $q=-4$, $bq=-12$, $r=1$, and $-11=3\cdot -4+1$. $\square$

Exercises 2.5

In 1-4, identify the existence part and the uniqueness part of your proof clearly.

Ex 2.5.1 There is a unique solution to $2x-3=7$.

Ex 2.5.2 For every $x$ there is a unique $y$ such that $(x+1)^3-x^3=3y+1$.

In the next two exercises, assume the universe of discourse is appropriate for a calculus class.

Ex 2.5.3 There is a unique function $f$ such that $f'(x)= \sin x$, $f(\pi/2)=0$.

Ex 2.5.4 There is a unique function $f$ such that $f'(x)=f(x)$ and $f(0)=1$ (note $f(x)=e^x$ works. To show uniqueness differentiate $f(x)e^{-x}$).

Ex 2.5.5 For the following values of $a$ and $b$, find $q$ and $r$ such that $0\le r< b$ and $a=qb+r$.

Ex 2.5.6 Find a positive integer $a$ and integers $q$ and $q'$ so that $$ a=5q+1=7q'+3. $$

Ex 2.5.7 Here we extend the proof of theorem 2.5.5 to the case of negative numbers. Suppose $-a$ is a negative number (so $a$ is positive). We already know that there are unique $q'$ and $r$ such that $a=q'b+r'$ and $0\le r'< b$. To finish the proof, we need to find $q$ and $r$ such that $-a=qb+r$. Hint: Consider two cases, when $r'=0$ and when $r'>0$. These examples may help: $$ \displaylines{25=2\cdot 9+ 7\quad -25=(-3)\cdot 9+ 2\cr 49 =5\cdot 9+4\quad -49=(-6)\cdot 9+5\cr} $$

Ex 2.5.8 Provide the details of the proof of corollary 2.5.6.