Exercise · ZW-CANTOR-S-DIAGONAL-THEOREM-009 · ★★★ Advanced
Let \(A\) be the set of binary sequences with finitely many ones. Is \(A\) countable?
Choose one option.
A No: every subset of an uncountable set is uncountable. B No: \(A\) contains the sequence \(000\ldots\), which forces the diagonal argument. C No: \(A\) has the cardinality of \(\mathbb{R}\). D Yes: each element of \(A\) is determined by a finite string of zeros and ones, and the finite strings form a countable set. Show answer D. Yes: each element of \(A\) is determined by a finite string of zeros and ones, and the finite strings form a countable set.← Back to the question
Explanation A sequence with finitely many ones can be truncated after its last 1, and finite binary strings form a countable set . A subset of an uncountable set can be countable.
Theorem proving that the set \(\{0,1\}^{\mathbb{N}}\) of binary sequences is not countable, by building a sequence that appears in no list.
\[t(n)=1-s_n(n)\]
More practice problems: cantor's diagonal theorem