In the question given below, determine the number of different equivalence classes. I think the answer is infinite as $\ b_1$ and $b_2\;$ can have either one 1's or two 1's or three 1's etc. I just want to clarify if this is right as some says the number of different equivalence classes should be 2, given that they are either related or not.
Question: $\;S$ is the set of all binary strings of finite length, and
$$R = \{(b_1, b_2) \in S \times S \mid\; b_1\;\text{ and}\; b_2\; \text{ have the same number of }\;1's.\}$$
The proof that the correct answer is infinite is quite easy.
First of all, let's note that the set of equivalence classes is not empty, since, trivially, "1" generates a class.
Suppose that the number of classes is finite. Then we can build over the set of the equivalence classes an order relation, defined as follows:
now, since we have supposed that the cardinality of
is finite, we can find the maximum of the set $\{d(C_i) | C_i \in Z\}$, say $M$.
It's now easy to write a string of $M+1$ "$1$", that is finite, and doesn't belong in any of the previous classes, that is absurd.