# Construct equivalence classes for a relation R

Define relation R as follows: xRy if x and y are bit strings with |x| >= 2 and |y| >= 2 such that x and y agree in their first two bits. Show that R is an equivalence relation. Construct the equivalence classes for R.

Reflexive? Let x=y. Then xRx, since x is a bit string with cardinality >= 2, and agrees in its own first two bits.

Symmetric? Yes, because the conditions are not dependent on order. If xRy then yRx just as well.

Transitive? Indeed; if xRy and yRz, then x, y, and z are all bit strings with cardinality >= 2 with the same first two bits. Therefore xRz.

But to construct the equivalence classes, I don't even know where to start =\

If $R$ is an equivalence relation on the set $A$, the equivalence class of the element $a \in A$ is ${[a]}_{R} = \{s \, | \, a R s\}$. The set $A$ here is the set of all bit-strings of length $\geq 2$.
We can take $00$, $01$, $10$, and $11$ as representatives (why?), giving us the following equivalence classes: $$\begin{gather*} {[00]}_{R} = \text{the set of all bit-strings which begin with }00 \\ {[01]}_{R} = \text{the set of all bit-strings which begin with }01 \\ {[10]}_{R} = \text{the set of all bit-strings which begin with }10 \\ {[11]}_{R} = \text{the set of all bit-strings which begin with }11 \end{gather*}$$