Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Lawrence D'Oliveiro <ldo@nz.invalid>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Tue, 15 Apr 2025 04:42:39 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 69
Message-ID: <vtko3u$2u0tr$6@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me> <vthad1$3oh15$3@dont-email.me>
	<9c27b08cca9d0fca87e57bcabc3412c80ff7a4f1@i2pn2.org>
	<vtk37d$295ku$7@dont-email.me>
	<99bd9c3545fdcc03cf33152ee0db852edbe1e23d@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 15 Apr 2025 06:42:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="84fb5bea06fc98d4d0df182c3d5aedf4";
	logging-data="3081147"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19zYCxyDeq4es85uraTIpxk"
User-Agent: Pan/0.162 (Pokrosvk)
Cancel-Lock: sha1:5gguPyoDZhPqtpL/6N6xLF2deLA=
Bytes: 4024

Here’s my counterexample list: write out the whole numbers
(non-negative integers) from 0 in increasing order, and flip the
digits of each one so that the digit from the 10⁰ place goes to the
10¯¹ place, 10¹ to 10¯² etc:

    0.0000000000000...
    0.1000000000000...
    0.2000000000000...
    0.3000000000000...
    ...
    0.9000000000000...
    0.0100000000000...
    0.1100000000000...
    0.2100000000000...
    0.3100000000000...
    ...
    0.9100000000000...
    0.0200000000000...
    ...

Notice an interesting property of the list:
* If you look at the first digit after the decimal point, then in
  every run of 10 consecutive list entries, you will find every
  possible value of that digit.
* If you look at the first two digits after the decimal point, then in
  every run of 100 consecutive list entries, you will find every
  possible combination of values of those two digits.
....
* If you look at the first N digits after the decimal point, then in
  every run of 10**N consecutive list entries, you will find every
  possible combination of values of those N digits.

(Combinatorial explosion? Of course it’s a combinatorial explosion.
But there’s plenty of room for a combinatorial explosion or two, or
many, in an infinite list!)

This is a priori not a *complete* list of all the reals (the original
point of the Cantor construction). You’d think it would make things
easier for the Cantor construction, but it doesn’t.

Step 1 of the Cantor construction: choose a digit in the 10¯¹ place
different from that of the first item in the list. There are 9
possibilities we could pick. But all the 10 possibilities for that
first digit occur in the following 10 numbers, so our pick will
definitely match one of them.

Step 2: choose the next digit, in the 10¯² place, different from that
of the second item in the list. There are, again, 9 possibilities we
could pick. But all the 100 combinations of possibilities for the
first two digits occur in the following 100 numbers, so our picks so
far will definitely match one of them.

And so on: at step N, we pick a digit in the Nth decimal place, to be
different from that of the Nth number in the list. But all the 10**N
possibilities for the digits we have picked so far occur in the
following 10**N numbers, so the number we have constructed so far will
provably match one of them.

Note this is a proof by induction: if our choices at step N match some
existing entry in the list, then so will the addition of our next
choice at step N + 1. Since our first choice already matches some
existing entry in the list, it follows that, however many digits we
choose, the result will always match some existing entry in the list.

So even in a list which we already know does not contain every
possible real number, the Cantor construction fails to find one of the
missing ones.

QED.