# Thread: Relation of eight bit strings

1. ## Relation of eight bit strings

Let R be the relation defined on the set of eight-bits strings by s1RS2
provided that s1 and s2 have the same number of zeros.
(a) Show that r is an equivalent relation.
(b) How many equivalence classes are there?
(c) List one member of each equivalence class.

3. ## Re: Relation of eight bit strings

The following remark is probably not very suitable to the level of the question, but if there is some function f : X -> Y, then the relation x₁ R x₂ defined by f(x₁) = f(x₂) is an equivalence relation. It is important that f is a function, not a general relation.

4. ## Re: Relation of eight bit strings

Hello, whyyie!

$\displaystyle \text{Let }\mathbb{R}\text{ be the relation defined on the set of eight-bits strings by: }\,s_1\mathbb{R}s_2$
$\displaystyle \text{provided that }s_1\text{ and }s_2\text{ have the same number of zeros.}$

$\displaystyle \text{(a) Show that }\mathbb{R}\text{ is an equivalence relation.}$

$\displaystyle \text{Reflexive: }\:s_1\mathbb{R}s_1$
. . $\displaystyle s_1\text{ has the same number of zeros as }s_1\text{ . . . Yes}$

$\displaystyle \text{Symmetric: }\:\text{If }s_1\mathbb{R}s_2\text{, then }s_2\mathbb{R}s_1$
. . $\displaystyle \text{If }s_1\text{ and }s_2\text{ have equal zeros, then }s_2\text{ and }s_1\text{ have equal zeros . . . Yes}$

$\displaystyle \text{Transitive: }\:\text{If }s_1\mathbb{R}s_2\text{ and }s_2\mathbb{R}s_3\text{, then }s_1\mathbb{R}s_3.$
. . $\displaystyle \text{If }s_1\text{ and }s_2\text{ have equal zeros and }s_2\text{ and }s_3\text{ have equal zeros,}$
. . $\displaystyle \text{then }r_1\text{ and }r_3\text{ have equal zeros . . . Yes}$

$\displaystyle \text{Therefore, }\mathbb{R}\text{ is an equivalence relation.}$

(b) How many equivalence classes are there?

Nine.

(c) List one member of each equivalence class.

$\displaystyle \begin{array}{cc} \text{no zeros} & 11111111 \\ \text{1 zero} & 01111111 \\ \text{2 zeros} & 00111111 \\ \vdots & \vdots \\ \text{7 zeros} & 00000001 \\ \text{8 zeros} & 00000000 \end{array}$