Set of finite sequences of naturals: countable

Show that the set $${\mathbb N}^{<{\mathbb N}} = \cup _{k=0}^{\infty } {\mathbb N}^{\{0, 1, \ldots , k-1\}}$$ of all finite sequences of natural numbers is countable.

Here are two standard ways to see that the set of all finite sequences of naturals

$$ \mathbb{N}^{<\mathbb{N}} \;=\;\bigcup_{k=0}^\infty \mathbb{N}^{\{0,1,\dots,k-1\}} $$

is countable.

---

1. Union of countably many countable sets

1. Each fixed‑length piece is countable. For each $k\ge1$, the set of $k$‑tuples

   $$ \mathbb{N}^k = \{\, (n_0,n_1,\dots,n_{k-1}) : n_i\in\mathbb{N}\} $$

   is in bijection with $\mathbb{N}$. For example, one can use the usual Cantor–Gödel pairing repeatedly to pair off coordinates:

   $$ \pi:\mathbb{N}\times\mathbb{N}\;\xrightarrow{\sim}\;\mathbb{N}, \quad (a,b)\;\mapsto\;\tfrac12(a+b)(a+b+1)+b, $$

   and then pair $\pi(\pi(n_0,n_1),n_2)$, etc., to get a bijection $\mathbb{N}^k\cong\mathbb{N}$.

2. A countable union of countable sets is countable. We have

   $$ \mathbb{N}^{<\mathbb{N}} \;=\; \bigcup_{k=0}^\infty \mathbb{N}^{k} \,, $$

   and since each $\mathbb{N}^k$ is countable, their (countable) union is again countable.

Hence $\mathbb{N}^{<\mathbb{N}}$ is countable.

---

2. Explicit injective coding via prime factorisation

Define a map

$$ \Phi:\mathbb{N}^{<\mathbb{N}}\;\longrightarrow\;\mathbb{N}_{>0} $$

by sending a finite sequence

$$ s=(n_0,n_1,\dots,n_{k-1}) $$

to the integer

$$ \Phi(s) \;=\; 2^{n_0}\,\cdot\,3^{n_1}\,\cdot\,5^{n_2}\,\cdots\,p_k^{\,n_{k-1}} \quad \bigl(p_k\text{ = the }k\text{th prime}\bigr). $$

• Injectivity. By the Fundamental Theorem of Arithmetic, every positive integer has a unique prime‑power factorisation; in particular, different sequences $s$ give different factorizations, so $\Phi$ is injective.
• Conclusion. An injective map from $\mathbb{N}^{<\mathbb{N}}$ into $\mathbb{N}$ shows $\#\mathbb{N}^{<\mathbb{N}}\le\#\mathbb{N}$. Since $\mathbb{N}^{<\mathbb{N}}$ is infinite, its cardinality is exactly $\aleph_0$.

---

Either argument establishes that the set of all finite sequences of natural numbers is countable.

Note: ChatGPT’s uses of \N, which rendered correctly in its own UI, were changed into \mathbb{N} here.