2

Let S be the set of all bit strings (a sequence of 1s and 0s) of length 3 or more.

Let R be a relation on S of all pairs (x, y) where x and y are in S if x and y have the same first two bits.

Is R is an equivalence relation? If so, how many equivalence classes are there?

Emanuele Paolini
  • 21,447
Hellokittybro
  • 43
  • Relations of the form "apply a function to both and check if the results are equal" are always equivalence relations, and the number of equivalence classes is the number of different results the function can have. – Hagen von Eitzen Sep 26 '15 at 06:06
  • Thanks for your answer. I am still confused as to what the equivalence classes would be in this example. – Hellokittybro Sep 26 '15 at 06:12

3 Answers3

1

The first two bits of every string identifies uniquely the equivalence class.

Emanuele Paolini
  • 21,447
1

Hint:

Remember that equivalence relations will induce a partition. So, ask yourself: will $S$ induce a partition on the Whole set? How many classes I will have if there are two different ways to set zeros and ones in the position you want to.

eNR
  • 321
  • So, (0,1) (1,0) ? So two different classes? – Hellokittybro Sep 26 '15 at 06:52
  • Whoops, (0,0) (1,1) maybe? – Hellokittybro Sep 26 '15 at 06:55
  • I would bet for the second comment you gave here. :) – eNR Sep 26 '15 at 06:56
  • Sweet. How would i write that out? I know the answer doesn't ask for the classes, i just say there are two, but how would i write it if it asked for them? – Hellokittybro Sep 26 '15 at 06:58
  • To write it, remember that $x$ and $y$ are sequences whit length 3 or more. Then ONE equivalence class would be given by the sequences of the form $x=\left{0,0,...\right}$. Write that in the notation your book, teacher or webpage gave you. Another thing to consider, there should be 4 different classes, check the form of the elements. – eNR Sep 26 '15 at 07:06
  • How come there are 4 difference classes? Isn't there only two? – Hellokittybro Sep 26 '15 at 07:48
1

I think what you looking for is for [00][01][10][11] I think!

RakaRajuCurrySmellMax
  • 11