0
$\begingroup$

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 =\

$\endgroup$
0
$\begingroup$

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*} $$

$\endgroup$
  • $\begingroup$ Oh, too true! Thanks! $\endgroup$ – user163831 Dec 5 '14 at 19:46

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.