Cardinality, Area, and Probability

Date: 09/05/2003 at 19:04:36
From: Giuseppe Urbani
Subject: Cantor, cardinality and randomness the infinite

Divide a rectangle into two parts, one with twice the area of the
other.  Pick a point randomly within the rectangle.  It would appear
that the probability of choosing a point in the larger part is twice
the probability of choosing a point in the smaller part.  

But Cantor showed that every part of an n-dimensional space has the
same cardinality.  Therefore, shouldn't the probabilities be equal?

Date: 09/05/2003 at 21:16:00
From: Doctor Tom
Subject: Re: Cantor, cardinality and randomness the infinite

Ciao Guiseppe,

Your question is VERY advanced.  To answer it in detail, you
need to study something called "measure theory" which is
usually taught in mathematics graduate school, or at the
least, in your senior year at university.

In the simplest case (say measure on a line), we would like
to be able to assign measures to subsets of the real numbers
satisfying the following conditions:

1)  The measure of the interval [a, b] is b-a.

2)  If S and T are two subsets of the line with no intersection,
then the measure of (S union T) is the sum of the measures
of S and T.  In fact, we'd like more: If you have any countable
non-intersecting subsets of the line then the measure of
the union is the sum of the measures.

3)  If S has a certain measure and you make a new set T
that is the same as S translated along the line, then T will
have the same measure.  In other words, if you slide a
subset rigidly along the line, it will continue to have the
same measure.

What would be great is if you could find a way to assign a
measure to every subset of the real numbers that satisfies
these conditions, but the first major result of measure
theory is that it is absolutely impossible to do so!  There
are so-called unmeasurable sets for which there is no
sane way to assign a measure.

But this is only if you accept the axiom of choice to be true,
so at once we see that the problem arises from a somewhat
"obvious" axiom of set theory which turns out to be not
so obvious at all!

The same sorts of problems occur in any finite number
of dimensions when we try to assign measures to n-
dimensional Euclidean spaces for exactly the same
reasons.

There are some results that can be proven.  For example,
any countable set MUST have measure zero.  But there
are LOTS and LOTS and LOTS of sets for which it is
impossible to assign a measure.

The easiest example of an unmeasurable set, unfortunately, 
is not all that easy to describe.  If you look at the 
rational numbers as a set, and then consider every possible 
set that is a translation of the rationals by a fixed 
amount, then you've divided up the reals into an uncountable 
number of disjoint subsets.  Take one member of each of 
those subsets (this requires the axiom of choice) and form 
a new set that consists of your selections.  That set will 
be unmeasurable.  (Don't worry if this is hard to understand 
-- it certainly was for me at first.)

There is a fascinating construction (that requires the axiom
of choice) called the "Banach-Tarski paradox."  Without
telling you how to do it, here's what it does:

The unit sphere in three dimensions can be divided into
5 disjoint subsets A, B, C, D and E such that if those
subsets are rotated and translated properly and recombined,
they form two complete spheres with identical size and
shape as the original, with NO POINTS OMITTED in either!

Clearly, at least some of the sets above must be
unmeasurable, and it turns out that 4 of the 5 are.  The set
A is just the center point of the sphere.

Anyway, I could go on for an entire semester in a graduate-
level course on this, but at least I hope this is enough to get
you interested and to do some reseach on your own.

Look up "Banach-Tarski", the axiom of choice, and "measure
theory" to get started.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 09/06/2003 at 07:26:14
From: Giuseppe Urbani
Subject: Cantor, cardinality and randomness the infinite

Thank you for your reply.  It was very interesting, and I have
started to do research on my own.  However, I can't find in your
reply the answer to my original question:  How do we reconcile 
the difference in probability according to area with the equality
in probability according to cardinality? 

Date: 09/06/2003 at 10:10:49
From: Doctor Tom
Subject: Re: Cantor, cardinality and randomness the infinite

Ciao Guiseppe,

I guess the point of all that I said in the previous response
is that the cardinality of the set does not determine its
measure.

There are some implications but they are not of much use:

1) In the real numbers, or in any higher-dimensional version
of the reals, like the 2-dimensional plane or 3-D space (and in
higher dimensions as well), every subset that is countable
has measure zero.

This is easy to show:  Enumerate the points in the countable
subset as p0, p1, p2, ...  I can cover this subset with a larger set
as follows:  Given any real number E, choose the interval of
size E/2 centered on p0.  Then choose the interval of length
E/4 centered over p1.  Then the one of length E/8 centered over
p2.  Then of length E/16 centered at p3, et cetera.  The measure
of the union of all those sets is less than or equal to:

E/2 + E/4 + E/8 + E/16 + ... = E

So no matter how small a number E you choose, you can show
that the measure of your countable set is less than or equal to
that.  Since E is arbitrary, the measure of the countable set is
less than any positive number and the only such number is
zero, so the measure of ANY countable set is zero.

2) Every set of positive measure is not countable (this comes
directly from 1), above.  In fact, even if the continuum hypothesis
(another interesting axiom from set theory that states that
the first uncountable cardinal is the cardinality of the continuum)
is not true, it is still true that every set of positive measure has
the cardinality of the continuum (I won't prove that for you).

So EVERY set with positive measure has EXACTLY the same
cardinality; namely, the cardinality of the continuum.   And all
the subsets of the reals that are NOT measurable also have
exactly the same cardinality -- the cardinality of the continuum.

So this basically means that if you know the cardinality of your
set is less than the cardinality of the continuum, it has measure
zero, but if your set has the cardinality of the continuum, it can
have ANY measure, from zero to infinity.  In other words,
the fact that a set has cardinality equal to the continuum gives
no information about its measure -- cardinality and measure
are almost unrelated other than the fact that the cardinality
has to be at least that of the continuum to get a positive
measure.

There are, by the way, sets with the cardinality of the continuum
that have measure zero.  The so-called "Cantor Dust" is such
a set.  It is obtained by beginning with the interval [0, 1] and
removing middle thirds:  first remove (1/3, 2/3) leaving the set
that''s the union of [0, 1/3] and [2/3, 1].  Then remove the
middle thirds of those -- the intervals (1/9, 2/9) and (7/9, 8/9),
leaving four intervals.  Then remove their middle intervals,
et cetera.  If you take the intersection of ALL those sets, it's
clear that each one has measure 2/3 of the previous one, so the
intersection has to be smaller than all of them, so its measure
must be zero.  But you can also show that there are an
uncountable number of points left.  This is done by looking
at the base-three expansion of the numbers that remain, and
showing that any number having a ternary expansion
consisting of only 0s and 2s remains.  But there's a 1-1
mapping of the ternary numbers with only 0s and 2s to the
binary numbers having only 0s and 1s (just map the 2s to
1s) and those are ALL the binary numbers which clearly
have the cardinality of the continuum.

I hope this helps.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 09/06/2003 at 11:41:28
From: Giuseppe Urbani
Subject: Thank you (Cantor, cardinality and randomness the infinite)

Thanks for helping me see the distinction between cardinality
and measure.  I think I was instinctively confusing cardinality
with 'amount', which was the cause of my confusion.