This page depends on a book by John Horton Conway, entitled On Numbers and Games. Just setting the scene, Conway defines a notion of number which beats the socks off anything I'd met previously in a fairly broad mathematical education.

ISBN: 0-12-186350-6
Library of Congress Catalog Card Number: 75-19626
© 1976 Academic Press Inc. (London) Ltd.

What follows is a mere shadow of the great work: I am plundering the notion of number and trying not to get tangled up in why it is such a good notion of number, and the rest ... any more than I can't help, anyway ;^>

This is also largely redundant with a newer page on the same topic.

Games

The following definitions are inductive.

Game = {[H, L]: Game subsumes H, L}. Thus Game is the collection of all pairs of Games' sub-collections. Its members are called games: like any collection, Game subsumes empty, so [empty,empty] is a game, call it 0 (for reasons I'll return to), so {0} is a sub-collection of Game and [empty,{0}], [{0},{0}] and [{0},empty] are also games. The more games we get, the more sub-collections of Game we know, so the more games we can construct. This definition produces lots of games out of thin air ;^>

(For reference: I could use any pair notion. The singleton(H,L) = ({H}:H->L:{L}) has the advantage that it's defined a priori to the natural numbers - and the (surreal) numbers could give me an equally good way of arriving at those, so lists would be defined in terms of numbers. However, I prefer to use a list [H, L]: I'm happy with von Neumann's construction of the natural numbers so I'm not interested in getting them another way. If nothing else, f[0]=L, f[1]=H lets me introduce the list as f and still have easy access to the two crucial collections: for contrast, a singleton s= ({L}:L->H:{H}), has (|s)={L} and (s|)={H}; but we want to talk about members of L and of H, which means talking about the members of the single member of (|s) or (s|) - the extra level of indirection gets rather tedious.)

I'll define a trace of a game, g, to be a list, s, of games for which: either s is empty or; s is (1+n|s:Game) for some n, with s(n) in g(0)&unite;g(1) and (n:s:) a trace of s(n). (If each even s(i) is in s(1+i,0) and each odd one in s(1+i,1), or the same with even and odd swapped, the trace is alternating: this corresponds to playing the game in Conway's discussions.) I'll describe a trace, s, as terminated precisely if s(0) is 0, whose only trace is []: otherwise, I'll describe any trace of s(0) as a valid extension of s. A basic premis of the inductive definitions above is that (any trace of any game is finite and) there is no infinite sequence of non-empty traces each of which is a valid extension of its predecessor. I define a relation simpler on games by: I'll phrase simpler relates x to y as x is simpler than y, so (|simpler:{y}) is the collection of games simpler than y; define x is simpler than [H,L] iff x in H, L, (|simpler:H) or (|simpler:L). The foundation of our inductive definitions is that simpler is a strict partial order - that is, it is transitive and disjoint from its reverse. It is transitive because, by construction, it is the transitive closure of x in y(0)&unite;y(1); x->y. That it is disjoint from its reverse - ie for no x simpler than any y do we find y also simpler than x - follows from the constructibility of games. The last, and most pivotal, property of simpler is then:

Ordering

I define a relation, (Game:≥:Game), inductively as follows: ≥ relates u to x (written u≥x) whenever u, x are games with x not in (|≥:u(1)) and u not in (x(0):≥|). [That is, there is no v in u(1) or y in x(0) with x≥v or y≥u.] Note that this makes u≥x trivial whenever u(1) and x(0) are empty: [empty,L]≥[H,empty] for any sub-collections L, H of Game. In particular, 00

Following Conway because he did it right, I first prove that, for any game g for which each x in either g(1) or g(0) is a fixed point of ≥,

g is not in (|≥g(1))
because each x in g(1) has x≥x hence x in (|≥:g(1)), so no such x has g≥x
g is not in (g(0):≥|)
likewise, each x in g(0) is in (g(0):≥|) so isn't ≥g
g≥g
follows trivially from the above

This suffices to prove that every game is ≥ itself: so ≥ is reflexive and every collection of games is a sub-relation of ≥. The inductive reasoning begins with the observation that the definition doesn't initially give us any members of Game, so every sub-collection of it available for use in building games is a sub-relation of ≥; whenever the sub-collections paired to make a game are sub-relations of ≥, we've just shown that the game constructed is a fixed point of ≥; adding this game into any collection which is a sub-collection of ≥ thus gives a collection which is a sub-relation of ≥, so every constructible collection of games is a sub-relation of ≥. The basis of the inductive definition is that Game is the union of all constructible collections of games: and a union of sub-relations of ≥ is necessarily a sub-relation of ≥. Thus ≥ subsumes Game and, given ≥ = (Game:≥:Game), we obtain (≥|) = Game = (|≥), with ≥ reflexive.

So ≥ is reflexive: is it transitive ? That is, if f≥g≥h, do we always find f≥h ? Well, let C be the union of f(1), f(0), g(1), g(0), h(1) and h(0) and suppose that x≥y≥z implies x≥z whenever at least one of x, y, z is in C and the others are either f, g, h or members of C. (This condition is certainly met for every game given in our definition, since it gives none.) Thus any v in C which is v≥f has v≥f≥g so v≥g: and we know that no u in h(0) has u≥g; so v≥f implies v not in h(0). Likewise, for x in C, h≥x implies g≥x implies x not in f(1). Thus no u in h(0) or y in f(1) has u≥f or h≥y, so f≥h.

Equally, if f≥g≥h but not(f≥h) then either u≥f≥g but not(u≥g) for some u in h(0) or g≥h≥x but not(g≥x) for some x in f(1): so there is no simplest failure of transitivity.

Given games x=[H,L] and g, consider y= [H, L&unite;{g}] and w= [H&unite;{g}, L]. Since g is in y(0) and in w(1), applying the above, w isn't ≥g and g isn't ≥y. We have x not in (x(0):≥|) so not in (w(0):≥|) as w(0) = x(0) and w not in (x(0):≥|) similarly: likewise, y not in (|≥:x(1)) and x not in (|≥:y(1)). Since y(0) subsumes x(0) and w(1) subsumes x(1), we also get y not in (y(0):≥|) so, in particular, not in (x(0):≥|), nor is w in (|≥:x(1)). Thus we have y≥x≥w: further, x≥y unless g≥x and w≥x unless x≥g. Examining q= [H&unite;{g}, L&unite;{g}] we find q isn't ≥g and g isn't ≥q; and q relates to w as y relates to x, and to y as w relates to x, so we have y≥q≥w, with w≥q unless g≥w and q≥y unless y≥g. Note, in particular, that y≥w with both x and q falling between them.

So consider any collection C (for example empty) of games for which x≥y≥z implies x≥z whenever at least one of x,y,z is a member of C with the others being either members of C or pairs of sub-collections of C. We've just seen that the condition at least one of x, y, z is in C can be dropped.

Let D be the union of C with {[H,L]: C subsumes H,L}, the games constructible out of C. We have (D:≥:D) transitive: when x≥y≥z in D we have x≥z. Suppose one of them is t= [H&unite;{g},L] with C subsuming H, L and with g in D: if g is in C t is a member of D, so we still have x≥z. Let s= [H,L], which is in D with s≥t and either t≥s or s≥g. Any n≥t gives n not in (t(0):≥|), so not in (L:≥|), and t not in (|≥:n(1)); so either n≥s≥t or s in (|≥:n(1)). Any t≥m gives m not in (|≥:t(1)), so m not in (|≥:H) and m not ≥g, and t not in (m(0):≥|); so either s≥m or s in (m(0):≥|). Any s≥m gives s not in (m(0):≥|) and m not in (|≥:H) From x≥t≥z with x, z in D For t≥y≥z, we have t not in (y(0):≥|), y not in (|≥:t(1)), hence not in (|≥:H), so either s≥y or s (but not t) in (y(0):≥|),

For any pair, g, of sub-collections of C, let D= C&unite;{g}. A sub-collection of D is either a sub-collection of C or the union of such a one with {g}, and we have: for x≥y≥z with each of x, y, z either a member of D or a pair of its sub-collections

if all are members of D or pairs of sub-collections of C
then x≥z

from the properties of C already given. Otherwise, one of themis a pair of sub-collections of D which is either [H, L&unite;{g}], [H&unite;{g}, L&unite;{g}] or [H&unite;{g}, L] for some sub-collections H, L, of C.

if one, f, has this form, the others being members of C,

take, first, the case [H, L&unite;{g}] = f and observe: any c in C with c≥f has c not in (f(0):≥|) so not in (L:≥|) and f not in (|≥:c(1)). The former gives us c≥[H,L] unless [H,L] in (|≥:c(1)): but [H,L]≥t implies t isn't in (|≥:H)=(|≥:f(1)) and [H,L] isn't in (t(0):≥|), making f≥t unless f in (t(0):≥|) with [H,L] the relevant pair of sub-collections of C, any c in C with c≥f has c not in (f(0):≥|), which subsumes (L:≥|), so c not in (L:≥|). Consequently, c≥[H,L] unless [H,L] in (|≥:c(1)). Now,

if one is a member of D

