II.5: The Theory of Numbers

Almost all of the results in this post will apply equally well to the non-short case (you can add “transfinite” before “induction” and “recursion” where appropriate). If you’re not comfortable with that, you can just assume everything is finite and you won’t miss much. Also, when I say “positions” I really mean “positions” not “any equivalent position”; it will actually matter for some of these arguments.

In the positions we’ve looked at so far, some play nicely with the order (-5, 1/4, etc.) and others don’t (*3, ±2, etc.). It would be nice if we could find a nice big class of positions that are all comparable with each other (this means that A<B or A=B or A>B; remember that {|}={-1|1} even though they’re different positions). Also, since we’d like to use some sort of induction, it should be “closed under options”: the options (the positions that can be moved to) of something in this class should all be part of this class as well.

You might guess that all we have to do is take the positions that aren’t N-positions, but {0|*} is an L-position with an N-position as an option. A second guess might be that all we have to do is take positions that aren’t N-positions and whose options (and options’ options, etc.) aren’t N-positions, but that still wouldn’t work: {4|2} is one of those, but {4|2}-2=±1+1 is an N-position, so {4|2}‖2! From this sort of example, there’s one restriction that stands out (and it turns out to be the only restriction, in some sense):

1. If a position G has A as a right option and B as a left option and A≤B, then G‖A.
Why? We have to show that G-A is an N-position. If Right goes first, they can move to A-A=0 and win. If Left goes first, they can move to B-A≥0 and they either win because they handed Right a P-position or because they handed Right an L-position. ✓

With this in mind, we make the following recursive definition (since we’re dealing with non-loopy things, recursion is fine):
A position is said to be a “Number” if all of its options are Numbers and none of its right options are less than or equal to any of its left options.
Basically, if something doesn’t have any non-Numbers as options, and isn’t a position where theorem 1. would apply, it’s a Number. There are a few ways of motivating this definition, but they come down to the fact that a whole lot of things you’d want from numbers are satisfied by Numbers.

2. Every integer (as defined earlier) is a Number.
Why? Well, { | }=0 is a number since it has no options at all so there’s nothing that can go wrong. Note that here I’m using 0 to refer to that particular position, not any equivalent position like {*|*}. { 0 | }=1 is a number since 0 is a number and there are no right options to be less than or equal to any of the right options. By induction, the same can be said of {1|}=2, {2|}=3, etc. Similarly for {|0}=-1, {|-1}=-2, etc. ✓

3. The negative of a Number is a Number.
Why? We can prove it by induction. -{ | }={ | } so it’s true for the base case of 0. Now assume, as an inductive hypothesis, that it’s true for all of the options of some Number G={ Gℓ1,Gℓ2,… | Gr1,Gr2,… }. For convenience, I’ve ordered the left and right options; by the axiom of choice I can do this in the infinite case too, but it’s not actually necessary. Then -G={ -Gr1,-Gr2,… | -Gℓ1,-Gℓ2,… } passes the first test for being a Number by hypothesis. Suppose it failed the second test. Then there would be -Gℓn≤-Grm for some naturals (or ordinals) n and m. This implies that Grm≤Gℓn, which would have made G not a Number: contradiction. ✓

4. A Number G is greater than all of its left options and less than all of its right options.
Why? We’ll prove that G is greater than all of its left options; the proof that it’s less than all of its right options is exactly analogous. It’s trivially true for { | }=0. Now assume, as an inductive hypothesis, that it’s true for all of the options of some Number G. Call an arbitrary left option of G “Gℓ”. Then to check G>Gℓ, we need to see that Left can always win G-Gℓ. If Left goes first, they can just move to Gℓ-Gℓ=0 and win. If Right moves first, and they move in G to Gr-Gℓ, then since G is a Number, we know that Gr≰Gℓ so that either Gr>Gℓ (so Gr-Gℓ is an L-position) or Gr‖Gℓ (so Gr-Gℓ is an N-position); either way, Left wins. Finally, suppose Right goes first and moves in Gℓ to G+(-Gℓ)r=G-(Gℓℓ) (by this I mean that a right option of -Gℓ is the negative of a left option of Gℓ). Then Left can move to Gℓ-Gℓℓ, which is >0 by inductive hypothesis, and win. ✓

Incidentally, I think this fact 4. is a big part of the justification for the convention that L-positions are positive, rather than R-positions. If you have a Number like {0,1|3,7}, then the left options are to the left on the “Number line” (they’re lower) and the right options are to the right (they’re greater). Unfortunately, this convention will cause problems with other views of the number line: the positive games that Left can win either have to be on the right or the picture of the number line has to be flipped (this is common in CGT).

5. The sum of two Numbers is a Number.
Why? Recall G+H={Gℓ+H,G+Hℓ|Gr+H,G+Hr} from II.2. As usual, we’ll prove fact 5. by induction, it being clear for 0+0=0. Assume, by inductive hypothesis, that all of the options of G+H are Numbers. We must show that G+H can’t have a right option less than or equal to a left option. Suppose Gr+H≤Gℓ+H where Gr and Gℓ are some particular options of G (elements of sets). Then Gr≤Gℓ which is impossible since G is a Number. Suppose Gr+H≤G+Hℓ. By 4., which we just proved, Hℓ<H, so G+Hℓ<G+H. Also by 4., G<Gr, so G+H<Gr+H. We have G+H<Gr+H≤G+Hℓ<G+H, which is a contradiction. The two cases with things of the form G+Hr are analogous. ✓

For those who know what this means, 0 being a Number and facts 3. and 5. make the Numbers a subGROUP of the proper class of all positions. However, they’re not just any subGROUP:

6. Numbers are never confused with other Numbers. (i.e. Two Numbers are always comparable.)
Why? Suppose G and H are Numbers and G‖H, so that G+(-H)‖0. By facts 3. and 5., G+(-H) is a Number too, so it will suffice to show that no Number is an N-position. Suppose, for sake of contradiction, that G is a Number that’s also an N-position. Then for Left to have a winning move, G must have a left option that’s either a P-position or an L-position. For Right to have a winning move, G must have a right option that’s either a P-position or an R-position. Since P/L-positions are ≥ P/R-positions, all four combinations would contradict the assumption that G is a Number. ✓

Note that in the proof of 4. we considered a hypothetical case where a Number might be an N-position, but we didn’t know it was a Number because we didn’t have 5. yet, and we needed 4. to prove 5. and 5. to prove 6. But anyway, Numbers really do play nicely with the order, as we had hoped from the beginning, and they also play nicely with + and -, but right now they’re just some nebulous bunch of positions with nice properties. For example, we know that {0|1}=1/2 and “LRR”={0|1/2,1}=1/4 are Numbers, but we don’t really know (immediately) what the value of the Number {1+1/2|2+1/4} is.

To really understand the Numbers, we need a series of lemmas, beginning with something which Conway calls the “simplicity rule”. We’ll say that a position H “fits (for G)” if H is greater than all of G’s left options and less than all of G’s right options. In this language, fact 4. says “a Number fits for itself”.

7. Simplicity Rule: If G and H are Numbers, and H fits for G and none of H’s options fit for G, then G=H.
Why? To test that G=H, we need to show that the second player always has a winning strategy in G-H. If Left starts and moves to Gℓ-H, then since H fits, this is negative, and Right wins. Similarly, if Right starts and moves to Gr-H, then since H fits, this is positive, and Left wins. Now suppose Left starts and moves to G-(Hr). Since none of H’s options fit, Hr must not sit in between all of G’s left and right options. Since H is a number, fact 4. gives us that Hr>H. Therefore, there exists a right option of G, call it Gr, such that Gr≤Hr (remember fact 6.). Right moves to Gr-(Hr), which is negative or 0, and wins. The case of Right starting and moving to G-(Hℓ) is analogous. ✓

8. It makes sense to recursively define non-integer dyadic fractions by (2p+1)/2q+1={p/2q | (p+1)/2q}.
Why? Base case: q=0. To verify that we can call {p|p+1} “(2p+1)/2”, we need to check that {p|p+1}+{p|p+1}=2p+1 for integers p. We’ll assume that p≥0 as the p+1≤0 case is analogous. We must verify that the following is a P-position:
{p|p+1}+{p|p+1}-(2p+1)
={p|p+1}+{p|p+1}-{2p | } by definition/proven fact about 2p+1
={p|p+1}+{p|p+1}+{ | -2p} by definition of –
={p+{p|p+1}-(2p+1) | p+1+{p|p+1}-(2p+1), {p|p+1}+{p|p+1}-2p} by definition of +
=0 since 0 fits (use fact 4. on {p|p+1} to see that 0 fits and fact 7. to see that it must therefore equal 0)
(Notice how no “If Left goes first…” type arguments were necessary.)
The induction step is essentially identical in style to this base case argument, except for the fact that everything has the denominator 2q attached. ✓

9. If some dyadic fraction fits for a Number G, then G is equivalent to some dyadic fraction (maybe not the same one).
Why? First, suppose that an integer fits for G. Then suppose that n is the integer of lowest absolute value that fits for G (if both positive integers and negative integers fit, then so does 0). Then either n is 0 and n has no options at all or n has only one option which is of lower absolute value, so it doesn’t fit. By fact 7., G=n. Now suppose that no integer fits but a half-integer (see fact 8.) fits. Then since the options of a half-integer are integers, fact 7. says we’re done. Similarly for quarter-integers, etc. ✓

10. Canonical form for short Numbers: A short Number is equivalent to a dyadic fraction.
Why? From fact 9., it suffices to prove that for a Number G, some dyadic fraction fits. Suppose, for sake of contradiction, that some finite Number is not equivalent to a dyadic fraction. Then by non-loopiness, we can go through the options until we get to a “minimal” one: a Number whose options are all equivalent to dyadic fractions, but is not equivalent to one. By finiteness, there are only finitely many left options and finitely many right options, so any dyadic greater than the greatest left option and lower than the lowest right option should fit. ✓

This was a lot of theory, but it’s important theory because Numbers are very tidy positions, and they’re (in a non-technical sense) sort of orthogonal to the impartial ones. They also still have more nice properties, especially if we don’t require them to be short, in which case they’re generally called (or isomorphic to, depending on who you ask) the “Surreal numbers”, and I’ll talk more about them next time.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s