Surreal Nimbers: No, that's not a typo!

(A substantial part of this post was rewritten since it was first posted. I managed to mangle things while editing, and the result was not particularly comprehensible: for example, in the original version of the post, I managed to delete the definition of "mex", which continuing to use mex in several other definitions. I've tried to clear it up. Sorry for the confusion!)

This is actually a post in the surreal numbers series, even though it's not going to look like one. It's going to look like an introduction to another very strange system of numbers, called nimbers. But nimbers are a step on the path from
surreal numbers to games and game theory.

Nimbers come from a very old game called Nim. We'll talk more about Nim later, but it's one of the oldest strategy games known. The basic idea of it is that you have
a couple of piles of stones. Each turn, each player can take some stones from one of the piles. Whoever is left making the last move loses. It seems like a very trivial game. But it turns out that you can reduce pretty much every impartial game to some variation of Nim.

Analyzing Nim mathematically, you wind up finding that it re-creates the concept of ordinal numbers, which is what surreals are also based on. In fact, creating nimbers can end up re-creating the surreals. But that's not what we're going to do here: we're going to create the nimbers and the basic nimber addition and multiplication
operations.

The trick to creating nimbers is going to be using an ordinal process where we don't distinguish between left and right sets in the nimbers, but we use the idea of the corresponding surreals to define things like ≤. And using this non-distinguishing
ordinal process, we're going to create numbers that form a (peculiar) field. In fact, we're going to get the number field with characteristic 2 - meaning a number field where
each number is its own additive opposite.

So we start with ordinal 0. Obviously, ordinal 0 defines the number 0 - the additive identity. After that, for successive ordinals, we'll just play around with a definition of addition based on the idea of the minimum excluded ordinal: the smallest ordinal which is not yet a part of our set. The sum of two of two ordinals can't exist before the ordinals themselves - and we'll exploit that. So we'll define things in terms of the minimum exluded ordinal (mex) the minimum ordinal number which isn't yet part of the set of nimbers.

So we've got zero. And we can't add any new numbers using addition - because 0+0=0. So we look for the mex of the set of defined ordinals: mex({0}). That's 1. So now we have two numbers, 0 and 1.

Now, for successive generations, we're going to use nimber addition. Given two nimbers A and B, A+B = mex({A'+B : A'<A} ∪ {A+B': B'<B}). Using that, we get a set of new nimbers defined from the sums of existing nimbers. Each time we've exhausted the new numbers that can be generated using sums, we'll create a new nimber by taking the mex of the nimbers that we've defined so far.

Nimber addition, as defined above, is strange. Let's take a moment and look at why. In nimber addition, what's 1+1? It's 0: 1 is its own additive inverse. In fact, we'll find that every nimber is its own additive inverse: N+N=0 for all N. And if we work through from there, we'll find that we can treat every number as its binary expansion, and cancel pairs of the same power of two. So, for example, we can take thu nimber sum of 7 and 9: 7=4+2+1; 9=8+1; so 7+9=(4+2+1)+(8+1) = 8+4+2+1+1; cancel the pair of ones, and it equals 8+4+2 = 14. For another example, we can take the nimber sum of 15 (8+4+2+1) and 6 (4+2) = 8+4+4+2+2+1; cancel the pair of 4s and the pair of twos, and we get 8+1=9. So 15+6=9. So for any two nimbers A and B, the addition operation is really bitwise exclusive-or of the binary expansion of the number. (The first addition example in this paragraph originally contained a typo: when I re-arranged the additive expansion terms, I changed a 1 to a 2. Thanks to alert commenters who noticed and pointed that out.)

What about multiplication? Well, it's similar to addition: A×B = mex(A'×B + A×B' : A'<A and B'<B). The nimber product of any two nimbers ends up being the nimber sum of numbers of the form 2²ⁿ. Those numbers are called Fermat 2-powers. In nimber multiplication, the nimber product of two distinct Fermat 2-powers is their product in the normal surreal number field. The nimber-product of any Fermat 2-power N with itself it 3N/2.

So what's 4×4? 6. 4×6? Well, 6=4+2, so 4×6=4×(4+2)=4×4 + 4×2. We know 4×4=6, so that's 6+(4×2) = 6+8=14.

How about 4×10? Well, 10=8+2. 8=4×2. So 10=4×2+2. So 4×10 =
4×(4×2+2) = 4×4×2 + 4×2 = 6×2 + 8 = (4+2)×2 + 8 = 8+3+8=8+8+3=0+3=3.

All of this works out to give us a new field of ordinal numbers. Yes - this crazy stuff actually does work out to be a field. And these operations actually do make sense, in a strange way. When you start analyzing games, any impartial game is equivalent to a game of Nim for some set of piles. And given a game of Nim two piles of size A and B, there's an equivalent game of Nim with one pile - and the size of that pile is the nimber sum A+B.

There's a similar reason why the product makes sense. But we'll get back to that
some other time.