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

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 9 at 11:23

• 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... – 5xum Apr 9 at 8:17
• @5xum So I need to build a function $f : R \mapsto P(\mathbb{N}\times \mathbb{N})$ that is both surjective and injective? – trizz Apr 9 at 8:26
• 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. – 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$$.
• 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. – Arthur Apr 9 at 8:36