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

["Daniel S. Wilkerson" <dsw@digital-integrity.com>]

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.  Consider this: Let R1 be {x a
real | 0 <= x < 1} (the half-open unit interval), let S be the set of all
mappings from the whole numbers {0, 1, 2, ...} to the digits {0, 1, 2, ... 9}
(all countably-infinite sequences of decimal digits.  I have switched back to
decimal from binary.) and let S' be the subset of S where no sequence has only a
finite number of non-9s (that is, we omit the sequences that end in an infinite
sequence of just 9s).

R1 and S' have a 1-1 mapping using the standard interpretation of a sequence of
digits as a decimal expansion (put a decimal point in front.)  This is theorem
136 of "An Introduction To The Theory of Numbers" by Hardy and Wright.  In
particular, this shows R1 and S' have the same cardinality, 2^aleph_0.

Notice that S \ S' (that's a set-minus), that is, the sequences where the non-9s
are finite (sequences that eventually becomes just 9s forever) is a countable
set.  To see this, notice that to represent any element of the sequence, I just
write down the digits to the point where it becomes 9's forever.  This is a
finite string.  The set of finite strings from a finite alphabet is countable.
(For any integer N, the number of strings of length N is finite.  Write them
down.  Do this for each N increasing.  You will enumerate them all.)  Thus, S
also has cardinality 2^aleph_0 (the union of two sets has the cardinality of the
larger set if the sets are infinite).

Therefore, R1 and S have the same cardinality.  By the Schroeder-Cantor-Bernstein
theorem
(http://www.math.lsa.umich.edu/~mathsch/courses/Infinity/Cardinality/Lesson4.shtml),
there is a 1-1 onto map between R1 and S.  (Perhaps I could be accused of
overkill here.  Wedging a countable set into an uncountable one in a
constructable way is not so hard.)

Daniel


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