Now, C was a collection of games for which x≥y≥z implies x≥z whenever at least one of x, y, z is a member of C and the others are either members of C or pairs of sub-collections of C. We've just shown that the same holds without the constraint at least one of x, y, z is a member of C. Take any pair, g, of sub-collections of C and replace C with D= C&union;{g}. Let p,q,r be pairs of sub-collections of D having p≥q≥r: let B be the union of p(1), p(0), q(1), q(0), r(1) and r(0). If g isn't in B, B is a sub-collection of D and we have p≥r as before. Otherwise, consider any x,y,z with x≥y≥z, at least two of x, y, z in B and the other either p, q, r or a member of B. If two of x,y,z are g, x≥z follows either trivially (because x is y or y is z) or from our earlier g≥g (when x and z are g). Otherwise, We know that (D:≥:D) is transitive and that x≥y≥z implies x≥z whenever any two of x, y, z are members of D, the third being either a member of D or a pair of sub-collections of C (note that the cases with more than one instance of g among x, y, z give x≥z either trivially or from our earlier g≥g). Given any collection, C, of games for which (C:≥:C) is transitive and each entry in each game in C is a sub-relation of (C:≤:C) [eg the empty collection], consider any game, g, we can construct out of sub-relations of (C:≤:C). If games e, f in C satisfy e≥f≥g, observe that either e≥g or g≥ some member of e(1) or some member of g(0) is ≥e. Now, any member, x, of C with x≥e has x≥e≥f hence (as e,f in C) x≥f: so, as f≥g so no member of g(0) is ≥f, no x in C with x≥e is in g(0), whose members are all in C, so no member of g(0) is ≥e. Now, e is not ≥ any value in e(1), so any x in C with e≥x is not in e(1) and, in particular, any x with f≥x, hence e≥f≥x so e≥x, isn't in e(1) Now g≥ some member of e(1), with e not ≥ to this value, but e≥f≥g f≥g means neither is g in (|≥:f(1)) nor is f in (g(0):≥|) f is not in (g(0):≥|) but, for each x in f(1), either x in (|≥:g(1)) or g in (x(0):≥|)

For any game g=[H,L], we have g≥g unless: either g is in (|≥:g(1)) or g is in (g(0):≥|) - that is, some y in g(1) or x in g(0) has g≥y or x≥g. Now, so long as each y in g(1) has y≥y, we have y in (|≥:g(1)) so we don't have g≥y: likewise, so long as each x in g(0) has x≥x, x is in (g(0):≥|), so x is not ≥g. Thus, so long as each value of g's entries is a fixed point of ≥, so is g. For something to be demonstrably a game, it must be built up from the definition: which initially gives us no values for g's entries, so all such entries are fixed points of ≥ (because there are none such failing the condition) and the new game, 0, we construct is thus also a fixed point of ≥. But it suffices that every game whose entries' (relevant) values are fixed points of ≥ is itself a fixed point of ≥: from this, we induce that all games are fixed points of ≥, so ≥ is reflexive.

Now, suppose f≥g≥h. Can we show f≥h, that is f isn't in (h(0):≥|) and h isn't in (|≥:f(1)) ? We know f isn't in (g(0):≥|), g isn't in (|≥:f(1)), g isn't in (h(0):≥|) and h isn't in (|≥:g(1)). So no x in g(0), p in f(1), y in h(0) or q in g(1) has x≥f, g≥p, y≥g or h≥q. Not(x≥f) tells us that either x is in (f(0):≥|) or f is in (|≥:x(1)) - likewise: either g in (p(0):≥|) or p is in (|≥:g(1)); either y in (g(0):≥|) or g in (|≥:y(1)), and; either h in (q(0):≥|) or q in (|≥:h(1)).

I define a relation, ≥ with reverse(≥) known as ≤, on games: u≥x unless

either
x is in (|≥:u(1))
or
u is in (x(0):≥|)

This means that, to prove u=[V,U]≥[Y,X]=y we must prove that no v in V has y≥v and no x in X has x≥u: if we can do so, then we can use this knowledge in subsequent proofs of ≥ for games whose elements have u=[V,U] or y=[Y,X] as memebers. Note that when X or V is empty, its branch of the unless condition is vacuously false: when both are empty, we find [empty,U]≥[Y,empty] regardless of U, Y. Although these two do not appear directly in the definition, our knowledge of u≥y, in the non-vacuous cases, depends on knowing whether some x≥u, or some v has y≥v: the former compares (u to members of x(1) and) x to members of u(0), which is U, the latter compares v to members of y(1), which is Y, so this is when U and Y get to influence the outcome.

One can, of course, extract strict orderings > and < from these, for example: x>y iff x≥y but not(y≥x). Likewise, an equivalence may be obtained from: x~y iff x≥y and y≥x; indeed, ~ is ≥&intersect;≤. To show that this is an equivalence, or indeed to make sense of > et al. as orderings, we need ≥ to be transitive: that is, a≥b and b≥c must imply a≥c. With a ≥ b ≥ c, we are given that a is not in (b(0):≥|), b is not in (|≥:a(1)), b is not in (c(0):≥|) and c is not in (|≥:b(1)): transitivity requires that a is not in (c(0):≥|), nor is c in (|≥:a(1)). For numbers, we'll have (n(0):≥:n(1)) empty

