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 $\displaystyle A: \mathbb{N}\to S$ be a sequence such that $\displaystyle A_n$ is at most countable. And let $\displaystyle a: \mathbb{N}\to T$ be a sequence such that $\displaystyle a_n$ enumerates $\displaystyle A_n$ i.e. $\displaystyle a_n: \mathbb{N} \to A_n$ is a surjection. Then $\displaystyle \bigcup A[\mathbb{N}]$ is at most countable (i.e. $\displaystyle A_0\cup A_1\cup ...$ is at most countable).

Proof: Define the function $\displaystyle f: \mathbb{N}\times \mathbb{N}\to \bigcup A[\mathbb{N}]$ as $\displaystyle f(x,y) = a_x(y)$. The function $\displaystyle f$ is onto and so $\displaystyle 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 $\displaystyle \mathbb{N}\times \mathbb{N}$ is countable).

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

Theorem: $\displaystyle N$ is countable.

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