Number of Different Equivalence Classes?

Question

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

You are correct: there is one equivalence class for each non-negative integer $n$, and it contains the finite binary strings with exactly $n$ ones. — Brian M. Scott, Mar 11 '13 at 15:41
@BrianM.Scott Thanks. I wonder if people answered 2 because they were confused? — Ray.R.Chua, Mar 11 '13 at 15:44
That would be my guess: they haven’t yet quite grasped what equivalence classes are. — Brian M. Scott, Mar 11 '13 at 15:45

score 1 · Answer 1 · answered Mar 11 '13 at 16:20

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.

Number of Different Equivalence Classes?

1 Answers1