How many equivalence classes have the quotient set of this relation $R$?

22 Views Asked by At

How many classes have the quotient set defined on $\Bbb{Z}^2$ by the following?: $$(x,y)R(u,v)\iff x\equiv u\pmod{4}\quad\wedge\quad y\equiv v\pmod{2}.$$


I think they are asking for $|\Bbb{Z}^2/R|$.

We can express the relation as a system of equations: $$\begin{cases}x-u=4k\\y-v=2m\end{cases}\to (x+y)-(u+v)=2(2k+m)=2l\to x+y\equiv u+v\pmod{2},$$ hence $|\Bbb{Z}^2/R|=2$.

Is that right?

3

There are 3 best solutions below

0
On BEST ANSWER

No. There are $8$ equivalent classes. For each $(x,y)\in\mathbb Z^2$ there is one and only element$$(u,v)\in\bigl\{(0,0),(1,0),(2,0),(3,0),(0,1),(1,1),(2,1),(3,1)\bigr\}$$such that $(x,y)\mathrel R(u,v)$. You just take $u$ equal to the remainder of the division of $x$ by $4$ and take $v$ equal to the remainder of the division of $y$ by $2$.

0
On

Hint: show $\,(x',y')\,R\,(x,y)\!\iff\! (x'_{(4)},\:\!y'_{(2)}) = (x_{(4)},\:\!y_{(2)}),\,$ where $\,x_{(n)} := x\bmod n.\,$ This means that the remainder pair $\,(x_{(4)},y_{(2)})\,$ is a normal form for $\,(x,y).\,$ Clearly there are $\,4\cdot 2\,$ such pairs.

2
On

Consider the group homomorphisms $\mathbf Z\xrightarrow{\quad p\quad}\mathbf Z/4\mathbf Z$, $n\longmapsto n\bmod 4$ and the similar map $q$ onto $\mathbf Z:2\mathbf Z$. One deduces the product map \begin{align} \mathbf Z\times\mathbf Z&\xrightarrow{\enspace p\times q\enspace} \mathbf Z/4\mathbf Z\times \mathbf Z/2\mathbf Z,\\(x,y)&\xrightarrow{\qquad\:}(x\bmod4,y\bmod 2)\end{align} which is onto and has kernel $4\mathbf Z \times 2\mathbf Z$. Therefore $(\mathbf Z\times\mathbf Z)/R$ is isomorphic to $\mathbf Z/4\mathbf Z\times\mathbf Z/2\mathbf Z$, which has $8$ elements.