# Show that R is an equivalence relation

• Mar 21st 2010, 10:22 AM
Runty
Show that R is an equivalence relation
Let $\displaystyle A$ be the set of all bit strings of length 10. Let $\displaystyle R$ be the relation defined on $\displaystyle A$ where two bit strings are related if the third, fourth and last bits are the same. Show that $\displaystyle R$ is an equivalence relation and enumerate one bit string from each of the different equivalence classes of $\displaystyle R$.

I've already proven that $\displaystyle R$ is an equivalence relation, so don't worry about that half of the question.

The second half is what's giving me trouble. I am not entirely sure of how to do this, though I could guess. Since three bits are the same, are there $\displaystyle 2^3=8$ different equivalence classes of $\displaystyle R$?

EDIT: Here's my current answer to the second half. Can someone confirm if it works?
1100111110
1100111111
1101111110
1101111111
1110111110
1110111111
1111111110
1111111111
• Mar 21st 2010, 11:43 AM
Soroban
Hello, Runty!

Quote:

Let $\displaystyle A$ be the set of all bit strings of length 10.
Let $\displaystyle R$ be the relation defined on $\displaystyle A$ where two bit strings
are related if the third, fourth and last bits are the same.

a) Show that $\displaystyle R$ is an equivalence relation.

(b) Enumerate one bit string from each of the different equivalence classes of $\displaystyle R$.

You are right . . . There are 8 equivalence classes.

And they look like this:

. . $\displaystyle \begin{array}{c} \_\;\_\;0\;0\;\_\;\_\;\_\;\_\;\_\;0 \\ \_\;\_\;0\;0\;\_\;\_\;\_\;\_\;\_\;1 \\ \_\;\_\;0\;1\;\_\;\_\;\_\;\_\;\_\;0 \\ \_\;\_\;0\;1\;\_\;\_\;\_\;\_\;\_\;1 \\ \_\;\_\;1\;0\;\_\;\_\;\_\;\_\;\_\;0 \\ \_\;\_\;1\;0\;\_\;\_\;\_\;\_\;\_\;1 \\ \_\;\_\;1\;1\;\_\;\_\;\_\;\_\;\_\;0 \\ \_\;\_\;1\;1\;\_\;\_\;\_\;\_\;\_\;1 \end{array}$

And the blanks can be filled with any combination of 0's and 1's.