Cantor’s Diagonalization For Other Lists

This Question attempts to get at the heart of a key distinction many have rambled about on here. Mods please see final section first.

Question

Below is an incorrect proof that the cardinality of the set of even numbers is greater than the cardinality of the set of natural numbers.

Question: What logic can be given to explain why this proof is incorrect, but cannot also be used to claim the standard diagonal $$|\mathbb{R}|>|\mathbb{N}|$$ proof is incorrect? Familiarity with that proof might be useful.

The “Proof”

Bijection from naturals to positive evens cannot be done. Proof:

Suppose a listing is proposed, naturals in order on the left mapped to some listing of even numbers, on the right:

$$1 \mapsto E1$$

$$2 \mapsto E2$$

$$3 \mapsto E3$$

$$...$$

Take every $$E$$ in the list and add $$2$$ to $$n$$th digit to the left of the of the decimal.

(Example if we have gone through the first three lines and our number is $$284$$, and $$E4$$ is $$78$$ then the new number is $$2284$$, because $$E4$$ has a $$0$$ four places to the left of the decimal. If $$4 \mapsto 25476$$ then $$7284$$, if $$4 \mapsto 29476$$ then $$1284$$)

If applied to the standard ordering of $$1 \mapsto 2, ~ 2 \mapsto 4, ~3 \mapsto 6 ~...$$ Then our new number is developing as: $$... ~ 2222224$$ continuing to the left as we go. Like the standard diagonalization proof; it yields a new number each time. Whatever line $$n$$ you go to, the new number will vary from that one in the $$n$$th place to the left of the decimal.

Applied to any listing that can be proposed, for any item we reach on the list, the new number will vary from that $$n$$th number in the $$n$$th digit to the left of the decimal. Therefore the new number varies from every number and is not on the list. Therefore the list is not complete.

The Question Again / Note

Again, the proof is incorrect. Explain how it is by using logic that cannot be analogously employed to contradict the normal proof for the cardinality of reals vs. naturals.

Thanks.

Possibly Related w/o Solution

I’m hoping the minefield of past Cantor ramblings won’t bias mods. A good answer to the above will go a very long way for us.

This questioner argues with “anti-Cantor Cranks” which I am not. In his whole argument, it seems like every statement defending the diagonal proof could apply to my above incorrect proof. What am I missing? Refuting the Anti-Cantor Cranks

Also maybe slightly related: proving cantors diagonalization proof

Despite similar wording in title and question, this is vague and what is there is actually a totally different question: cantor diagonal argument for even numbers

Similar I guess but trite: Cantor's Diagonal Argument

This is more similar but solved by periodicity not applicable here: Why does Cantor's diagonalization not disprove the countability of rational numbers?

• Your "New number" is an infinite sequence of digits -- NOT an even integer. It is true that the set of infinite sequences of digits, or even of 0's and 1's, is not countable.
– Ned
Oct 1, 2021 at 19:22
• The diagonal argument for the uncountability of $\mathbb{R}$ has two components. First, given a map $F:\mathbb{N}\rightarrow\mathbb{R}$ we define an object $\alpha$ and show $\alpha\not\in ran(F)$. Second, we show that $\alpha\in\mathbb{R}$. This second step is so trivial that it's generally not highlighted, but it's exactly what breaks down in your approach. You're focusing entirely on the construction of the "antidiagonal object" $\alpha$ and ignoring the importance of checking that it actually belongs to the relevant set. Oct 1, 2021 at 19:28
• @AlBrown It's not a new observation at all. For example, it's exactly what Arturo said in his initial comment: "For the number you are producing to be an even number, it must contain no more than finitely many nonzero digits, because integers only have finitely many nonzero digits." Oct 1, 2021 at 19:33
• @AlBrown: What I wrote does not apply to the original argument because every sequence of digits represents a real number between $0$ and $1$; there is no restriction that all but finitely many of them must be equal to $0$. It's not the infinity of the list that matters, it's that integers only have finitely many nozero digits extending to the left, and real numbers can have as many nonzero digits as you want extending to the right. So your assertion that "Nothing [you] wrote wouldn't apply to the other diagonalization proof" is incorrect. Oct 1, 2021 at 19:38
• @AlBrown : And Noah is saying that it is not new compared to other comments: it's exactly what I said. Oct 1, 2021 at 19:39

