The cardinality of all equivalence relations over $\mathbb{N}$

Question

Let $R$ be the set the contains all equivalence relations over $\mathbb{N}$.

Prove that $\left | R \right | = 2^{\aleph_0}$

This question is very counter - intuitive to me. I know that Each $R_i \subseteq \mathbb{N}\times \mathbb{N}$ but that still that doesn't give me any intuition on why $\left | R \right | = 2^{\aleph_0}$, because $\left | \mathbb{N}\times \mathbb{N} \right | = \aleph_0$

Answer 1

There is a natural bijective correspondence between subsets of $\Bbb N$ with more than one element, and equivalence relations where exactly one equivalence class has more than one element. There are $2^{\aleph_0}$ such subsets of $\Bbb N$, so there is an injection from $2^{\aleph_0}$ to $R$.

Take any equivalence relation $C$ on $\Bbb N$, and order all the equivalence classes of that relation according to the size of their least element. Index the equivalence classes in order as $C_0, C_1, \ldots$, and consider the following subset of $\Bbb N\times \Bbb N$: $$ \{0\}\times C_0\cup \{1\}\times C_1\cup \cdots $$ This gives an injection from $R$ to $P(\Bbb N\times\Bbb N)$, showing that there is an injection from $R$ to $2^{\aleph_0}$.

Since we have shown there is an injection from $R$ to $2^{\aleph_0}$, and an injection from $2^{\aleph_0}$ to $R$, the Schröder-Bernstein theorem tells us that there is a bijection.

Answer 2

Let $A \subseteq \mathbb N$ be a subset of the natural numbers, and define the equivalence relation $R_A$ by $a \sim b$ if $a \in A$ and $b \in A$. This is clearly an equivalence relation, meaning we have an injective mapping from the powerset of $\mathbb N$ to $R$.

As you already noticed each relation $R_i \in R$ is a different subset of $\mathbb N \times \mathbb N$. So we have an injective mapping from $R$ to the powerset of $\mathbb N \times \mathbb N$.