Arithmetic with Surreal Numbers

Last thursday, I introduced the construction of John Conway's beautiful surreal numbers. Today I'm going to show you how to do arithmetic using surreals. It's really quite amazing how it all works! If you haven't read the original post introducing surreals, you'll definitely want to [go back and read that][surreals] before looking at this post!

Transfinite Induction and ≤
--------------------------------

I'm going to start off by working through the way that the recursive
definition of the surreals and the "≤" operator work. It's based on
something called *transfinite induction*.

Transfinite induction is based on the use of *ordinals*. The idea is to use the basic technique of mathematical induction - only instead of doing induction over the numbers themselves, you're doing induction over the *ordinals* associated with sets of numbers.

So, the way that we make "≤" work is induction over the ordinals. Ordinal N is the set of surreal numbers whose birthday is N.

The set containing the surreal 0 has ordinal 0 in the surreals. 0 ≤ 0 is true, because there is nothing in its right set (∅) that is not less than or equal to anything in its left set; and there's nothing in its left set that is greater than or equal to anything in its right set.

Ordinal 1 for the surreals is the set { -1, 1 }. Does ≤ work for -1, 0, and 1? Check it through; it does.

Since each new ordinal introduces a set of numbers constructed from the previous ordinals; and the construction rule requires the values in a new ordinal to be built from valid values of *previous* ordinals, then the new values will *also* work correctly with "≤".

All of the other arithmetic on surreals works using definitions that similarly depend on transfinite induction.

Addition with Surreal Numbers
--------------------------------

Addition for surreals is pretty straightforward:

If x = { X_L | X_R } and y = { Y_L | Y_R } are surreal numbers, then

x + y = {X_L + y ∪ x + Y_L | X_R+y ∪ x + Y_R} where

* if X is a set of surreal numbers, and y is a surreal number, then X+y = {x+y|x ∈ X}.

Once again, take note of the fact that this definition is recursive, and applies to all surreal numbers by transfinite induction.

So, to translate into english a bit: to add two surreals x and y, take the left side of x, and add it each member of it to y; take the left side of y, and add each member of it to X. Same basic idea for the right side.

So, for example, let's look at 2 + 3.

* {1|} + {2|} = {{1}+{2|} ∪ {1|}+2 | ∅ ∪ ∅ } =
* {{{0|}}+{2|}) ∪ {{0|}+{1|}} |} = {{3|}} ∪ {2|}|} = {3,4|} = {4|} = 5.

To get subtraction into the picture, we need to define *negation* for surreal numbers:

* -0 = 0;
* if x={ X_L | X_R }, then -x = { {-xr | xr ∈ X_R} | {-lx | xl ∈ X_L}}

And now, we can say:

* For any two surreal numbers x and y, x - y = x + (-y)

Multiplication with Surreal Numbers
---------------------------------------

The definition of multiplication is very similar to the definition for addition:

If x = {X_L | X_R } and y = {Y_L | Y_R }, then:

z = x × y = { Z_L | Z_R } where:

* Z_L = (X_L× y + x×Y_L - X_L×Y_L) ∪ (X_R×y + x×Y_R - X_R×Y_R)
* Z_R = (X_L× y + x×Y_R - X_L×Y_R) ∪ (X_R×y + x×Y_L - X_R×Y_L); and
* if S and T are sets of surreals (e.g., X_L above), then S×T= { s×t | s ∈ S, t ∈ T };
* if t is a surreal and S is a set of surreals, then t × S = S × t = { t }×S. (Note that this implies that if S is ∅, then t×S={∅|∅} = 0; and therefore S×T=0 if S or T = ∅.)

To make it easier to write things out, we can write x×y as four components: l₁, l₂, r₁, and r₂, where:

* l₁ = X_L× y + x×Y_L - X_L×Y_L
* l₂ = X_R×y + x×Y_R - X_R×Y_R
* r₁=X_L× y + x×Y_R - X_L×Y_R
* r₂ = X_R×y + x×Y_L - X_R×Y_L
* x×y = {l₁ ∪ l₂ | r₁ ∪ r₂ }

Multiplication is a bit hard to follow, so we'll work through a couple of examples.

Let's start with 0×1. In surreal format, that's: 0 × {0|}.
We'll look at l₁ first:

1. l₁ = ∅×{0|} + 0×{0} - ∅×{0} =
2. ∅ + 0×{0} - ∅×{0} = ∅

The same thing happens to all four terms: 0 always contributes an ∅ component, which turns every term it's a part of into ∅. In fact, the above works for any number multiplied with zero: zero's part of every combination is always ∅, which eliminates the contribution from the other number, so the result will always end up being {∅ | ∅} = 0.

How about 1×1 =

{0|}×{0|} =
* l1 = {0}×{0|} + {0|}×{0} - {0}×{0} = {0} + {{0|}×0} - {0} = {{0|} × 0} = {0}.
* l2 = ∅×{0|} + {0|}×∅ - ∅×∅ = ∅
* r1 = {0}×{0|} + {0|}×∅ - {0};×∅ = {0} + ∅ - ∅ = ∅.
* r2 = ∅×{0|} + {0|}×{0} - ∅×∅ = ∅ + 0 + ∅ = ∅

So 1×1 = { {0} ∪ ∅ | ∅ ∪ ∅ } = {0|} = 1.

One last example: 2 × 2, aka {1|} × {1|}. I'm actually going to cheat with this one. I've written some Java code to do basic surreal manipulations, so I'm going to let it spit out the pieces.

1. L1 = { {{{{{|0}|{0|}}|{{0|}|}}|{{{0|}|}|}}|{{{{0|}|}|}|}} }
2. L2 = ∅
3. R1 = ∅
4. R2 = ∅

So 2×2 = { {{{{{|0}|{0|}}|{{0|}|}}|{{{0|}|}|}}|{{{{0|}|}|}|}} | } =

* {{{{{-1|1}|{1|}}|{{1|}|}}|{{{1|}|}|}}|} =
* {{{{0|2}|{2|}}|{{2|}|}}|} =
* {{{1|3}|{3|}}|} =
* {{2|4}|} =
* {3|} =
* 4.

See, it works!

Why should I care?
-------------------

The thing about surreal numbers that's fascinating is that they're such a simple construction - and yet they manage to capture the richness of behavior of the real numbers, while also giving us a handle on playing with infinitely large and infinitely small values. They're a lot like Church numerals in lambda calculus, where you start with one trivial little thing - nothing but two empty sets in the surreal numbers! - and you can create *everything*.

Ultimately, all of the definitions of arithmetic reduce to nothing more than a bunch of recursive set unions; and yet, somehow, using nothing but those set unions, we can get absolutely everything to work exactly the way we expect real numbers to work.

When you think about it that way - we've built up everything we need to be able to do any algebraic operation, using nothing but the empty set and set unions - it's just amazing.

[surreals]: http://scienceblogs.com/goodmath/2006/08/introducing_the_surreal_number…