I am learning about relations and I was hoping to find out if my attempt for my question looks right.
Let b(n) equal the value of the highest bit set to 1 in the binary representation of the positive integer n. (For example, b(27)=16 because in 27= $11011_2$ and the most significant bit set to one is the first bit on the left, which has value $2^4$.)
Prove that the relation, R, defined below over the set of integers in between 0 and 1023, inclusive, is an equivalence relation. Into how many equivalence classes does R partition the set described? Explicitly list all of the members of the following equivalence classes: [2] and [13]. Let the set X be the largest of the equivalence classes. What is the smallest integer that belongs to X?
$$R = \{ (x,y) | b(x) = b(y) \} $$
- R is reflexive as $b(i) = b(i) $ for all $i \in Z$.
- R is symmetric as $b(i) = b(j) \rightarrow b(j) = b(i)$
- R is transitive as $b(i) = b(j) \wedge B(j) = b(k)$ then $b(i) = b(k)$
[2] = $ \{2, 2 \} $ (2 in binary is 10)
[13] = $ \{13, 4 \} $ (13 in binary is 1101)
Would 512 make sense to be the smallest integer?