Cantor’s Diagonalization For Other Lists

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.