Countability Examples

Eventually zero sequences

Proposition: Let \(S\) be the set of eventually zero sequences of non-negative integers \(a_1,a_2,\ldots\); eventually zero means that for each sequence \(s\) there is an \(N\) so that \(a_i=0\) for \(i\ge N\). (Informally, the sequence can have anything at the beginning but eventually it becomes \(0,0,0,\ldots\).) Then \(S\) is countable.

This is interesting because we know on the one hand that, for any \(k\), the set of \(k\)-tuples of non-negative integers \((a_1,\ldots, a_k)\) is countable because it is a finite product of countable sets; and we know that the set of all sequences of non-negative integers \((a_1,a_2,\ldots)\) is uncountable by the diagonalization argument. So \(S\) is a kind of intermediate case, but it turns out to be countable as well.

Proof: First, let \(\mathbb{W}\) be the set of non-negative integers and let \(A(n)\) be \[ A(n)=\overbrace{W\times W\times W\times \cdots\times W}^{(n-1)}\times \mathbb{N} \] For each \(n\), \(A(n)\) is countable because it is a finite cartesian product of countable sets. For each \(n>0\) let \[ f_{n}:\mathbb{N}\to A(n) \] be a bijection, and let \(f_0\) send \(0\) to the zero sequence.

Now, let \(S(n)\subset S\) be the subset of sequences whose last non-zero entry is in position \(n\) (and let \(S(0)\) be the zero sequence). Now each element of \(S\) belongs to exactly one \(S(n)\) – just choose the \(n\) corresponding to the last non-zero entry in the sequence, or zero if the sequence is all zero. It suffices to prove that \(S^{*}\), which is \(S\) with the zero sequence deleted, is countable.

To construct a bijection from \(\mathbb{N}\to S^*\), first construct a bijection \(h:\mathbb{N}\times\mathbb{N}\to S^{*}\) by sending \((x,y)\) to \(f_x(y)\). This is a bijection, since every \(s\in S\) belongs to exactly one \(S(n)\) and \(f_n:\mathbb{N}\to S(n)\) is bijective by construction.

Finally, since \(\mathbb{N}\times\mathbb{N}\) is countable, \(S^*\), and also \(S\), is countable.