Re: [FWP] japhy had a silly idea...

[Jasvir Nagra <jas@cs.auckland.ac.nz>]

"Abigail" <abigail@foad.org> writes:

> On Tue, May 29, 2001 at 11:41:56AM +1200, Jasvir Nagra wrote:
> > Ronald J Kimball <rjk@linguist.thayer.dartmouth.edu> writes:
> > 
> > > On Tue, May 29, 2001 at 12:51:26AM +0200, Marc Lehmann wrote:
> > > > On Mon, May 28, 2001 at 10:57:17PM +0200, Abigail <abigail@foad.org> wrote:
> > > > > can match infinite strings as well. And since there is an obvious,
> > > > > 1-to-1 mapping between the set of reals between 0 and 1 and the set of
> > > > > strings (including the infinite length strings) consisting of digits onl
>                                --------
>                                   ^
>                                  /|\
> > > >                             |
> > > > actually, there isn't on obv|ous mapping (which is the problem with this
> > > > argument). the set of all st|ings is countable, the set of reals isn't.
> > > > there are a lot of examples |ut there that prove that the integers are
> > > > uncountable by extnding them|with zeroes, for example.
> > > >                             |
> > >                               |
> > > I don't follow you.  Integers |re obviously countable:
> > >                               |
> > > 0, 1, -1, 2, -2, 3, -3, 4, -4,|...
> > >                               |
> > > You say that the set of all st|ings is countable....  Then, as Abigail
> > > said, the set of reals between|0 and 1 must be countable, because each real
> > > can be represented as a string| specifically a string of digits.
> >                                 |
> > Not quite.  The set of all reals|can't be represented as *finite*
>                                   |                         ------
>                                   |                           |
>                                   +---------------------------+
> > strings.  In particular, fr'instance, you can't represent pi as a
> > string of digits.
> 
> 
> Please prove this claim.
> 
> 
> Abigail

Okay. I said that the set of reals, [0,1) cannot be represented by a
set of strings of finite length.  This means, I am saying there is no
1-1 mapping from [0,1) to the set of *finite* strings.

Suppose there was such a mapping, f - that is, suppose that the reals
[0,1) is countable.  This means we can enumerate them as { r1, r2,...,
rn }.  Now construct a real number, x, by considering the nth digit of
the decimal expansion of rn. This real number is between 0 and 1.

If the nth digit of rn is 0, let the nth in digit the decimal
expansion of x be 1 Otherwise, let the nth in digit the decimal
expansion of x be 0

So x is clearly in [0,1), but it differs in the nth decimal place
from rn, so x is not in our enumeration of the real numbers, which
thus is not an enumeration. 

This procedure can be used on any supposed enumeration of real
numbers, there exists no enumeration of the real numbers, and thus
they are not countable and therefore cannot be mapable 1-1 onto the
set of finite strings.

This is Cantors Diagonal Argument.  Did I miss something?

Jas

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe