Number of Different Equivalence Classes?

189 Views Asked by At

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.\}$$

1

There are 1 best solutions below

0
On

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:

Given a class $C$, we define $d(C)$ the number of "$1$" in a string sequence of said class and use the order between natural numbers

now, since we have supposed that the cardinality of

$Z = \{ C_i | \forall x\in C_i, |x_1| = i \}$

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.