Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Lists
Replies: 7   Last Post: Jan 24, 2013 5:06 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Mike Terry

Posts: 660
Registered: 12/6/04
Re: Lists
Posted: Jan 24, 2013 1:04 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

"Don Deluise" <thedon@tomato.red> wrote in message
news:1xh71bla4hvjd$.wf5fd9paee0w$.dlg@40tude.net...
> This list enumerates all 2 bit binary sequences:
>
> 00
> 01
> 10
> 11
>
> This one enumerates all 3 bit binary sequences:
>
> 000
> 001
> 010
> 011
> 100
> 101
> 110
> 111
>
> Using diagonalization on the first to produce a sequence that is not in

the
> list fails. It produces '10' which *is* in the list.
>
> Using diagonalization on the second list also fails. It produces '111'
> which *is* in the list.
>
> Clearly, increasing the length of the sequences does not produce lists in
> which diagonalization will achieve its purpose, i.e. to produce binary
> sequences of a given length which are not already in the list.


..at least, not while we are restricted to finite binary strings lengths,
and there is no limit placed on the allowed list length.

We can have a sort of equivalent theorem for finite binary strings of length
n:

Theorem: If (s_1, s_2, ...., s_n) is a sequence of n-bit binary
sequences, there will always be an n-bit binary sequence
not present in the sequence.
Proof: usual diagonalisation argument

>
> So if we were to compile an enumeration of infinite length binary
> sequences, how do we know that diagonalization produces a sequence not
> already in the list?


The difference is that with infinite length binary sequences, there is an
obvious 1-1 correspondence that can be exploited between "entry number in
the list" and "binary digit position". As you've observed above, the proof
does not work without some such correspondence.

In Cantor's proof, the list length is deliberately restricted to being
"countable" - in fact this is implicit in the definition of the term "list"
used in the proof, a list being a map from N to the target set in question.
If Cantor had allowed arbitrarily large "lists" (i.e. uncountable "lists")
the proof would fail in the same way as your finite examples.

So, Cantor restricts consideration to "countable lists" (generally just
called lists!) and the proof works. Similarly if we suitably restrict the
list lengths in the finite case as I did above, the proof also works in the
same way. (No surprise really I suppose...)

Regards,
Mike.

>
> P.S. This is not an attempt to prove that the Real numbers are either
> countable or not. It is simply to raise a question about one of the proofs
> that they are not







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.