Re: limitation to the halting proof

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 05/31/04 

Date: Mon, 31 May 2004 02:39:16 GMT

In sci.logic, |-|erc
<gotcha@beauty.com>
 wrote
on Sun, 30 May 2004 23:07:13 GMT
<BOtuc.19004$L.6255@news-server.bigpond.net.au>:
> "Barb Knox" <see@sig.below> wrote in message > >>
>> >> So where's the diagonal number in the list? Be specific.
>> >> (Bear in mind that the diagonal number was constructed
>> >> *from* the numbers in the list, as opposed to any
>> >> generating function coupling them [Cantor does not require
>> >> a generating function in his proof, merely an assumed list
>> >> of reals], and need not be computable in the UTM sense.)
>> >>
>> >
>> >The diagonal number itself appears only in the infinite list itself, not as a
>> >member.
>>
>> So you DO concede that the diagonal number does not appear as a member of the
>> list? If so, that's progress.
>
> only when you can tell me the number, not a self referencing specification.

The number is constructed from the specification. How is that
"self-referencing"? No TM can implement the diagonal number.

>
>
>>
>> >Tell me what digit is not in the list and I'll show you a result
>> >that contains the diagonal number perfectly up to and including
>> >that digit.
>>
>> Big deal -- it's only the ENTIRE infinitely-long diagonal number
>> that does not appear as a member of the list; it matters not a
>> bit that some or all of its finite prefixes do appear as members.
>
> lets examine the connundrum you are forced to endure. all the

FINITE.

> prefixes of the number are on the list, of unlimited length, yet
> the entire string does not appear. how do you sleep at night?

I suspect Barb sleeps very well, although I am not at all sure
she'll let me verify that. :-) (Me, I snore.)

>
> surely Cantor meant... it appears that a sequence of digits is
> not present. if you have proven there is a missing sequence of
> digits then you can specify some finite subsequence of the
> missing sequence that is also not present. Can you do that?

An interesting but irrelevant point. The set

0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,
0.01, 0.02, ..., 0.09, 0.11, 0.12, ..., 0.19, 0.21, 0.22, ..., 0.29,
..., 0.91, 0.92, ..., 0.99,
0.001, 0.002, ..., 0.009, 0.011, 0.012, ..., 0.019, ..., 0.099,
0.101, 0.102, ..., 0.109, ..., 0.999,
0.0001, ... 0.9999,
0.00001, ..., 0.99999,
...

contains all base-10 finite prefixes, yet does not cover the real set,
although it's dense.

(I'm not sure what this set is called. It's vaguely Cantorian,
admittedly.)

>
>>
>> >Stalemate.
>>
>> No (changing sports): own goal.
>
> every list I declare you find a new number, every number you declare
> I'll find it on that same list. you've just wrongly assumed your
> own benefit of the doubt.

I for one don't see how.

>
>
>
>>
>> >By induction the number is contained in the list for infinite digits.
>>
>> So you say, according to the following flawed reasoning:
>>
>> >We've been through this 100 times.
>>
>> And going through it a few more times won't make it any more valid.
>>
>> >0.1 is in the list. 0.12 is in the list. 0.123 is
>> >in the list where diag is 0.123xyz.... for all digits in diag,
>> >that number is in the list.
>> >As the list approaches infinity the point on the number line is enscribed,
>>
>> Induction tells us that for every NATURAL NUMBER k, the k-digit prefix can
>> appear as a member of the list. You then go on to conclude that for "K =
>> infinity" this proves that the entire INFINITE sequence of digits appears as a
>> member of the list.
>
> not as a member.
>
> This sequence of points in its infinite form will mark the point 1/3 [T / F]?

False. 1/3 is the supremum of the sequence, which does not contain 1/3.

>
> 0.3
> 0.33
> 0.333
> 0.3333
> ...
>
>
>>
>> Is it possible that you might somehow someday understand that "infinity" is
>> NOT a natural number? If you say it is, then maybe you can tell us which
>> natural number is the one immediately before "infinity" (since we know that
>> every non-zero natural number has a unique prececessor).
>
> is it possible you might somehow understand that numbers are symbolic
> represenatations of points and their specification of those points is
> merely that, the string of digits is a symbol for the number. to
> refine the region on the number line there are initially 10 options.
> that means whatever digit is used there are 9 other candidates.
> This is all part and parcel of specifiying a number using digit strings.
> Given the fact that there are 9 contender digits for anti-diag,
> it doesn't matter, real numbers are a set and there are infinitely
> many that start with the other 9 contender digits. Diag loses at
> position one, its not possible to specify a 1 digit number that is
> not listable. Digit 2 is no different, there are well over 100 reals
> we can list, so 0.00 to 0.99 are covered, Diag loses again. Sets are
> specified on the foundation that their distinguishing members are
> disjoint. All the digits are effectively identical in other regards.
> If you specify a number 0.7xxxxxx you are *also* declaring 0.0, 0.1,
> 0.2, 0.3, 0.4, 0.5, 0.6, 0.8, 0.9 as the vector space surrounding that
> path. It doesn't matter if diag is defined to always select from that
> vector space, that's what the other members of the SET are designed for.
> There is no digit in diag that forms a contradiction, even if I present
> you with some finite list, the only contradiction you could try to
> predict is off the list. If I give you a 1000000 by 1000000 list of
> digits, you can only suggest the contradiction lies at digit 1000001
> or higher. Numbers are options not sentences.
>

