[Date Prev][Date Next][Thread Prev][Thread Next] [Search] [Date Index] [Thread Index]

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



On 28 May 2001, at 20:07, Daniel S. Wilkerson wrote:

> Bernie Cosell wrote:
> 
> > > .. 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 infite length strings) consisting of digits only,
> > > and each such a string is matched by /^\d+$/, it's not true that a set
> > > matched by a regex is of countable size.
> >
> > First off, there is *NO* 1-1 such mapping, but that's a math subtlety
> > that doesn't really matter, obvious to you or not.
> 
> I think that perhaps there might be after all.

You're right, of course.  I was referring to the 'obvious' part and I've 
been trying to remember the associated theorem --- there *is* a theorem 
that has something to do with digit-based mappings to the reals and that 
you *cannot* get away from having coutably-infinite multiple mappings.

Ah, I remember it now, I think: I think the theorem was something along 
the lines of that there is *no* numeric representation of the reals that 
doesn't have countably infinite many->one mappings.  Basically, there's 
no way doing 'normal' things with the strings that avoides the infinite-
9s. problem.

But you didn't need to work that hard actually.  It is actually very easy 
to show that the cardinality of "all strings of digits" is the same as 
the reals.

1) reals are a subset of strings.  Easy: use ANY representation of the 
particular real.  Some stings will NOT have reals map to them, but we 
only needed to show 'subset'.

2) strings are a subset of the reals.  Consider the strings of digits as 
*base*11* real numbers.  In one stroke the multiple-mapping problem goes 
away [it does leave a lot of "holes", but again: we only care about 
subset-ness].

Since they're each subsets of the other, they have the same cardinality.

That's easy.  And it isn't hard to understand that there *ought* to be a 
1-1 mapping between the sets [indeed, for some forms of set theory, 
that's the *definition* of two sets having the same cardinality!].

But I claim that there is no *obvious* mapping [indeed, I don't even 
think you can _describe_ a means of constructing a 1-1 map -- you can 
subtract the '9's to get the 'simple' 1-1 map, but it sure doesn't seem 
eash to me to "make room" for the "niners"  to map them back in and still 
stay 1-1]

  /Bernie\
-- 
Bernie Cosell                     Fantasy Farm Fibers
mailto:bernie@fantasyfarm.com     Pearisburg, VA
    -->  Too many people, too few sheep  <--          

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