Simple City

[This is a sequel to my post on the Axiom of Choice]

In the late 19th century, Georg Cantor’s work in set theory opened up an exciting world: that of infinite numbers.

Cantor’s basic insight was that the fundamental concept is not number per se, but the equinumeracy of sets.

Two sets are equinumerous if you can pair up the elements of one set with those of the other. This works just as well for infinite sets as for finite ones.

Cantor then built a system of special sets called cardinals. The point is that every set is equinumerous with exactly one cardinal, called its cardinality. The finite cardinals are just the natural numbers: 0,1,2,3,4,5,…. But there are infinite cardinals too (infinitely many of them in fact).

The first infinite cardinal is called and is the cardinality of the set of natural numbers. Basically is the set {0,1,2,3,…}. So a set has cardinality if its elements can be matched up one to one with the natural numbers, that is to say if you can count them. So sets of cardinality are called countable. The next cardinal is . It’s the first uncountable cardinal. Then there’s , and so on (and that’s just for starters).

Whenever you have a cardinal number, you can always talk about the next cardinal number: just the smallest cardinal which is bigger than the one you already have. But that’s not the only way of obtaining one cardinal number from another.

If you have a set X, you always can form a bigger set P(X) called the power set of X. ^[1]

If you do this to a finite set (say X has 4 elements), then the number of elements in P(X) is 2 to the power of the size of X (in this case 2⁴=16). This can be extended to infinite cardinals: if X has cardinality A, then P(X) has cardinality of 2^A.

The cardinal 2 has a special significance, and is called the continuum. We know that that several important sets (for example the set of real numbers and the set of complex numbers) have cardinality 2.

Now here’s a question: does 2=?

The statement that these two infinite numbers are equal is called the Continuum Hypothesis (CH). It would imply, for example, that any infinite collection of real numbers is equinumerous either with the set of natural numbers, or with the set of all real numbers. But if CH is false then there is a collection of real numbers which is bigger than the set of natural numbers but smaller than the set of all real numbers.

CH was the 1st of David Hilbert’s 24 mathematical questions for the 20th century, set out in 1900.

Using his pioneering technique forcing, Paul Cohen constructed two models of ZFC: one in which CH is true, and one in which it is false. This proves that CH is independent of ZFC (just as the Axiom of Choice (AC) was independent of ZF). So it is impossible to conclude from the ordinary rules of mathematics whether CH holds or not. This was the remarkable result for which Cohen won the Fields Medal.

Whereas most people now accept the Axiom of Choice as a reasonable additional assumption, the same is certainly not true of CH. In fact the celebrated set-theorist W Hugh Woodin now argues that the assumption that 2= is more a natural assumption than CH. Other people argue for far larger values of the continuum.

There is a stronger statement which says – roughly – that for every cardinal A, the next cardinal is 2^A. This is the Generalized Continuum Hypothesis (GCH) and implies the ordinary Continuum Hypothesis as a special case.

[1] Formally, P(X) is the collection of all subsets of X. So for instance if if X is just the two element set {0,1} then P(X) is { , {0}, {1}, {0,1}}. (Here is the empty set.) Or if X is the set of natural numbers, then the set of numbers between 1 and 100: {1,2,3,…,100}, and the set of primes {2,3,5,7,11,…}, and the set of odd numbers {1,3,5,7,9,11,… }, and the empty set , are all examples of subsets of X, and so are members of the P(X).