0
$\begingroup$

I have the following relation $R\subseteq\mathbb{N}\times\mathbb{N}$: $$R=\left\{ (x,y)\,:\,x\equiv y\mod5\right\} $$ I have proved that $R$ is a equivalence relation. I would like to find the equivalence classes. As I understand the classes are $[i]$ where $i\in \{0,\ldots,4\}$. I'm struggling of proving it formally. Is it possible to show how to prove it formally?

$\endgroup$
2
  • $\begingroup$ For you, is $0$ an element of $\mathbb N$? $\endgroup$ Dec 28 '19 at 20:27
  • $\begingroup$ @JoséCarlosSantos Yes $\endgroup$
    – vesii
    Dec 28 '19 at 20:30
0
$\begingroup$

You have to show that these classes are disjoint and their union is the set of natural numbers. Make sure to chose $5$ instead of $0$ as the representative of that class.

$\endgroup$
0
$\begingroup$

Yes, it is correct. If $x\in\mathbb N$, then let $r_x$ be the remainder of the division of $x$ by $5$. Then:

  1. $r_x\in\{0,1,2,3,4\}$;
  2. $x\equiv r_x$.

Furthermore, if $i,j$ are distinct elements of $\{0,1,2,3,4\}$, then $i\not\equiv j$.

$\endgroup$
0
$\begingroup$

It can be proved that an equivalence relation partitions the set it's defined on.

In this case, the equivalence classes partition $\Bbb N$ into $5$ equivalence classes. For each $n\in\Bbb N$, $\exists! k\in\{0,1,2,3,4\}$ such that $n=k+5l$ for some $l$.

This is the result of Euclidean division.

$\endgroup$

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.