I recently found Cantor's diagonal argument in Wikipedia, which is a really neat proof that some infinities are bigger than others (mind blown!).

But then I realized this leads to an apparent paradox about Cantor's argument which I can't solve. Basically, Cantor proves that a set of infinite binary sequences is uncountable, right?. But what about a set of all possible binary sequences (infinite or not)? Wouldn't that then be uncountable as well? And if so, doesn't that also imply that the natural numbers are also uncountable?

Note: I looked at other similar questions in this site, which says there is no natural number with an infinite number of digits. I don't understand this explanation, because we need a large number of digits to represent a large number. So why can't we have a interger with infinite digits?

  • $\begingroup$ The set of finite binary sequences (which may be interpreted as the set naturals expressed in base two) is countable. The set of infinite sequences is uncountable. The union of the two is uncountable. The Cantor argument fails in the finite case because the counterexample constructed by the argument is infinite and therefore not part of the set itself. $\endgroup$ – Arthur May 14 '16 at 9:32
  • $\begingroup$ See the post: how does Cantor's diagonal argument work $\endgroup$ – Mauro ALLEGRANZA May 14 '16 at 9:37
  • $\begingroup$ Every natural number is finite (however big it is): thus, only a finite number of digits will suffice to represent it. $\endgroup$ – Mauro ALLEGRANZA May 14 '16 at 9:40
  • $\begingroup$ @MauroALLEGRANZA Infinities always makes my head spin. So what you are saying is that my natural number can be infinitely large, but its representation requires only a finite number of digits? $\endgroup$ – curious May 14 '16 at 10:07
  • 2
    $\begingroup$ There are no infinitely large natural numbers. $\endgroup$ – Mauro ALLEGRANZA May 14 '16 at 10:19

Your Answer

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

Browse other questions tagged or ask your own question.