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$.
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, that is, the "round down to the nearest integer'' function). Now $bq=9$ so $r=2$.
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$. We need to find $q$ and $r$ such that $-a=qb+r$, and prove uniqueness.
a) Suppose $b\vert a$, i.e., $r'=0$ and $a=q'b$. How should we define $q$ and $r$?
b) Suppose now that $b\notdiv a$, i.e., $r'\ne 0$. Consider the examples (with $b=9$): $$ \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} $$ How do these examples suggest that we should define $q$ and $r$? Write a complete proof of theorem 2.5.5 for the case $a< 0$.
Ex 2.5.8 Provide the details of the proof of corollary 2.5.6.