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$

1 Answer 1

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$
1
  • $\begingroup$ Oh, too true! Thanks! $\endgroup$
    – user163831
    Commented Dec 5, 2014 at 19:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .