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

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