10
$\begingroup$

Every game of Red-Blue Hackenbush represents a surreal number. Is the converse true? Assuming that it is false, what can be said about the class of surreal numbers that are representable by such games?

For instance, it is obvious that this class is a group under addition, but I can't visualize why it should even be closed under multiplication.

Edit (by request): A game of Red-Blue Hackenbush is a rooted graph G whose edges are either red or blue. It's helpful to think of the surreal value of the game G as the number of moves by which Blue is ahead. The addition operation is simply the disjoint union with roots identified. The additive inverse of a game is found by changing the color of every edge. [Of course, this is only an inverse after passing to equivalence classes, which are surreal numbers.]

A finite path graph beginning with a blue edge at the root represents a positive dyadic rational number, which you find as follows:

  • Each blue edge that appears before the first red edge is worth 1.
  • Beginning with the first red edge, every edge is worth half as much as the edge before.
  • The value of the game is the sum of the values of the blue edges minus the sum of the values of the red edges.

This algorithm is presented by Tom Davis in pp. 11-13 of this paper, where you can find a full explanation of what's going on.

By using graphs with infinitely many edges, we can represent many surreal numbers. If I understand correctly, the game {1|9} (for example) is not literally a Red-Blue Hackenbush game, but it is equivalent to 2={-1,0,1|3}, which is represented by a 3-edge blue path joined at the root to a single red edge.

Is there a surreal number that is not equivalent to any Red-Blue Hackenbush game?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ It would be very kind of you to help us out by showing how the dyadic rationals arise, and also how some various ordinals arise? $\endgroup$
    – Joel David Hamkins
    Commented Aug 26, 2017 at 11:53
  • $\begingroup$ have you read Winning Ways? ONAG? $\endgroup$
    – john mangual
    Commented Aug 27, 2017 at 23:09
  • 2
    $\begingroup$ Are you sure that "Every game of Red-Blue Hackenbush represents a surreal number. " is true in this level of generality (arbitrary graphs)? What about single node with infinitely many red edges? On the other hand if you have a finiteness condition, which is it? $\endgroup$
    – Will Sawin
    Commented Aug 28, 2017 at 6:08
  • $\begingroup$ @WillSawin - A single node with $\omega$ red edges represents the surreal number $-\omega$, etc. $\endgroup$
    – swensonj
    Commented Aug 28, 2017 at 19:14
  • 2
    $\begingroup$ @swensonj But how can that be the case when you can move from that graph to itself? Or what about a node with infinitely many red edges and infinitely many blue edges? $\endgroup$
    – Will Sawin
    Commented Aug 28, 2017 at 19:42

2 Answers 2

Reset to default
4
$\begingroup$

All surreal numbers are representable by a Red–Blue Hackenbush game. This is discussed in On Numbers and Games, although it is left to the reader to fill in the details of the proof for the transfinite case. In Chapter 3 it is explained that every (surreal) number has a sign expansion. Then in Chapter 8 it is explained that the value of a Red–Blue Hackenbush chain is the number whose sign expansion is given by reading off the colors of the edges of the chain from the ground up, interpreting black edges as + and white edges as –. Of course one has to allow chains (or "beanstalks") whose edges are arranged in accordance with the structure of an arbitrary ordinal.

Improve this answer
$\endgroup$
15
  • 1
    $\begingroup$ But this isn't really a rooted graph, right? $\endgroup$
    – Will Sawin
    Commented Aug 28, 2017 at 6:04
  • $\begingroup$ @WillSawin : I'm not sure what you mean by a "rooted graph" but what I described is a valid Red-Blue Hackenbush game. It is a graph in the sense that it consists of vertices and edges, and it is rooted in that there is no ambiguity which vertex is the smallest in the total order that we impose. $\endgroup$
    – Timothy Chow
    Commented Aug 28, 2017 at 18:14
  • 1
    $\begingroup$ The order is not determined by the edge structure as soon as your ordinal is greater than $\omega$. So you would be playing, instead of a game on graphs, a game on some generalized objects. $\endgroup$
    – Will Sawin
    Commented Aug 28, 2017 at 18:37
  • 1
    $\begingroup$ What is the right formal definition of a red-blue Hackenbush game? Having ordinals is fine, but it would seem one would also want well-founded trees, whose adjancency relations are colored. But there is no need to insist on a tree order. Well-founded relations with colored adjacencies? Or what? $\endgroup$
    – Joel David Hamkins
    Commented Aug 29, 2017 at 15:23
  • 1
    $\begingroup$ @TimothyChow It's a bit strange to ask and answer a mathematical question about a mathematical object that is not completely well-defined, but of course you're completely right that Conway has pinned down the definition well enough to answer this question. $\endgroup$
    – Will Sawin
    Commented Aug 29, 2017 at 16:17
2
$\begingroup$

If you only allow connected graphs, and in particular do not allow ordinal numbers, the answer is no, unless you assign surreal numbers to Hackenbush games by a means other than induction.

First it's important to realize that, contrary to what's stated in the question, not every rooted graph with edges colored red and blue corresponds to a surreal number. To assign a surreal number to a game, you can only handle a game if every move takes you to a game already handled, which means you can't handle a game if there is some infinite sequence of legal moves (for either player).

This means a graph that corresponds to a surreal number cannot have infinitely many leaves, infinitely many loops, or infinitely many topological ends. Otherwise we could move infinitely often by chopping off leaves, by cutting loops, or by chopping off ends. (For the third case, you can start by cutting off loops until the graph is a tree, then observing that if a vertex has infinitely many ends among its descendents, at some point oen of its descendents must split in such a way that at least one side doesn't contain all but finitely many of the ends, and you can cut off that side, then repeat).

If a graph does correspond to a surreal number, the graph is a finite graph glued to finitely many infinite paths. This is because after chopping off the finitely many loops, the graph is a tree with finitely many ends, hence finitely many branch points, and there can only be finitely many edges between any two branch points.

Thus, the ordinal for when the game finishes is $< n \omega$, where $n$ is the number of infinite paths - i.e. we can bound the time until we are forced to chop one of the infinite paths, then bound the time until we are forced to chop the next path, etc. a finite number of times.

So you cannot express this way any surreal number that occurs in the generation $\omega^2$ or after.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ In The Book of Numbers, Conway and Guy explicitly say, "Hackenbush chains can be infinite! Indeed, we allow the height of our Hackenbush chains to be any of Cantor's ordinal numbers." As an example they show (among other things) a picture of $\sqrt\omega$, whose order type is $\omega^2$. $\endgroup$
    – Timothy Chow
    Commented Aug 29, 2017 at 0:55
  • $\begingroup$ Will, doesn't your example in the comments still refute the claim that "every red-blue hackenbush game is a surreal number"? Perhaps it would be good to include a discussion of this in your answer. $\endgroup$
    – Joel David Hamkins
    Commented Aug 29, 2017 at 15:22
  • 2
    $\begingroup$ @JoelDavidHamkins I thought I was discussing this. I guess I'll make it more explicit. $\endgroup$
    – Will Sawin
    Commented Aug 29, 2017 at 16:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .