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?)

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.

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)$.

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.)

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).

*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 …''

**Proof.**

See exercise 8.

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$.

## 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$.

a) $a=81$, $b=6$

b) $a=728$, $b=7$

c) $a=-11$, $b=8$

d) $a=-58$, $b=9$

e) $a=375$, $b=1$

f) $a=5$, $b=11$

**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.