# Problems with Cantor's diagonal argument and uncountable infinity

Cantor's diagonal argument:
As a starter I got 2 problems with it (which hopefully can be solved "for dummies")

First: I don't get this: Why doesn't Cantor's diagonal argument also apply to natural numbers? If natural numbers cant be infinite in length, then there wouldn't be infinite in numbers. By using a randomly ordered list, you wouldn't end with an endless sequence of 0's you have to change. Also it initially goes for "set of numbers". It is applied to the "right" side (fractional part) to prove "uncountability" but can't be used for the "left" side (integer part) because of "reasons" (I simply do not get it).

Second: the way is is used so many times, would just work in the case that the length and width of the list equals. Just listing all natural numbers where $$0<=x<100$$ will have a width of 3 but a length of 100. At base x each increase of digits will increase the length by x times. At base 10, all 4 digit numbers will create a list with 1000 entries. The length increases exponentially while the width does linearly. This is wrong in so many ways but: Doing this infinitely makes it a square?!? (Natural numbers are a "part" of integers but as you can map both with each other they are considered being the same size aka 2 different countable infinities always have the same "size" while one can be just a part of the other)

As the last part: lets assume we divide all real numbers in 2 parts. The integer part which defines the "set" we use. (there will be "countable" infinite of them) Now, all we need to do is mapping the fractional part. Just use the list of natural numbers and flip it over for their position (numeration). Ex 0.629445 will be at position 544926. You could argue that this isn't possible for numbers like $$\sqrt{2}$$.
Lets pick $$\pi$$:

3.1415926535897932384626433832795… will be
3rd set at position: …5972383346264832397985356295141


There is no reason you cannot pick the next digit and put it in front for the position. There is no limit in length for natural numbers -> you can write a natural number which is the index for just that fractional part. Simply put: you can map EVERY number with $$0<=x<100$$ with a natural number. And a countable infinite amount of sets containing countable infinite entries still is countable.

So there are 3 Questions (I probably need to split this question):

• Why doesn't Cantor's diagonal argument also apply to natural numbers? (for dummies: why you can't simply use it to the left)
• If the count of digits equals the the length of the list, doesn't it just proves that this construction cannot contain all possibilities?
• Wouldn't the construction of a set like in "the last part" be a prove that all real numbers are countable infinite? (Which part can't be done / is invalid?)

The most important part would be the third question. (If it only qualifies for one answer) Thanks in advance.

An additional big "thanks" in advance for correcting all the spelling, orthography and typos...

