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.