The size of infinity

How can you tell how many things are in a set? You count them, of course! I bring this up because, believe it or not, it’s going to tell us how to tell how big infinity is.1

What do you do when you count? Let’s say we’re counting superheroes. (Ah, this is bringing me back to Sesame Street. Those were the days.)

four

For each superhero, we associate a number with it. One number, one super. One super, one number. Since we get up through the number 4 in this process, we know our set of superheroes has four elements.

set

I know this is what you do with a 4-year-old, but bear with me.

Note that here, we’re not using the numbers to represent the order of the superheroes, but rather how many of them there are. That means, in this case, the number 4 isn’t really an ordinal, like we talked about last week, but a cardinal, which is just fancy math talk for a symbol representing how many of something there is. The cardinality of our set of superheroes is four.

The correspondence of the superheroes with the set of numbers \{1, 2, 3, 4\} is how we know the two sets are the same size. This correspondence is technically called a bijection, but really it just means that for each object in one set there’s another one in the second set, and vice versa. Two sets have the same size, or cardinality, if you can come up with a way to compare the sets, one for one.

Well, what is the size of infinity? Remember, we can’t just say “infinity,” since cardinality is all about sizes of sets.

So, a reasonable way to define the size infinity is to say that it’s the size of the set of all counting (natural) numbers, i.e., it’s the size of the set \{1, 2, 3, 4, 5, \cdots\}. And, so that we have a symbol for it, we’ll label this infinite size \aleph_0, which is aleph, the first letter of the Hebrew alphabet. 2 This is read “aleph null.”

Another super important name (get it?) for this is countable infinity. This name comes from the fact that making this correspondence between your set and the natural numbers (representing \aleph_0) is the same as counting your set. In other words, if you can put your set in an ordered (infinite) list, it has the same cardinality as the natural numbers, \aleph_0.

sets

What other sets are countably infinite?

Let’s start with a simple example, similar to the hotel example we discussed in the last post. The set of numbers \{0, 1, 2, 3, \cdots\} clearly has more elements than the counting numbers \{1, 2, 3, 4, \cdots\}, but it’s straightforward to find a bijection. Simply associate 0 with 1, 1 with 2, etc. So those sets are the same size.

0123

Okay, a slightly less obvious example. Consider all the integers, so the set \{\cdots, -2, -1, 0, 1, 2, \cdots\}. If you tried to start with 0 with 1, 1 with 2, 2 with 3, etc, you would not get a bijection (i.e., a one-to-one correspondence) since you’d never get to -10, for example.

But with a bit more cleverness, we can associate 0 with 1, 1 with 2, -1 with 3, 2 with 4, -2 with 5, etc. We have to alternate, but the set of integers is really the same size as the set of natural numbers, even though it seems twice as big.

01122

Alright, now for a difficult one.

rational number is a fraction with an integer on top or bottom. There are a lot of them. In fact, there are infinitely many of them between 0 and 1. No matter how close you look, there are always infinitely more of rational numbers squeezed into that gap.

Certainly there are more rational numbers than natural numbers, right?

Well, this one requires even more cleverness. We’ll just worry about positive rational numbers, but the same trick we did with the integers would work to get the negative ones, too. Let’s arrange all the positive numbers in a grid.

matrix

There are duplicates here (like 4/2 and 2/1), but that’s not so important. Now, if we tried to count straight down a column, we’d get lots of rational numbers, but we would never get all of them. Instead, we count the numbers in a zigzag fashion. Anytime we get to a duplicate, we can skip that one.

matrix2

So, if we associate 1/1 with 1, 2/1 with 2, 1/2 with 3, etc., we will count all the rational numbers.

There are as many natural numbers as there are rational numbers!

This defies my expectation. This is definitely one of those cases where your intuition gets confused about infinity and you need to tread carefully.

There are even bigger sets that are still only countable. For instance, the set of all algebraic numbers, i.e., numbers that solve polynomial equations like 27x^7-23 x^5+17x + 1 = 0, contains all the rational numbers, but is still only countable. In fact, the argument to show this is essentially the same as the one we just used for rational numbers.

With all that, you may be tempted to believe every infinity is the same size.

But math is more awesome than that.3


  1. Dear twitching mathematicians: Don’t worry, I’ll be careful. 
  2. Most things in math are Greek, but occasionally, we do use other languages. I have one friend who is fond of using a Korean symbol for tree as a variable instead of x
  3. We’ll be exploring larger infinities in the next post. 

Infinity plus one

supermanvsbatman

I think most of us have had this conversation. Two kids keep trying to one-up each other with bigger and bigger numbers, until one inevitably pulls out the trump number, infinity.

The problem is, Superman here is wrong.

