Let B denote the set of all bit strings of length 5, $b_1,b_2,b_3,b_4,b_5$. Define a relation R on B by: two bit strings are related by R if and only if they both have bits $b_1$ the same and both have the bits $b_5$ the same.

(a) List all the elements of the equivalence class [10010].

(b) How many distinct equivalence classes are there? List them.

So we never went over bit strings in class and I'm trying to apply the same concepts as a similar question that had integers and ordered pairs.

For part (a), the elements of the equivalence class [10010] is just 0 and 1?

For part (b), the distinct equivalence classes are all of the variations of the 5 bit strings where bits $b_1$ and $b_5$ are the same? for example, [10010] and [11110]? How would I go about determining the exact number of distinct equivalent classes?

Any help is appreciated,

thanks in advance

  • 1
    $\begingroup$ Well, can you give a single string equivalent to $10010$ other than itself? $\endgroup$ – lulu Sep 7 '17 at 23:11
  • 1
    $\begingroup$ I don't understand your answer "$0$ and $1$"...neither of those are strings of length $5$. $\endgroup$ – lulu Sep 7 '17 at 23:12
  • 1
    $\begingroup$ Every string with $b_1 = 1$ and $b_5 = 0$ is in the equivalence class of 10010 $\endgroup$ – Namaste Sep 7 '17 at 23:13
  • $\begingroup$ I guess I'm confused by what the question means by the word element. An element of the equivalence class. $\endgroup$ – Jamie Sep 7 '17 at 23:13
  • $\begingroup$ Ah, thanks. so every string with [1 _ _ _ 0] and filling in the blanks with variations of 0 or 1 is an element of [10010]. $\endgroup$ – Jamie Sep 7 '17 at 23:18


(a) [10010] [10110] [10100] [10000] [11000] [11100] [11010] [11110]

(b) 4 distinct equivalence classes. [10000] [10001] [00000] [00001]

  • $\begingroup$ No. (b) asks for how many distinct equivalence classes. Not for each element of each class. $\endgroup$ – Wildcard Sep 8 '17 at 0:30
  • $\begingroup$ @Wildcard So the distinct equivalence classes would be [10000] [10001] [00000] [00001] ? $\endgroup$ – Jamie Sep 8 '17 at 0:40
  • $\begingroup$ Yes, and the actual answer is "4." And then execute the further instructions given by writing what you just commented. To do math textbooks you should get good at exact readings and executions of what is stated. "How many distinct equivalence classes are there? List them." $\endgroup$ – Wildcard Sep 8 '17 at 0:42
  • $\begingroup$ @Wildcard Thanks for the help and tips! $\endgroup$ – Jamie Sep 8 '17 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.