# The set of all finite subsets of $\mathbb{N}$ is countable [duplicate]

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?

• Which other thread? – Asaf Karagila Jan 31 '14 at 0:44
• – user3064097 Jan 31 '14 at 0:44
• – Asaf Karagila Jan 31 '14 at 0:45

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.