The set of all finite subsets of the natural numbers is countable

Question

Could someone verify my proofs?

Proposition: the set of all finite subsets of $\mathbb{N}$ is countable

Proof 1:

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

We can have a function $g_{n}: \mathbb{N} \rightarrow A_{n} $ for each subset such that that function is surjective (by the fundamental theorem of arithmetic). Hence each subset $A_{n}$ is countable.

By the "Union of countable sets is countable" theorem, X is countable.

Q. E. D.

Proof 2: Suppose we have an ordered list of prime numbers $p_{1}, p_{2}, ..., p_{n}$. Define a function $g: X \rightarrow \mathbb{N}$ such that $ g(A) = (p_{1})^{a_{1}}*(p_{2})^{a_{2}}*...*(p_{k})^{a_{k}} $ with $k=$ number of elements of each subset and $ a_{1}, a_{2}, ..., a{k} $ the ordered elements of them. By the fundamental theorem of arithmetic, that function is injective, hence $X$ is countable.

Q. E. D.

Answer 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)$.

Answer 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."

Answer 3

As others have remarked, you seem to already assume that the set you want to be countable is countable by the way you label the finite sets. However, you can "lexicographically order" the finite sets of natural numbers in many ways, for example the following: If $A$ and $B$ are finite sets of natural numbers, say that $A <B$ if $|A| < |B|$. If $A$ and $B$ are different subsets of $\mathbb{N}$ of the same cardinality, define $A <B$ if the smallest element if $B$ is less than the smallest element of $B$. If $|A| = |B|$ and $k >0$ and the $k$ smallest elements of $A$ coincide with the $k$ smallest elements of $B$, but the $k+1$-st smallest element of $A$ is less than the $k+1$-st smallest element of $B$, say that $A <B.$ this allows you to list the subsets of $\mathbb{N}$ in a strictly increasing order, and shows that there are countably many such sets. ( For each $n,$ there are countably many subsets of cardinality $n$, so the theorem you want to use does indeed apply here).

Answer 4

But the union of an *un*countable number of countable subsets need not be countable; think of the union of the singleton elements of $R$; so you need to have shown that $X$ is countable at this step - but that's what you're trying to prove.

The only evidence I see that there are a countable number of elements in X is your notation $A_n$. Usually with this notation, we mean it goes without saying that $n$ is in $N$ and that there is an implicit injective function $f : X \rightarrow N$.

But that again assumes what you already want to prove: that $X$ is countable.

Obviously, nobody would be asking you to prove that $X$ is countable if it weren't countable (well, actually, I've encountered a number of mistakes in textbook mathematical questions, so actually that isn't always true). But you always need to be careful that you aren't somehow assuming what you want to prove.

As a hint, think of the function f:

$f(A) = \sum_{a \in A} 3^a$

So, first off we must make sure - is $f(A)$ well-defined for all $A \in X$? It sure wouldn't be for all $A \in P(N)$!

Next, is $f$ in bijection with a subset of $N$ (in particular, does $f(A')=f(A'')$ if and only if $A'=A''$)?

Can we say "Q.E.D" now? What is the definition of "$X$ is countable"?

Answer 5

Here's a thought:

For $i\in\mathbb{N}$ let $B_i=\{S\subseteq\mathbb{N}\mid \sum_{x\in S}x=i\}$