An interesting point, if one looks it that way. Basically, a digit
sequence

0.abcdef

could declare an *interval*, if I'm reading you correctly. (This interval
can be represented as [(abcdef0 - 5) / 10^7, (abcdef0 + 5) / 10^7),
with the usual rounding). Therefore, the set

0.3
0.33
0.333

covers 1/3 -- which is within the interval [0.25, 0.35), after all --
with sufficiently greater accuracy as one goes down the list.

This is a slightly unusual usage.

>
>
>>
>> But of course you can't answer that, because there is no such natural number,
>> because "infinity" is not a natural number. Your induction is perfectly
>> valid, but it only applies to natural numbers (which are each finite).
>
> This is *your* induction.
>
> x
> this list is finite
>
> x
> xx
> this list is finite
>
> x
> xx
> xxx
> this list is finite
>
> therefore,
>
> x
> xx
> xxx
> ...
>
> this list is finite
>
>

Induction doesn't quite work that way. The usual formulation is:

    P(1)

    P(N) => P(N+1) for arbitrary N.

    Therefore P(N) for all N.

where P is a predicate depending on its argument.

For example, I posit that the square of all integers is nonnegative,
and I'll do so using induction in a slightly roundabout fashion.
(Direct methods are more comprehensible in this case, but bear
with me here. :-) )

The predicate in this case is:

    P(n) = "n^2 and (-n)^2 are both nonnegative".

Obviously P(0).

If I take P(n) and I know n^2 and (-n)^2 are both
nonnegative, then P(n+1) is the statement "(n+1)^2 and
(-n-1)^2 are both nonnegative". Since (n+1)^2 = n^2 +
2*n + 1 and (-n-1)^2 = (-n)^2 - 2*(-n) + (-1)^2 = (-n)^2
+ 2*n + 1, and 2*n is nonnegative for all nonnegative n
(if you want I can prove *that* by induction as well),
P(n) => P(n+1); therefore P(n) for all integers n.

Now it turns out that one can prove that all finite digit lists
are finite (which is admittedly not all that useful a result)
using this method.

P(1)

All lists of length 1 are finite. (There are 10 of these.)

P(n)

All lists of length n are finite. One can tack on an arbitrary
digit onto the end of these lists, resulting in ten times as
many lists of length n+1, but they're still finite; ergo,

P(n) => P(n+1)

and therefore all finite lists are finite.

Whoopee.

However, the postulated list is *infinite*. Weird things happen
with infinite lists. For example, there are as many integers
as there are even numbers.

1 <-> 2
2 <-> 4
3 <-> 6
...
0 <-> 0
-1 <-> -2
-2 <-> -4
...

This is a bijective mapping, therefore card(J) = card(2J).

1 <-> 0
2 <-> 1
3 <-> -1
4 <-> 2
5 <-> -2
...

This is a bijective mapping, therefore card(N) = card(J).

1 <-> 1/1
2 <-> 2/1
3 <-> 1/2
4 <-> 3/1
  [dup] 2/2
5 <-> 1/3
6 <-> 4/1
7 <-> 3/2
8 <-> 2/3
9 <-> 1/4
...

This is also a bijective mapping; therefore card(Q) = card(N).

>
>
>>
>> Now, you might want to read up on "transfinite induction", so you can spout
>> mathematically-ignorant delusional rubbish in a whole new subject area...
>
> all digit prefixes are on the list, therefore all_digits_are_on_the_list,
> but the number is not on the list, now thats delusional rubbish.

The aforementioned countable set of prefixes does not cover the reals.
It is dense, of course; for any real r in (0,1) and epsilon e>0 I can
find an infinite number of elements within the interval (r-e, r+e).

But r is not part of that set.

>
> Herc
> 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages

  • Re: In a Bad Mood
    ... >> the same digit can occur). ... > There is no unique sequence of digits to anti_diag. ... does the infinite list map to the entire number line? ... but the LISTS INFINITE FORM is required to ...
    (sci.logic)
  • Re: Radix Sorting
    ... I'm trying to do the most basic of radix sorting and it was hard for me to understand that code. ... Read the first number from the list, and the appropriate digit from that number, and place the digit into the according bin. ... My program is one main recursive loop, ... All the recombine function does is take a two dimensional array of size 10 by whatever (linked lists) and append all the lists together into one. ...
    (comp.lang.c)
  • Re: In a Bad Mood
    ... > the same digit can occur). ... but the entire infinite-length diagonal sequence can not be a member ... You treat countable infinity like its *big*, its not its infinite, therefore every ... but the LISTS INFINITE FORM is required to map to every number. ...
    (sci.logic)
  • Re: order of the arguments for functions
    ... two lists that are equal. ... there perhaps should be some bias toward trying to have short ... (contains sequence item) ... Either of these would bias towards MEMBER, ...
    (comp.lang.lisp)
  • Re: abundance of irrationals!)
    ... > Ask for the k-th digit of any real number of. ... >> It is the cardinality of N x N. ... >> that more than 2 lists are possible. ... Therefore countability is an ill-defined ...
    (sci.math)