# Sets as Combinatorial Games

Just a few days ago my seemingly eternal and recurrent fascination for Conway's combinatorial game theory (CGT) & surreal numbers had a recrudescence, so I grabbed this excellent survey, and began reading.

Some old thoughts came to the surface from the archives of my memory. Here they are:

the class $SURREAL$ contains the class $ON$, and ordinals are the spine of $V$, the "universe of sets". So, pushing the analogy, can I say that combinatorial games generalize sets, or conversely sets are (special) combinatorial games?

If the answer is yes, can I even go further, and develop some foundational theory which starts from games, not sets, and then define ordinary sets as those special games?

This question can be broken down into 3 sub-questions:

1. does there exist a treatment of combinatorial games as a first order axiomatic theory, presented without the recourse to sets?

2. what kind of games are ordinary ZF sets? (perhaps "solitaire" games, where the opponent doesn't do anything, or perhaps perfectly symmetric games). In other words, assuming 1) above, which interpretations of ZF are available inside CGT?

3. could one reformulate some familiar constructions of classical set theory in the language of CGT?

Any material, thoughts, refs, on 1) -3)?

PS In this daydreaming I saw a picture of an extended universe where there is a double-cone of sets, V and -V, as in SURREAL there are positive and negative ordinals....

-

I think the answer to the first question (in bold) is, "of course." Just as, quoting On Numbers and Games,

• If $L, R$ are any two sets of numbers, and no member of $L$ is $\geq$ than any member of $R$, then there is a number $\{L|R\}$. All numbers are constructed this way

we can say

• If $L, R$ are any two sets of games, then there is a game $\{L|R\}$. All games are constructed this way.

A good picture of a game is a tree with no infinite branches (so that we can argue by recursion; this corresponds to the phrase "all games are constructed this way", and is analogous to the Foundation axiom of set theory), where each edge is colored either Lavender or Red. If all edges are colored Lavender, say, then we have an ordinary (hereditary) set, and on the class of such games, the relation "$x$ is a member of $y$" is synonymous with "$x$ is an ($L$) option of $y$".

It seems to me that a theory of games is perforce a theory of hereditary sets with not one but two membership relations $\in_L$, $\in_R$. You could of course give a theory of such just the same way you give a theory of sets, and it no more requires a pre-existing class of sets than the theory ZF requires a pre-existing class of sets. (Maybe I'm not exactly sure what you mean by "without recourse to sets".) The theory has two binary predicates $\in_L, \in_R$ where each separate predicate satisfies some axioms; they could be the ZF axioms, or the axioms of any other membership-based set theory. In combinatorial game theory, these two predicates don't interact (at the level of the axioms), but it might be interesting to contemplate theories where they do interact.

Put this way, one can reformulate any construction of set theory in terms of game theory, but I don't see what advantage there would be. My own preferred development of the theory might be along the lines of Algebraic Set Theory (see the book by Joyal and Moerdijk).

-
Todd, great answer! A few observations: to begin with, not so sure it does not have any advantage. Back in the stone age, I studied the so-called topological games, ie games where the players choose an open set (and perhaps somthing else) alternatively. There are very subtle topological ideas which can be expressed in this language (see for instance here: rac.es/ficheros/doc/00232.pdf). Now, are we sure that playing sets cannot give deep insights into their structure? –  Mirco Mannucci Jun 4 '11 at 16:51
As for your axiomatization: of course it works, only thing is, I believe it is not conducive to new insights. I would better think of a set/game as the something that PROJECTS down into its left and right sides, its Jedi moves, and its Sith moves. epsilon is not the proper conceptualization, I think, something like your other suggestion, an algebraic categorical framework maybe better. As for hereditary sets, yes, but we could also consider games that are "circular", namely after a sequence of moves you may come back to the same place. That is beyond conventional CGT, but why not? –  Mirco Mannucci Jun 4 '11 at 16:57
Presumably, there is one way in which $\in_L$ and $\in_R$ do not separately satisfy the ZF axioms, but instead must "interact": the appropriate extensionality axiom would be that two games are equal if they have the same extension under both membership relations; simply having the same extension under one or the other would not suffice. –  Sridhar Ramesh Jun 4 '11 at 17:09
@Sridhar: whoops! Good point; I overlooked that. @Mirco: I like the idea of circular games; sort of like the analogue of sets with the antifoundation axiom. I believe this could be formalized along the lines of algebraic set theory (which I all too briefly mentioned); instead of considering an initial ZF algebra, in the sense of Joyal and Moerdijk, as capturing the cumulative hierarchy, one could consider a terminal ZF algebra instead, and perform arguments by corecursion. I'm pretty sure David Corfield has mentioned something along these lines at the n-Category Cafe. –  Todd Trimble Jun 4 '11 at 22:20
foundation of math, but so what? more than 30 years later cats are all over the places, providing a language (and tools) for almost everything under the sun. Now, do really I believe games are better than cats or sets? Dunno. But my gut feeling tells me that they unravel some basic intuition about math which is neither the "extensional" one (sets), nor the "functional" one (cats). What is it then? I would say, "free actions", in a given environment. Not to mention the fact that games predate both sets and functions in the history of civilization.... –  Mirco Mannucci Jun 7 '11 at 22:10

I wrote a little something about sets as 1-player games here. A set is the collection of moves you can make in a game. Well-foundedness means you always lose. So the only thing you can do is try to put off the inevitable for as long as you can. If you can model the state of a computer program as a game, you can use this to prove termination. As Todd says, there isn't really an advantage to be had by looking at things this way, except it's fun to think of sets in a different way, and I think it might help motivate some parts of set theory to some students who might otherwise find the concepts daunting.

-
Thanks for your EXCELLENT link! When I suggested the slogan "sets are solitaires" in my question I was thinking at something along your lines. By the way, I think your approach is a superb educational approach to set theory, that cuts through the mystique, and gives some "operational" insights into the beautiful world of sets. But I believe that this interpretation is not the only one possible: how about considering a set $X$ as "doubled"? I mean both L and R have the same set of moves, namely X itself. As for being useful, read my answer to Todd –  Mirco Mannucci Jun 4 '11 at 16:48