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:

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


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:

  1. There is a unique President of the United States.
  2. There is a unique US Senator from Florida.
  3. 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.