Wow, that was a much longer hiatus than I had planned. Let’s see if I can pick this up again.

Last year, I spent several weeks describing in intricate detail what natural numbers are. If I had to describe my thesis in a sentence, this might be it:

*“The natural numbers are a computational tool for answering questions about finite sets.”*

Here’s a somewhat longer and possibly more helpful recap.

**Sets**are ‘pure extensions’: collections of objects that are entirely defined by what is a member, and what is not.- Given two sets, sometimes there’s a
**bijective correspondence**or**bijection**between them: a mapping in which every element of the first set is associated to a single element of the second, and*vice versa*. In this case we say the sets are**equipotent**, or “the same size”. - We choose a representative from each class of equipotent finite sets, and call those representatives
**natural numbers**. In this way we can determine whether two finite sets are equipotent just by seeing which natural number each one corresponds to. The natural number associated to a finite set is its**cardinality**or “size.” - The ordering and arithmetic on the natural numbers is defined to reflect facts about the sets they describe. For example, addition reflects what happens when two disjoint sets are put together.

An obvious next step would be to give a similar at-length development of rational numbers, integers, real numbers, and so on. But I’d prefer to move in a novel direction, so right now I want you to notice something specific about the construction above, which is how unnecessary was the limitation to *finite* sets.

There is nothing about the definition of a bijection that says the sets have to be finite! Taking the same construction above, and removing that limitation, won’t create any paradoxes—instead it will give us a whole new collection of numbers to work with. Instead of a computational tool for answering questions about finite sets, we’ll get a tool for answering questions about sets in general.

### Introducing Aleph

Before I proceed, I’ll offer just one definition: a set will be called **finite** if and only if it has some natural number as its cardinality (i.e. its “number of elements” is a natural number). Otherwise it’s **infinite**.

In order to start talking about cardinalities of infinite sets, we need some infinite sets to work with. Fortunately I have one in mind already: the set of natural numbers themselves. Call it **N**.

If some skeptic really doubts that **N** is an infinite set, I can offer the following argument: if **N** were finite, its cardinality would be some natural number *n*. But **N** actually has {0,1,2,3,….,*n*} as a subset, and that’s already larger than *n*. So **N** must not be finite after all.^{1}

So, just how big is **N**? Well, it’s bigger than any finite set of natural numbers, so we’ll have to find something else to compare it to. How about the set of *even* natural numbers: {0,2,4,6,…}? For reference I’ll call it **E**. So, which is bigger, **N** or **E**? Or are they the same size?

Ask this question to ten non-mathematicians, and they’ll all agree that the answer is perfectly obvious. The problem is that they disagree about what the perfectly obvious answer is!

Here’s the intuitive argument that **N** is bigger than **E**: everything in **E** is also in **N**, but some of the things in **N** are not in **E**. That is, **E **is a proper subset of **N**. So obviously **N** is bigger!

Here’s the intuitive argument that they’re the same size: Obviously **E** can’t be bigger than **N**. But **N** can’t be bigger than **E** either, because there is a number in **E** for every number in **N**: namely its double. (2 is “the double of 1,” 4 is “the double of 2,” and so on.) If neither set is bigger, they must be the same size!

So which argument wins? Is this proof that truth is relative and mathematical reality depends on your point of view?

Well, no, it isn’t. The second argument wins, because it’s setting up a bijection. Remember how we showed that “the fingers on my hand” and {0,1,2,3,4} were the same size, way back in the first post? If you accept that form of argument, you can use it to show that {0,1,2,3,4,…} and {0,2,4,6,8…} are the same size as well, by declaring the following correspondence:

“Associate to each natural number n in

N, the natural number 2n inE.”

So these two sets are equipotent; that is, they have the same cardinality. This cardinality is often called ℵ_{0} (pronounced **aleph nought**, **aleph null**, or **aleph zero**).

This number ℵ_{0} is the smallest of the** infinite cardinal numbers**. For symmetry, the natural numbers can be retroactively called the **finite cardinal numbers**.

### subsets, cardinality, and infinity

So how can we res0lve the seeming paradox above? Why does the first argument, that there are fewer even natural numbers than there are natural numbers altogether, fail? You might be tempted to say that this really is just a matter of opinion. This isn’t as relativistic as it sounds: all it means is that the word “size” is ambiguous. All this stuff about cardinality and bijections is clever, but that doesn’t mean it’s the final word on questions about comparative size.

I’m sort of sympathetic to this view. There’s an obvious sense in which **E** really is smaller than **N**. And, in fact, there are other notions of “size” that I hope to discuss on this very blog someday. But maybe I can convince you that, when it comes to comparing sets, cardinality really is the Right Thing.

Suppose we accepted the first argument above. That is, suppose we accept that {0,2,4,6,…} is a smaller set than {0,1,2,3,…}.

Now, the symbols “0” and “1” and “2” and so on are just *names* for numbers. Using a different name system shouldn’t make a difference. So I propose the following change of names for the elements of **E**:

- Replace “2” with “II”.
- Replace “4” with “IIII”.
- Replace “6” with “IIIIII”.
- And so on.

Now we ought to be able to say that {0, II, IIII, IIIIII, …} is smaller than {0, 1, 2, 3, 4, …}—which looks much more dubious.

In fact, let’s change the name system for the elements of **N** as well:

- Replace “1” with “H”.
- Replace 2 with “HH”.
- And so on.

Now we’re claiming that {0, II, IIII, IIIIII, ….} is smaller than {0, H, HH, HHH, …}. Neither one is a subset of the other, so the original argument sure doesn’t apply.

The problem is that the subset relation isn’t total. We want to be able to compare completely different sets, not just sets of natural numbers. And we don’t want our answers to change based on what language we’re using, or what system of labels we prefer. Compared to these, the “problem” of having **E** and **N** be the same size is really inconsequential: all it means is that infinite sets behave differently from finite ones.

In fact, many writers use this strangeness as the definition of an infinite set: a set is finite if it is strictly larger than all of its proper subsets, and infinite otherwise.

### ….and beyond

There are at least two good questions to ask at this point.

- Is ℵ
_{0}really the smallest infinite cardinal number, as promised? - Is ℵ
_{0}really the largest (i.e. only) infinite cardinal number?

The answers to these questions are *yes* and *no*. The demonstration of the first answer is a bit technical, but the idea is straightforward: it amounts to proving that if you can embed every finite set of natural numbers into a set *S*, you can embed **N** as a whole into *S* as well.

There’s a pretty easy way to demonstrate the second answer as well, but I don’t think it’s all that instructive, so I’m not going to offer it right now. Instead, I’m going to spend the next several posts constructing the better-known extensions of the natural number: the integers, rational numbers, and real numbers. Each of these is in the naïve sense “bigger” than the natural numbers: we’ll see if they have bigger cardinalities as well.

[1] There is an even more sophisticated way of denying **N** is an infinite set, which is to deny that it’s a set at all. Some philosophers of mathematics deny that such a thing as an infinite set can exist. This surprisingly hard-to-assail opinion is called finitism and, while calling it popular would be a stretch, it does have serious adherents within the mathematical community.

Prime #s Rule