Determine whether the given sets are countable or uncountable. Justify your answers either with bijections or using results/methods.
The set of all possible binary strings. Note a binary string is a sequence of 0s and 1s.
If a binary string consists only of 0s and 1s, then is it even possible to find a bijection for it?
Best Answer
If the strings are of finite length, they are countable. A bijection from them to the set of positive natural numbers is given by $f(s)=1s_2$, where $1s$ denotes prepending 1 to $s$.
If the strings are of infinite length, they are uncountable. The bijection of prepending a radix point turns them into the set of real numbers in $[0,1]$, which were themselves shown uncountable by Cantor.