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 = { XL | XR } and y = { YL | YR } are surreal numbers, then
x + y = {XL + y ∪ x + YL | XR+y ∪ x + YR} 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={ XL | XR }, then -x = { {-xr | xr ∈ XR} | {-lx | xl ∈ XL}}
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 = {XL | XR } and y = {YL | YR }, then:
z = x × y = { ZL | ZR } where:
* ZL = (XL× y + x×YL – XL×YL) ∪ (XR×y + x×YR – XR×YR)
* ZR = (XL× y + x×YR – XL×YR) ∪ (XR×y + x×YL – XR×YL); and
* if S and T are sets of surreals (e.g., XL 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: l1, l2, r1, and r2, where:
* l1 = XL× y + x×YL – XL×YL
* l2 = XR×y + x×YR – XR×YR
* r1=XL× y + x×YR – XL×YR
* r2 = XR×y + x×YL – XR×YL
* x×y = {l1 ∪ l2 | r1 ∪ r2 }
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 l1 first:
1. l1 = ∅×{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.php

0 thoughts on “Arithmetic with Surreal Numbers

  1. Blake Stacey

    Oh yeah, that Java code for basic surreal arithmetic sounds like a neat idea. The next time I have to procrastinate on something really important, I might throw together a Python version of the same thing.

    Reply
  2. Alon Levy

    Since the set {x in R: x = k / 2^n for some k, n in Z} is dense in R, it follows that all real numbers have finite or omega birthdays. Is it also true that all surreal numbers whose birthday is finite or omega are real? If it is, is it true that all surreals whose birthday is countable are real?

    Reply
  3. Mark C. Chu-Carroll

    Alon:
    I think that it’s true that all surreals whose birthday is countable are real; but it’s *not* true that all reals have countable birthdays. Lots of fractions – for example, 1/3 – have birthday ω+1. And birthday ω+1 includes a lot of non-real numbers: ω itself, 1/ω, etc.
    -Mark

    Reply
  4. Blake Stacey

    According to the Knuth book, all of the reals which have birthdays earlier than that of ω have terminating binary expansions (a finite sum of dyadic rationals, I think). Unfortunately, my math books are packed in several different containers right now, so I can’t give a more complete/truthful/useful reply.

    Reply
  5. Mark C. Chu-Carroll

    Blake:
    Yes, everything with a birthday earlier than ω has a finite representation as a surreal. In the case of fractions, that means terminating binary expansions.
    Unfortunately, there are a lot of common real numbers that *don’t* have birthdays before ω.

    Reply
  6. Xanthir

    An interesting but probably useless corollary: While a nice portion of the reals have countable birthdays, *all* of the reals are born or reborn on birthday ω+1. Within the countable birthdays each number is represented exactly once, but at birthday ω+1 you get everything being defined a second time with infinite series for left and/or right sets.

    Reply
  7. Alon Levy

    I don’t understand, Mark – doesn’t the definition {0, 1/4, 5/16, 21/64, 85/256… | …43/128, 11/32, 3/8, 1/2, 1} imply a birthday of ω, since no number in either the left set or the right set has a transfinite birthday?

    Reply
  8. Pseudonym

    Incidentally, surreal numbers are much, much more elegant in WHNF lambda calculus language such as Haskell. As a bonus, you can represent objects of birthday N (though comparisons may take infinitely long).

    Reply
  9. Confused

    What do I have to do in my browser to be able to read this blog comfortably? I see a bunch of sqares at the places where I suspect a mathematical symbol for ‘the element of’, ‘union’, ‘for each’, etc. are being used?

    Reply

Leave a Reply