Proof of a countable set

Question

I want to prove that $$ E = \{ A \subset \mathbb{N} | \hspace{0.1cm} |A| < ∞ \} $$ is countable. Additionally I got the hint to first prove, that $$ E_{k} := \{ A \subset \mathbb{N} | \hspace{0.1cm} |A| < k \} $$ is countable; to show that I should consider $ \mathbb{N}^{k} = \prod_{i=1}^{k}\mathbb{N} $

So far, I know that $ \prod_{i=1}^{k}A_{i} $ is countable by definition, where $(A_{1},..., A_{n})$ is a finite family of countable sets. Furthermore, I know, per definition, that $\mathbb{N}$ is also a countable set. Therefore, I assume that $ \prod_{i=1}^{k}\mathbb{N} = \mathbb{N}^{k} $ is countable as well.

Unfortunately I don't know how to continue at this point as I do not have a clear understanding how the last hint can be used to show that E is actually countable.

Any help is greatly appreciated!

Answer 1

Hint: If $A=\{a_1,\ldots,a_k\}\in E_k$ how many possibilities are there for each $a_i$? Maybe you should consider $E_k:=\{A : |A|=k\}.$

Answer 2

Try to show that $E_k=\{A\subset\Bbb N\colon |A|=k\}$ is countable. Then $E=\displaystyle\bigcup_{k\in\Bbb N}E_k$ is countable.

Try the induction. For $k=1$, $E_1$ is the set of singletons, trivially countable. Suppose that $E_k$ is countable. Show that then $E_{k+1}$ is also countable.

Answer 3

An alternate approach:

Note or prove first that any finite subset of the natural numbers must have a largest element and any subset of the natural numbers with a largest element must be finite.

Now, consider $E_k=\{A\subseteq \Bbb N~:~\max(A)=k\}$: the family of subsets of the natural numbers with largest element $k$.

Consider now $\{\emptyset\}\cup\bigcup\limits_{k=0}^\infty E_k$