I was reading this pop math piece on "the different sizes of Infinity." The article explains why the real numbers are uncountably infinite.

Taking a real number, my uneducated mathematical mind intuits that it could be considered as an infinitely-long word made up of letters drawn from an infinitely long alphabet (the rational numbers) in arbitrary combination (hence $+\infty$ to the power of $+\infty$ possible combinations). This would seem to suggest that the real numbers are countably infinite.

Of course, I know my reasoning must be wrong, but I do not have the mathematical background to find out why. Does anyone care to explain?

  • $\begingroup$ You're looking for the Cantor diagonalization argument. en.wikipedia.org/wiki/Cantor's_diagonal_argument $\endgroup$ – user18862 Nov 12 '14 at 23:23
  • 1
    $\begingroup$ All real numbers can be defined by infinite strings made from a finite alphabet. There are only $10$ digits but every real can be made from a string of them. $\endgroup$ – Jam Nov 12 '14 at 23:25
  • $\begingroup$ In other words, you are asking us why $\aleph^\aleph>\aleph$ $\endgroup$ – Lucian Nov 12 '14 at 23:25
  • $\begingroup$ @Lucian I think I am asking why |N^N| does not equal |R|. $\endgroup$ – user2398029 Nov 12 '14 at 23:27
  • $\begingroup$ @louism $2^{\mathbb{N}}$ is the same size as $\mathbb{R}$. $\endgroup$ – Matt Samuel Nov 12 '14 at 23:28

The diagonal argument says that $\aleph_0<2^{\aleph_0}$ and $\aleph_0^{\aleph_0}=2^{\aleph_0}$ because $$2^{\aleph_0}\le\aleph_0^{\aleph_0}\le(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$$

  • $\begingroup$ I understand this is correct symbolically, but I fail to rationalize to myself "why" this should be. $\endgroup$ – user2398029 Nov 12 '14 at 23:54
  • $\begingroup$ @louism I don't know where's the problem. Cantor's argument shows the infinite sequences on 2 letters are uncountable, so surely the infinite sequences of infinitely many letters are. And my argument shows that you can reduce the infinite sequences on infinitely many letters to the infinite sequences on 2 letters. $\endgroup$ – user2345215 Nov 13 '14 at 0:10
  • $\begingroup$ Ah-ha! Now I get it. Thanks for the re-statement / further explanations. $\endgroup$ – user2398029 Nov 13 '14 at 0:14
  • $\begingroup$ While this is a convincing argument for someone who has been introduced to cardinals, I fear that this doesn't make any sense to someone without a mathematical background and it appears to me that user2345215 might be convinced by "authority" rather than the given argument. $\endgroup$ – Stefan Mesken Nov 13 '14 at 2:56

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.