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.

JustinAlso notable, the continuum hypothesis can not be

disprovenwith ZFC either.Mike SaelimI 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.

BrentGreat 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.

TokenI 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?

TokenNo, I lied. It works as injective both times if you mean there’s an injective function both ways.

pIs there anywhere that Cantor’s original papers can be found online in English? I’ve checked multiple local university libraries and all over Google.

AnonymousSo the generalized continuum hypothesis hasn’t been proving, but what about specific cases? In particular for ones like aleph-0 and 1?

MattGood old Dover publishes a translation of Cantor:

http://store.doverpublications.com/0486600459.html

Ørjan JohansenYes, 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.

TokenTokenWhoops… 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.

Harald Hanche-OlsenToken: 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

nto be a cardinal number if no smaller ordinal has the same cardinality asn. The cardinality of a setSis the smallest ordinal which has the same cardinality asS(and this ordinal exists, by the wellordering theorem and the fact that ordinals are well ordered). Now, given any cardinaln, you can work through the definitions to find thatnis a set with cardinalityn. (Handy.) There are bigger cardinalities, for example 2n(the cardinality of the set of subsets ofn), and the smallest of these bigger cardinalities will be the successor ofn. The generalised continuum hypothesis states that this successor is in fact 2n.MaxWhat 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?

EJMax: 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.

Mark C. Chu-CarrollMax:

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) ofN.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.

Jonathan Vos Post“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.