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

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



"Bernie Cosell" <bernie@fantasyfarm.com> writes:

[...]

> > Be assured that Abigail has a firm grasp of such subtlety (and that
> > there is such a mapping, which I think you can figure out if you
> > haven't already).
> 
> You're right, I haven't.  Perhaps you can help me.  In particular, 
> consider the two strings:   .49....  [9's forever] and
>                             .50...   [0's forever]
> If there is a 1-1 mapping, these two strings must map to different reals. 
> Do you have an 'obvious' 1-1 mapping that actually separates those two 
> strings and maps them to different reals?

Yes.  It's not straightforward, but there's nothing particularly
complicated about it.  And it's way standard.

Start with your mapping m from reals to infinite digit strings.  Say
you always map to a string ending in consecutive 9's, given the choice
between that and a string ending in consecutive 0's.

Now your mapping is 1-1, but not onto: it doesn't map onto the strings
ending in consecutive 0's (but it maps onto every other string).  Note
that this set is countable; enumerate it (the set of "holes" in our
mapping m([0,1))) with e(n).  Let's fix the holes!

Take the numbers 1/1, 1/2, 1/3, 1/4, ...; map 1/2n to m(1/n); that's
all the images of m(1/n) covered, right?

OK, now we've got all the numbers 1/(2n-1).  Map 1/(2n-1) onto e(n).

In other words, define (WARNING!  BAD ASCII ART AHEAD!!!):

            { e(n)     if x=1/(2n-1), n=1,2,...
            {
   m'(x) =  { m(1/n)   if x=1/(2n),   n=1,2,...
            {
            { m(x)     otherwise

Then m'(x) is 1-1 and onto the set of *all* infinite digit strings.


This sort of argument is completely standard, which is probably why it
doesn't appear in more set theory textbooks.  This is sometimes a
pity.

[...]

-- 
Ariel Scolnicov        |"GCAAGAATTGAACTGTAG"            | ariels@compugen.co.il
Compugen Ltd.          |Tel: +972-2-5713025 (Jerusalem)	\ We recycle all our Hz
72 Pinhas Rosen St.    |Tel: +972-3-7658117 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555    http://3w.compugen.co.il/~ariels


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