2
$\begingroup$

Is this set countable or uncountable?

"Set of binary strings of length greater than 30"

not sure if length can be infinite or has to be considered finite. For every binary string we can map it to the corresponding decimal value in the set of natural numbers. But if length becomes infinite then decimal value would not exist. It becomes confusing after this.

$\endgroup$
  • $\begingroup$ If you admit the infinite string then this set is uncountable. However if you does not admit infinite string then the given set is countable. $\endgroup$ – Hanul Jeon Sep 26 '13 at 16:26
2
$\begingroup$

You can forget the $30$. Why? Let $A$ be the set of all strings (of any length) and $B$ be the set of a strings of length $> 30$. There is an injection $A \to B$ by sending a string to the same string with $31$ zeros appended to the beginning; and there is an injection $B \to A$ by sending a string to itself. By the Cantor-Bernstein-Schroeder theorem, $A$ and $B$ have the same cardinality. So $A$ is countable (resp. uncountable) if and only if $B$ is countable (resp. uncountable).

So the question boils down to: does 'string' cover only those of finite length or those of infinite length? This is now a 'standard' result.

  • If you allow infinite strings, use a diagonal argument (or a bijection with $\mathbb{R}$ or $[0,1]$ or whatever) to prove uncountability;
  • If you do not allow infinite strings, use the fact that there are only finitely many strings of a given length, and that a countable union of finite sets is countable.
$\endgroup$
  • 1
    $\begingroup$ I would claim that the standard definition of string is finite. You covered what I said (both ways) on this topic better. +1 $\endgroup$ – Ross Millikan Sep 28 '13 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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