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.
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:
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, 0≥0
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 ≥,
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
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.
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,
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
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
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.
and, implicitly, u-v means u+(-v).
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.]
A number is a game, [H,L], for which:
x in L and y in Hsatisfy
x≥y.
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],
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.
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.