Set question, relations, equivalence classes

571 Views Asked by At

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?

3

There are 3 best solutions below

6
On BEST ANSWER

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.

0
On

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

0
On

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