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.)


Your Answer

