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.

  • $\begingroup$ 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. $\endgroup$
    – DonAntonio
    Feb 4, 2018 at 20:43
  • $\begingroup$ @DonAntonio Thank you, I understand, I'll change it :) $\endgroup$
    – Noy
    Feb 4, 2018 at 20:44
  • $\begingroup$ Thanks...Also, do you mean $\;\aleph=2^{\aleph_0}=2^c\;,\;\;c=\;$ the continuum cardinal? $\endgroup$
    – DonAntonio
    Feb 4, 2018 at 20:53
  • 1
    $\begingroup$ @Noy $\aleph_1$ does not need to be $\mathfrak c=\aleph$. Similarly, $2^{\aleph_1}$ does not need to be $2^{\mathfrak c}$. $\endgroup$ Feb 4, 2018 at 20:59
  • 1
    $\begingroup$ @NoyPerel Fine. So $\;\aleph=c=2^{\aleph_0}\;$ is just another way to denote the continuum cardinal $\endgroup$
    – DonAntonio
    Feb 4, 2018 at 21:08

2 Answers 2


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.

  • $\begingroup$ 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). $\endgroup$ Feb 5, 2018 at 0:03
  • $\begingroup$ @AndrésE.Caicedo Good point. Lebesgue simply popped up in my mind, but you're right. Thanks. $\endgroup$
    – DonAntonio
    Feb 5, 2018 at 8:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .