On Numbers and Games

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.

The surreals

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.

Other Games

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.

Valid CSSValid HTML 4.01 Written by Eddy.