Let $P(\mathbb{N})$ denote the set of all subsets of $\mathbb{N}$. Define a relation $D$ on $P(\mathbb{N})$ as follows: $(A, B) \in D$ if the symmetric difference $A\Delta B := (A \cup B) \setminus (A \cap B)$
is finite. (That is: $A$ and $B$ only differ by finitely many elements).
I have already proved that $D$ is an equivalence relation and that all finite subsets of $\mathbb{N}$ are in the same equivalence class. Then the problem asks to prove that every equivalence class is a countable collection of sets and that there are uncountably many equivalence classes. These two questions come with the following hint: fix $A_{0} \in P(\mathbb{N})$, then for each $n \in \mathbb{N}$ define $A_{0}^{(n)} = \{A \subseteq \mathbb{N} : A \text{ differ from } A_{0} \text{ by } n \text{ numbers}\}$. The issue is that I still do not know how to prove $A_{0}^{(n)}$ is countable. Could you give me some hints or the solution, please?
Best Answer
If we fix $n$ digits that are the different ones (let's say the first $n$), then the difference can only happen in finitely many ways, since each of these digits can only vary in finitely many ways. Clearly, there countably many ways of choosing these $n$ digits, so you get a countable union of finite elements, which is countable.
We then union these over all $n$, which gives a countable set (countable union of countable sets).