Top , Next (Fractals)

The *cardinality* of a set is the number of elements in the set.
We showed in class that the cardinality of the set of integers **Z**,
which we'll denote by card(**Z**), and the cardinality of the rational
numbers **Q**, card(**Q**), are the same. We did this by demonstrating
a one-to-one correspondence between the elements in **Z** and the
elements of the set of natural numbers **N**, and a one-to-one
correspondence between **Q** and **N**. The cardinality of **N**
we call infinity (or countable infinity). Thus, both **Z** and **Q**
have the same 'size' in this respect; they are both (countably) infinite.
It may happen that a set can be put in a one-to-one correspondence with
only a *finite* subset of **N**. In this case we say that the set
is finite. A set that is either finite or countably infinite is called
*countable* (the elements of the set 'can be counted').

There are sets, though, that can not be put in a one-to-one correspondence
with **N**. These sets are called *uncountable*; they contain
too many elements to be counted with merely **N**. There is a way to
count these sets, which we won't get into here, so that you can at least
define the cardinality of an uncountable set. This cardinality is a
'number' that is bigger than (countable) infinity; it is 'another' infinity.

We showed in class that the interval
[0,1] is uncountable. We did this by showing that given *any* infinite
list of numbers from [0,1] we can always find a number from [0,1] that
is not in that list (Cantor's 'diagonal' argument). Therefore, there is no
countably infinite list of numbers from [0,1] that contains *all*
the numbers from [0,1]. The cardinality of [0,1] is called *the
power of the continuum* (the continuum being the real numbers **R**).
The 'continuum
hypothesis' in mathematics states that the power of the continuum is the
'next' infinity after the countable infinity (that is, card(**R**) is
the 'next' infinity after card(**N**) ).
The sets [0,1] and **R**
have the same cardinality because they can be put into a one-to-one
correspondence.
Can you think of a one-to-one correspondence
between [0,1] and **R**? Start with the fact that you can match all the
numbers in (0,1) with all the numbers in (1, infinity) in a one-to-one
fashion via the function f(x) = 1/x.

Note that infinity + 1 = infinity, i.e., card(**N** U {0}) =
card(**N**).
(Right? If you add one more element to the set **N**, like {0},
you can easily find a one-to-one correspondence between this set and
**N**.) Here, U denotes union.
In fact, infinity + infinity = infinity (eg. **Z** =
{**N**,0} U **N**; **Z** is made up of two copies of **N**
(plus {0}) and is countably infinite). It is also true that
infinity*infinity = infinity (eg. **Q** = countable union of countable
sets - that's muliplication!). So you see, you can not construct an uncountable
set by combining countable sets - the cardinality of an uncountable
set is really something much larger than countable infinity.
Since the cardinality of an uncountable set
(like the real numbers **R**) is bigger than infinity, it must be
*really* big! So don't think that the 'Cantor diagonal argument'
for the uncountablility of **R** only shows that there are 'a few more'
numbers than infinity in **R**; there are actually *many, many* more.

**R** is the union of **Q** and the irrationals (in fact, the
irrational numbers are defined as those numbers that are not rational,
so they are everything left in **R** after you remove **Q**).
If both **Q** and the irrationals were countable, then **R**
would be countable (right?). However, **R** is *not* countable
and so the irrational *must* be uncountable; there are
many, many more irrational numbers than rational numbers.

Some facts:

- Any subset of a countable set is countable (eg.
**Z**as a subset of**Q**). - An uncountable set has both countable and uncountable subsets (eg.
**R**has subsets**Q**and the irrationals). - If a set has a subset that is uncountable, then the entire set must
be uncountable. (That's what we used in class to prove that
**R**is uncountable; we proved that [0,1] is uncountable.) - A set of numbers of zero length can either be countable or uncountable,
but any countable set of numbers
*must*have length zero. - An uncountable set can have any length from zero to infinite!
For example, the Cantor set has length zero while the interval [0,1]
has length 1. These sets are both uncountable (in fact, they have the same
cardinality, which is also the cardinality of
**R**, and**R**has infinite length). So by rearranging an uncountable set of numbers you can obtain a set of any length what so ever! This is definitely not true for a countable set; no matter how you rearrange it, it will always have length zero (so**Q**has length zero; in probabilistic terms this means that if you randomly put your pencil down anywhere along the real line, with probability*zero*you will land on a rational number and with probability*one*you will land on an irrational number).

For more information about countable and uncountable sets, see books about "Analysis" (as advanced calculus is called). For example,

*Introductory Real Analysis*, by A.N. Kolmogorov and S.V. Fomin (see Ch. 1 section 2)*Foundations of Mathematical Analysis*, by R. Johnsonbaugh and W.E. Pfaffenberger (see Ch. 3).

See also section 7.3 ('The Cantor Middle-Thirds Set') of Devaney's
book *A First Course in Chaotic Dynamical Systems* which is
on reserve at the Short Term Loans section at Gerstein.

For information on the continuum hypothesis, as well as 'transfinite' numbers, see books about "Set Theory". You can read Cantor's papers on the subject in "Contributions to the Theory of Transfinite Numbers", by Georg Cantor, reprinted by Dover . See also the University of St Andrews web page on the history of mathematics, topic #11 ("The Beginnings of Set Theory"). There is also a biographical essay about Cantor (as well as many other mathematicians).

See also Morris Kline's "Mathematical Thought from Ancient to Modern Times" chapter 41 (The Foundations of the Real and Transfinite Numbers).

Top, Next (Fractals)