# Let $X= \{ A \subset \mathbb{N} : \mathbb{N} \backslash A \text{ is finite}\}$. What is the cardinality of $X$? Prove it.

Let $X= \{ A \subset \mathbb{N} : \mathbb{N} \backslash A \text{ is finite}\}$. What is the cardinality of $X$? Prove it.

For me the cardinality should be the same as the natural numbers. I am trying to show a way of ordering it, the first A is one with the smallest numbers and so on.

-
– Martin Sleziak Mar 9 '13 at 15:11

Hint: Note that $f(A)=\Bbb N\setminus A$ is a bijection from $X$ to $\text{Fin}(\Bbb N)=\{A\subseteq\Bbb N\mid A\text{ is finite}\}$.

(If you haven't seen that $\text{Fin}(\Bbb N)$ is countably infinite before, you can demonstrate an injection into $\Bbb N$ by mapping $\{a_1,\ldots,a_k\}$ to $p_{a_1}\times\cdots\times p_{a_k}$, where $p_i$ is the $i$-th prime number.)

-

$X$ can be placed into 1-1 correspondence with the finite subsets of $\mathbb{N}$. This is countable, so $X$ is countable.

-

Hint:

1) There is one subset of the naturals without the number $\,1\,$ , also one subsets of the naturals without the number $\,2\,$ ...etc.

2) There is one subset without the numbers $\,1,2\,$ ,also one without $\,1,3\,$ ...

...................................

Thus, there are $\,\aleph_0\,$ subsets of the natural without one element since if $\,S^{(1)}\,$ is the subset of $\,\mathcal P(\Bbb N)\,$ containing all these subsets, then if

$$S_k:=N-\{k\}\Longrightarrow S^{(1)}=\bigcup_{k=1}^\infty S_k$$

...and etc.

-