Logic: Uniqueness – Foundations of Mathematics

There is another quantifier, besides existential and universal: the unique existential quantifier.

Definition. The sentence $\exists!x:S(x)$ is true if there is exactly one $x$ in the universe so that $S(x)$ is true. We read There is a unique $x$ such that $S(x)$ ."

Notice that mathematically, unique means something rather different from what it means in ordinary English. Mathematically, unique always appears attached to some property. If we said Maxine's a unique person, mathematically we'd mean There is only one person in all the universe, and that one person is Maxine.

Proposition. $\exists!x:S(x)$ is equivalent to each of the following:

$\left[\exists x:S(x)\right]\wedge \left[\forall y,z,\left(S(y)\wedge S(z)\right)\Rightarrow y=z\right]$
$\exists x:\left[S(x)\wedge \forall y,\left(S(y)\Rightarrow y=x\right)\right]$

Proof.

First we'll show that each of (1) and (2) is enough to guarantee $\exists!x:S(x)$ . (1) guarantees that there is at least one $x$ with $S(x)$ . If we had two distinct members of the universe, say, $y$ and $z$ , satisfying $S(y)$ and $S(z)$ , then we'd have $y=z$ , so $y$ and $z$ wouldn't actually be distinct after all. Thus there is at most one $x$ with $S(x)$ .

Now assume (2) is true. We know that there is at least one $x$ with $S(x)$ . Suppose we had another, say $x'$ . Then applying $\forall y, S(y)\Rightarrow y=x$ with $y=x'$ , we see that $x=x'$ . So $x'$ was $x$ to begin with. So there is at most one $x$ with $S(x)$ .

Now we'll show that $\exists!x:S(x)$ guarantees (1) and (2).

First, examine (1). Since we are proving a statement of the form $A\wedge B$ , we must establish both conjuncts $A$ and $B$ . The first conjunct $\exists x:S(x)$ is clearly true; there is a unique $x$ with $S(x)$ , therefore there is some $x$ with $S(x)$ . Now let's prove the second conjunct, $\forall y,z,\left(S(y)\wedge S(z)\right)\Rightarrow y=z$ . If this were false, we'd have $\exists y:\exists z:\left(S(y)\wedge S(z)\wedge y\neq z\right)$ . Thus we have two distinct values of $x$ for which $S(x)$ is true. But this contradicts $\exists!x:S(x)$ .

Now consider (2). We need to find the special $x$ ; let's use the $x$ given by $\exists!x:S(x)$ . Such an $x$ has $S(x)$ . Now given $y$ with $S(y)$ , we see that since there is exactly one value $z$ with $S(z)$ , and $S(y)$ and $S(x)$ , it must have been that $y=x$ .

Thus we've shown that $\exists!x:S(x)$ guarantees (1) and (2) and each of (1) and (2) guarantees $\exists!x:S(x)$ . This completes the proof. $\Box$

We can describe (1) above as saying: there is at least one $x$ with $S(x)$ , and there is at most one $x$ with $S(x$ ).

We can describe (2) as saying: there is a special $x$ with has both $S(x)$ , and the property that whenever $S(y)$ is true, $y$ must be the same as $x$ .

Here we could say some words about how to prove a statement of the form $\exists!x:S(x)$ , but we'll postpone that a bit.

Exercising our powers of what-if-not thinking, let's ask how $\exists!x:S(x)$ could be false. Consider the following statements:

There is a unique President of the United States.
There is a unique US Senator from Florida.
There is a unique US Senator from Washington, DC.

(1) is true. (2) and (3) are false, but false for different reasons. Let's see why:

Exercise. Compute the denial of $\exists!x:S(x)$ , using the fact that $\exists!x:S(x)$ can be expressed

$\begin{equation*} \left[\exists x:S(x)\right]\wedge \left[\forall y,z,\left(S(y)\wedge S(z)\right)\Rightarrow y=z\right] \end{equation*}$

Explain the relevance of this to the problem of uniqueness of Senators from Florida and from Washington, DC.