Introducing the Surreal Numbers

Surreal numbers are a beautiful, simple, set-based construction that allows you to create and represent all real numbers, so that they behave properly; *and* in addition, it allows you to create infinitely large and infinitely small values, and have *them* behave and interact in a consistent way with the real numbers in their surreal representation.

The surreals were invented by John Horton Conway (yes, *that* John Conway, the same guy who invented the "Life" cellular automaton, and did all that amazing work in game theory). The name for surreal numbers was created by Don Knuth (yes, *that* Don Knuth!).

Surreal Numbers are something that has come up in discussions in the comments on a number of posts around here. Before they were first mentioned in a comment back when this blog was on Blogger, I had never heard of them. After someone said a little about them, I thought they sounded so cool that I rushed out and got the two main books that have been written about them: Conway's "On Numbers and Games", and Knuth's "Surreal Numbers".

The Basic Rules
------------------

The basic idea of surreal numbers is that you can represent *any* real number **N** using two sets: a set *L* which contains numbers *less than* **N**, and a set *R* which contains numbers *greater than* **N**. To make it easy to write, surreals are generally written N={ L | R }, where L is the definition of the set of values *less than* N, and R is the definition of the set of values *greater than* N.

There are two fundamental rules for surreal numbers:

1. **The Construction Rule**: If L and R are two sets of surreal numbers, and ∀ l ∈ L, r ∈ R : l < r, then { L | R } is a valid surreal number.
2. **The Comparison Rule**: If x = {X_L | X_R} and y = {Y_L | Y_R} then x ≤ y if/f:
* ¬ ∃ x_i ∈ X_L : y ≤ x_i *(y is not less than and member of the left set of X)*, and
* ¬ ∃ y_i ∈ Y_R : y_i ≤ x. *(x is not greater than any member of the right set of Y.)*

In addition, we need two basic axioms: finite induction, and equality. Finite induction is basically the induction rule from the Peano axioms, so I won't repeat it here. The equality rule for surreals is also very simple: x = y if/f x ≤ y ∧ y ≤ x.

Constructing Integers
-----------------------

With the rules set, we can start creating numbers. The first one we create is 0: we say that *by definition*, 0 is the number with the empty set as its L and R values: 0 = { ∅ | ∅ }, also written { | }.

Next we want to define the basic unit values, 1 and -1. So how do we define 1? Well, the only number we have so far is 0. So we define 1 as the value with 0 in its left set, and an empty right set: 1 = {0|}. -1 is pretty much the same deal, except that it uses 0 as its *right* set: -1 = {|0}.

We follow the same basic pattern for all of the integers: the positive integer *i* is a surreal number with all of the positive integers less than *i* in its left set, and an empty right set: i = { 0, ..., i-2, i-1 | }. Similarly for the negatives: a negative number -i = { | -i+1, -i+2, ... 0}.

Now, if we look at the possibilities for surreals so far - we're always using a null set for either the left, the right, or both sets. What happens if, for a positive number *i*, we leave out, say, *i-2* in its left set?

What happens is *nothing*. It's effectively exactly the same number. Just think of the definition above, and look at an example: 4 = {0, 1, 2, 3 |}, and {2, 3|}. Is {0, 1, 2, 3|} ≤ {2, 3|}? Yes. Is {2, 3|} ≤ {0, 1, 2, 3|}? Yes. So they're the same. So each integer is actually an *equivalence class*. Each positive integer *i* is the equivalence class of the surreal numbers formed by: { {l|} where l ⊂ { 0, ..., i-1 } && i-1 ∈ l }.

At this point, we've got the ability to represent integers in the surreal form. But we haven't even gotten to fractions, much less to infinites and infinitessimals.

Constructing Fractions
-------------------------

The way we construct fractions is by dividing the range between two other numbers in half. So, for example, we can create the fraction 1/2, by saying it's the simplest number between 0 and 1: {0 | 1}. We can write 3/4 by saying it's halfway between 1/2 and 1: {1/2 | 1}.

This is, obviously, sort of limited. Given a finite left and right set for a number, we can only represent fractions whos denominators are powers of 2. So 1/3 is out of the question. We can create a value that is as close to 1/3 as we want, but we can't get it exactly with finite left and right sets. (Fortunately, we *aren't* restricted to finite left and right sets. So we'll let ourselves be lazy and write 1/3, with the understanding that it's really something like a continued fraction in surreal numbers.)

Happy Birthday to 2
---------------------

One thing that's important in understanding the surreals is the idea of a *birthday*.

We started creating surreals with the number 0 = {|}. We say that 0 has the *integer* **0** as its birthday.

Then we created 1 and negative one. So it took one step each to get from the set of surreals we knew about to get to the new set consisting of {|0}, {|}, {0|}, or -1, 0, and 1. So -1 and 1 have a birthday of **1**.

Once we had -1, 0, and 1, we could create -2, -1/2, 1/2, and 2 in one step. So they had a birthday of **2**.

What we're doing here is creating an idea of *ordinals*: the ordinal of a surreal number is its birthday - the number of steps it took until we could create that number.

Given any surreal number {L|R}, the value that it represents is the value between the largest value in L and the smallest value in R with *the earliest birthday* (or, equivalently, the lowest ordinal).

So if we had, for example {1, 2, 3 |} (a surreal for 4), and {23|} (a surreal for 24), then then surreal number { {1, 2, 3|} | {23|} } would be *5* - because it's the surreal between 4 and 24 with the earliest birthday.

What about infinity?
-----------------------

I promised that you could talk about infinity in interesting ways.

Let's call the *size* of the set of natural numbers ω. What can we create with birthday ω + 1? Things with birthday ω+1 are things that require *infinite* L and R sets. So, for example, in step ω+1, we can create a precise version of 1/3.

How?

Let's give a name to the of all surreal numbers with birthday N. We'll call it **S_N**.

The left set of 1/3 is: { x/2^y ∈ S_ω : 3x < 2^y}

The right set of 1/3 is: { x/2^y ∈ S_ω : 3x > 2^y }

So 1/3 = { { x/2^y ∈ S_ω : 3x < 2^y} | { x/2^y ∈ S_ω : 3x > 2^y } }, and its birthday is ω+1.

Using pretty much the same trick, we can create a number that represents the *size* of the set of natural numbers, which we'll call infinity. ∞ = { {x ∈ S_ω} | }, with birthday ω+1. And then, obviously, ∞+1 = { ∞ | }, with birthday ω+2. And ∞/2 = { 0 | ∞ }, also with birthday ω+2.

Infinitesimals are more of the same. To write an infinitely small number, smaller than any *real* fraction, what we do is say: { 0 | { 1/2, 1/4, 1/8, 1/16, ... } }, with birthday ω+1.

What about irrationals? No problem! They're also in S_ω+1. We use a powers-of-2 version of continued fractions.

π = {3, 25/8, 201/64, ... | ..., 101/32, 51/16, 13/4, 7/2, 4}, birthday=ω+1.

Coming Soon
--------------

Either tomorrow or next monday (depending on how much time I have), I'll show you how to do arithmetic with surreal numbers.