Cantor, Sets and Cardinality II

In an earlier post I discussed the work of Cantor to use cardinality to distinguish between different infinite sets. Recall that Cantor defined two sets A and B to have the same cardinality if there is a one-to-one onto function between them. We showed that the natural numbers, even numbers all have the same cardinality. More surprisingly, the natural numbers have the same cardinality as the rational. At this point, one might think that all infinite sets have the same cardinality. Cantor found that the set of real numbers has cardinality greater than the set of natural numbers. We will prove this by proving the slightly stronger result that the set of real numbers between zero and one have cardinality greater than the cardinality set of positive integers. That is I will show |A| > |N| where A is the set of positive real numbers that are less than 1. We shall use an argument due to Cantor called the diagonalization argument. This argument is due to Cantor but is not his original line of argument. We will sketch this proof in base 10 and then discuss issues that come up when trying to modify the proof for base 2.



We will assume there is a one-to-one onto function f from |N| to A as n ranges from 1 to infinity. We denote by fk(n) the kth decimal digit of f(n). We then want to look at fn(n). This forms the diagonal of our list of numbers, hence the name of this argument. To make this more concrete let us assume that we have f(1)=.618… f(2)=.141… and f(3)=.718… so we have a list that looks like:
1) .618…
2) .141…
3) .718…


The bolded digits are those that are fn(n) for some n. Now, we make a new number D. D is defined as having a 4 in the kth place of its decimal expansion past the decimal point except when fk(k)=4 in which case there is a 5. Thus in our earlier example list D would start with .454… Now, we claim that D cannot be anywhere on our list since D disagrees with the nth number on our list in the nth decimal place (D has a 4 there precisely when f(n) does not, has a 5 when f(n) has a 4). Thus, our list is not complete and we have reached a contradiction. A few things to note: First, this result was completely constructive. It allows us given any function f from N to A to construct an element of A that is not in the range of f. Second, nothing was special about 4 and 5, although choosing 9 instead of 4 might have been problematic because if D ended in all 9s then we would have a string that should not be on our list anyways (by our convention for terminating decimals).


Now I’d like to address a question that Etienne asked in the comment’s thread of the previous post on this topic. It is easy to see in the above argument that we could use any base b rather than base 10 as long as b>2. However, in base 2 there’s a problem: we only have two digits available for our number D. Thus, using this argument straight off we must choose one of them to be the digit 1 which in base 2 will trigger the same rollover problem that 9 triggers in base 10. Etienne asked if there is a way to repair this hole in the proof for base 2. I assert that it is possible although it requires some careful attention to detail. A brief sketch of how to repair it follows.


Assume we are in the same situation as earlier, but we write fn(n) for base 2 rather than base 10. Further, use the same convention as earlier that in an ambiguous situation we use 00s rather than 1s. Now, unless fn(n) extends a string of all 0s our earlier proof will go through and we will be done. If fn(n) is 0 for all arbitrarily large n then we will construct a function g that is also a 1-1 onto map from N to A that has arbitrarily large n such that gn(n) is 1. We define g as follows: Start with f. Then permute f as follows: At each n that is a power of 2 starting at 1, if fn(n) is 0 then we can pick some t>n such that ft(n)=1 and fn(t)=ft(t). We do this for every successive power of 2, unless that power of 2 was already used in a swap. When we complete this process we will have a new function g such that there are arbitrarily large n such that gn(n) is 1 and we get the desired contradiction.


Cantor proved much more than what we have proved here. Cantor showed that there is an infinite hierarchy of infinite sets of successively higher cardinalities. I will discuss this and related results in a later post.

Cantor, Infinite Sets and Cardinality

Many people from a young age are fascinated by the concept of infinity. This post will examine one way that the notion of infinity can be examined rigorously and compare different sizes of infinity.

When we look at finite sets, how can we tell if they are the same size without counting? Imagine a primitive tribe that determines social status based on who owns more goats, but no one in the tribe can count past 5. If two members of the tribe both own more than 5 goats , how can the tribe compare the total number of goats the two people own? One solution is they can take out pairs of goats with one goat from each person. When one of the two goat owners runs out of goats first, that person has fewer goats. If they run out at the same time, they have the same number of goats. (This goat analogy is a good analogy, but is not, as far as I am aware, frequently used to motivate what we are doing here. I'm not sure where I saw this analogy. If someone can point out where it comes from, I'd appreciate it.)

We wish to do the same thing with infinite sets. We are like the primitive tribe and we can only count finite numbers. So we say that two sets in general are the same size if there is a function which maps elements from one to the other with no overlap and no element missed. That is, if we have two sets A and B, if they are of the same size, then there is a function f from A to B such that for any b in B there is some a in A such that f(a)=b and for any x and y in A f(x)=f(y) if and only if x=y. A mathematician would call such a function a bijection or say that it is one-to-one and onto. Thus, for example the sets {a,b,c} and {cow, potato, glockenspiel} are the same size and we could define the function f by f(a)=cow, f(b)=potato and f(c)=glockenspiel. We can generalize this notion to sets that are not necessarily finite. We call this notion "cardinality". We say that |A|=|B| if A and B share a function like that above. We similarly say that |A|<|B| if there is no such function, but there is a subset C of B such that |A|=|C|. It is not hard to see that cardinality obeys the properties one would expect a notion of equal size to obey. For example, if |A|=|B| then |B|=|A|. Similarly, if |A|=|B| and |B|=|C| then |A|=|C|.

At first glance, cardinality leads to some strange results. For example, the positive even integers are the same cardinality as the positive integers. We can see this by setting f(n)=2n. So a set can be the same cardinality as a proper subset of itself. That's not intuitive. And if one plays around a bit, one will see that any infinite subset of the natural numbers is the same cardinality as the set of natural numbers.

One might tentatively conclude that all infinite sets are the same cardinality. In the 1870s, Cantor systematically examined infinite sets and first made the notion of cardinality precise. Cantor first showed that the natural numbers have the same cardinality as the rational numbers.

This is even more counterintuitive than the earlier results since the rationals are dense on the real line, but this result fits with our tentative conclusion that all infinite sets are the same cardinality.

There are a variety of proofs of Cantor’s result. One method is to show that N, the set of natural numbers, has the same cardinality as N x N, the set of ordered pairs of natural numbers. We can use the map (m,n) -> k = 2^(m-1)(2n-1). Thus, for any positive natural number k, m determines the highest power of 2 that divides k and n determines the largest odd divisor. It is easy to see from that m and n uniquely determines k. From that result it is not hard to show that that the rationals and natural numbers have the same cardinality.

Then Cantor hit upon a surprising result. Cantor showed that there was no one-to-one and onto function from the natural numbers to the real numbers. Not all infinite sets are the same size. We shall discuss this and related results in a follow up blog entry.