Finding the equivalence classes of a relation R

Question

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?

Answer 1

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.

Answer 2

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 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 since 2 does not occur in any other pairs in R, it 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$.

Answer 3

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