Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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


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.

share|improve this answer
    
$\forall x ((\forall y,z((y \neq x \land z \neq x) \to y = z))\land(\exists y(y \neq x )))$ Is this it? –  Metta World Peace Jan 11 '13 at 21:57
    
@MettaWorldPeace: Unfortunately not. Translate exactly what I wrote into first-order language. (Your sentence should begin with $\exists\;\equiv$ "there are".) –  Arthur Fischer Jan 11 '13 at 22:04
    
@MettaWorldPeace: After looking at your sentence a bit more closely, it is much better than I had originally thought. The only problem it has is with the empty structure (since it is a universal sentence, it is vacuously true in this structure). But every nonempty structure which satisfies this sentence has exactly two individuals. –  Arthur Fischer Jan 11 '13 at 22:18
    
My goodness! How stupid I am. Thank you very much for your patience –  Metta World Peace Jan 11 '13 at 22:22
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.