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 
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,/em>: If x = {XL | XR} and y = {YL | YR} then x ≤ y if/f:
¬ ∃ xi ∈ XL : y ≤ xi (y is not less than and member of the left set of X), and ¬ ∃ yi ∈ YR : yi ≤ 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 SN.
- The left set of 1/3 is: { x/2y ∈ Sω : 3x < 2y}
- 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. ∞ = { {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.
You left out the best part about Surreal Numbers, which is the bizarre frame story Knuth sets up in his book to explore the things, which you just have to read to believe.
It’s the most sexually explicit math text I’ve ever seen. Not to mention all that stuff that plays at Conway being God.
okay, i’m really really interested in this, and this looks like the most accessible explanation i’ve see. so i want to figure it out, and sorry if i’m missing something here…but…
in your comparison rule, doesn’t x≤y have to be defined entirely in terms of the x_i and y_i numbers?
that is, “y is not less than any member of the left set of X” doesn’t feel well-defined yet because we don’t know how to compare the surreal number y to the numbers in the left set of X because we’re in the very process of defining “less than”.
i’m sure there’s some way that’s not circular (applying the definition recursively maybe?), but i’m not seeing it. if you could help me see how you got “yes” out of “Is {0, 1, 2, 3|} ≤ {2, 3|}?” i think it would really help.
Polymath:
The trick to the surreals is that the construction rule and the comparison rule are mutually recursive. Just follow through the recursion, and it makes sense.
I’ll try to include an example of doing the recursive comparison when I write the other part of the surreal numbers stuff tommorowish.
It does work, but it’s not at all obvious that it works. The easiest way to prove this is probably to prove that, for each ordinal/birthday a, if x and y have birthdays before a, then x ≤ y is well-defined (since you can find such an a for any pair of surreals x and y). The proof would have to be by transfinite induction on a. The trick is, once you have it for all birthdays below a and want to prove it for birthdays below a+1, you have to assume one of the birthdays of X and Y is exactly a and then do another induction on the other birthday.
That gets a bit complicated, so let’s start at the beginning. We have 0 = {|}, with birthday 0; then we have 1 = {0|} and -1 = {|0} with birthday 1.
First, let’s tackle birthdays {0,0}. We only have to check 0 ≤ 0. Both clauses are trivially true because 0_L and 0_R are both empty.
Now let’s try birthdays {0,1}. We have four to check: 0 ≤ ±1 and ±1 ≤ 0. We have -1 ≤ 0 and 0 ≤ 1, for similar reasons to the above. However, 1 ≤ 0 fails, by the first clause; 0 is in 1_L and 0 ≤ 0. Similarly 0 ≤ -1 fails. This is all as we expect.
Finally, try birthdays {1,1}. We check the four relations 1 ≤ ±1 and -1 ≤ ±1. -1 ≤ 1 succeeds trivially. 1 ≤ 1 also succeeds; the only possible problem is the 0 in 1_L, and we do not have 1 ≤ 0. Similarly -1 ≤ -1. 1 ≤ -1 fails on both clauses: we have 0 in 1_L with -1 ≤ 0, and we have 0 in -1_R with 0 ≤ 1.
To reach numbers with larger birthdays (both of yours have birthday 4), you have to fill in much of the table below those numbers.
Incidentally, Mark, are you familiar with Abraham Robinson’s work in nonstandard analysis? He also found a way to add infinities and infinitesimals to the real numbers, except he used model theory (it’s an extension of the argument for nonstandard models of arithmetic). It’s more abstract than the surreals, but he gets a set instead of a proper class.
I find surreal numbers to be extremely appealing due to the simplicity of their definition.
How about using them as a foundation for arithmetics? Then prove the usual axioms as theorems instead, thus making it easy to prove consistency, since surreals themselves require very few axioms. That could be quite useful in some applications, such as proof-carrying code.
Surreal numbers are great– you get all of conventional ‘countable’ ordinal arithmetic and the ability to define numbers like sqrt(omega)/pi – 37.6. However the greatness of surreals is weighed down somewhat because they are a special case of a much messier theory– the ‘games’ of Conway’s ‘On Numbers and Games’. Conway’s real interest seemed to be in the ‘games’ part of the theory. But frankly, it’s not for people who like systematic theories.
Not to stress Mark out, but this leads me to hope he will tackle hyperreals and nonstandard analysis some day.
Or perhaps, considering the interest in categories, synthetic differential geometry and smooth infinitesimal analysis instead. “The third insight is that over a certain category, these are representable functors. Furthermore, their representatives are related to the algebras of dual numbers, so that smooth infinitesimal analysis may be used.”
“Intuitively, smooth infinitesimal analysis can be interpreted as describing a world in which lines are made out of infinitesimally small segments, not out of points.” (I’m browsing wikipedia here.)
Surreals and games are great fun, but analysis has its points (lines) too.