0
$\begingroup$

I want to express the fact that a set has at most 2 elements, in logical notation. Is the following correct:

$$\exists x_1 \exists x_2 \exists x_3(x_1=x_2 \lor x_1=x_3 \lor x_2=x_3)$$

Or must I use universal quantifiers (which would seem to be correct, given that the above statement is the negation of at least 3 elements). Thank you.

$\endgroup$
4
  • $\begingroup$ You can do it much simpler by saying $\exists x_1\exists x_2: x_1\neq x_2$. In your case $x_1=x_2=x_3$ - which would lead to only 1 element - is not excluded. $\endgroup$
    – LegNaiB
    May 10, 2021 at 14:35
  • $\begingroup$ @LegNaiB Doesn't your expression say that there are at least 2 distinct elements? And I don't think OP's expression implies that $x_1 = x_2 = x_3$. For instance, we could have $x_1=x_2=0$ and $x_3 = 1$. $\endgroup$ May 10, 2021 at 15:12
  • $\begingroup$ It doesn't imply that, but it is a possibility. But you are correct, I interchanged "at most" and "at least". However, the third element is not necessary. It would be enough to just say $\exists x_1\exists x_2$. Just the case of zero elements is not included then. $\endgroup$
    – LegNaiB
    May 10, 2021 at 15:22
  • $\begingroup$ See the accepted answer in this question: math.stackexchange.com/questions/1936315/…? $\endgroup$ May 11, 2021 at 8:54

1 Answer 1

1
$\begingroup$

The following set satisfies your sentence: $\{0, 1, 2\}$ where we take $x_1 = x_2 = x_3 = 0$. In fact, any nonempty set would satisfy that sentence. You could modify your sentence to use universal rather than existential quantifiers.

$$ \forall x_1 \forall x_2 \forall x_3(x_1=x_2 \lor x_1=x_3 \lor x_2=x_3) $$

This sentence being true means that among any choice of 3 elements in the set, there must be some pair that is the same. In other words, it expresses the property that the set cannot have more than 3 elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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