Sporadically through the course of 2006 I have read John Horton Conway's elegant treatise on (the surreal) numbers and (other) games. The copy I have was lent to me by my friend Colin Fine many years ago – now I'll have to find what's become of him, so I can give it back. It was published by the Academic Press (London) in 1976; its Library of Congress Catalog Card Number is 75-19626; and its ISBN number is 0-12-186350-6.
The book is a systematic study of deterministic two-player games, complete
with a full treatment of how to win them (and whether you can). This revolves
around treating games very much like numbers: they can be added and compared
against one another, notably including a zero game (which is a second player
win). The comparison is necessarily a little more complex than we are used to
with numbers; as well as less than, equal and greater than, there is also the
possibility of two games being confused with
one another. The surreal
numbers emerge as a special class of games among which there is no confusion;
these behave exactly like the numbers mathematicians are used to, aside from the
little detail of coping gracefully with a rich vocabulary of infinities and
infinitesimals.
This is a quite excellent book, which I commend to anyone with any interest in mathematics. Conway is not only a brilliant algebraist with a vast intellect: he is also witty and entertaining in his exposition.
Each game is characterized by the sets of positions to which the two players
can move, if it's currently their turn; each position being, in turn, a game
describing the subsequent play. The game is lost by the first player to be
unable to move – i.e. (except in the case of the empty game) won by the
last player to move. The canonical zero game is the empty game, for which
neither player has a move: the two sets are empty. Other games both less than
or equal to zero and greater than or equal to zero are more convoluted zero
games. Conway names the two players L and R and denotes a game x = {
xL | xR }, using xL to denote an arbitrary
position to which L can move and likewise for xR. Thus 0 = {|} and
its existence as a game enables us to define games {0|}, {0|0} and {|0} as
games; the first turns out to fill the rôle of 1 while the last fills that
of −1; whereas {0|0} is confusable with 0, hence not a number. Each
ordinal, n, then emerges as the game whose nL are all the earlier
ordinals (though all but the last can be omitted, when there is a
last
, i.e. when n is not a limit ordinal), with no nR.
Negatives of the ordinals are obtained in exactly the same way, with no L values
and the negatives of all earlier ordinals as R values.
Each diadic rational (that is, fraction whose denominator is a power of two)
can be obtained as the mid-point between two diadic rationals with smaller
denominator: (2.p+1)/2n+1 = {p/2n|(1+p)/2n},
for any integer p and natural n, with the result that the surreal numbers
naturally think in binary. Each classical real number is expressible as the
game whose L values are all smaller diadic rationals and whose R values are all
larger diadic rationals; this is essentially the same construction as a Dedekind
section. Indeed, every number is a sort of generalized Dedekind section: no R
value may be less than or equal to any L value, but there may be a gap between
the upper bound of the L values and the lower bound of the R values, in which
case the number is the simplest
number in the gap – where any
diadic rational is simpler than any other real and diadic rationals with smaller
denominators are simpler than those with (even when in simplest form) larger
denominators.
The criterion for comparison is defined in terms of ≤ and its reverse ≥, with x≥y precisely if: no R value of x is ≤y and x ≤ no L value of y. Equality among games is then defined by the equivalence relation obtained by intersecting ≤ with its reverse, ≥. Strict comparison, < and >, then follow naturally; x<y precisely if x≤y but not x≥y, and so on. A number is exactly a game of which no L value is ≥ any R value. Addition is defined by: the typical L values of x+y are the result of adding either to an L value of the other; and likewise for R values. Negation is defined by: each L value of −x is the negation of an R value of x and likewise with L and R swapped. Multiplication is a little more complex, with typical values of x.y being of form a.y +x.b −a.b with a and b being values of x and y, respectively; for x.y's L values, either both are L values or both are R values; for x.y's R values, one is an L value, the other an R value.
These definitions are, of course, heavily inductive: one can only construct
numbers expressible in terms of numbers constructed previously
, for which
one must already have addressed all questions of comparison, addition and
multiplication. It's necessary to prove that replacing either of x and y in x+y
with a number equal to the one replaced yields a sum equal to x+y; and likewise
for x.y and −x.
None the less, the resulting structure has an elegant simplicity – contrast with classical constructions of the reals, which require one: first to build the naturals; thence to build the rationals as pairs of naturals subject to an equivalence relation that causes a pair to take on the semantics of a ratio; thence to construct the reals as limits (or minimax bounds) of sets (or sequences) of rationals; pausing at some point in this process to extend from only non-negative values to include negatives, via a pair construction subject to equivalence analogous to that used to obtain rationals from whole numbers. (As Conway points out, this sign-extension is best done as late as possible, to simplify the reasoning in the other steps.) At each step in this process, the prior numbers have to be re-created inside the new ones by exhibiting a natural embedding of the old in the new, so that the reals, rationals and naturals each have a distinct entity for 0 (or any other natural), but we are obliged to interpret these entities as interchangeable. With all this complexity we are, furthermore, only provided with finite numbers; where the simplicity of the surreals naturally yields a rich and complex algebra of infinities and infinitesimals.
Conway devotes Part Zero
of the book to a thorough study of the
surreal numbers, demonstrating (inter alia) that they
(or, at least, the reals within them) have all the properties we expect from the
real numbers; he also examines various curious and fascinating sub-fields of the
surreals.
Part Zero ends with a cry for a
Mathematicians' Liberation Movement
in which Conway merrily dispenses with
any objection to his use of notation not wedded to Zermelo-Fränkel set
theory, asserting instead that we should be exploring meta-foundations that'll
let us found our study of any given field in whatever manner suits that field
better, subject to some theorems showing this foundation to satisfy the
meta-foundation's requirements, which would amount to a proof that the chosen
foundation could be expressed faithfully (but possibly clumsily) in terms of any
other foundation (e.g. Z-F) matching the meta-requirements. I delighted in
this; I, too, have liberated myself gladly from the Z-F strait-jacket; and
Conway, the algebraist par excellence, is a most
excellent advocate for such liberation. I only wish we had that meta-foundation
at our disposal, to enable me to clarify how my own semi-foundation matches up
with it: without it, I remain a little unsure about possibly fatal flaws in my
work.
The rest of the book, Part One, is concerned with games in general. Here, Conway is clearly having fun. In particular, he explores the strange and fascinating world of games confusable with zero; and, in particular, those confusable only with infinitesimal games. This is rich and complex territory but of relatively little interest to me, for all that it was fascinating to be led on a tour of it all: the surreals are what I wanted to learn about.
Conway describes the optimal strategies for an assortment of games, notably
the broad class of impartial
games – in which every move open to
either player is open to the other. These are generally equivalent to games of
Nim with suitably chosen piles: in Nim, each position is a (generally finite)
set of (generally finite) piles of discrete things (e.g. match-sticks) and each
move consists of removing a positive number of objects from one pile. The
solution to Nim, for all that it involves learning a peculiar kind of
addition
(instantly familiar to any computer programmer as bitwise xor),
is essentially straight-forward; hence most of the difficulty in any other
impartial game lies in working out how it corresponds to Nim.
It should also be noted that chess is indeed a game in the sense discussed (though not an impartial one); so that, in principle, one may compute its optimal strategy. However, one should bear in mind that doing so would, at least in principle, involve describing the full digraph of possible moves: this is huge, making such an analysis singularly difficult. One can perhaps prove some general theorems which settle the analysis for some broad classes of positions, which may enable one to simplify the full analysis; all the same, the popularity of chess puzzles, often involving few pieces yet requiring much thought to discern who shall win, attests to the vastness of the problem which would remain even after all such simplifications have been exhausted.
Written by Eddy.