Cardinal numbers

I’ve said a bunch about natural numbers, but I seem to have ignored what we’re most used to doing with them: counting things! The reason is that we actually don’t use natural numbers to count, we use something called cardinal numbers.

So let’s go back and think about sets and functions. In fact, for the moment let’s just think about finite sets. It seems pretty straightforward to say there are three elements in the set , and that there are also three elements in the set . Step back for a moment, though, and consider why there are the same number of elements in these two sets. Try to do it without counting the numbers first. I’ll wait.

The essential thing that says there’s something the same about these two sets is that there is a bijection between them. For example, I could define a function by , , and . Every element of is hit by exactly one element of , so this is a bijection. Of course, it’s not the only one, but we’ll leave that alone for now.

So now let’s move back to all (possibly infinte) sets and define a relation. Say that sets and are “in bijection” — and write — if there is some bijection . This is an equivalence relation! Any set is in bijection with itself, using the identity function. If is in bijection with then we can use the inverse function to see that . Finally, if and are bijections, then is a bijection.

Any time we have an equivalence relation we can split things up into equivalence classes. Now I define a cardinal number to be an bijection class of sets — every set in the class is in bijection with every other, and with none outside the class.

So what does this have to do with natural numbers? Well, let’s focus in on finite sets again. There’s only one empty set , so let’s call its cardinal number . Now given any finite set with cardinal number — bijection class — , there’s something not in . Pick any such something, call it , and look at the set . If I took any other set in bijection with and anything not in then there is a bijection between and . Just apply the bijection from to on those elements from , and send to . This shows that the bijection class — the cardinal number — doesn’t depend on what choices we made along the way. Since it’s well-defined we can call it the successor .

We look at the set of all bijection classes of finite sets. We’ve got an identified element , and a successor function. In fact, this satisfies the universal property for natural numbers. The set of cardinal numbers of finite sets is (isomorphic to) the set of natural numbers!

And that’s how we count things.