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.