First of all, about the Notation:

Conwaygame: Let x,y be sets containing Conwaygames, then the ordered tuple G:=(x,y) is a Conway game. Call the elements of x (the elements of y) the left options of $G$ (the right options of $G$).

Game: By game I mean a specific type of game, namely one with: two players L and R, taking alternating turns $t\in T$, $T$ being the set of turns for the game, beginning with a first turn $t_0$; two relations $\rightarrow_R$ and $\rightarrow_L$, such that a turn can be written as $t\rightarrow_R t'$ for $t,t'\in T$ in the case of player R making a turn for example. The player who cannot make a turn loses the game. Finally, require every game to be of finite length, meaning that there are only finite many turns.


I want to show:

Every Conwaygame is a game.

Let $G=(x,y)$ be a Conwaygame and set $t_0 = G$. Set T equal to the set containing $t_0$ and all the left and right options of $G$. Let $t\rightarrow_R t' ~iff~$ $t'$ right option of $G$, $t\rightarrow_L t' ~iff~$ $t'$ left option of $G$.

My question is about the requirement of finiteness: I've read that if there exists an infinite sequence of turns $t_0 \rightarrow t_1 \rightarrow \dots$, then the axiom of regularity would be contradicted. What is the connection between the existence of such an infinite sequence and the axiom, which says that every nonempty set contains an element which is disjoint to the set itself? (Is it possible to construct the infinite sequence in a way, such that it would be equal to the set $T$?)


This is a good question that is mainly about set theory.

Instead of $G=(x,y)$, I will write things like $G=(G^L,G^R)$. Suppose, for sake of contradiction, that we had a Conwaygame with an infinite sequence of play like $G_0\to_LG_1\to_RG_2\to_L\cdots$. You didn't define how the ordered pair is formed as a set, but whether we use Kuratowski's definition or not, grant me that it's some set with the two components as (possibly layers-deep) elements, possibly several layers deep. This leads to a descending sequence of sets (each one an element of the previous) like $G_0,?,G_0^L,G_1,?,G_1^R,G_2,?,G_2^L,\ldots$. But the axiom of regularity/foundation proves no infinite descending sequence of sets exists.

However, instead of relying on regularity/foundation, the graduate textbook "Combinatorial Game Theory" by Aaron N. Siegel just defines the class of long games inductively using ordinals, so that it doesn't matter if regularity/foundation holds.

Unlike what you have called Conwaygames, "loopy games" are games where play can go on forever. They are defined differently, usually in terms of a version of graphs with two kinds of directed edges for $\to_L$ and $\to_R$. These sorts of games are discussed in Coping with cycles by Aaron N. Siegel.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.