Counting equivalence relations

Solution 1:

Firstly, to address Beth numbers (as you noted, the math markup doesn't work with them. I'll use words instead)

$\beth$ (Beth) numbers are cardinal numbers defined as followed:

1. $\beth_0 = \aleph_0$,
2. $\beth_{\alpha+1} = 2^{\beth_n}$,
3. $\beth_\delta=\sup_{\gamma<\delta}\beth_\gamma$, for a limit ordinal $\delta$.

Now, given an infinite set $X$ and assuming the axiom of choice, we have that $|X\times X|=|X|$, therefore $|P(X\times X)| = |P(X)|$. Define $R(X)$ as the set of all equivalence relations on $X$, then clearly $R(X) \subset P(X\times X)$ and therefore $|R(X)| \le |P(X)|$.

On the other hand there are $2^{|X|}$ partitions of $X$ into two sets (an easy exercise in cardinal arithmetic), so for every partition as such $\{X', X\setminus X'\}$ we can define an equivalence relation with two equivalence classes, namely $X'$ and its complement in $X$. Therefore $|R(X)| \ge |P(X)|$.

All in all we have that the number of equivalence relations on $X$ is $2^{|X|}$.

Solution 2:

I will assume that the axiom of choice holds: this may not be necessary, but I am not sure.

Start by observing that equivalence relations on a set $S$ are the "same" as partitions of $S$ (recall that a partition of $S$ is a set $B$ of subsets of $S$ with the properties that

1) $\cup_{b \in B}b = S$, and

2) for all $b,b'\in B$ we have $b \cap b'=\emptyset$).

Let $S$ be an infinite set, let $B(S)$ denote the set of partitions of $S$ and $P(S)$ the power set of $S$ (namely, the set of all subsets of $S$). I am going to show that $|B(S)| = |P(S)|$; note that $|P(S)| = 2^{|S|}$.

First of all, use the axiom of choice to fix, for every non-empty subset $A$ of $S$, an element $c(A) \in A$.

To any function $f \colon S \to S$ we associate a partition $B_f$ of $S$ by letting $B_f = \{ f^{-1}(s) | s \in f(S) \}$; in words, $B_f$ is the partition whose elements are the non-empty fibers of the function $f$. Any partition $B$ is obtained by this construction: we define a function $f_B \colon S \to S$ by letting $f_B(s) = c(b_s)$, where $b_s$ is the part of $B$ containing $s$. Clearly, the partition $B_{f_B}$ coincides with the partition $B$. We deduce that there is a surjection from the set of all functions $S \to S$ to the set of partitions; thus we conclude that $|B(S)| \leq |S^S| = |P(S)| = |2^S|$.

For the other inequality, let $P'(S)$ denote the set of unordered pairs of subsets of $S$ of the form $\{ A , S \setminus A \}$, where $A \subset S$ is a proper non-empty subset of $S$. Each unordered pair in $P'(S)$ determines uniquely a partition of $S$ with two parts, so that there is an injection $P'(S) \to B(S)$. We deduce that $|B(S)| \geq |P'(S)|$. To conclude it suffices to show that $|P'(S)| \geq |P(S)|$. This is easy, since there is a natural surjection $P(S) \setminus \{ S , \{\emptyset\} \} \to P'(S)$ whose fibers consist of exactly two elements, and $P(S)$ is an infinite set.