The set of all finite subsets of the natural numbers is countable [duplicate]

Solution 1:

What you have is nowhere near a proof. The definition of $X$ can be accepted, but it is not conveying any insight transgressing the verbal formulation of the problem.

We have to construct a bijective map $$f:\quad {\mathbb N}_{\geq0}\to X,\qquad n\mapsto A_n\ .\tag{1}$$ This map produces for each $n\in{\mathbb N}$ a finite set $A_n\in X$, and each element $A\in X$ is produced exactly once.

(Depending on the theorems of elementary set theory that are available at this point one could make do with a surjective $g:\ {\mathbb N}_{\geq0}\to X$, or an injective $h:\ X\to{\mathbb N}_{\geq0}$.)

There are various examples of such $f$'s around. The simplest that comes to mind is the following: Any set $A\subset{\mathbb N}_{\geq0}$ can be encoded as a bit string ${\bf b}_A:=(b_0,b_1,b_2,\ldots)$ by putting $b_k:=1$ when $k\in A$ and $b_k=0$ otherwise. When $A\in X$ this string has only finitely many ones. Now put $$\hat f(A):=\sum_{k=0}^\infty b_k2^k\qquad(A\in X)\ .$$ This means that we interpret ${\bf b}_A$ as binary expansion of a certain nonnegative integer. The $\hat f$ defined in this way is the inverse of a function considered in $(1)$.

Solution 2:

Comments on your proof.

Define a set $ X=\{A\subseteq\mathbb{N}\mid \text{$A$ is finite} \}$. OK

We can have a function $g_{n}: \mathbb{N} \rightarrow A_{n} $ << Problem: You have to define $A_n$

Say you wanted to say, $A_n$ is a finite subset of $\mathbb{N}$ defined by: $$A_n = \{n_1,n_2,... | ~ n_i \text{ occurs as exponent in } n = p_1^{n_1} p_2^{n_2} ... \}$$ then a better notation is to use

$g:\mathbb{N} \rightarrow X$ where $g(n) = A_n$ where $A_n ... \text{*as above*}$

Then you would say "By the fundamental theorem of arithmetic, each $A_n$ is finite and $g$ is surjective."

With the above clarifications, your remark "By the 'Union of countable sets is countable' theorem, X is countable" does not help.

You would invoke instead the following argument:

"Likewise, it is easy to find $h:X \rightarrow \mathbb{N}$, a surjective function too, for example $h(A) = min(A)$.

And as we have a surjective function in both directions, they have the same cardinality."