Let $S = [10]$ (the set containing the integers 1,...,10). Define an equivalence relation R on S by $xRy$ $iff$ $x^2 \equiv y^2$ (mod 5) is an equivalence relation and determine the equivalence classes.

What I have

I'll define R by $$R=\{(3,2), (4,1), (6,1), (6,4), (7,2), (7,3), (8,2), (8,3), (8,7), (9,1), (9,4), (9,6), (10,5)\}$$

Definition of equivalence classes: Given an equivalence relation of S, the set of elements equivalent to $x \in S$ is the equivalence class containing x.

I interpret this as meaning that to be in the same class that one of the coordinates must be the same as another one of the coordinates in a different ordered pair?

If so then the equivalence classes are:

$EC_1=\{(3,2), (7,2), (7,3), (8,2), (8,3), (8,7)\}$

$EC_2=\{(4,1), (6,1), (6,4), (9,1), (9,4), (9,6)\}$


I cannot really tell if I've applied all the definitions and concepts correctly, and would appreciate any input, but this is as far as I could get from reading the chapter, in my textbook. Thank you in advanced.


2 Answers 2


Equivalence classes are subsets of $S$ where all elements of each one are related by the equivalence relation.

They partition the set.   Every element in the set will appear in one and only one equivalence class.

The relation $R$ defined as $x\mathop{R}y \iff \Big[x^2\equiv y^2\mod 5\Big]$ means that one such class is $\{1,4,6,9\}$ another is $\{2,3,7,8\}$, and the third is $\{5, 10\}$.

Because $ \begin{align} 1^2 & \equiv 4^2\mod 5 \\ & \equiv 6^2 \mod 5 \\ & \equiv 9^2 \mod 5 \end{align}$ and so forth.

PS: Your representation of relation $R$ is not complete.

$$\begin{array}{rl}R & =\left\{\begin{align} (1,1),(1,4),(1,6),(1,9), \\ (2,2),(2,3),(2,7),(2,8), \\ (3,2),(3,3),(3,7),(3,8), \\ (4,1),(4,4),(4,6),(4,8), \\ (5,5), (5,10), \\ (6,1),(6,4),(6,6),(6,9), \\(7,2),(7,3),(7,7),(7,8), \\ (8,2),(8,3),(8,7),(8,8), \\ (9,1),(9,4),(9,6),(9,9), \\\ (10,5),(10,10)\end{align}\right\}\end{array}$$


The equivalence classes should be:




The equivalence classes are made of the elements of $S$.


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.