Find classes of relation equivalence

Question

$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!

score 1 · Accepted Answer · answered Nov 28 '18 at 17:57

1

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.

answered Nov 28 '18 at 17:57

Alejandro Nasif Salum

5,703

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! – Haus Nov 28 '18 at 18:28
1

No, because ${0,4,8,16,\ldots}\not\subset S$. – Alejandro Nasif Salum Nov 28 '18 at 18:43
So how would class of 4 look like? – Haus Nov 28 '18 at 18:45
1

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$.
– Alejandro Nasif Salum Nov 29 '18 at 21:17

Find classes of relation equivalence

1 Answers1