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$


marked as duplicate by user21820, Javi, Asaf Karagila elementary-set-theory Apr 9 at 11:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Well, intuitively, at least, you know that $R\subseteq 2^{\mathbb N\times\mathbb N}$, so there's at least a chance for $|R|$ to not be countable... $\endgroup$ – 5xum Apr 9 at 8:17
  • $\begingroup$ @5xum So I need to build a function $f : R \mapsto P(\mathbb{N}\times \mathbb{N})$ that is both surjective and injective? $\endgroup$ – trizz Apr 9 at 8:26
  • 1
    $\begingroup$ Be careful using the word "group", and especially the tag group-theory. A group means something specific in math, and it is not the same as a set. $\endgroup$ – Arthur Apr 9 at 8:47

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.


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

  • $\begingroup$ Your first paragraph needs some work. You need to make sure that any number is equivalent to itself. At the same time, $A$ might contain a single element, or be empty, and all those cases will give the same equivalence relation. $\endgroup$ – Arthur Apr 9 at 8:36

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