# Let $A, |A|=a$ be a set where $a$ is infinite. How many equivalence relations are there over $A$?

Let us denote the set of equivalence relations $B$. So, the first direction is to say that the number of equivalent relations won't exceed the number of relations, that is $|P(A\times A)|=2^a$.

Now, for the other direction(inequality, $|B|\ge 2^a$) is a bit more complex for me. What I did in my exam is saying that from every subset $K$ of $A$ I can create the distribution $\{K,A\setminus K\}$ (Considering that the set of distributions of $A$ is isomorphic to the set of equivalence relations.). The problem is, I can't create an injection with it because for every image $H$ such that $H$ is a distribution of $A$, I have two sources. Since my teacher never defined $\left|{P(A)\over 2 }\right|$, how can I overcome it?

I would really appreciate your help.

• Split $A$ into two sets $B, C$ of size $a$, and count the equivalent relations with exactly two classes, one of them a subset of $B$. Note that a modicum of the axiom of choice is used here and in your computation of an upper bound. Indeed, without choice it is consistent that for some infinite sets $A$, the number of equivalence relations is not $2^{|A|}$. Mar 12 '15 at 18:04
• How do you derive that one of the classes is in B? Suppose I take $D=B\cup \{x\}$ where $x\in C$. Then it's not in $B$. How can I know that $A\setminus D$ is in $B$? Mar 12 '15 at 18:27
• I think what Andres is proposing is to only take those partitions where one of the classes is a subset of $B$ and ignore the rest, then the subsets of $B$ are in one-to-one correspondence with those partitions. Since $B$ is of size $a$, then there must be $2^a$ of those partitions. The size of $C$ is actually immaterial as long as it is not empty, to ensure that in any partition of $A$ at most one of the classes is a subset of $B$. Mar 12 '15 at 19:24

Take some element from $A$, say $x$. Now let $A'=A\setminus\left\{x\right\}$; since $A$ is infinite there is a bijection between $A$ and $A'$, and therefore between their respective power sets. Now you can make an injection from $\mathcal{P}(A')$ to $B$ by mapping $C\subseteq A'$ to the partition $\left\{C, A\setminus C\right\}$. Note that $A\setminus C$ is not a subset of $A'$ so the ambiguity in your original argument does not happen; now you can proceed with it and complete the proof ☺
We have that the cardinality of $\{A_0 \subseteq A \mid |A_0| > 1\}$ is $2^a$.
Now, for every $A_0$ in this set, define $\sim_{A_0}$ by:
$$a \sim a' \iff a = a' \lor \{a,a'\} \subseteq A_0$$
Then $A_0 \mapsto \sim_{A_0}$ is an injection, so that $|B| \ge 2^a$ as desired.