Skip to main content
added 233 characters in body
Source Link
Will Sawin
  • 148.8k
  • 9
  • 324
  • 563

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 the treea 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 this is the casea 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.

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.

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 the tree 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 this is the case, 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.

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.

added 102 characters in body
Source Link
Will Sawin
  • 148.8k
  • 9
  • 324
  • 563

It depends on howIf you want toonly allow connected graphs, and in particular do not allow ordinal numbers, the answer is no, unless you assign surreal numbers to Hackenbush games. The obvious way is inductively by a means other than induction. 

To do it inductivelyassign 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 the tree 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 this is the case, 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.

It depends on how you want to assign surreal numbers to Hackenbush games. The obvious way is inductively. To do it inductively, 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 the tree 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 this is the case, 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.

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. 

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 the tree 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 this is the case, 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.

Source Link
Will Sawin
  • 148.8k
  • 9
  • 324
  • 563

It depends on how you want to assign surreal numbers to Hackenbush games. The obvious way is inductively. To do it inductively, 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 the tree 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 this is the case, 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.