Find the cardinality of the set of all equivalence relations in $\mathbb{R}$.

Question

Find the cardinality of the set of all equivalence relations in $\mathbb{R}$.

Hello all. My attempt: Let $B=\{X\subseteq \mathbb{R}\times\mathbb{R}|Id_\mathbb{R}\subseteq X \land X\circ X \subseteq X \land X^{-1}=X\}$ be the set of all equivalence relations in $\mathbb{R}$. (is this correct?)

We'll claim $|B|=2^{\aleph}$.

First, it is trivial that $|B|\le |P(\mathbb{R\times R})|=2^\aleph$ since $B\subseteq P(\mathbb{R\times R}) $

Now, I had already proved that the cardinality of $A$= {The set of all reflexive relations in $\mathbb{R}$} is $2^{\aleph}$ so I want to use the set A in this current proof. We'll show an injective map $\psi:A\rightarrow B$ and by that we'll prove $|A|\le |B| \Rightarrow 2^{\aleph}\le |B|\le 2^{\aleph} \Rightarrow |B|=2^{\aleph}$ according to CSBT.

Let $\psi:A\rightarrow B$ be the function $\psi(X)= X\cup X^{-1} \cup X\circ X \cup (X\circ X)^{-1} $. Yes, this is indeed inelegant and possibly not even correct. I would love to get your help on that question. Thanks in advance.

Answer 1

It may be simpler to count the number of nonempty subsets $S$ of $\mathbb R$ (it is easy to see it is $2^{\mathfrak c}$). Each induces an equivalence relation whose classes are $S$ and singletons. This shows there are at least $2^{\mathfrak c}$ equivalence relations, and since this is largest possible, you are done.

(It may be best to consider simply sets $S$ of size at least $2$, as all sets of size $1$ generate the same equivalence relation: the identity. And it is easy to check that there are $2^{\mathfrak c}$ sets $S$ of size at least $2$.)

Answer 2

I'm not sure your function $\;\psi\;$ actually works, but I can propose you the following.

Definition: A partition of a non-empty set $\;A\;$ is a family of non-empty sets $\;\{A_i\}_{i\in I}\;$ s.t.

$$\begin{align*}\bullet\;\;&\bigcup_{i\in I} A_i=A\\{}\\ \bullet\;\;&i,j\in I\,,\,\,i\neq j\implies A_i\cap A_j=\emptyset\end{align*}$$

Claim: There's a one-to-one function between equivalence relations on $\;A\;$ and partitions of $\;A\;$ .

The proof of the above is very easy, and now your problem is equivalent to count the number of partitions of $\;\Bbb R\;$ ...but this is easy using Cantor-Bernstein, since clearly, if $\;\mathcal L(\Bbb R)\;$ is the set of all Lebesgue measurable subsets of $\;\Bbb R\;$, and since $\;\left|\mathcal L(\Bbb R)\right|=2^c=2^{2^{\aleph_0}}\;$ , then

$$\;\forall\,L\in\mathcal L(\Bbb R)\in\Bbb R\;,\;\left\{\,L,\;\;\Bbb R\setminus L\,\right\}$$ is a partition of $\;\Bbb R\;$ , and thus the wanted number is at least $\;2^c\;$ ...but also at most, of course.