How can I show that $$F = \{ E \subseteq \mathbb{N}^2: \ E \ \text{is an equivalence relation on} \ \mathbb{N}\}$$ is a set with cardinality of the continuum? The usual idea is to show $\vert F\rvert \leq \mathfrak{c}$ by showing $F$ is a subset of some well-known set with cardinality of the continuum, and then show $\vert F\rvert \geq \mathfrak{c}$ by finding an injection from some other well-known set with cardinality of the continuum to $F$. In this example, I don't know how to approach either of the inequalities.

  • 1
    $\begingroup$ Well, $F$ is subset of the power set of $\mathbb{N}^2$. $\endgroup$ – ryanblack Jan 10 '17 at 20:58
  • $\begingroup$ Can you think of an equivalence relation that has a cardinality that shows a potential for the desired result? That might give you a lower bound. $\endgroup$ – Meitar Jan 10 '17 at 21:01

As noted in the comments, $F$ is a subset of $\mathcal{P}(\mathbb{N})$, and hence its cardinality is at most the continuum. To get a lower bound, consider equivalence relations on $\mathbb{N}$ which have two equivalence classes exactly. We can represent these equivalence classes by infinite binary sequences, with the $i$th term being $1$ if $i$ is in the same class as $1$ and $0$ otherwise. Can you go from here?


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.