Translate into first order logic: "$R$ has at least two classes of equivalence" and "$R$ has exactly two classes of equivalence"

106 Views Asked by At

Let $R$ be a relation of equivalence defined on set $X \times X$. Using only logical symbols, translate into a first-order logic: "$R$ has at least two classes of equivalence" and "$R$ has exactly two classes of equivalence"

1) $R$ has at least two classes of equivalence
This means that there are elements $x, y$ in $X$, such that they are not in the relation, and so my answer to this part of the problem:
$$(\exists x\in X)(\exists y \in X)((x,y ) \notin R \land (\exists z\in X)(x,z ) \in R ) $$ 2) $R$ has exactly two classes of equivalence
It means that there exist two non-identical elements in $X$ such that every element in $X$ will be in relation with one of them, but not with both of them at the same time, thus:

$$(\exists z \in X)(\exists y \in X)(z \ne y \land (\forall x)(x\in X \Rightarrow (xRy \lor xRz \land \neg(xRy \land xRz))$$
Is my solution correct to any extent? What should I change?

1

There are 1 best solutions below

0
On BEST ANSWER

For the first one, you are right that:

This means that there are elements $x, y$ in $X$, such that they are not in the relation

so why not just:

$$(\exists x\in X)(\exists y \in X) \ (x,y ) \notin R $$

or, using $R$ as a two-place predicate symbol:

$$(\exists x\in X)(\exists y \in X) \ \neg xRy $$

The second one can be simplified a little bit as well:

$$(\exists z \in X)(\exists y \in X)(\neg zRy \land (\forall x)(x\in X \Rightarrow (xRy \lor xRz))$$

Also note that you're doing a restricted quantifiation on $z$ and $y$, but not on $x$, which seems a bit arbitrary, so instead I would do:

$$(\exists z \in X)(\exists y \in X)(\neg zRy \land (\forall x\in X) (xRy \lor xRz))$$

And to be totally nitpicky, I would swap variables to keep it more consistent with the first answer:

$$(\exists x \in X)(\exists y \in X)(\neg xRy \land (\forall z\in X) (xRz \lor yRz))$$

So, while they were not incorrect, your translations could have been simplified.