Is my proof that the set of all finite subsets of a countable set is countable correct?

Question

Q. Let $X$ be a countable, infinite set. Prove that the set of all finite subsets of $X$ is countable.

So I say;

Let $X$ countable be given.

Let $F$ be the set of all finite subsets of $X$.

Let $F_i$ be the subsets of $X$ containing $i$ elements where $i$ a natural number.

Then $F$ is the union of all the $F_i$.

This union is countable as the natural numbers are countable.

A countable union of finite sets is countable, hence $F$ is countable.

(I have already proved a countable union of finite sets is countable in an earlier stage of the question, that is why I am stating this as fact)

Does this proof hold? I have seen a few other proofs that seem to be more complicated than mine and so I worry that I am missing something simple.

Answer 1

You say that $F$ is countable because it is a countable union of finite sets, which is false. $F_1$ is not a finite set if $X$ is infinite, and neither is $F_i$ for any other $i$!

Answer 2

There are numerous method for this kind of question.

This is a nice one. In my opinion at least.

The first step; Consider the empty set. We won't want to ruin our proof by considering everything except the empty set. This is easy, however, as if we can show all non-empty finite subsets are countable, we can show adding the empty set is.

Step 2; We consider $ n > 0$ t be fixed. Let X be a subset of the natural numbers (for the sake of simplicity) that is of size $n$ - that is, is of the form {$x_1 , x_2 , ... , x_{n-1} , x_n$}. Can you associate this to n-tuple of real numbers?

Hint; that is $(x_1 , x_2 , ... , x_{n-1} , x_n)$

Now, we have an injection of finite subsets of size $n$ to the set of n-tuples of natural numbers, i.e. $\mathbb{N}^n$.

Now, can you prove that the (countable) union of countable sets is countable? Hint; Arrange the naturals in some kind of grid, where every row is infinite and not equal to any rows above or below it.

Now, prove via induction that for a countable set $\mathbb{B}$ we also have $\mathbb{B}^k$ is countable for any natural number k. Hint; consider your notes of proving the rational numbers are countable.

Now, we finally see that there is an injection from the set of all finite subsets of the natural numbers to the set $U_{n \in \mathbb{N}} \mathbb{N}^n$.

Thus, the set of all subsets of $\mathbb{N}$ is countable (*).

(*) assuming the following; that any subset of a countable set is countable, and if there is an injection from an infinite subset to a countable set, that set must be countable - can you prove these and state at which points they should be used (try to explicitly construct a bijection)?