If $\forall x,y \in B$ if $(x,y) \in S$ and if $x+y$ is even then $x=y$ then each class of $S$ has at most $2$ elements

Question

Set $B = \{1,2,3,4,5\}$, $S$ - equivalence relation. It is given that for all $x,y \in B$ if $(x,y)\in S$ and if $x+y$ is an even number then $x = y$. In such case is it true that:

1. the number of elements in each equivalence class of $S$ is at most $2$
2. any relation $S$ would have an equivalence class made up of just one even number.

As far as I understand $S$ could be only of such form: $$ S = \begin{pmatrix}1&2&3&4&5\\1&2&3&4&5 \end{pmatrix} $$ because all pairs of $(x,y), x \neq y$ which are both odd numbers can't be in $S$ as well as all pairs $(x,y), x \neq y$ which are both even numbers for example: $$ \begin{pmatrix}1\\3 \end{pmatrix}, \begin{pmatrix}2\\4 \end{pmatrix} $$ because their sum will be even but $x \neq y$.

In addition $(x,y), x\neq y$ where one of them is odd and one is even also can't be in $S$ because then the relation will not be transitive and hence will not be an equivalence relation.

In such case I think the statement 1 is false because all equivalence classes are exactly of size $1$ and statement 2 is true because we have for example the equivalence class $\{2\}$ which is one even number.

I'm not sure about my logic because the question is quite tricky.

Answer 1

Your are right about the fact that you cannot have $(x,y)$ with both even or both odd and different, but there is a flaw in the second part of your argument. If you add to the identity relation also a single couple of pairs $(x,y)$ and $(y,x)$ with $x$ odd and $y$ even, everything is still fine: why should transitivity be broken? You can add even more, as long as you do not have $(x,y)$ and $(x',y)$ with $x$ and $x'$ even and different (or the same for $y$), because then you would brake transitivity. 1. follows from this, 2. requires a bit more but is also not far.

Answer 2

Assume that $S$ has an equivalence class with $2$ even numbers, namely $2$ and $4$. Then, $(x,y)\in S$ and $x+y=6$ which is even, but this contradicts $x=y$. Hence, two even numbers cannot be in the same equivalence class.

Now, assume that there exists an equivalence class with two odd numbers $x\neq y$. Then $x+y=\text{even},$ but again $x=y$ is not satisfied. Hence, if $x\neq y$ and $x,y$ odd, then they cannot be in the same equivalence class.

So, you have that any equivalence class in $S$ contains at most one even and at most one odd number. Since, there are five elements in $B$, this leaves you with a class that necessarily has one element. But I do not see why this has to be an even number. So, I agree with the first statement but disagree with the second statement (the even numnber part).

Answer 3

The answer to the first part is that if an equivalence class has three elements in it then two are odd or two are even, and the pair of common parity gives a counterexample to the condition.

For the second part, any equivalence class of size $2$ must consist of an odd number and an even number. Can you create a set of equivalence classes without an even singleton set?

I've left you some work to do, because only by working this through for yourself will you really get to understand. But you should appreciate that specifying an equivalence relation as a set of pairs is itself equivalent to expressing it by specifying the associated equivalence classes.