I have an given set $S$ where $S=$ set of finite subsets of $\mathbb{N}.$ We need to prove $S$ is countably infinite.
My approach: I need to prove there is one-to-one correspondence between $S$ and ${\mathbb{N}}.$
Suppose $S =
\{\{1,2,3\}, \{1,3,4,5\},\{4,5\}, \{\emptyset\},………….\}
=\{f_1,f_2,f_3,f_4…………..\}$where $f_i\subseteq\mathbb{N}.$
$\mathbb{N}=\{1,2,3,4……
…………..\}$
Now $1$ map to $f_1,$$2$ map to $f_2,$
$3$ map to $f_3……….$ and so on. Now apply Cantor diagonalisation theorem $f'=\{2,3………….\}$ where $2$ comes from $f_2$ because $2\notin f_2,$$3$ comes from $f_3$ because $3\notin f_3………..$ and so on, $f'$ is different from $f_i.$ $f'$ isn't covered in bijection.
$f:\mathbb{N}\to S$ isn't bijection.
So $S$ is uncountable. Where did I wrong don't understand?
Best Answer
Your proof that $S$ is not countable goes as follows:
Consider any $f : \mathbb{N} \to S$. Define $f' = \{n \in \mathbb{N} \mid n \notin f_n\}$.
Then we see that $f'$ is not in the range of $f$. Therefore, $f$ cannot be surjective. Thus, $f$ can't be a bijection.
However, there is a flaw in this reasoning. It assumes that $f' \in S$. In other words, it assumes that $f'$ is finite. If $f'$ is not finite, then there is no problem at all with the fact that $f'$ is not in the range of $f$.
In fact, it is indeed possible to construct a bijection $f : \mathbb{N} \to S$. The resulting $f'$ will be an infinite set.
For how to prove that $S$ is countable, see this answer.