The Lesser of Infinitely Many Evils

This is the second post in a series called Before I Forget, which is an exposition for the semi-layman of some freaky high-level mathematics (mostly set theory). This episode is still about infinity, but covers the Cardinal numbers.

Last Time

Last time I introduced the ordinal numbers, specifically the ordinal ω—the least number greater than all the integers—and things derived from it (like ω × 2, and ωωω an infinite number of times… (ω times, actually :-)). Today we’ll be exploring a parallel concept to the ordinal numbers called the cardinal numbers. Ordinals are used to index positions: the 1st position, 2nd position, ωth position; cardinals are used to measure sizes.

Well-ordering

Okay, let’s step out of the context we’ve been working for just a little while. Numbers are now the numbers you are familiar with: not just the nonnegative integers, but also negatives, fractions, and irrationals. Here is an exercise: come up with a set of numbers which has no least member. This should be pretty easy, but it should be obvious that the set must be infinite.

Got one yet? I want you to come up with one before you continue reading.

One of the most obvious examples is the set of all numbers greater than (but not equal to) 0. How do you know it doesn’t have a least member? Well, suppose it did, and call it x. We know that x > 0, because it was in our set. Well, if x > 0, then x/2 > 0 also, so x/2 is in our set. But of course x/2 < x, so it turns out that x wasn’t the least member after all (but we chose x specifically to be the least member, so this is a contradiction). Our supposition that our set had a least member must have been flawed, and we have thus proved that our set has no least member.

Another example is the set of all integers (positive and negative). It extends infinitely in the negative direction, so it can’t have a least member. (Exercise for the reader: prove formally that the set of all integers has no least member like we did for the real numbers greater than 0 in the last paragraph) There are tons of sets with no least member, and yours could have been quite different from my two examples.

Here’s another challenge: come up with a (nonempty) set of positive integers that has no least member. Got one? No, come on, come up with one. I dare you. Don’t continue reading until you have one.

Yo mama’s fat.

You shouldn’t have read that. You shouldn’t be reading this either. That’s because there’s no nonempty set of positive integers with no least member! It doesn’t exist! To see why informally, just start at 1 and ask “is 1 in the set?”. If so, then 1 is the least member. If not, ask about 2. And so on, until you find a number that is in the set, and that’s the least member. The set is nonempty, so you will eventually find one.

A set of numbers which has the property “every nonempty subset has a least member” is called well-ordered by mathematicians. The set of positive integers is one example of a well-ordered set. The real numbers, we proved, is not well-ordered.

And it turns out that the ordinal numbers from last time, the set of the nonnegative integers together with all those crazy infinities, is also well-ordered. We will use this fact to introduce cardinal numbers in a later section. Right now, let’s go off on a tangent and prove something quite counterintuitive: there are just as many positive even integers are there are positive integers.

WTF Are You Talking About?

“You’re full of crap. Every other positive integer is even, so the number of even positive integers is exactly half that of the number of positive integers!” you say. I think otherwise. But since we have no way of counting the number of integers yet, I first have to construct a way to compare the size of sets without using numbers, and convince you that it’s right.

Mathematicians say that two sets have the same size if (and only if) they can be put into “1-1 correspondence” with each other. That is, we have two sets A and B. A and B have the same size only if for every member of A I can assign a unique member of B, and vice versa. For example, I can show that the sets { 1, 4, 3, 8, 9 } and { Alice, Bob, Charlie, David, Eve } have the same size by making an assignment correspondence between them: 1=Bob, 4=Charlie, 8=Alice, 3=Eve, 9=David. Notice that every member of the first set appears exactly once on the left side of an equals sign, and every member of the second set appears exactly once on the right side of the equals sign. Thus the two sets have the same size. I was able to do this without mentioning the number “5″ anywhere. I hope you agree that this is an adequate method for comparing the sizes of two sets.

So I have still to convince you that the positive integers have the same size as the even integers. Well, by the “lemma” I argued above, I have to come up with an assignment correspondence between them. Well here it is: take any positive integer x, and assign to it the even integer 2x. So 1=2, 2=4, 3=6, 4=8, etc. (where = does not mean “equals”, but rather “is assigned to”). If you look at this sequence, you will note that each positive integer appears exactly once on the left side of an equals sign, and each positive even integer appears exactly once on the right side of an equals sign. If you don’t believe me, try to come up with a counterexample.

So, therefore, there are exactly as many positive even integers are there are positive integers, not half.

Rational Reasoning

Here’s another counterintuitive correspondence. This one makes people go crazy. There are exactly as many positive rational numbers (fractions) as there are positive integers. This is a fun argument: first, line up all rational numbers in a 2-D lattice, with numerators increasing to the right and denominators increasing to the bottom, like so:

  1/1  2/1  3/1  4/1  ...
  1/2  2/2  3/2  4/2  ...
  1/3  2/3  3/3  4/3  ...
  1/4  2/4  3/4  4/4  ...
  ...  ...  ...  ...

Now cross out all the fractions that are not fully reduced; i.e. their numerator and denominator has a factor in common:

  1/1  2/1  3/1  4/1  ...
  1/2       3/2       ...
  1/3  2/3       4/3  ...
  1/4       3/4       ...
  ...  ...  ...  ...

Now do you agree that every rational number appears exactly once somewhere in this lattice? 4487619248762348976143/12376810344412 may be way, way, way out by Pluto, but it is there. Now all we have to do is to assign a positive integer to each one. Go along the diagonals of this lattice, from the top right to the bottom left, and assign ever-increasing numbers to each one. So 1=1/1, 2=2/1, 3=1/2, 4=3/1, 5=1/3, 6=4/1, 7=3/2, ….

