I was wondering if I can get a hint on the following question:
Let $R$ be an equivalence relation on $\mathcal P(\mathbb{N})$, which satisfies: $\langle A,B\rangle \in R$ iff $A \Delta B $ is finite. Prove that $R$ is an equivalence relation, and that each equivalence class is countable.
I managed to prove that it is an equivalence relation,but got stuck on second part of the question. This is from a class of elementary set theory.
On
Hint : the set of finite sets of $\Bbb N$ is $$\bigcup_{k=0}^\infty \{A\subset\Bbb N, \text{A is finite and } \max A = k\}$$
On
Hint: Try a proof by contradiction. Let $A \in \mathcal{P}(\mathbb{N})$ be such that there uncountably many $B \in \mathcal{P}(\mathbb{N})$ such that $(A,B) \in R$, i.e. $A \Delta B$ is finite. Observe that every $X \in \mathcal{P}(\mathbb{N})$ is countable (finite or infinite). Remember that the set of finite subsets of $\mathbb{N}$ is countably infinite. Then, ...
Here's a route. Let $\mathcal C$ be an equivalence class.
$\qquad (1)$: Show that the collection of finite subsets of $\mathbb N$ is countable.
$\qquad (2)$: Show that if $\mathcal C$ has a finite element, then all of its elements are finite.
$\qquad \qquad(2.1)$: Conclude that if $\mathcal C$ has a finite element, then it is countable.
$\qquad (3)$: Let $\mathcal C_\infty$ have an infinite element $A_\infty$. Consider $\mathcal C_\infty'=\{B\setminus A_\infty\,;\, B \in \mathcal C_\infty \text\}$. Show that each element in $C_\infty'$ must be finite.
$\qquad \qquad(3.1)$: Conclude that $\mathcal C_\infty'$ is countable.
$\qquad (4)$: Show that the set $\widehat{\mathcal C_\infty}=\{B\in C_\infty\,;\, B\subset A_\infty\}$ is countable.
$\qquad \qquad(4.1)$: I suggest you show that $\widehat{\mathcal C_\infty}$ is in bijection with $\left\{A_\infty\setminus B\,;\,B\in\widehat{\mathcal C_\infty}\right\}$.
$\qquad (5)$: Show that $\mathcal C_\infty$ is in bijection with $C_\infty'\cup\widehat{\mathcal C_\infty}$ and conclude.