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

Question

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.

Answer 1

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 ☺

Answer 2

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.