Let the relation $R$ be defined on the set $\Bbb Z$ of integers by $a R b$ if and only if $a^2 − b^2$ is an integer multiple of $3$.

a) Determine whether $R$ is an equivalence relation. Either prove that $R$ is an equivalence relation or specifically demonstrate which properties of an equivalence relation it fails to have.

b) Determine $[1] =\{n \in\Bbb Z | 1 R n\}$.

I have already done part a (I believe it is reflexive, symmetric, and transitive, therefore it is an equivalence relation), however the second part is crazy. My professor's lecture notes on equivalence class was viciously underwhelming and he explained nothing in a way that was easy to understand. He is also not taking questions. I am not sure what "Determine $[1] =\{n \in\Bbb Z | 1 R n\}$. even means, let alone how to solve the problem. Can someone please explain and walk me through this in such a way that is easy to comprehend?

Thank you.

  • $\begingroup$ $[1]$ is the equivalence class of $1$ (with respect to $R$). This equivalence class contains all elements of $\mathbb Z$ that is equivalent to $1$ under $R$, i.e. the definition given, $[1] = \{n \in \mathbb Z|1\ R\ n\}$. The question asks you to write out that set explicitly. $\endgroup$ – player3236 Nov 11 '20 at 5:33

An equivalence relation partitions the domain into disjoint sets called equivalence classes. Every element of an equivalence class is related to every element of the same class but to no element outside the class. The union of the disjoint equivalence classes is the domain, i.e. each element of the domain belongs to exactly one equivalence class.

The equivalence class containing $x$ is denoted by $[x]$. It is the set of all members of the domain $\Bbb Z$ that are related to $x$. The expression $[1]=\{n\in\Bbb Z:1Rn\}$ says exactly that. Note that two integers may belong to the same equivalence class, but the distinct equivalence classes must be disjoint.

Can you reason why every element in $[1]$ defined in this manner is related to every other element in $[1]$, and not to any element in $\Bbb Z-[1]$?

If $x,y\in[1]$, then by definition $1Rx$ and $1Ry$. By transitivity of $R$ we have $xRy$. Further, if $\exists z\in\Bbb Z-[1]$ such that $xRz$, then by transitivity, $1Rx$ implies $1Rz$, a contradiction.

We know from the definition of the relation that $1Rn\iff nR1\iff3\mid(n^2-1)$. We can take $n=3k+i,i\in\{0,1,2\},k\in\Bbb Z$. Then $n^2-1=9k^2+i^2+6ki-1$.

Thus $3\mid n^2-1\iff3\mid i^2-1\iff i=1,2$.

Thus, $[1]=\{3k+1,3k+2:k\in\Bbb Z\}$.


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.