Surreal numbers

Warning: this is very much WORK IN PROGRESS - the scripts do not work yet ;) for instance

Arjen Markus (17 may 2004) Miguel Sofer introduced me to a booklet by the famous Donald E. Knuth, Surreal Numbers - a mathematical novelette. Though I have only read a few chapters sofar, it is rather intriguing: it describes how two ex-students discover a number system due to John Horton Conway. This number system, called the surreal numbers, has two rules for constructing such a number:

Every number corresponds to two sets of previously defined numbers, such that no member of the left set is greater than or equal to any member of the right set.
One number is less than or equal to another if and only if no member of the first number's left set is greater or equal to the second number, and no member of the second number's right set is less than or equal to the first number.

Now this immediately brings up a problem: how to start? This is the clever bit: take the empty set as the left set and the right set of the first number to be defined and call it "0":

   0 = < {} : {} >

where {} is the empty set (a very convenient notation for a Tcler ...).

From this you can define two other numbers:

   1 = < 0 : {} >
  -1 = < {} : 0 >

and you can derive all the classical properties of the ordinary numbers, such as:

   x <= x
   if x <= y and y <= z, then x <= z

Complicated? Abstract? Yes, but the story as told by Knuth is very readable.

It also brought back a different approach to elementary arithmetic: you start with the empty set and build the natural numbers from that. (I agree: mathematics can be weird at times :). But have a look:

We define "0" to be a number corresponding to the empty list
We define a successor function, such that:

     succ 0 = 1, succ 1 = 2, ...

Here is a little Tcl proc to do that:

 proc succ { x } {
    lappend x [list [lindex $x end]]
 }

Lars H: If you instead define

 proc succ {x} {lappend x $x}

then pred is just

 proc pred {x} {lindex $x end}

and comparison becomes

 proc < {x y} {expr {[lsearch -exact $y $x]>=0}}

AM I like that! I had not thought of that solution ... See: Tcl is a perfect language for this sort of things :)

Lars H: Well, it is a pretty standard definition of ordinal numbers (although usually done with sets instead of lists). The goal is to construct them such that "less than" is the same as "element of". That way, the first transfinite ordinal (Aleph_0) is just the set of all finite ordinals. But you won't get that far in Tcl.

AM :) Sure, what I meant about Tcl being ideal for the job, is that it takes very little code to implement this. And the really bizarre/wonderful thing of course is that you construct something from nothing ...

From this function we can define integer addition and a predecessor function:

 proc add { x y {res {}} } {
    if { $x != $res } {
       return [add $x [succ $y] [succ $x]]
    } else {
       return $y
    }
 }

 proc pred { x {res {}} } {
    if { $x == $res } {
       error "No predecessor for the empty list!"
    }
    if { $x != [succ $res] } {
       return [pred $x [succ $res]]
    } else {
       return $res
    }
 }

 #
 # Simple tests
 #
 set 0 {}
 puts "Successor to 0: [succ $0]"
 puts "Successor to 1: [succ [succ $0]]"
 set 1 [succ $0]
 set 2 [succ $1]
 set 3 [succ $2]
 puts "Add 2 and 3: [add $2 $3]"
 puts "Predecessor 3: [pred $3]"

So far, so good. Tcl is ideal (IMHO) for this sort of things: computationally it will not be very efficient (with all these recursions), but the code can hardly get shorter and cleaner, can it?

Back to the story of the two ex-students. Can we turn the two rules into Tcl code? Sure enough:

A number in this system is simply a list of two lists of numbers that have already been defined. A number in the left set (first list element) or the right set (second list element) is again such a list. We build them up recursively.
A comparison of two numbers to check if the one is less than or equal to the other is merely a set of two foreach loops ...

So, here we go!

 set  0 [list {} {}]
 set  1 [list $0 {}]
 set -1 [list {} $0]

 proc CheckNumber {number} {
    #
    # Rudimentary check
    #
    foreach set $number {
       set noelems [lindex $set]
       if { $noelems > 2 } {
          error "Not a valid number"
       }
       if { $noelems == 2 } {
          CheckNumber $number
       }
    }
    return 1 ;# All okay
 }

 proc newNumber {leftset rightset} {
    #
    # Check the numbers in both sets
    #
    foreach l $leftset {
       CheckNumber $l
    }
    foreach r $rightset {
       CheckNumber $r
    }

    list $leftset $rightset
 }

 proc _LE {x y} {
    puts "_LE: $x -- $y"
    if { [lindex $x] == 1 } {
       if { [lindex $y] == 1 } {
          expr {$x <= $y }
       } else {
          set result 1
          foreach r $y {
             if { ! [_LE $x $r] } {
                set result 0
                break
             }
          }
       }
    } else {
       set result 1
       foreach l $x {
          if { ! [_LE $l $y] } {
             set result 0
             break
          }
       }
    }
    return $result
 }

 proc LE {x y} {
    set left  [lindex $x]
    set right [lindex $y]

    if { [_LE $left $y] && ! [_LE $right $x] } {
       return 1
    } else {
       return 0
    } 
 }

With these procedures, we ought to be able to check simple arithmetical properties (this is mainly a sanity check for the moment):

 puts " 0 <= 0? [LE $0 $0]"
 puts " 0 <= 1? [LE $0 $1]"
 puts "-1 <= 1? [LE ${-1} $1]"

For a quick overview of what you can do with them: http://en.wikipedia.org/wiki/Surreal_number

Another source of information is http://mathworld.wolfram.com

and look for surreal numbers.

Category Mathematics