0
$\begingroup$

I was taught that the cardinality of equivalence relations in $\mathbb{R} \to \mathbb{R}$ is $2^\mathfrak{c}$.

I was wondering if it could be proven using CSB.

Any help would be appreciated.

$\endgroup$
1
$\begingroup$

Given a subset $S$ of $\mathbb R\setminus\{0\}$, you can define an equivalence relation $\sim$ on $\mathbb R$ by $$a\sim b\iff(a\in S\land b\in S)\lor(a\notin S\land b\notin S)$$ for any $a,b\in\mathbb R$. Note that exclusion of $0$ ensures that the maping is injective (otherwise a set and its complement would lead to the same equivalence relation), but doesn't affect the cardinality. Therefore there exist at least as many equivalence relations as there exist subsets of $\mathbb R$.

On the other hand, an equivalence relation on $\mathbb R$ is a relation on $\mathbb R$, and thus a subset of $\mathbb R\times\mathbb R$. And $|\mathbb R\times \mathbb R|=|\mathbb R|$. Thus there exist at most as many equivalence relations as there exist subsets of $\mathbb R$.

$\endgroup$
4
  • $\begingroup$ What is this $\sim$ symbol? a and b are elements, am I wrong? $\endgroup$ Feb 8 '18 at 9:02
  • $\begingroup$ @GalushBalush: The equivalence relation. $a\sim b$ here means "$a$ is equivalent to $b$". See my edit. And yes, $a$ and $b$ are elements; I now edited this in, too. $\endgroup$
    – celtschk
    Feb 8 '18 at 9:06
  • $\begingroup$ I don't understand why is this an injection. $\endgroup$ Feb 8 '18 at 9:24
  • $\begingroup$ @GalushBalush: The relations defined through $S_1$ and $S_2$ are only the same if either $S_1=S_2$ or $S_1=\mathbb R\setminus S_2$. But the second case is excluded because neither $S_1$ nor $S_2$ has the element $0\in\mathbb R$. Or more directly: If $S_1\ne S_2$, then the symmetric difference $S_1\triangle S_2$ is not empty. But for $a\in S_1\triangle S_2$ we have either $a \sim_1 0$ or $a\sim_2 0$, but not both. $\endgroup$
    – celtschk
    Feb 8 '18 at 18:43
1
$\begingroup$

I'm assuming CSB is Cantor-Schröder-Bernstein.

One family of $2^c$ equivalence relations in $\mathbb R$ is this. For each subset $S$ of $[0,1]$, take $x \sim x+1$ for $x \in S$.

On the other hand, any relation in $\mathbb R$ can be considered as a subset of $\mathbb R \times \mathbb R$.

$\endgroup$
2
  • $\begingroup$ Can you explain the injection? I don't really get it. Thank you for your help. $\endgroup$ Feb 8 '18 at 8:48
  • $\begingroup$ Injection #1 takes the subset $S$ of $[0,1]$ to the equivalence relation $\sim$ where $x \sim x+1$ (and $x+1 \sim x$) for each $x \in S$. Injection #2 takes an equivalence relation on $\mathbb R$ to itself as a subset of $\mathbb R \times \mathbb R$. Use an injection of $\mathbb R \times \mathbb R$ into $[0,1]$ to map these into subsets of $[0,1]$. $\endgroup$ Feb 8 '18 at 19:19

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.