Counting

Let’s start at the beginning.

Long ago, likely earlier than you can remember, you were (hopefully) introduced to the so-called natural numbers or whole numbers. In case you don’t recall what they are, here are a few examples:

• 0
• 1
• 2
• 42
• 53,166
• 3,454,046,406,040,014,098,134,254,561

(All of these are pretty small as whole numbers go, since most whole numbers are much larger.)

Here’s the great thing about being a human: you have an incredibly sophisticated pattern-matching system built in. Given a very few examples like the ones above, you can probably recall exactly what pattern natural numbers follow.

The downside is that, when something is so obvious intuitively, it can become hard to define explicitly. Just try telling a computer—or even worse, a mathematician—what the natural numbers are, using just examples. The computer will have no idea what you’re talking about, and the mathematician will just pretend he doesn’t. “Ah, the natural numbers are the set {0,1,2,42,53166,3454046406040014098134254561}! Now I understand!”

Smartass.

But the mathematician’s feigned ignorance has a point. We haven’t explained what natural numbers are—at least not in a way that a blank-slate listener would understand. At the very least, you would have to already understand what numbers were, to understand our ‘definition’. We ought to be able to do better.

It’s generally understood that you can’t define something in terms of itself. It’s also usually a bad idea to define a simple idea in terms of a more complex one. That means, in order to define the natural numbers, we’ll need something even simpler than natural numbers.

Sets

Suppose I have a bunch of independent things that I want to consider as a group:

1. the fingers on my left hand
2. the members of my salamander breeding club
3. all the vowels of the alphabet
4. all the people living in my apartment
5. all the cats living in my apartment
6. Whitney Houston, the word ‘quinoa’, and a baked potato

