# 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. Commented Aug 23, 2010 at 10:21
• You're absolutely right. (Even though in terms of cardinality it doesn't mean anything) I'll fix that right away. Commented Aug 23, 2010 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. Commented Aug 23, 2010 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
Commented Aug 23, 2010 at 10:40
• Yes, the use of the axiom of choice is perfectly fine with me, thanks.
– Andy
Commented Aug 23, 2010 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. Commented Aug 23, 2010 at 10:57
• @Olod: sure! I was not saying that it was impossible to go the way you had suggested (which in fact is also the way followed by all the answers to this question!), just that the given argument only showed one inequality. Commented Aug 23, 2010 at 12:03