0
$\begingroup$

Can someone explain this in the most straightforward manner possible? I've looked at one other thread on here, but the mathematics was unfortunately too confusing for me. Is there some way I can understand why this is true without getting too much into mathematical bijections?

$\endgroup$
1
$\begingroup$

Here's one way to think about it:

The set of sequences of length $n$ will always be countable. We usually show that $\mathbb{N}^2 = \mathbb{N}\times \mathbb{N} \sim \mathbb{N}$ (that is, $\mathbb{N}\times \mathbb{N}$ has the same cardinality as $\mathbb{N}$) by some diagonalization argument. From there, it follows that for any $n$, $$\mathbb{N}^n = (\mathbb{N}^{n-1})\times \mathbb{N} \sim (\mathbb{N}) \times \mathbb{N} \sim\mathbb{N} $$ From there, we note that the union of countably many countable sets is countable. The key to this one is to note that we can fit any union of countable sets into $\mathbb{N} \times \mathbb{N}$ by making each set its own "row".

Thus, the set of finite sequences, which is the union of all sequences of length $n$ for every $n \in \mathbb{N}$, must be countable.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.