Re: Question about the Diagonal Method.

Scott says...

Could you please explain why it is not f(2)? It is the original
enumeration and nothing new was added to it - there is no new list/
function, as you put it. As I corrected, let f be enumeration where
f(2) contains a certain set.

Scott,

The real content of Cantor's proof is that given any infinite
list L of decimal expansions of real numbers, there is a real
number r, called "the diagonal of L" that is not on the list.

Let's work with a particular example: Let L be the following
list

L(0) = .1000...
L(1) = .01000...
L(2) = .001000...
etc.

Notice the pattern: every element in L is of the form of
1 over a power of ten: 1/10, 1/100, 1/1000, etc. In particular,
every element of L is nonzero.

Now, the diagonal procedure is this:

1. First, create the
decimal expansion r such that the first digit of r is
the first digit of L(0), the second digit of r is the
second digit of L(1), the third digit of r is the
third digit of L(2), etc. For the above list, this
produces the number r = .11111...

2. Now, replace each digit of r by a different digit.
For definiteness, if the digit is 0 or 9, replace it
by 1, and otherwise replace it by 0. In our case, this
produces the diagonal number d = .00000...

d is zero, and so is not on the list L.

Start with a different list. Let L be the following list:

L(0) = .1111....
L(1) = .0111...
L(2) = .00111..
L(3) = .000111..
etc.

If you don't get the pattern, L(0) is the decimal representation
for 1/9, L(1) is the decimal representation of 1/90, L(2) is the
decimal representation of 1/900, etc.

Looking at the diagonal, we get r = 0.111.... Change
each digit by our rule: replace 0 and 9 by 1, and replace
anything else by 1. The result is the diagonal number
d = 0.000..., which is definitely not on the list.

Try it yourself: make up any pattern you want for an infinite
list of reals. Compute the diagonal as I have described it.
You will find that the result is a number that is not on the
list.

Do you agree that for any fixed infinite list L, it is possible to
construct a real number d that is not on the list L? If
not, why not? Can you give a counterexample?

--
Daryl McCullough
Ithaca, NY

.

Relevant Pages

  • Re: countability of rationals
    ... > digit of q1, the second decimal digit different from the second decimal ... According to the proof, enumerate *all* the reals in the interval (0,1] ... Now he makes the argument that x is not in the above enumeration. ... (because the enumeration is infinite) ...
    (sci.math)
  • Re: Review of Mueckenheims book.
    ... If infinite, the limits of the ... that the reals are not countable. ... He starts with the sequence of rationals: ... in the building of the diagonal *each* digit has to be changed. ...
    (sci.math)
  • Re: Courage?
    ... > This same approach can be done with infinite sets. ... The reals are NOT countable however. ... By then writing the number whose first digit ... Have you heard of leading zeros? ...
    (sci.math)
  • Re: induction vs Cantor
    ... >>be the same as the 1st digit of x. ... I didn't create a "Cantor number". ... Let A and B be countably infinite ordered sets of real ... Each x in B is the "Cantor number" of some list of reals, ...
    (sci.logic)
  • Re: Is continuum completely filled up?
    ... Does not this property include the fact that reals have cardinality of power ... In any representation, these operations /must/ be understood as part ... involve /writing out/ the sum, digit by digit, of the decimal ... Rationals are build from naturals. ...
    (sci.math)
Loading