cantors-attic

Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.

View the Project on GitHub neugierde/cantors-attic

Quick navigation
The upper attic
The middle attic
The lower attic
The parlour
The playroom
The library
The cellar

Sources
Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine

The omega one of chess

Infinite chess is chess played on an infinite edgeless chessboard. Since checkmates, when they occur, do so after finitely many moves, this is an open game and therefore subject to the theory of transfinite game values for open games.

Specifically, the game value (for white) of a position in infinite chess is defined by recursion. The positions with value $0$ are precisely those in which white has already won. If a position $p$ has white to move, then the value of $p$ is $\alpha+1$ if and only if $\alpha$ is minimal such that white may legally move from $p$ to a position with value $\alpha$. If a position $p$ has black to play, where black has a legal move from $p$, and every move by black from $p$ has a value, then the value of $p$ is the supremum of these values.

The term omega one of chess refers either to the ordinal $\omega_1^{\mathfrak{Ch}}$ or to $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, depending respectively on whether one is considering only finite positions or also positions with infinitely many pieces.(Evans & Hamkins, n.d.)

There is an entire natural hierarchy of intermediate concepts between $\omega_1^{\mathfrak{Ch}}$ and $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, corresponding to the various descriptive-set-theoretic complexities of the positions. For example, we may denote by $\omega_1^{\mathfrak{Ch},c}$ the ‘computable’ omega one of chess, which is the supremum of the game values of the computable positions of infinite chess. Similarly, one may define $\omega_1^{\mathfrak{Ch},\text{hyp}}$ to be the supremum of the values of the hyperarithmetic positions and $\omega_1^{\mathfrak{Ch},\Delta^1_2}$ to be the supremum of the $\Delta^1_2$ definable positions, and so on.

Since there are only countably many finite positions, whose game values form an initial segment of the ordinals, it follows that $\omega_1^{\mathfrak{Ch}}$ is a countable ordinal. The next theorem shows more, that $\omega_1^{\mathfrak{Ch}}$ is bounded by the Church-Kleene ordinal $\omega_1^{ck}$, the supremum of the computable ordinals. Thus, the game value of any finite position in infinite chess with a game value is a computable ordinal.

Evans and Hamkins (Evans & Hamkins, n.d.) have proved that the omega one of infinite 3D chess is true $\omega_1$, as large as it can be: $\omega_1^{ {\mathfrak{Ch}_{\!\!\!\!\sim}}_3}=\omega_1$. Meanwhile, there remains a large gap in the best-known bounds for $\omega_1^{\mathfrak{Ch}}$ and $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, with Evans and Hamkins finding (computable) infinite positions having value $\omega^3$ and somewhat beyond.

References

  1. Evans, C. D. A., & Hamkins, J. D. Transfinite game values in infinite chess. http://jdh.hamkins.org/game-values-in-infinite-chess
Main library