$S=\{3n+1:n∈N\} = \{1,4,7,10,...\}$ and relation is defined as:

$(x,y) ∈ ρ \text{ def }⇔ 4|(x + 3y)$

I need to prove that relation is relation of equivalence (that means that it is reflexive, symmetric and transitive.) I know how to do that, and once I prove that it is relation of equivalence, I need to find the equivalence classes.

My question is: For example: class of $1$ is defined as $$1=\{x∈S : x\text{ is related to }1\} = \{x∈S: 4|(x + 3*1)\} = \{3n+1:n∈N\text{ and }4|(3n+1)+3\text{ or just }4|(3n+3)\}$$ ???

Please help, thank you!


Well, let's say that the equivalence class of $1$ is $$\bar 1=\{x\in S \colon (x,1)\in \rho\}=$$$$=\{x\in S\colon 4|x+3\cdot 1\}=\{x\in \mathbb N_0\colon x=3n+1, 4|(3n+1)+3\}.$$

So $\bar 1$ is the set of natural numbers such that $x=3n+1$, $(n\in \mathbb N_0)$ and $4|3n+4$.

Since this is the same that $4|3n$, this implies $4|n$, so $n=4k$ with $k\in \mathbb N_0$.

So the elements of $\bar 1$ are those of the form $3n+1=12k+1$ with $k\in \mathbb N_0$, that is, $$\bar 1=\{1,13,25,37,\ldots\}$$ (note that, in fact, $\bar 1\subset S$) and you can figure out what (and how many) other equivalence classes there are.

  • $\begingroup$ Does it means that the elements of class 4 will have form 3n+1 = 4k with k ∈ N and that is {0, 4, 8, 16,...} ? Thanks! $\endgroup$ – Haus Nov 28 '18 at 18:28
  • 1
    $\begingroup$ No, because $\{0,4,8,16,\ldots\}\not\subset S$. $\endgroup$ – Alejandro Nasif Salum Nov 28 '18 at 18:43
  • $\begingroup$ So how would class of 4 look like? $\endgroup$ – Haus Nov 28 '18 at 18:45
  • 1
    $\begingroup$ You can do the same math for $4$ instead of $1$, and you would get$$\bar 4=\{4,16,28,40,\ldots\}.$$ Also $$\bar7=\{7,19,31,43,\ldots\}$$ and $$\bar{10}=\{10,22,34,46,\ldots\},$$ and those are the only four equivalence classes in $S$. $\endgroup$ – Alejandro Nasif Salum Nov 29 '18 at 21:17

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.