# Thread: mapping

1. ## mapping

Hi can anybody help me here,
i need help explaining the theory that

The set of all finite subsets of the natural numbers is countable.
i need to explain this by constructing an injective mapping. I looked on wikipedia but it was not too helpful.
thanks

2. Originally Posted by math_lete
Hi can anybody help me here,
i need help explaining the theory that

The set of all finite subsets of the natural numbers is countable.
i need to explain this by constructing an injective mapping. I looked on wikipedia but it was not too helpful.
thanks
This takes work if you are willing to avoid choice. There is a theorem which says that a countable union of at most countable sets is at most countable. The proof of this results depends on choice. Instead there is a weaker result.

Theorem: Let $A: \mathbb{N}\to S$ be a sequence such that $A_n$ is at most countable. And let $a: \mathbb{N}\to T$ be a sequence such that $a_n$ enumerates $A_n$ i.e. $a_n: \mathbb{N} \to A_n$ is a surjection. Then $\bigcup A[\mathbb{N}]$ is at most countable (i.e. $A_0\cup A_1\cup ...$ is at most countable).

Proof: Define the function $f: \mathbb{N}\times \mathbb{N}\to \bigcup A[\mathbb{N}]$ as $f(x,y) = a_x(y)$. The function $f$ is onto and so $f[ \mathbb{N}\times \mathbb{N} ] = \bigcup A[\mathbb{N}]$ is at most countable since the image of a countable set is at most countable (here we are using the result that $\mathbb{N}\times \mathbb{N}$ is countable).

Let $N$ be the set of all finite subsequences of $\mathbb{N}$. We prove a stronger result.

Theorem: $N$ is countable.

Proof: Let $\mathbb{N}^n$ represent all functions $n\to \mathbb{N}$. Define $A: \mathbb{N} \to S$ by $A_n = \mathbb{N}^n$ where $S = \mathcal{P}(\mathbb{N}\times \mathbb{N})$. Then $\bigcup A[\mathbb{N}] = N$. Therefore by above if we can produce $a: \mathbb{N}\to T$ then $N$ would be countable. Let $g: \mathbb{N}\to \mathbb{N}\times \mathbb{N}$ be any bijection - we know one such exists. Define $a: \mathbb{N}\to N$ in following way. Define $a_1$ to be the set of all one-element sequences i.e. $a_1(k)$ is the function $a_1(k): 1 \to \mathbb{N}$ defined by $a_1(k)(0) = k$. Define $a_{n+1}$ recursively at a point $k$ by first letting $g(k)=(k_1,k_2)$ and then $a_{n+1}(k)$ to be the $n+1$ element sequence whose first $n$ elements are the terms of the sequence $a_n(k_1)$ and the $n+1$ element is $k_2$. It remains to show that $a_n$ is an enumeration of $A_n$ for $n\geq 1$. Of course we avoided $a_0$ since that is the empty sequence (empty sequence) and does not alter the cardinality in question. Therefore, $N$ is at most countable. There is just one last step and that is to find such a set $T$ which contains all these $a_n$ to complete the proof.