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.

  • $\begingroup$ 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$. $\endgroup$ – lulu Dec 15 '18 at 21:04
  • $\begingroup$ 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$? $\endgroup$ – lulu Dec 15 '18 at 21:09
  • 2
    $\begingroup$ Final hint: your argument for $(2)$ is much too hasty. If $k$ divides $x-y$ then it also divides $y-x$. $\endgroup$ – lulu Dec 15 '18 at 21:11
  • $\begingroup$ 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. $\endgroup$ – whiskeyo Dec 15 '18 at 21:11
  • 2
    $\begingroup$ Exactly correct, Well, I'd phrase it as "the equivalence classes are the Even numbers and the Odd numbers". $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ 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)? $\endgroup$ – whiskeyo Dec 16 '18 at 18:36
  • $\begingroup$ $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$. $\endgroup$ – Shubham Johri Dec 17 '18 at 6:38
  • $\begingroup$ The fact that it only works in one case means the equivalence classes of $T_0$ are singleton. They are $\{1\},\{2\},\{3\}...$ $\endgroup$ – Shubham Johri Dec 17 '18 at 6:42

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.