2
$\begingroup$

Let $\Sigma$ be an infinite set.

Let $A,B \subseteq \Sigma$ be of finite symmetric difference iff they have a finite difference, more formally:

$A \sim B$ iff $|A \Delta B| \in \mathbb{N}$

How many equivalence classes does $\sim$ have?

  • 0
    @Brian, thanks, I added "symmetric".2012-09-18

1 Answers 1

3

Let $A \subseteq \Sigma$ be an arbitrary set. Then the size of $[A]$ (the equivalence class of $A$) is equal to the number of finite subsets of $\Sigma$. The number of finite subsets of $\Sigma$ is of the same cardinality as $\Sigma$ since $\Sigma$ is an infinite set. Therefore we have $|[A]| = |\Sigma|$ for all $A$.

Let $I$ be the set of equivalence classes. We have $P(\Sigma) = \bigcup_{[A]\in I} [A]$ and distinct equivalence classes are disjoint. Therefore we have $2^{|\Sigma|} = |P(\Sigma)| = |\bigcup_{[A]\in I} [A]| = |I| |\Sigma|$. Thus by cardinal arithmetic we have $|I| = 2^{|\Sigma|}$.

  • 0
    Looks fine to me.2012-09-18