The cardinality of an equivalence relation over a set

Question

I'm trying to prove the following statement:

let $A$ be an infinite set, then for any equivalence relation $E$ on $A$, $ |E| = |A|$

But I'm really stuck. Trying to show a bijection from $E$ to $A$ made sense only when dealing with natural numbers, using maybe $f(x,y) = 2^x3^y$ but what do I do when these are real numbers?

Any idea on how this can be shown? Thanks in advance.

Answer 1

Since $E$ is an equivalence relation, it is reflexive in particular. Thus, you have an injection $A \hookrightarrow E$ given by $x \mapsto (x, x)$. Thus, $|A| \le |E|$.

On the other hand, by definition, $E \subset A \times A$ and thus, $|E| \le |A|^2$.

Now, since $A$ is infinite, we have $|A| = |A|^2,$ assuming the Axiom of Choice.
Then, by the Schröder–Bernstein theorem, we have $|E| = |A|$.

---

Note that you do indeed need the Axiom of Choice. Else, we may have an infinite set $A$ such that $|A| \neq |A \times A|.$ Then, taking $E = A \times A$ (which is indeed an equivalence relation), we get a counterexample.