### 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:

• 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).