• It's simply not true that natural numbers are allowed to have infinite decimal expansions to the left. This isn't a matter you get to disagree with; it's just what a natural number is. You can consider "numbers" which have infinite decimal expansion to the left but then these are not what everyone else calls "natural numbers". Oct 28, 2018 at 20:49
• The representation being used in the comment you linked to only looks like decimal expansion. What the bits they were using represented were positive powers of $2$. So $1000...=2^0$, $01000...=2^1$, $001000...=2^2$, and so on. You can represent every natural in this form, however, your representation must "terminate", else it would be infinite in size, not just in terms of bit length. Also, consider that $10000....$, $0100...$, $001000....$, $0001000...$,... are all "finite" in bit length, but the sequence is infinite. As we can always add another $0$ to the left of our $1$. Oct 28, 2018 at 20:54
• @EricWofsey if they cannot have infinite digits to the left, how can there be infinite many of them? Also, wouldn't that end with a point at which you cannot multiply it by 10? (for base 10) Is there anything out there that proves that a natural number will be something different if you increase it infinite many times? (again: for dummies.... i doubt that) Oct 28, 2018 at 21:10
• So you're saying that if all natural numbers are finite, then there are only finitely many of them? Oct 28, 2018 at 21:35
• @AsafKaragila "infinity" fooled me :( Having no "limit" isn't the same as "infinite". There is no "limit" to the size of a natural number, which makes them infinite in count, but each number itself needs to be finite (else it would be infinity).... the longer I think about it, the more correct it looks to me Oct 28, 2018 at 22:01

"If natural numbers can't be infinite in length, then there wouldn't be infinite in numbers." You are extrapolating properties of the natural numbers to what is called "potential infinity." But that is not what Cantor means by Aleph0.$$\newcommand\N{\mathbb{N}}$$

"Potential Infinity" is a hypothetical number that represents the hypothetical end to the sequence 1,2,3,... . Nobody treats it as a real object, but only in hypothetical evaluations of expressions where its impact on the result diminishes to nothing. For example, f(x)=3/(2+1/x) approaches 3/2 "as x goes to potential infinity." The point is that it is treated like a number with the same properties as "regular" numbers, but you can never reach it. "Actual infinity" is a well-defined mathematical concept, but it is nothing like a "regular number."

The "cardinality" of the set {1} is the cardinal number 1. That is, the set has one member. The cardinality of the set {1,2} is the cardinal number 2. In general, the cardinality of the finite counting set {1,2,3,...,n} is the largest number in it, n.

The Axiom of Infinity says that there is a set $$\N$$ with a similar form, but that has no largest member. Its cardinality is Aleph0, which can be called "Actual Infinity." It is not a member of the set it describes. It is not a "regular number" in any way. Even though we can extend the definition of numbers to include it as an "irregular number," it does not have the all the same properties. One that is different, is that you can't represent it with a string of digits. Not even an infinite string whose value you might think you could claim is "Potential Infinity."

Diagonalization does not work on natural numbers because it requires a digit for every member of $$\N$$, and that does not represent a natural number.

About your second problem: you can't consider an $$\N$$ by $$\N$$ array of characters to be square. "Square" means that you can only pair rows with columns one a 1:1 basis. While you can make such a pairing with an $$\N$$ by $$\N$$ array, you can also pair them on a 1:2 basis. Or 3:5. Or 14:9. The point of using Aleph0 for a cardinality, is that it represents any countably infinite set the same way.

• Thanks for the extended answer. I got multiple things wrong here to start with. By better understanding (at least a part) of the whole "infinity"-problematic a lot makes sense now. Nov 19, 2018 at 9:35
• Do you mean f(x) = 3 / (2 + 1 / inf) is equal to 3/2 as x approaches infinity? What you have currently would approach zero if I'm not mistaken. Apr 30, 2022 at 20:08
• Yeah, probably 3/(2+1/x). I was thinking more about the end result than what I was typing. Sep 17, 2022 at 12:36

This won't answer all of your questions, but here is a quick proof that a set of elements, each of which has finite length, can have infinite cardinality. Let $$\newcommand\N{\mathbb{N}}\N$$ be the set of natural numbers where each natural numbers are defined as having a finite decimal expansion. Suppose that the cardinality of $$\N$$ is finite. Then it must have some cardinality $$k$$ where $$k$$ is some finite number. By definition, that implies that there is a bijection $$f$$ from $$S=\{1,2,\dots,k\}$$ to $$\N$$. Now, let $$a_1=f(1)$$, $$a_2=f(2)$$, and so on until we have $$a_k=f(k)$$. In addition, let $$a_{max}$$ be the maximum of all of $$a_1$$ through $$a_k$$. Now, let $$b=a_{max}+1$$. It should be clear that $$b$$ isn't equal to any of $$a_1$$ through $$a_k$$ as it is larger than each of them. As such, there is no $$x\in S$$ where $$f(x)=b$$ as then $$b=a_x$$. On the other hand, $$b$$ is some number with a finite decimal expansion ($$a_{max}$$) plus $$1$$. Its decimal expansion can be at most $$1$$ longer than that of $$a_{max}$$, and a finite number plus $$1$$ is still finite. As such, $$b\in\N$$. We, therefore, have a contradiction as $$f$$ isn't subjective and so no such $$k$$ can exist. That means that $$\N$$ can't have a finite size.

To put this argument in less formal language, $$\N$$ is infinite not because any of it's elements is infinite, but because it has elements that get arbitrarily large. Suppose that we did have some finite size $$k$$. Then what would we say about $$k+1$$? It's still a natural number. The problem with putting a size on $$\N$$ isn't the size of the elements, but that they are unbounded.

This, in turn, with your proof is that the position of $$\pi$$ would not be that of a natural number as natural numbers have finite length. Your proof is actually correct that the cardinality of reals is equal to the cardinality of the set of all sequences with infinite digits.

• Looks like that isn't solvable "for dummies". As there is no point at which you cannot multiply a natural number by 10 it can be done infinitely... still the notation cannot be infinitely long. Will probably take some time to accept this. Simply put: the answer for the third question is: a real number does have a size and having infinite digits to the left makes it infinite and infinity is not a number thus this approach isn't possible :( While writing, it starts to make sense... Oct 28, 2018 at 21:52
• The second part is also the answer to the first. If you multiply a number by 10 an infinite number of times, it will be infinite and so will no longer be a number. You can only multiply a finite number of times. Oct 28, 2018 at 21:57
• Unfortunately I assumed that having "no limit" allows to do it "infinite" many times. There is no limit in multiplying by 10 and still getting another natural number, but doing it "infinitely" is something different... now I will check "Cantor's diagonal argument" another 100 times as the solution to my approach of mapping being wrong looks so simple to me as it is probably also not the big deal... thx again for everything Oct 28, 2018 at 22:10
• Also, look up $p$-adic numbers: these give the extension of natural numbers allowing infinitely many digits to the left, written in number system of base $p$. Note that Cantor's argument does apply to them, and their cardinality indeed equals to that of reals (continuum). Oct 29, 2018 at 9:46

For the first question-how natural numbers are infinite in number but every natural number has finite digits? I will be expressing every natural number in base 2 for simplicity. Consider a binary tree in which every node has 2 child nodes.Top most node is .0 its child nodes are 0.0 and 1.0.Child nodes for 0.0 are 00.0 and 10.0 and for 1.0 are 01.0 and 11.0 similarly for 00.0 - 000.0 and 100.0 and for 10.0 - 010.0 and 110.0 ......... by using this infinite binary tree we can make an infinite list - (by mentioning the elements of 1st row than 2nd row than 3rd row,4th row...... ) .0 0.0 1.0 00.0 10.0 01.0 11.0 000.0 100.0 010.0 110.0 001.0 101.0 011.0 111.0 . . .

clearly this infinite list will contain every natural number (more than ones). While making of this list the next element on the list would had only come into the list by being in one of the node of the infinite tree but that means that number would have some leftmost digit but since an infinite number like -'........11110' does not have any leftmost digit it would not be present on the tree and therefore would not have transferred to the list. ex - just like their is no last digit of e or pi or in the number 0.333333........ (=1/3). The formal argument that every natural number is finite/has finite digits can be made using induction.

If you are looking for some intuitive understanding for why their are much more real numbers than natural numbers or rational number here's a one that i developed for myself- If you think about the number of real numbers by using permutation - Consider numbers between 0 and 1 all of them can be represented like this- 0.xxxxxxxxxxxxxxxxxxxxxxxxxxx..... each "x" can have 2 possibility (if binary) and their are aleph null- "x" so total number = 2^aleph null. Now since numbers from 0-1 can be mapped to entire real number line so they too have 2^aleph null possibilities. But since natural numbers have only finite digits for permutation so aleph null possibilities. Also since every rational number can be mapped to natural number so they too have only aleph null possibilities.