## Counting to Infinity (Part I)

People have always had a great curiosity about the infinite. I think this is because infinity represents a palpable break between our mind and our experience. You probably don’t have much difficulty imagining an infinite row of apples, but you’ve never seen one and you never will. Among the religious and spiritual, it is not unusual to identify the infinite with the divine. A great triumph of mathematical thinking, I feel, is the fact that it enables us to actually talk meaningfully about infinite things.

When people find out that I am at a mathematician, sometimes they will ask me questions. This is very interesting for me, because I get some insight into what sort of mathematical things nonmathematicians think about. A large percentage of those questions involve infinity in some way. Two popular ones are ‘Can you count to infinity?” or “Are there different kinds of infinity?” The former question strikes me as rather Zen, hence its inclusion as the title of this article. Today we’ll give at least one answer to the latter question.

Of course, the concept of infinity is a little amorphous. Today I want to focus on the counting aspect. In other words, we want to think about “infinity” as an answer to a “how many” question. And before I can to take you to infinity and beyond, we have to make a pit stop back in kindergarten and ask ourselves “What is counting, really?”

### Counting

Suppose that you wonder which of two people is taller than the other.  There are two fundamentally different ways to settle a question like that; you can use a yardstick or you can stand them back to back. The former is a solution by measuring, the latter is a solution by comparing.

It turns out that these same options are available in counting. The usual way of deciding whether you have more apples or oranges in your fruit bowl goes something like this. I count seven apples and six oranges. Seven is more than six, so I have more apples than oranges. But another way would be to pair up the .

Though the first approach doesn’t make sense for infinite sets, the second one does. We don’t have a “yardstick” to assign a numerical “size” to infinite sets, but we can always stand sets back to back.

In other words, we don’t “count” infinite sets in absolute terms, but we can still talk about the size of one set relative to another.

A bijection or one-to-one correspondence between two sets of things, say apples and oranges, is just a way of matching each apple to an orange so that each apple and orange gets used, no two apples get the same orange and no two oranges get the same apple.

Then we say that a set $A$ is the same size as $B$ if there is a bijection between the elements of $A$ and the elements of $B$.

We say that a set $A$ is at least as big as $B$ if there is a bijection between some of the elements of $A$ and all of the elements of $B$. (Saying that $A$ is strictly bigger than $B$, i.e. that there are more things in $A$ than there are in $B$, means that $A$ is at least as big as $B$, but they are not the same size.)

If this seems like a crazy way to think about counting, think about what a child does when counting a pile of apples. She points to each apple, saying “one, two, three,…”, making sure she doesn’t skip or repeat numbers, making sure she doesn’t skip or repeat apples. If, at the end, the last number she says is “ten”, there are ten apples. This is nothing more or less than putting the apples in bijection with a list of numbers $\{1,2,3,\ldots,10\}$. If you count like this, but you aren’t sure you counted all the apples (maybe you only count the ones you can see, say), then the right conclusion is that there are at least ten apples.

So for finite sets, this really is the counting you know and love.

### Countable Sets

We call a set finite if it is the same size as one of the following sets: $\{\}, \{1\}, \{1,2\}, \{1,2,3\}, \{1,2,3,4\}, \ldots$.  A set which is not the same size as any of these is infinite.

A set which is the same size as $\{1,2,3,\ldots\}$, the set of all positive integers, is called countably infinite. A set which is countably infinite or finite is just called countable.

Another way of phrasing that: a set is countable if you can list its elements $a_1, a_2, a_3, \ldots$ in such a way that everything in the set shows up on the list eventually. The list can stop (for finite sets) or continue forever (for countably infinite sets).

Yet another way of phrasing: suppose we are immortal, and I am thinking of a thing chosen from a set. I give you one guess a day at the thing I’m thinking of; if  you’re right, you get a prize. The set is countable if you can be sure you’ll get the prize eventually.

Perhaps surprisingly, including 0 and the negative integers, another infinite set, doesn’t make the set any bigger!  We can list all the integers as follows:

$0,1,-1,2,-2,3,-3,4,-4,\ldots$.

So the set of integers (usually written $mathbb{Z}$, for Zahl, German for number) is the same size as the positive integers. Indeed it is countable.

The following sets are all countable.

• The set of even positive integers.  $2,4,6,8,10,\ldots$. Even though this set misses infinitely many integers, it is the same size  as $\mathbb{Z}$.
• The set of odd positive integers, likewise.
• The set of square positive integers. $1,4,9,16,25,36,\ldots$. Even though the members of the set are getting more and more spread out, this does not affect “listability”, so it is still the same size set, the same kind of infinity.

It turns out that if you take any subset of the integers, you will either get a finite set or a set the same size as the integers. In some sense this means that $\mathbb{Z}$ is the smallest possible infinite set. You will never find a set which is bigger than all the finite sets but smaller than the integers.

Now let’s go in the other direction and try to find a set which is larger than the set of the integers.

