0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This makes sense to me - I have verified that it is indeed an equivalence relation and I follow your reasoning. Could I ask how you knew the way to approach this question? Did you think up this equivalence relation off of the top of your head in response to my question? $\endgroup$
    – Natasha
    Apr 20 '20 at 18:59
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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