$\mathcal{P} (\mathbb{N})$ is uncountable and $\{S \in \mathcal{P} (\mathbb{N}) \mid S \text{ is finite} \}$ is countable

Question

$\newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}}$

I know you can prove the first proposition with a variation of Cantor's diagonal argument. Is the following a sufficiently rigorous or even correct proof too?

Consider the interval $(0,1)$ in the real numbers. The decimal places of each number in this interval are countable, as each decimal place is located at a position with a natural number valued index. For each number

$$r = 0 \cdot 10^{0} + k_1 \cdot 10^{-1} + k_2 \cdot 10^{-2} + \dots \in (0,1) \text{ where $k_i \in \{0,1, \dots, 9\}$}$$

it holds true, that the number

$$ n = k_1 \cdot 10^{1} + k_2 \cdot 10^{2} + \dots \in \N$$

corresponds to $r$'s decimal places digit by digit (edit: in reverse order). But

$$\{n\} \in \mathcal{P}(\N)$$

So therefore there exists an injection

$$(0,1) \rightarrowtail \mathcal{P}(\N)$$

which maps each $r$ onto that $\{n\}$ the $n$ of which digit by digit corresponds to the decimal places of $r$. (edit: in reverse order) Hence there are at least as many elements in $\mathcal{P}(\N)$ as in $(0,1)$. But $(0,1)$ is uncountably infinite, so $\mathcal{P}(\N)$ too must be uncountable.

This certainly is not very pretty, as it argues based on the string representations of the numbers rather than the numbers themselves, but is it even valid to do this?

Another doubt I have about this stems from the fact that I think you can also argue the following:

The set $M = \{S \in \mathcal{P} (\mathbb{N}) \mid S \text{ is finite} \}$ also includes the elements $\{n_i\}$ that we just used to argue that $\mathcal{P}(\N)$ is uncountable. $M$ includes these $\{n_i\}$ because these are finite sets. So therefore $M$ would be uncountable by the above argument. Which it is not.

So somewhere in here is an error. Is it in the first proof or the second?

Answer 1

that the number n=k1⋅101+k2⋅102+⋯∈N corresponds to r 's decimal places digit by digit (edit: in reverse order).

But $r$ has an infinite number of digits. You can not reverse an infinite sequence. (What would be the first element).

The only elements that are "reversible" are the finite decimals (or the periodic decimals), i.e. the rationals. Hence you don't have an injection of $(0,1)$ into the power set but an injection of the rational numbers in $(0,1)$ into the power set and only into the subset of the Power set that has only finite sets as elements.

Answer 2

Here I'll prove a fact which can be used to prove your result.

$\mathcal{P}_n (\Bbb{N})=\{{S\subset \Bbb{N} | \text{card}(S)=n }\}$ is countable for any $n\in\Bbb{N}$.

Consider the natural function $\Bbb{N}^n\to\cup_{1\le k\le n}\mathcal{P}_k (\Bbb{N})$ given by $(x_1, x_2, \cdots,x_n)\to \{x_1, x_2, \cdots,x_n\}.$ This is clearly surjective and therefore $$\text{card}(\mathcal{P}_n(\Bbb{N}))\le\text{card}(\cup_{1\le k\le n}\mathcal{P}_k (\Bbb{N}))\le\text{card}(\Bbb{N}^n)=\text{card}(\Bbb{N}).$$