Interesting ways to show that there are infinitely many equivalence relations on an infinite set (including Bell numbers).

Question

I am trying to answer the question "Is there infinitely many equivalence relations on any infinite set?"

My intuition says yes, and when I try to prove this, I feel like my reasoning is not sufficient. Here is what I have so far:

"The number of equivalence relations on an $n$-element set is given by the $n$th Bell number $B_n$, where

$B_{n+1}=\sum\limits_{k=0}^{n} B_{k}{n\choose k}$ for $n\geq 0$.

Now, the sequence of Bell numbers $(B_n)_{n \in \mathbb{N}} \geq (n)_{n \in \mathbb{N}}$ for all $n \in \mathbb{N}$. So I wanted to take limits (as n tends to infinity) across this inequality (which is allowed, by a basic result of analysis) and we see that $\lim_{x \to +\infty} (B_n) = \infty$ (since the limit of sequence of natural numbers is infinity). "

This "sort of" shows the result that I want, but it's not really explicitly showing it. Is there a final sentence I need to add to this to complete the proof, or is this method downright wrong? I feel like perhaps it is wrong as we're trying to give a result about infinite sets using finite objects.

I would also like to know if is there a more interesting way to prove this. Thanks

Answer 1

Here's a general approach that doesn't rely on Bell numbers.

Let $S$ be any infinite set. Fix an element $a\in S$. Then for each $b \in S$, with $b\ne a$, define an equivalence relation, $R_b$ where one equivalence class is $\{a,b\}$, and all other equivalence classes are singletons. (So $aR_b b, bR_b a$, and everything else is only related to itself.)

Each $R_b$ is an equivalence relation, and the cardinality of $\{R_b : b\in S, b\ne a\}$ is equal to the cardinality of $S$ since $S$ is infinite.

Answer 2

Here's a lower bound: Let $X$ be a set and $A\subset X$ be a subset of two or more elements. Then we can define an equivalence relation $\sim_A$ on $X$ per $$ x\sim_A y\iff x=y\lor\{x,y\}\subseteq A.$$ Clearly, different $A$ lead to different equivalence relations. If $X$ is infinite, there are $2^{|X|}$ ways to pick $A$ and hence at least $2^{|X|}$ equivalence relations on $X$.