3
$\begingroup$

Find the equivalence classes of the relation R = {(0, 0),(1, 1),(1, 2),(2, 2),(2, 1),(3, 3),(3, 4),(4, 3),(4, 4)}

on the set A = {0, 1, 2, 3, 4}.

How do i solve this question. I'm attempting to teach myself at the moment so any help will be appreciated.

As far as i'm aware the equivalence class of a is the set of all elements x in A, such that x is related to a by r.

$\endgroup$
3
  • 1
    $\begingroup$ just like you said, which are the elements that $1$ is related to, for example? $\endgroup$
    – Mirko
    May 20, 2019 at 2:45
  • $\begingroup$ For a equivalence relation, the relation itself is reflexive ($aRa$ is true), symmetric ($aRb \implies bRa$), and transitive ($aRb, bRc \implies aRc$). All at once. $\endgroup$
    – rikusp2002
    May 20, 2019 at 3:10
  • $\begingroup$ Since (1,1) is in R, 1 is related to itself (and in general x is related to itself, for every equivalence relation). For the given R, 1 is also related to 2 (and 2 is related to 1). 1 is related to no other elements (apart from 1 and 2). So the equivalence class of 1 is {1,2}. Since 0 is only related to itself, its equivalence class is {0}. All equivalence classes are {0}, {1,2} and {3,4}. Now let me give you a different problem, what are the equivalence classes for the relation Q={(5,6),(6,5),(7,7),(8,8),(5,5),(6,6)}? $\endgroup$
    – Mirko
    May 20, 2019 at 13:07

2 Answers 2

5
$\begingroup$

The equivalence class of $x$, denoted $[x]$, is the set of all elements of $A$ that are related to $x$. More formally, $[x] = \{y \in A | (x,y) \in R\}$.

Looking at $R$, we see that $1$ is related to $2$ and $3$ is related to $4$, so we can ‘combine’ the equivalence classes for $1$ and $2$, and for $3$ and $4$. We can ignore all of the other pairs as they are simply the result of the fact that $R$ is an equivalence relation—they don’t give us any more information. We have $[1] = [2]$ and $[3] = [4]$ and so our equivalence classes are

$$[0] = \{0\}$$ $$[1] = \{1,2\}$$ $$[2] = \{1,2\}$$ $$[3] = \{3,4\}$$ $$[4] = \{3,4\}$$

An equivalence relation on $A$ induces a partition on $A$, so we may also show the equivalence classes by writing

$$\{\{0\},\{1,2\},\{3,4\}\}$$

$\endgroup$
0
$\begingroup$

As you said in the question, we form equivalence classes by finding elements in $R$ related to different elements of $A$.

So from the relation $R$ we find that $(0,0) \in R \Rightarrow 0 \in [0].$ Also, $ (1,2) \in R \Rightarrow 2 \in [1]\ \text{and}\ 1 \in [2]$ etc. Therefore, $[0] = \{0\}, [1] = \{1,2\}$ etc.

Here $[\cdot]$ denotes an equivalence class and '$\cdot$' is the representative of the class.

Can you find other classes like $[2]$ and $[3]$ from here?

$\endgroup$
2
  • 1
    $\begingroup$ An equivalence class of an element of $A$ should be a subset of $A$, rather than a set of pairs in $R$. So $[0] = \{0\}$ rather than $\{(0,0)\}$, for example. $\endgroup$ May 20, 2019 at 3:47
  • $\begingroup$ I just made a blunder, I would correct it now, thanks. $\endgroup$
    – Rick
    May 20, 2019 at 3:50

You must log in to answer this question.

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