# Math Help - Show that R is an equivalence relation

1. ## Show that R is an equivalence relation

Let $A$ be the set of all bit strings of length 10. Let $R$ be the relation defined on $A$ where two bit strings are related if the third, fourth and last bits are the same. Show that $R$ is an equivalence relation and enumerate one bit string from each of the different equivalence classes of $R$.

I've already proven that $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 $2^3=8$ different equivalence classes of $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

2. Hello, Runty!

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

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

(b) Enumerate one bit string from each of the different equivalence classes of $R$.
You are right . . . There are 8 equivalence classes.

And they look like this:

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