One of the strangest, and yet one of the most important ideas that grew out of set theory is the idea of cardinality, and the cardinal numbers.
Cardinality is a measure of the size of a set. For finite sets, that’s a remarkably easy concept: count up the number of elements in the set, and that’s its cardinality. But there are interesting questions that we can ask about the relative size of different sets, even when those sets have an infinite number of elements. And that’s where things get really fun.
We’ve already seen an example of how to compare the cardinality of different infinite sets: Cantor’s diagonalization. The idea of measuring relative cardinality is based on the use of one-to-one functions between sets. If I have two sets S and T, and there is a total, onto, one-to-one function from S to T, them S and T have the same cardinality.
It seems like a simple notion, but it leads to some very strange results. For example, the set of even natural numbers has the same cardinality as the set of natural numbers: f(x)=2*x is a total, one-to-one, onto function from the set of naturals to the set of even naturals. So the set of even naturals and the set of all naturals have the same size, even though the set of evens is a proper subset of the set of natural numbers.
When we look at most sets, we can classify them into one of three cardinality classes: finite sets, whose cardinality is smaller that the cardinality of the natural numbers; countable sets, which have the same cardinality as the set of natural numbers; and uncountable sets which have a cardinality greater than the cardinality of the natural numbers.
Set theorists, starting with Cantor, created a new kind of number just for describing the relative cardinalities of different sets. Before set theory, people thought that for talking about sizes, there were finite numbers, and there was infinity. But set theory showed that that’s not enough: there are different infinities.
To describe the cardinalities of sets, including infinite sets, you need a system of numbers that includes something more than just the natural numbers: Cantor proposed what is know as the cardinal numbers: the cardinal numbers consist of the natural numbers plus the transfinite numbers. The transfinite numbers specify the cardinality of infinite sets. The first transfinite number is written ℵ0 (pronounced aleph-null), and it’s the size of the set of natural numbers.
Here’s where the really nifty trick comes in. The same trick used in Cantor’s diagonalization can be used to prove that for any non-empty set S, the set of all subsets of S (also called the powerset of S) – is strictly larger – that is, has greater cardinality than S. So given the smallest infinite set, you can prove that there’s got to be another infinite set larger, and one larger than that, and so on – an infinite sequence of ever-larger infinite numbers: ℵ0 < ℵ1 < ℵ2, …
Cantor proposed that the first infinite set larger than ℵ0 was of size 2ℵ0, which is the size of the set of reals. That proposition is known as the continuum hypothesis – if that were true, then ℵ1=2ℵ0.
There’s also an extended version
of the continuum hypothesis: the generalized continuum hypothesis, which says that
for every infinite set S, there are no cardinals between the cardinality of S, and the cardinality of the powerset of S – so ℵ1=2ℵ0, ℵ2=2ℵ1, and so on.
The continuum hypothesis remains unproven. in fact, it’s more than unproven: it’s unprovable using ZFC.
Also notable, the continuum hypothesis can not be disproven with ZFC either.
I smell a cliffhanger for the next interesting post…
Keep writing! This stuff is awesome and supplements the pieces I learned in my real analysis class.
Great explanation, Mark — now I finally understand what the continuum hypothesis is! I don’t know why I never really understood it before, it’s not really that complicated, but for some reason it never clicked. Apparently it was never explained to me very well.
I think you used “one-to-one” to mean both injective and bijective on separate occasions in this paragraph.
On a less pedantic note, is there anything that says that aleph-one is even defined? Or, to put it more simply, must there be a countable number of cardinals?
No, I lied. It works as injective both times if you mean there’s an injective function both ways.
Is there anywhere that Cantor’s original papers can be found online in English? I’ve checked multiple local university libraries and all over Google.
So the generalized continuum hypothesis hasn’t been proving, but what about specific cases? In particular for ones like aleph-0 and 1?
Good old Dover publishes a translation of Cantor:
http://store.doverpublications.com/0486600459.html
Yes, given that sets can be well-ordered (by the axiom of choice), so can their cardinalities. Basically you order cardinalities by the size of the smallest ordinal with the same size.
Then you use transfinite recursion: define aleph-x as the smallest cardinality larger than all the aleph-y, y < x.
Whoops… ignore the above post.
Yeah, there’s my question. What if there isn’t such a smallest cardinality under a sensible ordering? We’re looking for a cardinal x to be smaller than y if a set of cardinality x injects into one of cardinality y, right? Surely, just because we have a well-ordering doesn’t mean it fits the order we want.
Token: The class of cardinal numbers is itself well ordered. The easy way to see this is to identify the cardinal numbers with special ordinals: Define an ordinal number n to be a cardinal number if no smaller ordinal has the same cardinality as n. The cardinality of a set S is the smallest ordinal which has the same cardinality as S (and this ordinal exists, by the wellordering theorem and the fact that ordinals are well ordered). Now, given any cardinal n, you can work through the definitions to find that n is a set with cardinality n. (Handy.) There are bigger cardinalities, for example 2n (the cardinality of the set of subsets of n), and the smallest of these bigger cardinalities will be the successor of n. The generalised continuum hypothesis states that this successor is in fact 2n.
What does it mean, exactly, to use this Aleph-null as an exponent? Can we use it in every other way? Is there (conceptually) some set with cardinality Aleph-null * 2? And why would anyone ever suspect that 2^Aleph-null = Aleph-one?
Max: Consider two disjoint sets each of which has cardinality Aleph-null. The union of the two sets would be a set which has, conceptually, cardinality Aleph-null*2. But it turns out that Aleph-null*2 = Aleph-null.
(Or did I get that backwards? Maybe I described a set of size 2*Aleph-null. It comes out the same size in the end anyway.)
If Mark hasn’t already done a post explaining what multiplication and exponentiation of infinite cardinals means, then it’s overdue. But I’m pretty sure he’s done one.
Max:
I’ll get to exponents and such of cardinals. For now, just think of it in terms of powersets – which was what I was thinking when I wrote it.
ℵ0 is the cardinality of N, the set of natural numbers. 2ℵ0 is the cardinality of 2N – the powerset (set of all subsets) of N.
Why would we expect ℵ1 to be 2ℵ0? The intuition behind it is an intuition about the sizes of infinite sets. That is, if you’ve got an infinite set A, what’s the smallest infinite set B that’s larger than A? And how can you create a set B larger than A? The way we know of taking steps, to create larger infinities, is Cantor’s diagonalization: and that’s based on powersets. So we suspect that given an infinite set A of cardinality ℵA, the next larger infinite set is the powerset of A, which has cardinality 2ℵA. So we expect that 2ℵX = ℵX+1.
“So we suspect that given an infinite set A of cardinality ℵA, the next larger infinite set is the powerset of A, which has cardinality 2^(ℵ_A). So we expect that 2^(ℵ_X) = ℵ_(X+1).”
Well, we suspect that 2^(ℵ_X) = ℵ_(X+1) OR that 2^(ℵ_X) > ℵ_(X+1).
What we don’t know a priori is whether the inequality is an equality. That is, we don’t know a priori whether or not 2^(ℵ_X) is the successor of ℵ_X. There MIGHT be another cardinal in between. Or more than one.
I know that you know what comes next in this discussion. I’m not trying to get ahead of you here, but am trying to respect the already strained intuitions of some readers.
As I’ve posted previously, on other threads, Paul Cohen had his own unpublishable hunches about CH and GCH, and suspected that the power set is MUCH more powerful than he could prove.