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

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.

• Are you using the lambda calculus (or lambda notation) to denote a function? Because it looks so in your definition of $\;\psi\;$. I don't understand that and, in fact, I loathe that lambda calculus thingy...and I think many mathematicians share my feeling. Just that you know because it could be not many will understand what you meant there. Feb 4, 2018 at 20:43
• @DonAntonio Thank you, I understand, I'll change it :)
– Noy
Feb 4, 2018 at 20:44
• Thanks...Also, do you mean $\;\aleph=2^{\aleph_0}=2^c\;,\;\;c=\;$ the continuum cardinal? Feb 4, 2018 at 20:53
• @Noy $\aleph_1$ does not need to be $\mathfrak c=\aleph$. Similarly, $2^{\aleph_1}$ does not need to be $2^{\mathfrak c}$. Feb 4, 2018 at 20:59
• @NoyPerel Fine. So $\;\aleph=c=2^{\aleph_0}\;$ is just another way to denote the continuum cardinal Feb 4, 2018 at 21:08

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

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.

• Don't mention Lebesgue measurable sets or anything like that, it is unnecessary noise. Simply consider all partitions $\{L,\mathbb R\smallsetminus L\}$ with $L$ a subset of $\mathbb R$ (such that neither $L$ nor its complement is empty, or some such). Feb 5, 2018 at 0:03
• @AndrésE.Caicedo Good point. Lebesgue simply popped up in my mind, but you're right. Thanks. Feb 5, 2018 at 8:35