Now, immediately we have to answer some somewhat-philosophical questions about what sort of collections we’re going to allow. If a ‘collection’ doesn’t have anything in it—like the collection of all the dogs in my house—is that okay? Can I include ‘collections’ as members of other ‘collections’? If two ‘collections’ have all the same things in them, are they actually the same thing? Does a ‘collection’ need to be defined by some sensible rule, or can it be weird and heterogeneous (like #6 above)?

Starting with Georg Cantor in the 1870s, mathematicians have come up with something of a standard answer to these questions. The ‘collections’ mathematicians work with are called sets. The rules for defining and manipulating sets can sometimes get subtle and arcane, but here we’ll be able to get by with a few informal rules:

• A set must have an unambiguous criterion for membership. This means, given an object, it should be either absolutely in or absolutely out. Either you’re in my club or you’re not. Either something is a vowel or it isn’t. (There is the problematic “sometimes Y” here, so for #3 above to count as a set we’d have to decide once and for all whether Y is a vowel or not.)
• A set is entirely determined by its membership. If two ‘different’ sets have the same members, they’re actually not different sets at all. (For example, until I get someone other than my wife to join my salamander breeding club, sets #2 and #4 above will be the same set.)
• Anything can be a member of a set. This includes other sets. (Within mathematics, “anything” is restricted to “any mathematical entity”. In many popular systems, sets are the only mathematical entities.)
• A thing is distinct from the set containing it. For example, if I’m the only one living in my apartment, I still have to distinguish between “Ian” and “the set {Ian}”.

Let’s see how this answers our questions from before.

Can a set contain nothing? Well, it’s a valid criterion for membership, I guess: “Nothing is a member.” So we’ll allow it. (The set with no members is usually called the empty set or null set.)

Can a set contain another set as a member? Sure can. (But this is different from “including” another set: there is a difference between containing “the set of all the vowels” and containing the vowels themselves.)

Can two different sets have the same membership? No; if they have the same membership, they’re not different sets!

Can the membership of a set be silly and arbitrary? Yes, as long as it’s unambiguous. Any old bunch of letters from the alphabet form a set, for example, not just meaningful ones like “the vowels”.

Now, when you set mathematicians loose on the above description, the first thing they’ll do is look for a way to break it. That’s why they’ll start asking hard-to-answer questions like

• Can a set be a member of itself?
• Is there a set of all sets?
• Is there a set of all sets that are members of themselves?
• Is there a set of all sets that aren’t members of themselves? (This is particularly problematic.)

Mathematicians have mostly solved these problems by adding more rules than the ones above, putting technical provisos and restrictions on exactly how you can define a set. We will solve these problems by ignoring them, and staying away from the situations where they would come up.

Bijections

Very well, but what does all of this have to do with counting? Well, if you have sharp eyes, you may have noticed something about two of the sets above.

• the fingers on my left hand
• all the vowels in the alphabet

If you assume that Y is not a vowel, and that my left hand is fairly typical, then you might notice a certain structural similarity between the above sets. (Alternately, you could assume that Y is a vowel and that my left hand is quite exceptional.) You may want to say something like:

“Those sets are the same size!”

To which I, the smartass mathematician, will respond, “What do you mean, ‘the same size’?”

“Look, they both have five things!”

“What’s a five?”

Oh yeah, we haven’t invented numbers yet!

Well, maybe there’s a way you can show me the relationship between these two sets, without actually pointing to any numbers.

Thinking quickly, you grab my left hand and a permanent marker. On my thumb you write ‘A’. On my index finger you write ‘E’. on my middle finger you write ‘I’. On my ring finger you write ‘O’. And on my pinky you write ‘U’.

A bijection: There is a finger for every letter, and a letter for every finger.

“There,” you say. “For every finger there’s a vowel, and for every vowel there’s a finger.”

Impressed, I concede that these sets must have something in common after all.

Congratulations, you have invented a bijection! That is, you have devised a correspondence between two sets, such that every member of set A corresponds to one member of set B, and vice versa. This is fundamentally what it means for two sets to have the same size. (A fancy word for this is that the sets are equipotent or in bijective correspondence.)

Inventing numbers

We’re almost there! We know what it means for two sets to be the same size, so we can probably start somehow naming those sizes.

Our first impulse is to say something mystical, like, “‘Five-ness’ is the indescribable property that my left hand and the vowels have in common. Likewise, ‘two’ is the thing that the set of my ears and the set of your ears has in common…. etc.”

This is…. actually not that bad. In fact, it’s how I actually think of numbers like 5 when I’m using them. But it’s not quite a definition. I’d like a number to be an actual thing I can grab hold of, not a slippery metaphysical notion.

The first real attempt to pin down what a number was, was something a bit more like this:

“Take the set of all the sets that can be put into bijective correspondence with the fingers on my left hand, and call it 5.”

This is a little better. Now 5 is an actual thing! Surely we can’t do better than this: identify the quality of five-ness by just showing me everything that has it.

As it turns out, the above definition is great—as long as it actually works. Unfortunately, it runs into some of the technical problems we’re trying to avoid right now: specifically, whether there “really are” sets that big.

Maybe we can do an end-run around the whole issue. Instead of trying to find every five-y set in the universe at once, we’ll find one such set, and use it as a sort of prototype for five-ness. “You’re five-y if you are in bijective correspondence with this set.”

In fact, since we can define things however we want, we’ll say that set is five!

There are a lot of ways to choose such sets. One way isn’t necessarily better than another, but I have to admit I’m partial to the following construction:

• The number 0 is just the empty set, or {}.
• The number 1 is the set containing only 0, or {0}.
• The number 2 is the set containing only 0 and 1, or {0,1}.
• And so on: in general, after the number n, the next natural number is the set containing all the elements of n as well as n itself—the set {0,1,2,…,n}.

Counting: A bijection between 5 and my fingers.

In particular, the number 5 is the set {0,1,2,3,4}. And this is in bijective correspondence with the set of fingers on my left hand, and with the set of vowels of the alphabet, and with the set of cars in our driveway,¹ and with any other set you might suspect to have that mysterious five-ness.

We’ll call these objects—0, 1, 2, 3, 4, and all the rest—natural numbers. Every finite set is in bijective correspondence with exactly one of these natural numbers, and we’ll call that its cardinality (or, if we’re feeling quotidian, its size).

So, after all the fuss about needing numbers so we can count, it turns out that numbers aren’t essential for “counting” at all. We can get by without them; they just make life easier. If I want to make sure I have enough hors d’ouvres for everyone at the party, I could, if I wanted, set up an explicit bijection: write out the names of everyone coming, and place an hors d’ouvre next to each name. Or, using our new technology of ‘numbers’, I could just notice that there are 20 of each.

Of course, counting isn’t the only thing you can do with natural numbers. But it is basically why they exist: they are the distilled essence of counting.

---

[1] Most of those cars aren’t actually mine.