What are Conway's surreal numbers, and how do they make things such as 1/infinity rigorous?

You asked for it...

Here's the basic definition:

A -Real Number- (or just 'Number', for short) is:
An ordered pair of >sets< of real numbers, such that there is no L, an
element of the first set, and no R, an element of the second set, with
L>=R.  We won't need the definition of >= for a while, so leave it be.

Example number 1:  (empty,empty) is a real number.
Why?  Both sets are certainly sets of real numbers.
There is certainly no element of the left set that is >= an element of
the right set.  (Both sets are empty!)

Go back and read the example and the definition most carefully.  Make
sure that the example satisfies the very letter of the definition.  It
will save us both a lot of trouble later.

We like to represent (empty,empty) by the symbol '0'.  ('zero')

Example number 2:  ({0},empty) is a real number.
Why?  Both sets are certainly sets of real numbers.  (I just showed
that 0 is a real number, so {0} is a set of real numbers.)
Is there L in {0} and R in {} with L>=R?  Nope.

We like to represent ({0},empty) with the symbol '1'.  ('one')

Example number 3:  ({0,1}, empty) is a real number.
See previous two examples.

We call this number '2'.  ('two')

------

Will do >= in a little while.  Need to discuss >complexity< first.

0 has complexity 0 by definition.

Any other number has a complexity that is one more than the complexity
of the most complex element of either of its two sets.

So 1 has a complexity of 1, 2 has a complexity of 2.  If ({0},{0})
were a number (we're not sure yet), then it would have a complexity of
1, since the most complex element of either of its two sets is 0, which
has complexity 0.

The important thing to notice here is that for any number A=(Al,Ar)
[Al and Ar are sets of numbers, remember!], every x in Al or Ar has a
complexity strictly less than the complexity of A itself.  Remember
that.

------

About time I finally defined >=.  Enough of this sleazy sidewinding.

Let A and B be two numbers.  Let Al and Ar be A's first and second
sets, respectively.  Let Bl and Br be B's first and second sets,
respectively.

Then we say A>=B  ('A is greater than or equal to B') >unless<

either     1)  There exists b in Bl such that b >= A
    or     2)  There exists a in Ar such that B >= a

Oops!  Recursive definition!  Better prove it's not circular, quick!

To ask about A>=B, we need to know a lot of facts about b>=A and B>=a
for lots of different a's and b's.  Now, by an important fact I told
you to remember, a has complexity strictly less than A's complexity,
and similarly for b and B.  So to compare A and B, we need only know
about comparisons involving numbers at least one of which is strictly
less complex.  To evaluate those comparisons, we must know about the
results of comparisons less complex still, until finally we find
ourselves comparing zero with itself.

Hmm.. we'd better do that, to make sure we can.

Is 0>=0?   Yes, >unless<
either  1)  there exists b in 0l such that b >= 0  (there doesn't; 0l
            is empty)
    or  2)  there exists a in 0r such that 0 >= a  (..... .......; 0r
            .. .....)

So yes, 0>=0, and we didn't have trouble making the comparison.

Another example, slightly less vacuous:

Is 1>=0?  Yes, >unless<
either  1)  there exists b in 0l such that ... (nope!)
    or  2)  there exists a in 1r such that ... (1's second set is empty
            too!)

So 1>=0.  Now, to justify my names, I hope that it turns out that 0>=1
is >not< true.  This, fortunately turns out to be the case:

Is 0>=1?  Yes, >unless<
either  1)  there exists b in 1l such that b >= 0.
  but there does!  b=0 is a choice that does this, so 0 is >not< >= 1.
    or  (moot point)

When we have something like A>=B but not B>=A, we abbreviate and say
that A>B.  So we just proved that 1>0.

When we've shown that A>=B and also B>=A, we say that A=B.  So 0=0.

Is 1=1?  It suffices to show that 1>=1.

Is 1>=1?  Yes, >unless<
either  1)  there exists b in 1l such that b>=1
  the only possible b in 1l is 0, and we know that 0>=1 is not true.
    or  2)  there exists a in 1r such that (nope!  1r is empty!)

So 1>=1 >is< true.

------

Another number:  ({0},{1}).  We already know that both {0} and {1} are
sets of numbers.  We also know there's no L in the first set and R in
the second set with L>=R.  (The only choices are L=0, R=1, and we
showed 0 not >= 1.)

We call this number 1/2.

Exercise:  Show 1 > 1/2 > 0.

That was just so you could see a nonvacuous numberhood proof.

------

Addition:

This is complicated but not difficult, so go slow.

Let A and B be numbers.  The sum (A+B) of A and B is defined this way:

