Weekly commentary: MAT335 - Chaos, Fractals and Dynamics

Top , Next (Fractals)

7 January - Countable and Uncountable Sets

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:

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

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)