1
$\begingroup$

Cantor proved, using diagonalisation, that the set of infinite sequences of binary digits S is uncountable (a very simple proof can be found at wikipedia).

I do understand his arguments, but I do not understand how that can be: natural numbers can be represented in base 2, covering all of S. It seems obvious that there is a bijection between natural numbers and S:

0 <-> 00000000... 1 <-> 10000000... 2 <-> 01000000... 3 <-> 11000000...

and so on. Can anybody explain me please why S is still uncountable?

$\endgroup$
8
  • 5
    $\begingroup$ Which natural would you assign the sequence $01010101010101010101....$? (I mean each odd element is $0$ which each even element is $1$.) $\endgroup$ Commented Feb 14, 2015 at 22:03
  • $\begingroup$ @user59363, don't worry about it. He said the bijection was obvious. $\endgroup$ Commented Feb 14, 2015 at 22:05
  • $\begingroup$ Well, those are not the strings that Cantor used. A simple click on the link that you've provided yourself shows otherwise. $\endgroup$ Commented Feb 14, 2015 at 22:06
  • 2
    $\begingroup$ You can't delete the function with an upvoted answer. Next time, try harder. In any case, for future reference, the best way to deal with this on your own is to apply the proof of Cantor's theorem to your suggested bijection and see for yourself how it's not really surjective. There's really nothing better than that. No matter what people will answer, finding the answer on your own is always better. $\endgroup$ Commented Feb 14, 2015 at 22:16
  • 1
    $\begingroup$ Application of Cantors proof to your list would return the sequence $11111111111111111111111111111....$ (all ones). $\endgroup$ Commented Feb 14, 2015 at 23:07

1 Answer 1

Reset to default
4
$\begingroup$

In the map you have defined, just the sequences that are $0$ after some point are considered. Thus the sequences changing infinite times, like $0101010101010101...$, are not covered. Therefore it is not an onto map and not a bijection.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.