I'm having trouble with the following exercise:

Let S be the subset of all finite subsets of $\Bbb{N}$. Let $\mathcal{R}$ be a relation defined as $\mathcal{R} = \{ (X,Y) \in S\times S : \operatorname{card}(X) = \operatorname{card}(Y) \}$

How many different equivalence classes does $\mathcal{R}$ have? Find the simplest possible representative for each class.

I would tend to think that the number of equivalence classes in this relation is infinite.

For example:

Let $X= \{ 1;2;3\}$. Let $Y = \{ 4; 5; 6\} $.

$$(\{ 1;2;3\},\{ 4; 5; 6\}) \in S\times S \text{ and } \operatorname{card}(X) = \operatorname{card}(Y)$$

$\overline{X} = \overline{Y} = (\{ 1;2;3\},\{ 4; 5; 6\})$

And in general, one can come up with infinitely many examples with the following format:

$$X = \{ a_1,a_2,\ldots,a_i \} \text{ where } a_i \in \Bbb{N} \ \forall i$$

$$Y = \{b_1,b_2,\ldots,b_n \} \text{ where } a_n \in \Bbb{N} \ \forall n$$

If $i = n$, then $X \mathcal{R}Y \text{ and } Y \mathcal{R}X$

$\overline{X} = \overline{Y} = (\{ a_1,a_2,\ldots,a_i \},\{b_1,b_2,\ldots,b_n \})$

However, I haven't been able to prove this and the fact that I'm asked to find the simplest representative for each class leads me to think that maybe my conjecture is wrong and there is a finite number of equivalence classes.

Can anyone help me? If the number of different equivalence classes is infinite, how can I prove it? And if it is finite, why is it so?

  • 2
    $\begingroup$ Yes, countably many classes. The sets $\emptyset,\left\{0\right\},\left\{0,1\right\},\left\{0,1,2\right\},..$ are representatives of each class. In fact, if $Y\in S$ then $card(Y)$ is some finite cardinal $n$ therefore $Y$ is in the class of $\left\{0,1,2,...,n-1\right\}$. $\endgroup$ – Hellen Sep 25 '17 at 21:01
  • 1
    $\begingroup$ @Hellen I would have taken $S_0=\emptyset,S_1=\{1\},S_2\{1,2\},S_3=\{1,2,3\},...$ to have $|S_k|=k$ but I agree with you :). $\endgroup$ – Surb Sep 25 '17 at 21:04
  • $\begingroup$ I can't choose between these two... Thanks guys you destroyed my day :( $\endgroup$ – Leaning Sep 25 '17 at 21:06
  • 1
    $\begingroup$ Proper notation is $S\times S,$ not $SxS.$ I edited accordingly. $\endgroup$ – Michael Hardy Sep 25 '17 at 21:43
  • $\begingroup$ Sorry but what is the question exactly? $\endgroup$ – Did Sep 30 '17 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.