# Equivalence relations and their classes

Check for which $$k$$ given relations on set $$\mathbb{N}$$ are reflexive, symmetric or transitive. For these relations, that are equivalence relations, describe their equivalence classes.

1. $$xR_ky \Longleftrightarrow k\:|\:(x+y)$$
2. $$xS_ky \Longleftrightarrow k\:|\:(x-y)$$
3. $$xT_ky \Longleftrightarrow x - y = k$$

For the first example $$xR_ky \Longleftrightarrow k\:|\:(x+y)$$, I tried to do it like this:

• check if the relation $$R_k$$ is reflexive, so $$xR_kx \Longleftrightarrow k\:|\:(x+x)\equiv k\:|\:2x$$ - from that we get that $$2x$$ is always divisible if $$k=1$$ or $$k=2$$
• check if the relation $$R_k$$ is symmetric, so $$\Big[xR_ky \Longleftrightarrow k\:|\:(x+y)\Big] \Longrightarrow \Big[yR_kx \Longleftrightarrow k\:|\:(y+x)\Big]$$, which is true, because addition is commutative. From that we can conclude, that $$\exists n\in\mathbb{N} : x+y=k\cdot n$$.
• check if the relation $$R_k$$ is transitive, so $$(xR_ky \wedge yR_kz) \Rightarrow xR_kz$$. Thus $$\exists n\in\mathbb{N} : x+y=k\cdot n$$ and $$\exists m\in\mathbb{N} : y+z=k\cdot m$$.
And this is the first moment that I got stuck and I am not sure what to do next. Though I suppose that it is going to be an equivalence relation, but what would its equivalence classes look like?

When it comes to examples (2) and (3) I can easily say that they are not equivalence relations, as in both cases $$x-y \neq y-x$$, which tells us that the relation is not symmetric.

• Your argument for "symmetric" starts out well but then goes too far. Yes, commutativity shows that $xR_ky\iff yR_kx$ but that certainly doesn't show that $k$ always divides $x+y$. – lulu Dec 15 '18 at 21:04
• For transitive: note that, for all $k$, $1R_k(k-1)$ and $(k-1)R_k1$ but $1R_k1\iff k\in \{1,2\}$. So unless $k$ is $1$ or $2$ transitivity fails. Can you check $k=1,2$? – lulu Dec 15 '18 at 21:09
• Final hint: your argument for $(2)$ is much too hasty. If $k$ divides $x-y$ then it also divides $y-x$. – lulu Dec 15 '18 at 21:11
• I'm sorry for deleting my comment, but I accidentaly sent it before it was ready. Both $x$ and $y$ are $\mathbb{N}$, thus their sum is $\mathbb{N}$. And if $k = 1$, it divides any natural number. – whiskeyo Dec 15 '18 at 21:11
• Exactly correct, Well, I'd phrase it as "the equivalence classes are the Even numbers and the Odd numbers". – lulu Dec 16 '18 at 0:06

$$(a)R_k$$ is transitive for $$k=1$$, so we only need to check for $$k=2$$. If $$x+y$$ is even, either both $$x,y$$ are even or they are both odd. If $$y$$ is even, so is $$z$$ because $$y+z$$ is even. Similarly, if $$y$$ is odd, so is $$z$$. This means $$x,z$$ are either both even or both odd, or that $$x\ R_2\ z$$.
$$(b)$$ The equivalence of $$S_k$$ does not necessitate $$x-y=y-x$$. It only necessitates if $$k|\ x-y$$, then $$k|\ y-x$$, which is always true. In fact, $$S_k$$ is an equivalence relation $$\forall k\in\Bbb N$$.
$$(c)$$ Try $$x-y=y-x=k=0$$.
• I proved that $R_k$ from example (a) is equivalence relation for $k\in \{1,2\}$ and in (b) that it is true $\forall k \in \mathbb{N}$. When it comes to relation $xT_ky \Leftrightarrow x-y=k$ I know that it is reflexive for $k=0$ and symmetric for $k=0$, but I am not sure how to determine is transitive. According to earlier conclusion (that $k=0$), I think that it is enough to check if it works for $T_0$, which means $(x-y=0 \wedge y-z=0) \Rightarrow x-z=0$, the only case when it works is when $x=y=z$ - does it say that $T_0$ is not equivalence relation (because it works only in one case)? – whiskeyo Dec 16 '18 at 18:36
• $T_0$ is just the equality relation. It is transitive. By definition, if $T_0$ is transitive, then $x\ T_0\ y, y\ T_0\ z\implies x\ T_0\ z$. Now, $x\ T_0\ y\implies x=y; y\ T_0\ z\implies y=z\ \therefore x=z$ or $x\ T_0\ z$. – Shubham Johri Dec 17 '18 at 6:38
• The fact that it only works in one case means the equivalence classes of $T_0$ are singleton. They are $\{1\},\{2\},\{3\}...$ – Shubham Johri Dec 17 '18 at 6:42