this post is featured

Surreal numbers

The wonderful world of Surreal numbers
in   10 minutes read
The construction of the Surreal numbers.

We've all heard of integers, rationals, reals, even complex numbers, but what on earth are surreal numbers? They are a beautiful way of defining a class of numbers which includes all reals, but also ordinal numbers; i.e. all the different infinities and even infinitesimal numbers. Not only this but we get a full system of arithmetic for all these numbers. Ever wondered what ($\infty-1$) is, or $\sqrt{\infty}$ ? Before we get stuck into that, let's learn some history.

It all started a long, long time ago in a galaxy far, far away (Cambridge in the 1970s). A man by the name of John H. Conway was playing Go, an ancient Chinese game that's very elegant in itself. After much thought, he realised that the later stages of the game could be thought of as the sum of many smaller games. Conway then applied his ideas to other games like Checkers and Dominoes. It seemed that these games were behaving as if they were numbers.

Conway's ideas led him to define a new family of numbers from sets, which were contructed essentially by a series of binary choices. It turned out that this wonderfully simple new system included all the real numbers and more.

In 1972, Conway described his system of numbers to computer scientist Donald Knuth at Stanford. Knuth (creator of the $\TeX$ typesetting system) then went away and wrote a short novelette introducing these numbers. It was the first time for a major mathematical discovery to be published in a work of fiction first. Knuth coined the term surreal numbers; taking “Sur” from the French for “above”. The surreal numbers satisfy the axioms for a field (but the question of whether or not they constitute a field is complicated by the fact that, collectively, they are too large to form a set).

Only two axioms are needed to give you all the surreal numbers. Three more and you get additon and subtraction. One further axiom gives you multiplication. So not only can you get the full structure of the reals from six axioms, but we also get the full power of this arithmetic for the rest of the surreal numbers! So without further ado let's jump into this beautiful landscape.

Rule 1 - Defining what a number is

A number $x$ is an ordered pair of sets of numbers created previously \(x = (X_L,X_R)\text{, where }X_L \not\geq X_R\) I'm using notation where $ A \not\geq B $ means that, for any a in A and b in B, \(a \not\geq b\)

“But what is $\not\geq$?” I hear you say. Well that's the beauty of it – we don't have to define it! On the 1st day there was nothing and so the guy in charge said “Let there be $0$”. We haven't created any numbers yet, so the left and right sets of zero have to be empty! Yes that's it! \(0=(\emptyset,\emptyset) \text{, where $\emptyset$ is the empty set}\) We have to check that $0$ is a number. To do this we must check that each element of the left set of zero is $\not\geq$ each element of the right set. This is trivial because neither set has any elements!

So zero was created on the first day. Now on the second day we can use $0$ as an element in the left and right sets. So we get two new numbers,

\[\begin{eqnarray*} 1=(\{0\},\emptyset) \\ -1=(\emptyset,\{0\}) \\ \end{eqnarray*}\]

It is easy to check that these are both numbers also, because of the empty set again. Now you ask me why the first one is called 1 and the second -1. Here's where we need our second rule.

Rule 2 - defining “$x$ is less than or like $y$”

\[x \leq y \text{ means } X_L \not\geq y \text{ and } x \not\geq Y_R\]

The first thing to prove is that $0$ is less than or like $0$. This also falls through because of the empty set. I bet you've never proved that $0 \leq 0$ before!

We can go on and prove that $-1\leq 0 $ in the same way. If we try and prove that $-1=0$ by then showing $0 \leq -1$ we hit a brick wall (thankfully). As it is equivalent to $0 \not\geq 0$ which we already know is false: \(0 \leq -1 \text{ by definition, means } \emptyset \not\geq -1\text{ and } 0 \not\geq 0\) Thus -1 is strictly less than $0$. Well, it all makes good sense so far. We can carry on this way and on the 3rd day it turns out we get 17 new numbers, although most of them are like each other and we are left with only 4 new ones: 2, -2, $\frac{1}{2}$ and $-\frac{1}{2}$.

Another thing we need – and which is normally assumed when dealing with the reals – is the transitive law. We can prove (yes, I said prove) the transitive law.

To do this we assume the opposite; that we have 3 numbers satisfying the following:

\[x \leq y\text{, } y \leq z \text{ and } x \not\leq z\]

We will call such a triple of numbers, $(x,y,z)$ a naughty triple of numbers. The first two of these mean,

\[\begin{eqnarray*} X_L \not\geq y, x \not\geq Y_R\\ Y_L \not\geq z, y \not\geq Z_R\\ \end{eqnarray*}\]