• The set of all pairs of natural numbers. Believe it or not, this is countable too. The temptation is to try something like
$(0,0), (0,1), (0,2), \ldots, (1,0), (1,1),\ldots, (2,0), (2,1),\ldots$,
which doesn’t get off the ground. But we can arrange things another way,
$(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2),$
$(0,3), (4,0), (3,1), (2,2), (1,3), (0,4),\ldots$
• The set of all positive fractions. Countable again! Just use the previous list, ignoring pairs with zeroes and writing $(m,n)$ as $m/n$. This would list the same fraction more than once, so just skip repeats.
$1/1, 2/1, 1/2, 3/1, 1/3, 4/1, 3/2, 2/3, 1/4,\ldots$
• The set of all fractions. Just start with zero and interweave positive and negative fractions.
$0, 1/1,-1/1, 2/1, -2/1, 1/2, -1/2, 3/1, 3/1, 1/3, -1/3,$
$4/1, -4/1, 3/2, -3/2, 2/3, -2/3, 1/4, -1/4, \ldots$
This means there are the same number of fractions as there are integers! I hope you find that at least a little surprising if you didn’t already know it.

There is a really nifty discussion of countable and uncountable sets in Raymond Smullyan’s book, Satan, Cantor, and Infinity, which also contains many cheerful logic puzzles.

### Uncountable Sets

So we have seen a lot of sets which are the same size as the integers, even sets which might seem like they should be much much bigger. Is anybody feeling like guessing that all infinite sets are the same size after all? Or is there some set that is bigger? In other words, can there be so many of something that there are more of them than there are integers? Sets which are too big to be countable are called uncountable, but do such creatures even exist?

Consider the set of all real numbers between 0 and 1. Not just the fractions, but all the points on the number line. Essentially, we are looking at all the decimal expansions $0.a_1a_2a_3\cdots a_n\cdots$, where the $a_i$ are digits — not necessarily repeating, not necessarily in any sort of pattern (if the decimal “terminates”, as does 0.5, then just imagine trailing zeroes). It turns out that there are uncountably many of these real numbers. The easiest way to see this is the following “diagonal argument” due to Georg Cantor.

Theorem. The set of real numbers between 0 and 1 is uncountable.

Proof. Suppose instead that there is a matching between integers and real numbers. That is, suppose Sketchy Dan makes a list with the first real number $x_1$, the second $x_2$, and so on, and suppose tells you that every real number shows up on the list.  Imagine what such a list would look like.

$x_1 = 0.a_{11}a_{12}a_{13}\cdots a_{1n}\cdots$

$x_2 = 0.a_{21}a_{22}a_{23}\cdots a_{2n}\cdots$

$x_3= 0.a_{31}a_{32}a_{33}\cdots a_{3n}\cdots$

and so forth.

Now manufacture a new number $0.b_1b_2b_3\cdots b_n\cdots$ as follows. Let $b_1$ be 5 if $a_{11}$ is even and 6 if $a_{11}$ is odd. (In particular, notice that $b_1\neq a_{11}$. Proceed in this way, defining $b_n$ to be 5 if $a_{nn}$ is even and 6 if $b_{nn}$ is odd.  Then the number $0.b_1b_2b_3\cdots b_n\cdots$ was not on the list! It can’t be $x_1$ because the first digits don’t match. It can’t be $x_2$ because the second digits don’t match.  It can’t be $x_3$ because the third digits don’t match. And so on — it can’t be in the list anywhere.

Sketchy Dan was wrong! No matter how you make the list, there will be numbers left off.

(Actually, I swept a bit under the rug. There is a little wrinkle caused by the fact that some numbers have two “names”, such as $0.123000\cdots = 0.129999\cdots$. This isn’t a problem because the number we constructed doesn’t have any zeroes or nines in it.)

This means that there are, in a fundamental and not at all vague way, more real numbers than there are integers. So, as a thought experiment, if you throw a dart at a number line, you almost surely won’t hit an integer. That’s probably not much of a surprise, since the integers are pretty well spread out on the number line. But the fractions are also countable, and they are dense in the number line (which means roughly that any little piece of number line, however small, contains lots of fractions). But again, if you throw a dart at the number line, even though it will surely be near a fraction, it will almost surely not hit a fraction. So fractions, which for most people are almost all the numbers you ever think about, are just a negligible piece of the real numbers.

Let’s take this further. Think about all the numbers you can make, starting from integers and . Now $\pi$ is not in this category, and you probably know about $\pi$, so let’s throw in $\pi$.  And the number $e$ is pretty famous too. So consider all the integers that you can make from integers, $\pi$, and $e$, by adding, subtracting, multiplying, dividing, and taking roots and powers. Heck, you can even use logarithms and trig functions if you like. The set of all the numbers you can make that way is pretty big, and it contains all the numbers most readers have ever thought about. But it’s still countable. Almost all the real numbers aren’t in that set.

Actually the situation is even more intuition-defying than that. Think about all the numbers that can be described in any reasonable way whatsoever. So all the numbers in the previous category, but also things like $0.1234567891011121314151617\ldots$ and lots of other numbers. It turns out that the set of descriptions of numbers is countable, so this set is still countable. We feel like we have an intuitive understanding of the number line, but almost all the numbers on the number line can’t even be described.

Whoa.

### And Beyond?

Okay, so now we’ve seen a whole raft of countably infinite sets, which are in a sense the smallest possible sort of infinite sets, and now we know that even though these sets are infinite, they are not the largest sets in the world. There are strictly more points on the number line than there are integers. So what is the bottom line?

Does this mean that the set of points on the number line is the one that’s “really” infinite? Or is there another set that’s even bigger? If there is, is that one the ultimate infinite set? How do line segments compare to whole lines? How do line segments compare to squares and cubes?

Food for thought, I hope. See you Thursday?