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.

Re: Relation of eight bit strings

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.

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