8
$\begingroup$

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?

$\endgroup$
2
  • 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$ Apr 21, 2015 at 3:22
  • $\begingroup$ great point @TrevorWilson good of you to mention that $\endgroup$
    – void
    Jan 8, 2018 at 11:52

4 Answers 4

13
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .