Feature Column from the AMS

Combinatorial Games (Part II): Different Moves for Left and Right

4. Counting and sets

Given a piece of paper with the letters of a single word written on it, one finds how many letters there are in the word by counting them. Now suppose the page has a word on it, but when you look at the page it appears blank! How do you tell the emperor that there are no letters in the word on this page? It would perhaps be better if in our counting system we started counting with 0 instead of 1, since then we would have a way of telling someone when the count found that there was nothing there. Thus, a collection of objects that has no elements (the empty collection) is reported using the counting number 0.

Counting finite collections of objects is something we teach children, but the transition to counting infinite collections of objects requires a surprising amount of sophistication. The German mathematician Georg Cantor developed ideas about counting infinite collections into a theory.

One step he took was developing ideas about extending the counting numbers so as to deal with the infinite. Cantor reasoned that no matter how far one counted, there is always another number that has not yet been used. This system of numbers is known as the ordinal numbers. Cantor's beginning infinite number is known as ω (which we met above as an unending blue beanstalk). In preparation for the surreal numbers, we will introduce the following notation promoted by John Conway. For the "next" ordinal number after a, b, c, .... the notation {a, b, c, ....| } is used. Thus, { | } is used for 0, {0| } is used for 1, {0, 1, 2, 3, 4, 5| } is used for 6 and {0, 1, 2, 3, ....| } is used for ω. Cantor's ordinal numbers can give meaning to, say, ω + 1, which would be denoted by {0, 1, 2, ..., ω| }. Using the analogy of one thousand and 8 for the number 1008, one can use expressions such as ω + 8. Using this approach one can represent 2ω or ω x ω. Think of these numbers as orderings; in the case of ω + ω, that there are ω beans laid out, followed right after this (infinite) bunch of beans by another (infinite) bunch. The challenge is to count what one sees. A good way to do this is to call it 2ω.

What is unexpected here is that the usual "rules of arithmetic" do not work! For example 2 + ω is not ω + 2. To see this, if we have to count beans where first there are two beans, and then ω beans (think of the situation visually as b, b, (0, 1, 2, ....) beans, then we would count 0 for the first b, 1 for the second, 2 for the next bean, 3 for the next, etc. The result would be ω beans. However, for the beans lined up (0, 1, 2, ....), b, b we would count 0, 1, ..., ω, ω +1 and report that we had counted ω + 2 beans. Remember that when we count four beans starting with 1 we count 1, 2, 3, and 4 and the number of beans is the last number we state. However, when we count 4 beans starting at 0 we get 0, 1, 2, and 3, so we report the number of beans as 1 more than the last number we count. Thus, above, we would have ω + 2 beans because the last bean we called out was ω + 1. Suffice it to say that in the ordinal number world Cantor pioneered, one is able to give meaning to the product and exponentiation of ordinals as well as to "limits" of such ordered counting of beans.

Cantor also introduced the idea of cardinal number for dealing with the notion that it is not always necessary to count the number of elements in two sets to compare them. Thus, the positive integers and positive even integers, though infinite sets, have the same cardinal number, because one can pair these numbers off, 1 with 2, 2 with 4, 3 with 6, and so on. A set is said to becountable if its elements can be placed into one-to-one correspondence with a finite set or into one-to-one correspondence with the finite ordinal numbers (e.g. 0, 1, 2, ....). Amazingly, the set of all rational numbers and the set of all algebraic numbers (roots of polynomial equations with integer coefficients) are countable. The fundamental idea here is that one can avoid counting each element of a set separately and comparing the counting numbers one gets by just pairing things off!