0
$\begingroup$

How do I prove the cardinality of the set of all binary sequences equal c?

I know I have to find a bijective function from (0,1) to the set of all binary sequences. But I can't think of one.

Cantor's diagonal argument only shows it is uncountable, i.e. cardinality greater than d.

$\endgroup$
0
$\begingroup$

How about $$\{b_i\} \mapsto \sum_i b_i 2^{-i},$$i.e., treat each binary sequence like $01100000...$ as a binary fraction, i.e., $.011 = 3/8$. The non-finite ones will be where the irrationals get produced. :)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is not 1-1, as $011000000\ldots$ has the same image as $01011111\ldots$. You need some extra arguments that the exception points are but countable in number. $\endgroup$ – Henno Brandsma Feb 28 '16 at 12:48
  • $\begingroup$ Good point: The exceptional points are exactly those that end in an infinite unbroken sequence of 1s; there are countably many of these: the sequence starts at some digit $k$; the previous digit must be a 0; prior digits can be anything, so there are $2^{k-2}$ of these. We end up summing a countable sequence of finite numbers; the result is countable. $\endgroup$ – John Hughes Feb 28 '16 at 15:29

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.