## Logic: Uniqueness

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.