Each integer appears exactly once on the left of an equals sign, because we were just adding one as we added new assignments, and each rational appears exactly once on the right of the equals sign, because we striped the whole lattice with our diagonals. If you can think of a rational that we missed, or a rational that we assigned twice, do tell.

Among other things that are exactly the same size as the set of positive integers: the set of all algebraic numbers (roots of polynomials), the set of English sentences, the set of all logical formulae, the set of all the ordinal numbers that we were introduced to in the last episode (not all ordinal numbers in general! Just the ones that you can construct the way I did in that post). All of these have fairly straightforward proofs.

Everything Is The Same Size, I Get It

Now we’ll do something novel. We will prove that there is an infinite set which is bigger than the set of positive integers: namely, the set of real numbers (that is the rational numbers and the irrational numbers). And we will do this by contradiction.

We’ll suppose that you have in your possession a correspondence between the positive integers and the real numbers. I will show you that you must be full of crap: that there was a real number which your correspondence failed to assign. We will construct this number out of your mapping (we’re allowed to do that: you can assign every real number to an integer, you just can’t do it all in the same assignment; you have to double up (well, infinity up, really) integers to do it).

Your mapping looks something like this:

  1 = 0.1870581751981709817134871...
  2 = 3.1415926535897932384626433...
  3 = 9.2798748908761765740989128...
  4 = 7.0000000000000000000000000...
  5 = 3.3890787311111123672222323...
  ...

Something like that; i.e. it has increasing positive integers on the left and a bunch of unique real numbers on the right. Let’s make a new number, digit by digit. We will pick the first digit to be different from the first digit of your first number, let’s say 1. We will pick the second digit to be different from the second digit of your second number, let’s say 2. And so on; in general, the nth digit of our number will differ from the nth digit of your nth number.

And that’s it. The number we constructed must not be in your assignment. If you disagree, then tell me which integer n you assigned it to. Oops, you’re wrong, my number differs from the one you assigned to n by its nth digit, by construction.

Therefore, there are not the same number of real numbers as there are positive integers. It seems obvious, but we had to do all that work to prove it because it also seemed obvious that there were more rational numbers than there were integers, which was wrong. What we can say is obvious is that, since they are not the same size, the set of real numbers is the bigger one, because the positive integers are contained in the real numbers.

Cardinal Numbers

So now we have at least two different sizes of infinity. I said that each ordinal we saw in the last post has the same size (ordinals are sets, remember?) as the set of positive integers. It turns out that there are ordinals which are bigger than those, and in fact there are ordinals of every possible size. I won’t prove this, but it can be proved.

We want to define a representative object, called a “cardinal number”, for each size of infinity, so we don’t have to come up with weird mappings between the reals and whatever we’re trying to measure; we just have to map whatever we’re trying to measure into that cardinal number. So we say a cardinal number is the least ordinal of a given size (we can do that because ordinals are well-ordered, remember?). That’s it.

Since the cardinals are a subset of the ordinals, we can well-order them, too. So we call the least (infinite) cardinal number of all “Aleph-0″, and it is exactly the same object as ω, the least infinite ordinal. Then we call the least cardinal greater than Aleph-0 “Aleph-1″. And so on.

These are indexed by ordinals, so we can have Aleph-ω, Aleph-(ω+1) (the least cardinal greater than Aleph-ω), Aleph-(ωωω), ….

And since cardinals are ordinals, sometimes we want to refer to Aleph-1 as an ordinal, so we call that ω1. There is an ωn for every Aleph-n; in fact they are the same object.

Catching Your Tail

As you can see, the cardinal numbers increase in size way faster than the ordinal numbers. ω has size Aleph-0, ω+1 has size Aleph-0, ω+ω has size Aleph-0, ωω has size Aleph-0. Aleph-1 is bigger than all of those. We keep getting bigger with Aleph-2, Aleph-3 (these are really big; remember how many things were the same size as Aleph-0?), and we can even go to Aleph-ω, which is bigger than all the Aleph-ns for integers n. And yet, ω+ω is still just size Aleph-0.

So you might conject that Aleph-a > a for all ordinals a. In fact, you might not even conject that, because it’s so damn obvious. But—it’s wrong!

Somehow the ordinals catch up with the cardinals; there is an a such that Aleph-a = a (the ordinal never gets bigger than the cardinal, though). We will see how.

Just look at this sequence of ordinals: { ω, ωω, ωωω, … } (that is, Aleph-0, Aleph-ω, Aleph-ωω, etc.). Union them all together, and call it β (beta) which creates an ordinal which is bigger than all of them; in fact it is the least ordinal bigger than all of them.

Now what n satisfies Aleph-n = β? It’s bigger than 0, because it contains Aleph-0; it’s bigger than ω, because it contains Aleph-ω, it’s bigger than ωω, bigger than …. It is a cardinal bigger than all of those ordinals, and the least one at that, since it contains only those. So we just union together { 0, ω, ωω, … } (that is, 0, Aleph-0, Aleph-ω, Aleph-ωω, …). What do we get? Well, that’s exactly how we defined β! So our n that satisfies Aleph-n = β is exactly β, so Aleph-β = β.

Until Next Time

This has been a pretty dense article, at the end especially. Congrats at getting through it, I hope you learned something. I’d like to point out that every section of this article contained a mathematical proof, so if you think proofs are over your head and you understood even one section of this article, you’re wrong (but I can’t say which part of that you’re wrong about :-).

We will be putting these gigantic infinities away for a while, to simmer until we have done some other stuff. The next couple episodes will talk about logic and model theory, where I will introduce nonstandard analysis: numbers you didn’t even know existed, much stranger than i (square root of -1), which you can use to do ordinary arithmetic. After that, cardinal numbers will make a triumphant return, where we find cardinals which are large enough to hold all of set theory.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s