The last condition for $(x,y,z)$ to be naughty means that at least one of the following is true.

\[\begin{eqnarray*} \text{There is some } x_L \in X_L\text{ such that }x_L \geq z \\ \text{There is some } z_R \in Z_R\text{ such that }x \geq z_R \\ \end{eqnarray*}\]

Case 1: ($x_L \geq z$) This means that $(y,z,x_L)$ are naughty numbers. This is because we have, ($y \leq z$) and ($z \leq x_L$). Then using the initial assumptions about $x$, $y$ and $z$ we also have ($X_L \not\geq y$). Therefore ($y \not\leq x_L$)

Case 2: ($x \geq z_R$) This means that $(z_R,x,y)$ are naughty numbers for similar reasons to case 1. Can you see them?

If we call the day on which a number is created its day number, then in both cases the sum of the three day numbers has decreased, because a number can only be made up of sets of numbers that were previously made. This can't keep going forever because the smallest possible day sum is 3. Basically it's proof by induction on the day sum number: We prove that it is true for a day sum of 3 ($x=y=z=0$). Then we have shown that if it is true for all previous day sum numbers, then it is true for the next one. Now, look at the diagram at the beginning of this article. It makes a little more sense now doesn't it!

We can go on and prove some important things, like the fact that all numbers are related: \(x \not\geq y \rightarrow x \leq y\) and that a number is between its two sets, \(X_L < x < X_R\)

Addition is defined in a similar recursive way to $\leq$.

Rule 3 - Defining addition

\[x+y = ((X_L+y)\cup(Y_L+x),(Y_R+x)\cup(X_R+y))\]

What does this mean? It means that to get the left set of $x+y$, you take every element $x_L$ of $X_L$ and compute $x_L+y$, then do the same with x and y swapped. Then just take all the results of these additions and put them in the left set of $x+y$. For the right set of $x+y$ you just do exactly the same thing but with R's instead of L's.

For example,

\[\begin{eqnarray*} 0+0 = (\emptyset,\emptyset)=0\\ 0+1 = (\{0+0\},\emptyset)=(\{0\},\emptyset)=1\\ \end{eqnarray*}\]

The other two rules you need for addition are really to do with subtraction.

Rule 4 - Defining negative

\[-x = (-X_R,-X_L)\]

Rule 5 - Defining subtraction

\(x-y=x+(-y)\) With these the surreals become a group under addition. However, there's one more subtlety we've so far forgotten about: we have to prove that $x+y$ and $-x$ are both numbers; i.e. that they satisfy Rule 1. For this I'll refer you to Knuth's book.

So far we've only created numbers that have a finite binary representation (and every number with a finite binary representation gets created eventually). To get the remaining (real) numbers we need to keep going until we get to $\aleph_0$ day (the limit as the day number tends to infinity)! On this day all the remaining real numbers were created. To see this we just have to realise that now $X_L$ and $X_R$ can be infinite sets. So any remaining real number $r$ can just be made with a set of binary numbers below $r$ in $R_L$ that converge to $r$, and similarly for $R_H$. Now the rest of the diagram is beginning to make sense… We also get infinity! \(\omega = (\{1,2,3...\},\emptyset)\)

Something else intriguing is created on $\aleph_0$ day. Consider this number, \(\epsilon = (\{0\},\{\frac{1}{2},\frac{1}{4},\frac{1}{8}...\})\) This is greater than $0$ but smaller than every positive fraction (using the result that a number is between each of its two sets)! In fact we get this kind of number around every number that was created before $\aleph_0$ day. On the next day the rest of the reals get numbers like this close to them (i.e. that are closer to them than any other real number).

There is one important subtlety I've glossed over. The day sum argument doesn't work once we pass $\aleph_0$ day. We need a new way of handling induction. Basically, we always showed that if a theorem fails for $x$ then it fails for some element $x_L$ in $X_L$ and then it fails for an element in one of $x_L$'s sets and so on. This gives us a sequence of ancestors of $x$. All we need to do is realise that this sequence cannot be infinite. To see this we could, whenever we create a new number $x$, prove simultaneously that there is no infinite sequence of ancestors of $x$. NICE!

With the final rule, which defines multiplication, we get the full tapestry of the surreal numbers and their arithmetic. We can then prove all kinds of interesting things. Like, \(\epsilon \omega =1\)

Now, as promised, \(\omega-1=(\{1,2,3,...\},\{\omega\})\) and \(\sqrt{\omega}=(\{1,2,3,...\},\{\frac{\omega}{1},\frac{\omega}{2},\frac{\omega}{3},...\})\)

For more information, here are a few very good books:


 Tagged with  •