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.
- $xR_ky \Longleftrightarrow k\:|\:(x+y)$
- $xS_ky \Longleftrightarrow k\:|\:(x-y)$
- $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.
Best Answer
Hint.
$(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$.