2
$\begingroup$

The set R:

$R = $ {(0,1), (0,0), (1,0), (1,1), (2,3), (2,2), (3,2), (3,3) (4,5), (5,4), (4,4), (6,6), (5,5) (6,7), (7,6), (7,7)}

I was just wondering if I've found the right equivalence classes for this relation?

My working:

The relation is an equivalence relation. Therefore, $[X]_R = ${ {0,1}, {2,3}, {4,5}, {6,7} }

$\endgroup$
4
  • 2
    $\begingroup$ $R$ is not an equivalence relation because it is not transitive. $(1,0)\in R$ and $(0,1)\in R$, but $(1,1)\notin R$. $\endgroup$ – user729424 Jan 20 '20 at 23:35
  • 1
    $\begingroup$ @AndrewOstergaard sorry turns out there was a typo, I just corrected it. $\endgroup$ – jame_smith Jan 20 '20 at 23:40
  • $\begingroup$ "The relation is an equivalence relation. Therefore, [X]R={ {0,1}, {2,3}, {4,5}, {6,7} }" Huh???? Why does R being an equivalence relation mean those are the classes? $\endgroup$ – fleablood Jan 22 '20 at 2:37
  • $\begingroup$ Also what set is $R$ a relation on? If it's a relation on any set other than $\{0,1,2,3,4,5,6,7\}$ its not an equivalence relation. $\endgroup$ – fleablood Jan 22 '20 at 2:39
2
$\begingroup$

Yes. $$X/R = \{\{0,1\},\{2,3\},\{4,5\},\{6,7\}\}$$


The first task is to confirm that $R$ is an equivalence relation over $\{0,1,2,3,4,5,6,7\}$ (that is $X$).   After your correction, we can quickly verify that $R$ is indeed reflexive, symmetric, and transitive over $X$.   After a quick resort, we can just eyeball it.

$${R}~{=}~{\{~{{(0,0), (0,1), (1,0), (1,1),}\\{ (2,2), (2,3), (3,2), (3,3),}\\{ (4,4), (4,5), (5,4), (5,5),}\\{ (6,6), (6,7), (7,6), (7,7)}}~\}}$$

The next task is to identify what subsets sets of the base set are related. That is, determine how $R$ partitions the set.   We only need to step through all of the eight elements of $X$ and sort them into sets of related elements.   We immediately see that $0$ is related only to itself and $1$, and so forth.

Thus this partition is indeed: $\{\{0,1\},\{2,3\},\{4,5\},\{6,7\}\}$.

This partition is the set of the equivalence classes of $R$ over $X$.

$\endgroup$

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.