# The number of equivalence classes of finite symmetric difference relation

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?

-
What you’re calling difference is generally called symmetric difference. – Brian M. Scott Sep 18 '12 at 18:56
@Brian, thanks, I added "symmetric". – Kaveh Sep 18 '12 at 19:07

## 1 Answer

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

-
Looks fine to me. – Brian M. Scott Sep 18 '12 at 18:56