1
$\begingroup$

A misère game is one where a player with no moves wins. The object of the game is to be presented with a board position in which you cannot do anything.

If we imagine a two-player game where the players take alternate turns, then we can think of a game as being isomorphic to a set of games that we can choose to present to our opponent. This means we can represent any game fitting our criteria as a set.

Suppose the value to the player is $+1$ if they win and $-1$ if the opponent wins.

The game $\{\}$ has value $+1$ because the player cannot make any moves and therefore wins.

The game $\{\{\}\}$ has value $-1$ because the player must pick the game $\{\}$ and give it to the opponent, who then wins.

The game $\{\{\}, \{\{\}\}\}$ has value $+1$ because the player picks the game $\{\{\}\}$ (which has value -1), to give to the opponent.

Does every set in ZFC have a value as a misère game? I think the axiom of regularity, guarantees that there must be some kind of "trace" through any set which has a value in some sense, but I don't know whether it's possible to extend this to a value for the entire set.

$\endgroup$

1 Answer 1

3
$\begingroup$

This is mainly about set theory; the misère game business is a red herring. Note that the outcome of a misère game can be calculated recursively: It's $\mathcal N$, which you called "value $+1$", if there are no moves or there's a move to a $\mathcal P$-position. It's $\mathcal P$, which you called "value $-1$", otherwise. Therefore, all that matters is whether play in the set ends in finite time, so that the induction can get to the base case.

As you suspected, the axiom of regularity/foundation proves no infinite descending sequence of sets exists.

(As an aside, 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.)

$\endgroup$
2
  • $\begingroup$ Is the [combinatorial-game-theory] tag appropriate? I assumed "no" based on your answer and removed it. $\endgroup$ Jan 23, 2021 at 2:54
  • 2
    $\begingroup$ @GregoryNisbet Your question is about combinatorial games, and you need to know something about games to understand my answer, even if the key to the answer involves set theory alone. I wouldn't want someone with the same question not to find your post because the CGT tag were missing. $\endgroup$
    – Mark S.
    Jan 23, 2021 at 2:55

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.