Let $A = \{0,1,2,3,4\}$ and define a relation $R$ on $A$ as follows:

$$R = \{(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)\}.$$

Find the distinct equivalence classes of $R$.

How do I solve this problem? What is an equivalence class? As I understand it so far, the equivalence class of $a$, is the set of all elements $x$ in $A$ such that $x$ is related to $a$ by $R$. What does this mean in my problems case?

  • 2
    $\begingroup$ By the way, the elements of a relation (e.g. $R$) are ordered pairs (e.g. $(1,3)$) rather than unordered pairs (e.g. $\{1,3\}$.) Although the mistake is not very confusing here because $R$ is symmetric. $\endgroup$ – Trevor Wilson Apr 21 '15 at 3:22
  • $\begingroup$ great point @TrevorWilson good of you to mention that $\endgroup$ – void Jan 8 '18 at 11:52

The equivalence classes are $\{0,4\},\{1,3\},\{2\}$. to see this you should first check your relation is indeed an equivalence relation. After this find all the elements related to $0$. Then pick the next smallest number not related to zero and find all the elements related to it and so on until you have processed each number.

  • $\begingroup$ short and precise answer! +1 $\endgroup$ – void Jan 8 '18 at 11:59

Let $\sim$ be an equivalence relation (reflexive, symmetric, transitive) on a set $S$.

The equivalence class under $\sim$ of an element $x \in S$ is the set of all $y \in S$ such that $x \sim y$. An equivalence relation will partition a set into equivalence classes; the quotient set $S/\sim$ is the set of all equivalence classes of $S$ under $\sim$.

At the extreme, we can have a relation where everything is equivalent (so there is only one equivalence class), or we could use the identity relation (in which case there is one equivalence class for every element of $S$). But typically we're interested in nontrivial equivalence relations, so we have multiple classes, some of which have multiple members.

As an example, the rational numbers $\mathbb{Q}$ are defined such that $a/b=c/d$ if and only if $ad=bc$ and $bd\ne 0$. This is an equivalence relation on $\mathbb Z \times (\mathbb Z \setminus \{0\})$; here there are infinitely many equivalence classes with each with infinitely many members.

Considering your example, we find that

  • $(0,4) \in R$, so 0 and 4 are in the same class;
  • $(1,3) \in R$, so 1 and 3 are in the same class;
  • $(2,2) \in R$, and 2 does not occur in any other pairs in R, so 2 is in a class by itself.

Of course, before I could assign classes as above, I had to check that $R$ was indeed an equivalence relation, which it is.

Thus $A/R=\{\{0,4\},\{1,3\},\{2\}\}$ is the set of equivalence classes of $A$ under $R$.


The short answer to "what does this mean":

To say that $x$ is related to $y$ by $R$ (also written $x \mathbin {R} y$, especially if $R$ is a symbol like "$<$") means that $(x,y) \in R$.

(Well, there may be some ambiguity about whether $(x,y) \in R$ is read as "$x$ is related to $y$ by $R$" or "$y$ is related to $x$ by $R$", but it doesn't matter in this case because your relation $R$ is symmetric.)


Let 𝐴={0,1,2,3,4} and define a relation 𝑅 on 𝐴 as follows:

𝑅={(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)}. Find the distinct equivalence classes of 𝑅.

These are actually really fun to do once you get the hang of them!

The way I think of equivalence classes given a set of ordered pairs as well as given a set A, is what is related to what. First, I start with 0, and ask myself, which ordered pairs in the set R are related to 0?

Here it goes! (think of equivalence class as x in an ordered pair y, and the equivalence class of x is what x is related to in the y value of the ordered pair)

[0]: 0 is related 0 and 0 is also related to 4, so the equivalence class of 0 is {0,4}. [2]: 2 is related to 2, so the equivalence class of 2 is simply {2}. [3]: 3 is related to 1, and 3 is also related to 3, so the equivalence class of 3 is {1,3}. [4]: 4 is related to 0, and 4 is also related to 4, so the equivalence class of 4 is {0,4}.

Notice that the equivalence class of 0 and 4 are the same, so we can say that [0]=[4], which says that there are only three equivalence classes on the relation R.

New contributor
Joe is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

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.