Introducing the Surreal Numbers (Edited rerun)

Late last summer, shortly after moving to ScienceBlogs, I wrote a couple of posts about Surreal numbers. I've always meant to write more about them. but never got around to it. But Conway's book actually makes pretty decent train reading, so I've been reading it during my new commute. So it's a good time to take a break from some of the other things I've been writing about, and take a better look at the surreal numbers. I'll start with an edited repost of the original articles, and then move into some new stuff about them.

So what are surreal numbers?

Surreal numbers are a beautiful set-based construction that allows you to create and represent all real numbers in a simple elegant form that has the necessary properties to make them behave properly. In addition, the surreal number system 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. And finally, it makes the infinitely large numbers as natural a part of the number system as any other number: there's nothing about the construction of an infinitely large number that makes its construction any different from a perfectly reasonable real number like 1/3.

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:

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.

The Comparison Rule

If x = {X_L | X_R} and y = {Y_L | Y_R} are surreal numbers, then x≤y if/f:

• ¬∃x_i∈X_L: y≤x_i. (y is never less than any member of the left set of x.)
• ¬∃y_i∈Y_R: y_i≤x. (x is never greater than any member in the right set of y.)

To make it all work, we also 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. (Thanks to commenters for pointing out a typo in the previous sentence; I accidentally typed &lt; instead of &le;.)

Constructing Integers

Now that we've laid down the rules, we can use them to start creating numbers. Since we don't have any numbers at all yet, the first number has to be a number whose left and right sets are both empty: {∅ | ∅}, also written {|}. We'll say, by definition, that this number is 0.

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. 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 whose 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 Two

One thing about the surreals that seems a bit strange at first is the fact that they're created in an iterative fashion, where some numbers must be defined before
other numbers. And in fact, proving things about the entire set of surreals requires us to be able to talk about when certain numbers were created. The idea of the time when a number was created is called a numbers 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 a set of ordinals over the surreals: the ordinal of a surreal number is its birthday - the number of steps it took until we could create that number.

So now, we can define exactly how to figure out what fraction is meant by any surreal 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/2y ∈ S_ω:3x < 2y}; and the
right set of 1/3 is: {x/2y∈S_ω:3x>2y}.

So 1/3 = { { x/2y∈S_ω:3x<2y} | { x/2y∈S_ω:3x>2y } }, 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. &infinity;={ {x∈S_ω} | }, with birthday ω+1. And then, obviously, &infinity;+1 = {&infinity;|}, with birthday ω+2. And &infinity;/2 = { 0 | &infinity; }, 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. They're basically represented as a surreal form of a powers-of-2 version of continued fractions.

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