Tuesday, May 02, 2023

How to explain cardinals vs ordinals to a six-year-old

This discussion on Hacker News on whether infinity is odd or even got me to thinking about the right way to teach kids about infinity, and the difference between cardinals and ordinals.  Here's what I came up with.

It is important to realize that numbers can stand for two different kinds of ideas.  Numbers can talk about "how many" but they can also talk about "what position".  For example, we can talk about how many apples are in a bag of apples, and this lets us compare two bags of apples to decide whether one bag has more apples than the other, or whether the two bags have the same number of apples.  We can also talk about what happens when we add an apple to a bag, or take away an apple from a bag.  And this lets us define what we mean by zero: it is the number of apples in a bag from which it is not possible to remove an apple.

Now consider two bags of apples.  How can we tell if the bags have the same number of apples?   The obvious way is to count them, but suppose we don't know how to count.  Is there another way?  Yes, there is.  (See if you can figure it out.)

The way to do it is to start taking apples out of the bags two at a time, one from each bag, and stop when one of the bags is empty.  If the other bag is also empty, the two bags had the same number of apples to begin with.  That is what it means to have "the same number": for every apple in one bag, there was a corresponding apple in the other bag.

Now, what happens if we start adding apples to a bag and never stop?  It is tempting to say that we would eventually end up with a bag of infinity apples, but this is not true because if we never stop then we never end up with any particular number of apples.  We just have a bag that keeps getting fuller and fuller forever.  Is there a way to define infinity that doesn't require us to wait forever?

Yes, there is.  Remember, we have a way to tell if two bags of apples have the same number of apples (and we can do this without knowing how to count!)  So imagine if we took all possible bags of apples and grouped them together according to how many apples they had.  We take all of the one-apple bags and put them together (maybe we put them in a box instead of a bag) and all of the two-apple bags and put them together (in a second box) and so on and we do this for all possible bags of apples all at the same time.  The number of boxes we would end up with is (one kind of) infinity.

(Aside: it might seem like doing this for "all possible bags of apples at the same time" is cheating.  Why is that any better than talking about where the process of adding apples forever ends up?  It's because "forever" and "ending up" are contradictory.  Doing something to all possible bags at the same time might be physically impossible, but it is not logically contradictory.  The problem with trying to construct infinity by adding apples is that adding apples is inherently sequential.  We can't add the nth apple until after we have added the n-1'th apple.  By postulating "all possible bags of apples" we have taken the infinite bit and "parallelized" it so that the process of constructing the infinite set doesn't have an infinite chain of sequential dependencies, and so we can do it in a finite amount of "time".)

Now, instead of putting apples into bags, let's think instead about putting apples in a row.  This might seem at first like a distinction without a difference, but it's not.  When apples are in a bag, they are all jumbled together and you can't really tell one apple from another (assuming they are all the same kind of apple and the same size).  But if you put them in a row they now have an order associated with them.  So we can talk about the first apple, and the apple after the first apple (which we call the second apple) and the apple after that (third apple) and so on.

We can also go the other way and talk about the apple before (say) the third apple, which is the second apple, and the apple before the second apple, which is the first apple.  This is analogous to how we could talk about one apple more or one apple less.  But there is a huge difference between before and after versus more and less.  When we take apples out of bags, when we get to an empty bag, we have to stop.  There are no more apples to take away.  But with apples-in-rows, if we want the apple before the first apple we don't have to stop.  We can simply add an apple to that end of the row.

There is one little detail that we have to mention, and that is that to make this work we have to somehow mark the first apple so we don't lose track of it.  We could use a sharpie to write a big "1" on it, or use a granny smith as the first apple and make all the others be red-delicious or something like that.  But as long as we have a row with two ends, we can add apples to either end, and so we can go on before-and-aftering for as long as we like.  When we're adding-and-removing we are limited to removing only as many apples as we've added, after which we have to stop.

We have names for after-the-first apples: second, third, and so on.  Can we invent names for before-the-first apples?  Of course we can.  Unfortunately, the names that have been given to before-the-first apples break the pattern.  These should have been called before numbers, but in fact they are called negative numbers, or, less commonly, minus numbers.  This is really misleading because there is no such thing as negative-one apples, but there is such a thing as the-apple-that-is-two-before-the-first.  (Sometimes it seems that mathematicians are conspire to make things as confusing as they possibly can in order to maintain their job security ;-)

Note that what is important here is not so much the actual physical arrangement of apples, but rather that apples-in-a-row have a natural ordering to them which apples-in-bag don't have.  That ordering allows us to assign numbers not just to the total quantity of apples, but to each individual apple to identify where it is in that ordering.  And that very naturally leads us to a whole different kind of number (negative numbers) when we start to think in terms of before-and-after rather than less-and-more.

Note also that we can have an infinite number of after-apples, and that does not stop us from adding before-apples to the row.  In other words, when numbers are taken to stand for the order of things rather than the quantity of things, we get entirely new kinds of numbers as a result, and (and this is the really important bit) we get those additional numbers despite the fact that we started out with an infinite number of numbers!  There are an infinite number of positive numbers, but then there are an infinite number of negative numbers on top of that!

Are there even more kinds of numbers?  Yes!  Imagine an infinite row of apples that goes on forever in both directions.  We can add a new apple to that row by calling it, "The apple after all the after-apples that have (regular) numbers on them."  That's a bit wordy so it's usually abbreviated ω, which is the lower-case Greek letter omega.  (Exercise: what would you call the apple-before-all-the-before-apples-that-have-regular-numbers-on-them?)  Then we can add the apple-after-the-ω'th apple (abbreviated ω+1), the apple after that (ω+2) and so on.  Eventually you get to ω+ω=2ω, then 2ω+1, 2ω+2... 3ω, 3ω+1 and so on in a mind-boggling sequence that eventually gets you to ε0 and then ω1and then the Feferman–Schütte ordinal and the small and large Veblen ordinals.

But that's probably enough for one lesson.  Tomorrow we'll go back to bags of apples and talk about diagonalization.