# Relation of eight bit strings

• Jun 13th 2012, 11:25 PM
whyyie
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.
• Jun 14th 2012, 01:25 AM
tom@ballooncalculus
Re: Relation of eight bit strings
• Jun 14th 2012, 03:30 AM
emakarov
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.
• Jun 14th 2012, 07:33 AM
Soroban
Re: Relation of eight bit strings
Hello, whyyie!

Quote:

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

Quote:

(b) How many equivalence classes are there?

Nine.

Quote:

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