Even numbers (meaning, integers) have only finitely many nonzero digits when written in base 10.

Your procedure certainly produces a sequence of digits. But unless you know the digits produced are $$0$$ after a certain point, you will not obtain an even integer: you will just obtain an infinite sequence of digits which does not correspond to an even integer.

Under your procedure, in order for the sequence of digits to determine an even integer we need to make sure that there exists some natural number $$N$$ such that for every $$n\geq N$$, the $$n$$th digit of the $$n$$th number on the list is $$8$$. That way, when you construct your new sequence of digits, the resulting digit in position $$n$$ will be a $$0$$ after position $$N$$.

But consider the numbers $$2$$, $$22$$, $$222$$, $$2222$$, and so on. Since you start with a bijection between $$\mathbb{N}$$ and the even numbers, they must all be on the list. But since there are more than $$N$$ of them, for any given $$N$$, at least one of them appears after the $$N$$th term on your list.

That means that there is no $$N$$ such that for all $$n\geq N$$, the $$n$$th number on the list has $$n$$th digit equal to $$8$$: for every $$N$$, there is an $$n\geq N$$ such that the $$n$$th digit of the $$n$$th number is either $$0$$ or $$2$$. So the sequence of digits you produce contains $$2$$s and $$4$$s in arbitrarily "late" positions. They never become "all zero after this point."

This shows that the sequence of digits you are producing is not in fact an even integer. So the fact that it is not in your list of all even integers is not a surprise: it doesn't belong to the club, it doesn't have to be on the club's roll.

This doesn't occur in Cantor's argument because every sequence of digits corresponds to a real number between $$0$$ and $$1$$.

Like the standard diagonalization proof; it yields a new number each time. Whatever line $$n$$ you go to, the new number will vary from that one in the $$n$$th place to the left of the decimal.

There is a misunderstanding here. The standard argument does not "produce a new number each time." The argument produces a sequence of digits, that we then put together to create a new number. It is that end result that we compare to the $$n$$th number on the list to conclude it is not equal to that.

A key thing that is not often mentioned (as Noah Schreiber notes) is that for any sequence $$(d_1,d_2,d_3,\ldots)$$ of digits (so $$d_i$$ must be one of $$0,1,\ldots,9$$), $$\sum_{i=1}^{\infty}\dfrac{d_i}{10^i} = 0.d_1d_2d_3\cdots$$ is definitely, absolutely, no question, a real number between $$0$$ and $$1$$. Any sequence yields a real number when you have the completed sequence.

Your process also yields a sequence of digits. But you are trying to put the digits $$(d_1,d_2,d_3,\ldots)$$ into a number by doing $$\sum_{i=1}^{\infty} d_i10^{i-1} = \cdots d_4d_3d_2d_1.$$

But this is a number if and only if the sum is finite: if and only if $$d_i=0$$ for all sufficiently large indices $$i$$. Otherwise, what you have is not a number. Numbers don't extend infinitely to the left of the decimal point.

That is a key difference between real numbers and integers: real numbers can extend infinitely to the right of the decimal point. Integers cannot extend infinitely to the left of the decimal point.

Your error is to think that the resulting object is a "number", let alone an "even number". It isn't. As I show above, what you produce cannot be a number at all.