Infinity plus one is totally a thing.

To really understand infinity, we need to think about about it in two different ways. The first is to ask, “What is the number infinity?” The second is to ask, “What does it mean to have infinitely many?” The first we’ll answer in this post, the second we’ll answer next week.

So, what is infinity?

All of this depends on what precise definitions you choose to use, but the school child’s idea is still about right. What number occurs after all the other numbers? Well, infinity, of course.

Think about it this way: two is the number after one. Three is the number after two, and so on. Each counting number (also called natural number) is followed by another. Then, we define a number \omega, the Greek letter omega, to be the number just after all of the counting numbers1. This clearly has to be infinity!

But what’s the number after \omega? Well, \omega + 1 of course. Then \omega +2. And, after all of those, \omega\cdot 2. It goes on. You can go on for as many layers as you wish.

omega-to-the-omega
Representation of the ordinal numbers up to \omega^\omega. Each turn of the spiral represents one power of \omega

Numbers like 1, 2 or \omega are called ordinals since they define the order of things. You have the first thing, the second thing and the \omega-th thing.

While \omega isn’t useful in a lot of places in math, it does provide one resolution of the famous Zeno’s paradox. (Actually, Zeno has six surviving paradoxes, but let’s talk about the most famous one.) Achillles, the fastest of the Greek warriors, is chasing a tortoise. However, he can’t ever catch the tortoise. Why not?

racestart

In order to catch the tortoise, Achilles must first reach the place where the tortoise began. But by the time he arrives, the tortoise has moved farther away. Thus, Achilles has to run to that spot, but, again, the tortoise has moved on. Since Achilles must repeatedly reach the spot where the tortoise was, he can never catch the tortoise.

tied

Now, of course this sounds silly. Many of these philosophical paradoxes do. Zeno tried to use this to show that all movement is an illusion, despite our experience to the contrary.

But let’s talk about this using our new idea.

Let’s say Achilles runs 10 times faster than the tortoise2, but starts 100 meters behind him. After Achilles has gone 100 meters, the tortoise is still 10 meters ahead. After Achilles has gone that next 10 meters (110 meters) total), the tortoise is yet another meter ahead. And after Achilles has gone that additional meter (111 meters total), the dang tortoise is already ahead by another tenth of a meter. And so on and so forth, ad nauseum.

zeno_achilles_paradox
Source: Grandjean, Martin (2014) Henri Bergson et les paradoxes de Zénon : Achille battu par la tortue ?

After 20 cycles of this, Achilles has still not caught up, though he is closer than the diameter of an electron.

Achilles is still behind the tortoise, though.

But the \omega-th cycle is, by definition, the cycle after all of those cycles. And since he’s getting infinitely close during the first finitely many cycles, at the \omega-th cycle, Achilles has exactly caught up to the tortoise.

How long does it take for Achilles to catch the tortoise?

If he is traveling at 10 m/s (Olympic sprinter pace), the first cycle―100 meters―takes ten seconds, the first two cycles―110 meters total―takes 11 seconds, while the first \omega cycles takes 11.1111… seconds (or 100/9, to be exact).

And so, Achilles can quickly catch the tortoise.

achilles-wins

Using this idea, we’ve come up with a number representing infinity. We also have numbers that are after infinity. But while \omega +1 is after \omega, is it bigger than \omega? How about \omega \cdot 2 or \omega^\omega?

Before you decide, listen to this story.

The Hitchhiker’s Hotel is the largest hotel in the galaxy. In fact, it has infinitely many rooms. One night, every room was filled, when an unfortunate traveler came in begging for a room for the night. Fortunately for her, the hotel has a policy for such circumstances. They called each room and told them to pack up and move to the room with the next higher number on it. Each guest did so and the hotel worker put the new guest up in room number one.

When we started, we had infinitely many guests in infinitely many rooms. After our lucky guest came, we had one more guest and the same number of rooms, but each guest still had their own room. So they must be the same size, right?

In the next post, I’ll talk about how to carefully tell which set of things is bigger, and then show that some surprisingly different things are the same size.


  1.  Really, to define this carefully, we need set theory. The ordinal zero is the empty set. The ordinal one is the set of the empty set, i.e., the set of the ordinal zero. The ordinal two is the set of the ordinals zero and one. The ordinal three is the set of the ordinals zero, one and two. This goes on infinitely. The ordinal \omega is then defined to be the limit of this process over all the counting numbers. Following this same pattern, \omega+1 is union of \omega with the set \{\omega\}, i.e., the set of all the finite ordinals along with \omega. For more details, see Wikipedia, that endless source of knowledge. 
  2.  The land speed record for a tortoise is 5 miles per hour, so Achilles is going cheetah speed!