# The Unapologetic Mathematician

## 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 $\{a,b,c\}$, and that there are also three elements in the set $\{x,y,z\}$. 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 $f$ by $f(a)=x$, $f(b)=z$, and $f(c)=y$. Every element of $\{x,y,z\}$ is hit by exactly one element of $\{a,b,c\}$, 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 $X$ and $Y$ are “in bijection” — and write $X\leftrightarrow Y$ — if there is some bijection $f:X\rightarrow Y$. This is an equivalence relation! Any set is in bijection with itself, using the identity function. If $X$ is in bijection with $Y$ then we can use the inverse function to see that $Y\leftrightarrow X$. Finally, if $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ are bijections, then $g\circ f:X\rightarrow Z$ 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 ${}0$. Now given any finite set $X$ with cardinal number — bijection class — $c$, there’s something not in $X$. Pick any such something, call it $x$, and look at the set $X\cup\{x\}$. If I took any other set $Y$ in bijection with $X$ and anything $y$ not in $Y$ then there is a bijection between $x\cup\{x\}$ and $Y\cup\{y\}$. Just apply the bijection from $X$ to $Y$ on those elements from $X$, and send $x$ to $y$. 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 $S(c)$.

We look at the set of all bijection classes of finite sets. We’ve got an identified element ${}0$, 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.

April 13, 2007 - Posted by | Fundamentals, Numbers

## 3 Comments »

1. [...] We use cardinal numbers to count how many elements are in a set. Another thing we think of numbers for is listing elements. [...]

Pingback by Ordinal numbers « The Unapologetic Mathematician | April 26, 2007 | Reply

2. [...] and Ordinals as Categories We can import all of what we’ve said about cardinal numbers and ordinal numbers into [...]

Pingback by Cardinals and Ordinals as Categories « The Unapologetic Mathematician | May 24, 2007 | Reply

3. [...] to do the same thing. The term we tell them is “counting”, and the more technical term is cardinality. We can set up a bijection between two finite sets exactly when they have the same number of [...]

Pingback by Reading Hume’s Principle Eliminatively? « if-then knots | December 10, 2008 | Reply