• @AlBrown: You are completely missing the point. What you end up with is not an integer. Because what you end up with has infinitely many nonzero digits to the left of the decimal point So saying it is "even" is nonsense. "Even" applies to integers. What you have is not an integer. Oct 1, 2021 at 19:42
• @AlBrown: The really important point is in the first two paragraph. You need to realize that not every sequence of digits gives you an even integer (even if all digits are even), and that in order for the argument to go through you need the result of your procedure to be an even integer. That means more than just "the digits are even". Oct 1, 2021 at 19:45
• @AlBrown: I'm telling you that an infinite sequence of digits only represents an integer (even or not) if there are only finitely many digits that are not zero. An infinite sequence of $2$s is *not* an integer at all. There is no integer $\cdots 22222$ with infinitely many $2$s. That's just *not* an integer; it's not a number. Integers have only finitely many nonzero digits: you can prove that by induction. Before it can be an "even number", it has to be a **number**. And $\cdots 222222$ is not a number at all. Oct 1, 2021 at 20:18
• @AlBrown: Again: the "normal diagonal proof" constructs a real number between $0$ and $1$. EVERY sequence of digits, regardless of how many of them are equal to $0$ or different from $0$, determines a real number between zero and one. The same is not true for integers. To determine an integer, you cannot have infinitely many nonzero digits. An infinite sequence of $2$s in the original proof gives $0.22222\cdots$, which most definitely is a real number. An infinite sequence of $2$s in your argument gives $\cdots 222222$, which is nonsense. It's not a number. Oct 1, 2021 at 20:20
• @AlBrown: If I want the resulting digit to be $0$, using your process, then I need the $n$th digit of the $n$th number on the list to be $8$. that way, the digit I produce is $0$. Oct 1, 2021 at 21:06

This will not be a popular response. But I implore anybody who wants to object, to examine whether your objection is based on what you believe CDA says, and not what Cantor himself actually said.

The best way to explain how CDA can be applied to other sets, is to get it right in the first place. There is a pedantic error that is almost always included when CDA is taught, and that can be trivially removed. The problem is that it is almost always present, invalidating the logic. And I suspect that it is what makes students suspicious. (There are other errors as well, but they are less important.)

When you use proof-by-contradiction, you have to use all of the elements of the statement you assumed to derive the contradiction. As it is usually usually taught, CDA assumes that you can list every element of the subject set T; that is, t1, t2, t3, ... . It then proves that there is an element t0 that is not listed. This contradicts the part of the assumption that says the entire set is listed.

The error is that the derivation does use not the assumption that all elements of T are listed. It only uses the assumption that the listed elements are all in T. You could claim that "all are listed" is used when t0 is found to be not listed, but that is the pedantic and suspicious part. That form of proof-by-contradiction is rejected by some logicians, as being circular.

THE POINT IS THAT IT ISN'T WHAT CANTOR DID. He "breaks" the circle by making the contradiction about t0, not the list.

Cantor used a two-part proof. He first assumes there is a subset S of T that can be listed. Using CDA, he proves directly that there is an element s0 that is in T, but not in S. Only now does Cantor assume that S can be equal to T. By CDA, there is an s0 that is in T but not in S. By the assumption that S=T, s0 must be in both S and T.

What you asked about, is the part of Cantor's actual argument that proves that s0 is in T. Your T is the set of all even natural numbers. But s0 can be any infinite string of non-zero digits. Such a string does not have to represent a natural number, let alone an even one. So your s0 does not have to be in T.

I think the question misunderstands the Cantor diagonalization argument. The Diagonalization argument is that the constructed number is nowhere on the list. In the construction given, it is quite easy to see where the number would be on the list.

Let's take a simple mapping of n -> 2n for our list. So 1 -> 2, 2 -> 4, 3 -> 6, etc. So, the new number will have the nth digit have two added to it. So, that would be $$+ 2 \cdot 10^{n-1}$$. So, for the $$n$$th number on the list, the value of the number is $$2n$$ and the constructed number is $$2n + 2\cdot 10^{n-1}$$. Therefore, the location of the constructed number on the list is just $$n + 10^{n-1}$$.

Example: the 5th number is 10 ($$2\cdot 5$$). The constructed number is $$10 + 2\cdot 10^4 = 10 + 20000 = 20010$$. The location of the number on the list is $$5 + 10^4 = 10005$$. Therefore, the constructed number is in fact on the list.

In diagonalization, you can prove that the constructed number is nowhere on the list (not just that it differs from some specific location). That is because, for every position that you might consider it on the list, it triggers a contradiction, because if you had put it there, it would violate the terms of the construction.

• Hi Johnny. My bad but i had the construction misspecified. Check again if still interested thanks. Oct 1, 2021 at 20:33
• I'm not entirely sure I understand the construction, then. It sounds like you are constructing an infinitely long number. Well, infinite numbers aren't going to be on the list, because they aren't in the list of even numbers. Oct 1, 2021 at 22:26
• Yes thats the answer. Oct 1, 2021 at 23:37