Re: induction vs Cantor

From: Chairman of the David Hilbert Appreciation Society (mathgeekxxiiii_at_hotmail.com)
Date: 11/29/04 

Date: Sun, 28 Nov 2004 21:33:49 -0500

Poker Joker wrote:
> "Chairman of the David Hilbert Appreciation Society"
> <mathgeekxxiiii@hotmail.com> wrote in message
> news:vbydnR11EIpSbTTcRVn-rA@giganews.com...
>
>> "Let L_1 be a list of reals that implies a mapping F_1
>> between the naturals and reals.
>>
>> Let D_n be a Cantor anti-diagonal number that can be
>> formed using the mapping F_n
>>
>> Let L_n+1 be a list of reals by inserting D_n into L_n
>> at row 2n [*] and shifting down all the previous rows at 2n
>> and above. This process is clearly an inductive process
>> that creates a new mapping for each natural number.
>> (L_n+1 could also be formed by prepending D_n to
>> L_n.)"
>>
>>
>>I'm assuming that the rows of each L_n will start from 1.
>>It makes no difference to the result if we start from 0,
>>but is more convenient with 1 IMO.
>>
>>First we agree that:
>>
>>(1) L_1 is a list, an injection.
>>
>>(2) Any real number in row 2n-1 of L_n is in the
>> same row (2n-1) on any L_m with m >= n. This follows
>> from [*] in his description.
>>
>>(3) It follows from (2) that if x is a real number
>> in row 2n-1 of L_m with m >= n that the (2n-1)th
>> digit of any D_m will not be the same as the
>> (2n-1)th digit of x. Otherwise D_n would not
>> be an "anti-diagonal" number.
>>
>>Once we agree that items 1-3 characterize the method
>>we do as follows:
>>
>>(4) Denote the real number in row 1 of L_1 as x.
>>
>>Since L_1 is a list there must be some n for which
>>the first 2n digits of x aren't all the same as the
>>first 2n digits of any other y in L_1. Otherwise we
>>have x = y, contradicting (1).
>>
>>note that x has a unique initial segment of at least
>>2n digits.
>>
>>Denote the first 2n digits of x, by S and add to S a
>>(2n+1)th digit that is not the same as x's (2n+1)th
>>digit. This guarantees that the inital segment of S
>>doesn't appear on L_1.
>>
>>Construct a number T in the following way:
>>
>>Take D_n, the "anti-diagonal" number of L_n, and throw away
>>its first 2n+1 digits and replace them with S. Call the
>>resulting number T.
>>
>>T can't be on L_1, since no number on L_1 has the same
>>inital segment.
>>
>>By (4), x is in row 1 of L_1. And by (3) with n = 1,
>>we have
>>
>>x is a real number in row 1 of L_1 and m >= 1
>>implies that the 1st digit of any D_m will not
>>be the same as the 1st digit of x.
>>
>>Since the first digit of x is the same as the
>>first digit of T we conclude that no D_m with
>>m >= 1 shares the same 1st digit as T.
>>
>>Thus T is not any D_m, nor is it on L_1, thus
>>it isn't on any L_n.
>>
>>I may have made minor mistakes, but I'm pretty sure
>>the basic argument works.
>
>
> Note that you've described one of the countably many ways
> to cunstruct a Cantor number.

I didn't create a "Cantor number". The number I show, that isn't
on any L_n has the exact same first 2n digits as those of
the number on the first row of L_1 -- clearly this isn't
constructed by the same method that Cantor uses otherwise
its first digit would be different from the first digit
of the number on the first row of L_1.

> So your T is a D_n becaues

T can't be any D_n. The first digit of T is the same first
digit of the number in the first row of L_1. Since that number
is in the first row on L_1 and every subsequent list L_2, L_3, ...
none of the D_n share the same first digit with it -- otherwise
D_n wouldn't be an "anti-diagonal" number, as you specified.

> we assume that at any stage, the Cantor method can be any
> one of a countably infinite set of methods for generating the
> D_n. You've described one.

I used the most reasonable interpretation of the phrase:
"Cantor['s] anti-diagonal number", which in sci.math is
used to describe a number constructed based on the diagonal
string of digits of a list.

> So your T has been taken into
> account.

Then which L_n does T occur on?

> Cantor methods aren't required to create a new
> real in which the first digit is different from the first digit of
> the first real.

You were using Cantor's method, you said:

"Let D_n be a Cantor anti-diagonal number that..." -PJ

I suspect this is why you're no longer (as of this post)
calling it an "anti-DIAGONAL".

Even if you use a method that is different yet produces
a similar result to Cantor's method it makes no difference.
Once you give enough details of how D_n is constructed
the same thing can be done.

OTOH if you completely obscure how D_n is created then
of course you will experience the satisfaction of never
seeing a counter example created in the same way (based
on knowledge of how L_n is defined), but there are still
other ways...

Aside from the matter of trying to convincing you that
a number exists that isn't on any L_n, you seem to want
to convince me that there is something special about the
collection of all L_n, which so far I haven't seen.
Perhaps this example will help you see why I regard
the collection of all L_n as uninteresting:

(1) Let A and B be countably infinite ordered sets of real
     numbers such that A cap B = emptyset. Let C = A cup B.

It seems to me that C has the same distinguishing
features as the union of all L_n.

Each x in B is the "Cantor number" (*) of some list of reals,
each x in B is unique, and there are countably many x in B.
C is the collection of an initial list of reals A (like L_0)
with all of the diagonal numbers in B added.

(*) "Cantor numbers just have to be created so that we can be
assured that they are unique with respect to the list." -PJ

In other words, C is no different from the collection of all L_n.
By assuming that the collection of all L_n is complete, you may
as well assume that C is complete also, which is much simpler.

It's easy to show examples of A B and C which satisfy (1)
and which also fail to contain every real.

So what is so special about the collection of all L_n?

[...] 

-- 
Replace Roman numerals with digits to reply by email

Relevant Pages

  • 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: 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)
  • 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.math)
  • Re: Epistemology 201: The Science of Science
    ... > about seeing infinities as the same size, ... > the reals onto the integers like one does with the rationals? ... H'm should I leave for you to work out, or shall I show you how Cantor ... you've left out at least one, as follows: Take the first digit after the ...
    (sci.math)
Loading