Paul Cohen Dead at 72

Paul Cohen, one of the giants of twentieth century mathematics, has died of lung disease at 72.

Cohen's major claim to fame was his resolution of the Continuum Hypothesis. Here are the basic ideas:

Suppose you have two finite sets and you want to show they contain the same number of elements. You might try to do that by counting the number of elements in each set. But another method would be to pair up elements of one set with elements of the other. If the sets run out at the same time, then you know they have the same number of elements.

As an example, suppose you have a group of students in a classroom. To determine whether there are enough desks, you could simply ask everyone to sit down. If everyone sits down and there are still empty desks, then you know there are more desks than students. If all the desks are filled and there are still students standing, then you know there are more students than desks.

The nice thing about viewing things this way is that it applies just as well to infinite sets. Given two inifinite sets, we can ask whether their elements can be placed into “one-to-one” correspondence. In other words, can they be paired up in such a way that each element of one set gets paired with exactly one element of the other set? In this way we can compare the sizes of inifinite sets.

As an example, consider the set of positive integers on the one hand and the set of positive even integers on the other. We can pair them up as follows: (1,2), (2,4), (3,6), (4,8),... The first number in each pair is a positive integer. The second number in each pair is a positive even integer. Every positive integer appears exactly once as the first number in a pair, and every positive even integer appears exactly once as the second number in a pair. So it is meaningful to say that the set of positive integers and the set of positive even integers have the same size.

This seems bizarre. After all, the even integers are a proper subset of the set of all integers. Yet they have the same size. Well, that's infinity for you. Actually, you can define an infinite set to be one that can be placed into one-to-one correspondence with a proper subset of itself. It's not possible to do that for finite sets.

You can prove in this way that the rational numbers (that is, fractions with integer numerators and integer denominators) also have the same size as the integers. The real numbers, however, do not. The real numbers are strictly larger than the positive integers, even though both are infinite sets. In any pairing with the positive integers on one side and the real numbers on the other, you will “run out” of integers before you run out of real numbers.

The proof of this is both ingenious and comprehensible, though I won't bother to repeat it here. This Wikipedia entry describes the basic ideas.

So the real numbers are strictly larger than the positive integers. This raises the question of whether there are any infinite sets having a size intermediate between the positive integers on the one hand, and the real numbers on the other. That is, are there any infinite sets that are strictly larger than the integers, but strictly smaller than the real numbers.

The Continuum Hypothesis (CH) asserts that there is no such set. (“Continuum” is a fancy word for the real numbers in this context). Though I have expressed things in terms of integers and real numbers, we should point out that CH is ultimately a problem in set theory. In other words, it can be expressed entirely in terms of sets, without any reference at all to the integers or real numbers specifically. I did not present it that way simply because I am assuming that most people reading this are familiar with integers and real numbers, but are not necessarily familiar with the subject of infinite cardinals.

Ever since Cantor first formulated these ideas in the late nineteenth century, people have tried to prove CH on the basis of the standard axioms of set theory. These axioms are referred to as ZFC. The Z and the F refer to Zermelo and Fraenkel, the mathematicians who first formulated these axioms. The axioms were born from the calamity that befell more simplistic notions of the subject when Bertrand Russell and others pointed out various contradictions and paradoxes in “naive” set theory. The C in ZFC refers to the axciom of choice. This is a somewhat controversial axiom that really deserves a post of its own someday.

So that's the question. Based on ZFC, does it follow that there are no infinite sets with size intermediate between that of the positive integers and that of the real numbers.

The first major progress on this question came in 1940, when Godel showed that CH is consistent with ZFC. This means that it is impossible to prove that CH is false based on ZFC. Sadly, this is different from showing that CH is true based on ZFC. And this is where things stood until 1963. That's where Paul Cohen enters the picture.

Cohen resolved the question by establishing that the negation of CH is also consistent with ZFC. More than that, he did this by an entirely original method, now known as the “method of forcing,” that has found applications to countless other problems. This is the major basis for his fame. He not only resolved an important open problem, but did so via methods that have proven to have far wider aplpicability than what he originally devised.

The results of Godel and Cohen established that CH is independent of ZFC. Its truth or falsity can not be resolved one way or the other based on those axioms. Some people regard this as a defect in ZFC, and much time has been spent looking for other axiom systems that include the best aspects of ZFC, but also resolve CH. Such axiom systems exist, but all of them involve axioms that seem counter intuitive and unnatural. In other words, you would do better simply to take CH as an axiom and be done with it.

I'd happily describe for you what forcing is all about, but I'm afraid I know very little about it. A logician friend of mine tried to explain it to me once in graduate school, and then I felt like I understood it for a few hours. But it didn't stick.

Anyway, the New York Times editorial has some further tidbits. Go have a look.