# Counting equivalence relations

I am aware that on a finite set the number of equivalence relations is the n-th Bell's Number. On the other hand, the only reference I could find on the web for infinite sets was this: On counting equivalence relations by D.J. Baylis, in which he proves that the set of equivalence relations on $\mathbb{N}$ is uncountable. I am interested in any sort of theorem that gives some rule about counting equivalence relations on an infinite set -something like $\beth_0 = \aleph_0$ and $\beth_n = 2^{\beth_{n-1}}$ - if there are any.

-

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

-
+1. Just a minor point: in the paragraph before the last, the set X′X' should also be different from SS to really determine an equivalence relation with two elements. – damiano Aug 23 '10 at 10:21
You're absolutely right. (Even though in terms of cardinality it doesn't mean anything) I'll fix that right away. – Asaf Karagila Aug 23 '10 at 10:26

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.

-

Let $X$ be an infinite set. Any function $f : X \to X$ determines an equivalence relation on $X$: $$x_1 \equiv x_2 \iff f(x_1) = f(x_2).$$ It follows that there are at least $2^{|X|}$ equivalence relations on $X$ (see the comments below). On the other hand, any equivalence relation defines a function from $X$ to $X,$ take a complete set $S$ of representatives, send every element of a given class to its representative in $S.$ Thus there are no more than $|X|^{|X|}$ equivalence relations on $X.$ Therefore there are exactly $|X|^{|X|}=2^{|X|}$ equivalence relations on $X.$

-
I think that your conclusions are correct, but different functions could determine the same equivalence relation. Also, you are using the axiom of choice. – damiano Aug 23 '10 at 10:11
@Grigory: I just tried to demonstrate the old idea, some details are missing but could be easily supplied. @damiano: the questioner didn't forbid the use of AC. – Olod Aug 23 '10 at 10:40
Yes, the use of the axiom of choice is perfectly fine with me, thanks. – Andy Aug 23 '10 at 10:44
@Olod: the comments that both Grigory and I made were mostly on the fact that you only proved that there are no more than $|X^X|$ partitions, but you did not prove the converse inequality. – damiano Aug 23 '10 at 10:57
@damiano: but, surely, functions $f : X \to X$ determine at least $2^{|X|}=|X|^{|X|}$ equivalence relations. You take a subset $Y$ of $X$ and define a function $f_Y : X \to X$ as follows: take a $y_0 \in Y$ and let $f_Y(y)=y_0$ for all $y \in Y$ and let $f_Y(z)=z$ for all $z \in X\setminus Y.$ Then the equivalence relations distinct functions $f_Y,f_Z$ detemine are distinct. – Olod Aug 23 '10 at 11:30