Thread: Regarding Discrete Mathematics Questions (Relation Question)

Relation R defined on the set of seven-bit strings by s₁Rs₂, provided that the first four bits of s₁ and s₂ coincide

(i) Show that R is anequivalence relation.

(iii) List one (1) member of each equivalence class.

I answered this on another board but:
To be an equivalence relation R must be
1) Reflexive. For any x, we must have xRx.
That's easy to prove. Comparing such a string to itself, all bits are the same so certainly the first four bits are.

2) Symmetric. If xRy then yRx.
Again, easy. If xRy then x has the same first four bits as y. . But "=" is symmetric (it is the "ideal" equivalence relation) so . That is yRx.

4)Transitive. If xRy and yRz then xRz. If xRy then . If yRz then . Again "=" is transitive so . That is, xRz.

Two bitstrings are "equivalent" if the first four bits are the same. There are different 4 bit strings. They are
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, and 1111.
So there are 16 equivalence classes. We can list one member of each by appending any three bits we like to the end of those. I choose 000:
0000000
0001000
0010000
0011000
0100000
0101000
0110000
0111000
1000000
1001000
1010000
1011000
1100000
1101000
1110000
1111000

are one member of each of the 16 equivalence classes.