0
$\begingroup$

Each bead on a bracelet with three beads is either red, white, or blue. Define the relation R between bracelets as: (B1, B2), where B1 and B2 are bracelets, belongs to R if and only if B2 can be obtained from B1 by rotating it or rotating it and then reflecting it.

a) show that R is an equivalence relation

b) what are the equivalence classes of R.

I have no idea how to start this problem at all. We barely went over equivalence relations and equivalence classes. I realize that equivalence equations are when the equation is reflexive, symmetric, and transitive, but that's about it.

Any help is appreciated

$\endgroup$
1
$\begingroup$

I'll get you started on (a).

Consider an element $x$. Trivially, $xRx$, right? We just don't rotate or reflect at all. So the relation is reflexive.

Now consider symmetry. Suppose $xRy$. What happens if we undo those operations from $y$? We just get back to $x$. So undoing a reflection is a reflection, and the same for a rotation, right? So we have symmetry.

Now what about transitivity? If we have $xRy$ and $yRz$, haven't we just rotated and/or reflected from $x$ to $z$?

Edit: A bit more on equivalence classes. If you are given $x$, think of all the elements $x$ can reach through these operations of rotation and reflection. $xRy$ for all such $y$ where $x \to y$ from such combinations of rotations and reflections, right? Now consider if $x \not R y$. What does that mean?

$\endgroup$
  • $\begingroup$ Ok, I see what you are saying. To be honest, my main problem is that I dont really understand equivalence classes. If you could atleast point me in the right direction that would help alot $\endgroup$ – Eric Rangil Nov 25 '14 at 5:36
  • $\begingroup$ @EricRangil: The answer works because the process of Rotation and Reflection can be uniquely inverted. $\endgroup$ – user 170039 Nov 25 '14 at 5:40
  • $\begingroup$ @EricRangil I've updated with a bit more on equivalence classes. Hopefully this will help you conceptualize them. $\endgroup$ – ml0105 Nov 25 '14 at 5:57
  • $\begingroup$ An important fact here is that one rotation-plus-reflection operation, followed by another rotation-plus-reflection, results in a rotation (without reflection) of the original object. That's part of the reason why $xRy \wedge yRz$ implies $xRz$. $\endgroup$ – David K Jan 2 '15 at 16:05
0
$\begingroup$

An equivalence class is a subset of the domain. Given a relation $R$ that is reflexive, symmetric, and transitive, everything in an equivalence class is related through $R$ to everything in the same class.

Another way of putting it is that if you take any element $x$ of the domain, then the equivalence class of $x$ contains every $y$ such that $xRy.$ Note that because of symmetry and transitivity, $yRx$ as well and $yRz$ whenever $xRz,$ so the equivalence class of $x$ contains every $z$ such that $yRz$ and therefore it is an equivalence class of $y$ as well.

But no element of an equivalence class can relate to an element of any other equivalence class through $R$; if the two elements were related, they would be in the same class.

If $xRy$ means the bracelet $x$ can be rotated and/or reflected to match $y,$ then you can generate the equivalence class of a bracelet by performing every possible rotation and/or reflection on it. You can then take any bracelet that is not in the equivalence class of your first bracelet, and generate another equivalence class from it. Since you have only finitely many bracelets, and actually not very many of them, for this problem you can write out all the equivalence classes by literally listing every element in each class.

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