Sentence such that the universe of a structure has exactly two members

Question

On page 100, A Mathematical Introduction to Logic, Herbert B. Enderton（2ed),

Assume that the language has equality and a two-place predicate symbol $P$. For each of the following conditions, find a sentence $σ$ such that the structure $\mathfrak A$ is a model of $σ$ iff the condition is met. (a) $|\mathfrak A|$ has exactly two members.

My first attempt is the sentence $\forall x \exists y,z((y \neq x \land z \neq x) \to y = z)$, or equivalently, $\forall x \exists y,z(y \neq x \to (z \neq x \to y = z))$.

It seems to me this is incorrect, because if the universe is a singleton, then there doesn't exist $y$ and $z$ that don't equal $x$, which implies that the sentence is vacuously true, which lead to my second version:

$\forall x \exists y,z((y \neq x \land z \neq x)\land((y \neq x \land z \neq x) \to y = z))$ which is $\forall x \exists y,z(y \neq x \land z \neq x \land y = z)$. This is also incorrect, since it doesn't exclude the scenario that the universe contains more than elements.

Thus, finally, should the sentence look like $\forall x ((\exists y,z((y \neq x \land z \neq x) \to y = z))\land(\exists y,z(y \neq x \land z \neq x)))$ ? Is there any alternative that is less cumbersome?

Answer 1

None of the sentences you have come up with appear to work:

• The first is satisfied by any structure.
• The second appears to be satisfied by any structure with universe of size at least two (and the empty structure).
• The last again appears to be satisfied by any structure with universe of size at least two (and the empty structure).

The common mistake appears to be that you are forgetting that an implication is true whenever the antecedent is false. Consider the formula $$( \forall x ) ( \exists y ) ( \exists z ) ( ( y \neq x \wedge z \neq x ) \rightarrow y = z )$$ that essentially appears in each formula in the OP. Given any $x$, note that if $y = x$ then the antecedent $y \neq x \wedge z \neq x$ is false, and so the implication is true. As you are only looking for the existence of $y$ and $z$ so that the implication is true, we can take those that make it vacuously true.

---

Note that "$|\mathfrak{A}| = 2$" can be phrased in somewhat poor English by the following:

There are two different individuals such that every individual is equal to one or the other.

Taking care in translating this into a formal sentence, we are lead to the following: $$( \exists x ) ( \exists y ) ( x \neq y \wedge ( \forall z ) ( z = x \vee z = y ) ).$$

Answer 2

What does it mean to have exactly two members?

1. It means having at least two members, which we say that there exist two distinct elements.

2. It means there are no more than the above elements. So if we are given three elements, at least two are equal.

As the first part requires quantifying over two variable, we can do this with two existentials followed by a universal quantifier.