(A+B)'s first set is the set of all x such that
       there exists al in A's first set with     x = al + B
  or   there exists bl in B's first set with     x = A  + bl

(A+B)'s second set is the set of all x such that
       there exists ar in A's second set with     x = ar + B
  or   there exists br in B's second set with     x = A  + br

This definition is recursive, too.  (What did you suspect?  The
definition of -real number- was recursive!)  It works for the same
reason that the definition of >= works:  i.e. to add A and B, we only
need to know about sums of numbers at least one of which has strictly
lower complexity.  Eventually we find that all we need to know about
are sums of 0 and 0.

Hmm.  What is (0+0)?

Well, (0+0)'s first set will have all x such that
   there exists al in 0's first set with x = al + 0
  (There aren't any x that do this, because there are no al in 0's
  first set.)
or there exists bl in 0's first set with x = A  + bl
  (There aren't any x that do this, either, for the same reason.)

Okay, (0+0)'s first set is empty.  How about its second set?

Well, (0+0)'s second set will have all x such that
   there exists ar in 0's second set with x = ar + 0
  (There aren't any x that do this, because there are no ar in 0's
  second set.)
or there exists br in 0's second set with x = A  + br
  (There aren't any x that do this, either, for the same reason.)

So (0+0)'s second set is empty, too.  So (0+0) = (empty,empty) = 0.

Example 2:

What is (1+0)?

Well, (1+0)'s first set will have all x such that
   there exists al in 1's first set with x = al + 0
      [The only al in 1's first set is 0, so the only x that satisfies
       this condition is 0 = 0 + 0.  So 0 will be in (1+0)'s first
       set. ]
or there exists bl in 0's first set with x = A  + bl
      [There aren't any x that do this.]

Okay, (1+0)'s first set is {0}.  How about its second set?

Well, (1+0)'s second set will have all x such that
   there exists ar in 1's second set with x = ar + 0
      [There aren't any x that do this, because there are no ar in 1's
       second set.]
or there exists br in 0's second set with x = A  + br
      [There aren't any x that do this, either, for the same reason.]

So (1+0)'s second set is empty.  So (1+0) = ({0},empty) = 1.

Exercises:
  Calculate (1+1) and show that it's equal to 2.
  Calculate (1/2 + 1/2) and show that it's equal to 1.

------

It can be shown that for any number A, A is strictly less than any
element in its second set and strictly greater than any element in its
left set.  This makes Conway's definition look a lot like Dedekind
cuts, which it is, in fact, a generalization of.  For a proof of this
theorem, see [BCG] I, pp. 23-24.

------

Things get interesting.  Consider:

  omega = ({0,1,2,3,4...},empty)

Which is clearly a real number.  (3, 4, etc. are defined analogously to
0, 1, 2 above.  If you like, 0 = (empty,empty), and n+1 =
({0,1,...n},empty).  Numbers constructed in this way are called
-natural numbers-.  A simple (i.e., trivial) induction proof will show
that all natural numbers are real numbers.)

Since omega >0,  omega >1, omega >2, etc., omega is like infinity.  But
it's the ordinal infinity, not the cardinal one, since there's also

  omega + 1 = ({0,1,2,...,omega},empty)

with omega + 1 > omega.

We can also construct

  1/omega = ({0}, {1/2, 1/4, 1/8, 1/16, ...})

which is greater than 0 but still strictly smaller than each of 1/2,
1/4, 1/8, etc., and so behaves something like an infinitesimal.

It can, in fact, be shown that omega * (1/omega) = 1.

------

I've left out a lot of stuff, of course, but you can ask me if you
want to know, or look it up yourself.  For example, I left out the
definition of multiplication.  I also ignored the really interesting
things that happen when you throw away the condition that members of
the first set may not be >= members of the second set.  (A -game- is
an ordered pair of sets of games, period.)  I skipped the relations
between this theory and the construction of the real numbers by Cauchy
sequences, and glossed over the relations with Dedekind cuts.

Questions, comments, requests, and so on will be happily received.

Oh, and by the way, happy (slightly belated) Leonhard Euler's Birthday
to everyone.  May the next 181 years be as beautiful as the last.

------

References:

[BCG]  Winning Ways for your mathematical plays.  (two volumes)
       Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy.
       Academic Press 1982, London and New York
       ISBN 01-12-091150-7 (vol. I) and 01-12-091102-7 (vol. II)

[C]    On Numbers and Games
       J. H. Conway
       Academic Press 1976, London and New York
       ISBN? Ha.  You were lucky to get the one you got.

[K]    Surreal Numbers
       Donald Knuth
       Addison-Wesley 1974, Reading, Massachusetts
       ISBN ???

-- Mark-Jason Dominus <puswad@pawl.rpi.EDU>