Conway's definitions of arithmetic on games becomes

[V,U] + [Y,X]
= [{v+[Y,X], [V,U]+y: v in V, y in Y}, {u+[Y,X], [V,U]+x: u in U, x in X}]

and, implicitly, a+b+c shall mean a+(b+c), 'though we'll eventually show this could as readilly be (a+b)+c: I just need a definitive reading so as to be able to state the definition of multiplication.

-[H,L]
= [{-x: x in L}, {-y: y in H}]

and, implicitly, u-v means u+(-v).

[V,U] . [Y,X]
= [{u.[Y,X] + [V,U].x -u.x, v.[Y,X] + [U,V].y -v.y : u in U, y in Y, v in V, x in X}, {u.[Y,X] + [V,U].y -u.y, v.[Y,X] + [V,U].x - v.x : u in U, y in Y, v in V, x in X}]

Conway merrily proves that these definitions respect the equivalence given above, ~ = ≥&intersect;≤, enabling us to express +, - and . as acting on the equivalence classes. [I am somewhat tempted to define numbers as pairs of equivalence classes, with structure expressed in terms of the games in those classes ... but I'm not sure it'd work so well.]

Numbers

I'm pretty sure I want numbers to be ~-equivalence classes of games, probably ({[H,L]}: ~ |) for some H, L with the properties below but with values of H, L not being numbers but ... maybe H and L are unions of numbers ?

A number is a game, [H,L], for which:

So, let's take a look at what numbers this has given us. The simplest game, [empty,empty] is trivially a number: I'll call it 0 and prove it has some properties that make that mean what we're used to. First of all, notice that {-x: x in empty} is empty, so -0 = [empty,empty] = 0. For any number n with 0.n = [H,L], the members of L and H are of form u.n +0.y -u.y with u a member of empty, so there are no members of L or H: 0.n = [empty,empty] = 0 for every number n. That's two familiar properties of zero.

Now, for any number [H,L],

0+ [H,L]
= [{v+[H,L], 0+y: v in empty, y in H}, {u+[H,L], 0+x: u in empty, x in L}]
= [{0+y: y in H}, {0+x: x in L}]
[H,L] +0
= [{0+y: y in H}, {x+0: x in L}]

If each m in either L or H satisfies 0+m = m = m+0, this gives us 0+ [H,L] = [H,L] = [H,L] +0. [Our induction has no initial members, so we do not need to begin our proof with proving this property for each of them.] For any collection, C, of numbers the numbers we can construct directly out of C are all of form [H,L] with L and H sub-collections of C [and when C is empty, the one possibility 0= [empty,empty] is an identity, ie a collection, namely {empty}, so the collection of numbers C generates is just {0} = {{empty}} which is {{C}} !].

Any collection of numbers must, in the nature of the inductive definition, be constructible from the empty collection (which we inevitably have at out disposal): and such construction can only be done in steps which either discard members from the collection or add ones by the above construction. Discarding members preserves the property m in C implies 0+m=m=m+0, and we have shown that the given construction also perserves it: consequently, every step in the construction of a collection of numbers preserves this property of the empty collection, so every number, m, satisfies 0+m=m=m+0. [In some sense, 'though the collection of all numbers might not be constructible, it is by definition the union of all constructible collections of numbers.]

So, 0 is an additive identity.

Tailpiece: ramblings, mostly.

Now, I'm wondering ... can we define this purely in terms of subrelations of ≤ The problem is the absence of [empty,non-empty] or vice versa among the things that can arise.

≤ is a reflexive relation (on numbers), with reverse(≤) known as ≥. Each x in ≤ is a sub-relation of ≤ whose intersection with ≥ is empty. [Note: as ≤ is reflexive, each x in (|≤) or in (≤|) is a fixed point of ≤, which is what x in ≤ means, and it's easier to write]. We get empty in ≤ trivially. The rest of ≤ then needs inductive definition of form: for u, x in ≤, we have u≤x unless x in (|≤:u) or u in (x:≤|). [That says: x≤ some y in (|u) or some z in (x|) is ≤ u; in which y is a low value of u and z is a high value of x.] This gives a seductively simple form to the induction, but there's a problem with getting anywhere past the presence of empty in ≤. A relation r with either (|r) or (r|) empty is necessarily itself empty: hence so is the other of (r|) and (r|). So we really do need the pair notion.

Written by Eddy.
$Id: number.html,v 1.5 2005-06-26 09:51:27 eddy Exp $