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.
2
$\begingroup$
$\endgroup$
-
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
3
$\begingroup$
$\endgroup$
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?
