Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
+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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.