# Transfinite game values in infinite chess

• C. D. A. Evans and J. D. Hamkins, “Transfinite game values in infinite chess.” (under review)
@ARTICLE{EvansHamkins:TransfiniteGameValuesInInfiniteChess,
AUTHOR = {C. D. A. Evans and Joel David Hamkins},
TITLE = {Transfinite game values in infinite chess},
JOURNAL = {},
YEAR = {},
volume = {},
number = {},
pages = {},
month = {},
note = {under review},
eprint = {1302.4377},
url = {http://jdh.hamkins.org/game-values-in-infinite-chess},
abstract = {},
keywords = {},
source = {},
}

In this article, C. D. A. Evans  and I investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values—the omega one of chess—denoted by $\omega_1^{\mathfrak{Ch}}$ in the context of finite positions and by $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we present specific positions with transfinite game values of $\omega$, $\omega^2$, $\omega^2\cdot k$ and $\omega^3$. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true $\omega_1$.

The article is 38 pages, with 18 figures detailing many interesting positions of infinite chess. My co-author Cory Evans holds the chess title of U.S. National Master.

Let’s display here a few of the interesting positions.

First, a simple new position with value $\omega$.  The main line of play here calls for black to move his center rook up to arbitrary height, and then white slowly rolls the king into the rook for checkmate. For example, 1…Re10 2.Rf5+ Ke6 3.Qd5+ Ke7 4.Rf7+ Ke8 5.Qd7+ Ke9 6.Rf9#.  By playing the rook higher on the first move, black can force this main line of play have any desired finite length.  We have further variations with more black rooks and white king.

Next, consider an infinite position with value $\omega^2$. The central black rook, currently attacked by a pawn, may be moved up by black arbitrarily high, where it will be captured by a white pawn, which opens a hole in the pawn column. White may systematically advance pawns below this hole in order eventually to free up the pieces at the bottom that release the mating material. But with each white pawn advance, black embarks on an arbitrarily long round of harassing checks on the white king.

Here is a similar position with value $\omega^2$, which we call, ”releasing the hordes”, since white aims ultimately to open the portcullis and release the queens into the mating chamber at right. The black rook ascends to arbitrary height, and white aims to advance pawns, but black embarks on arbitrarily long harassing check campaigns to delay each white pawn advance.

Next, by iterating this idea, we produce a position with value $\omega^2\cdot 4$.  We have in effect a series of four such rook towers, where each one must be completed before the next is activated, using the “lock and key” concept explained in the paper.

We can arrange the towers so that black may in effect choose how many rook towers come into play, and thus he can play to a position with value $\omega^2\cdot k$ for any desired $k$, making the position overall have value $\omega^3$.

Another interesting thing we noticed is that there is a computable position in infinite chess, such that in the category of computable play, it is a win for white—white has a computable strategy defeating any computable strategy of black—but in the category of arbitrary play, both players have a drawing strategy. Thus, our judgment of whether a position is a win or a draw depends on whether we insist that players play according to a deterministic computable procedure or not.

The basic idea for this is to have a computable tree with no computable infinite branch. When black plays computably, he will inevitably be trapped in a dead-end.

In the paper, we conjecture that the omega one of chess is as large as it can possibly be, namely, the Church-Kleene ordinal $\omega_1^{CK}$ in the context of finite positions, and true $\omega_1$ in the context of all positions.

Our idea for proving this conjecture, unfortunately, does not quite fit into two-dimensional chess geometry, but we were able to make the idea work in infinite **three-dimensional** chess. In the last section of the article, we prove:

Theorem. Every countable ordinal arises as the game value of an infinite position of infinite three-dimensional chess. Thus, the omega one of infinite three dimensional chess is as large as it could possibly be, true $\omega_1$.

Here is a part of the position. Imagine the layers stacked atop each other, with $\alpha$ at the bottom and further layers below and above. The black king had entered at $\alpha$e4, was checked from below and has just moved to $\beta$e5. Pushing a pawn with check, white continues with 1.$\alpha$e4+ K$\gamma$e6 2.$\beta$e5+ K$\delta$e7 3.$\gamma$e6+ K$\epsilon$e8 4.$\delta$e7+, forcing black to climb the stairs (the pawn advance 1.$\alpha$e4+ was protected by a corresponding pawn below, since black had just been checked at $\alpha$e4).

The overall argument works in higher dimensional chess, as well as three-dimensional chess that has only finite extent in the third dimension $\mathbb{Z}\times\mathbb{Z}\times k$, for $k$ above 25 or so.

# A multiverse perspective on the axiom of constructiblity

• J. D. Hamkins, “A multiverse perpsective on the axiom of constructibility.” , pp. 1-23. (under review)
@INBOOK{Hamkins:MultiverseOnVeqL,
author = {Joel David Hamkins},
editor = {},
title = {A multiverse perpsective on the axiom of constructibility},
chapter = {A multiverse perpsective on the axiom of constructibility},
pages = {1--23},
publisher = {},
year = {},
volume = {},
number = {},
series = {Lecture Note Series, IMS, NUS},
type = {},
edition = {},
month = {},
note = {under review},
abstract = {},
keywords = {},
url = {http://arxiv.org/abs/1210.6541},
eprint = {1210.6541},
doi = {},
}

This article expands on an argument that I made during my talk at the Asian Initiative for Infinity: Workshop on Infinity and Truth, held July 25–29, 2011 at the Institute for Mathematical Sciences, National University of Singapore, and will be included in a proceedings volume that is being prepared for that conference.

Abstract. I argue that the commonly held $V\neq L$ via maximize position, which rejects the axiom of constructibility $V=L$ on the basis that it is restrictive, implicitly takes a stand in the pluralist debate in the philosophy of set theory by presuming an absolute background concept of ordinal. The argument appears to lose its force, in contrast, on an upwardly extensible concept of set, in light of the various facts showing that models of set theory generally have extensions to models of $V=L$ inside larger set-theoretic universes.

In section two, I provide a few new criticisms of Maddy’s proposed concept of restrictive’ theories, pointing out that her concept of fairly interpreted in is not a transitive relation: there is a first theory that is fairly interpreted in a second, which is fairly interpreted in a third, but the first is not fairly interpreted in the third.  The same example (and one can easily construct many similar natural examples) shows that neither the maximizes over relation, nor the properly maximizes over relation, nor the strongly maximizes over relation is transitive.  In addition, the theory ZFC + there are unboundedly many inaccessible cardinals’ comes out as formally restrictive, since it is strongly maximized by the theory ZF + there is a measurable cardinal, with no worldly cardinals above it’.

To support the main philosophical thesis of the article, I survey a series of mathemtical results,  which reveal various senses in which the axiom of constructibility $V=L$ is compatible with strength in set theory, particularly if one has in mind the possibility of moving from one universe of set theory to a much larger one.  Among them are the following, which I prove or sketch in the article:

Observation. The constructible universe $L$ and $V$ agree on the consistency of any constructible theory. They have models of the same constructible theories.

Theorem. The constructible universe $L$ and $V$ have transitive models of exactly the same constructible theories in the language of set theory.

Corollary. (Levy-Shoenfield absoluteness theorem)  In particular, $L$ and $V$ satisfy the same $\Sigma_1$ sentences, with parameters hereditarily countable in $L$. Indeed, $L_{\omega_1^L}$ and $V$ satisfy the same such sentences.

Theorem. Every countable transitive set is a countable transitive set in the well-founded part of an $\omega$-model of V=L.

Theorem. If there are arbitrarily large $\lambda<\omega_1^L$ with $L_\lambda\models\text{ZFC}$, then every countable transitive set $M$ is a countable transitive set inside a structure $M^+$  that is a pointwise-definable model of ZFC + V=L, and $M^+$ is well founded as high in the countable ordinals as desired.

Theorem. (Barwise)  Every countable model of  ZF has an end-extension to a model of ZFC + V=L.

Theorem. (Hamkins, see here)  Every countable model of set theory $\langle M,{\in^M}\rangle$, including every transitive model, is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$. In other words,  there is an embedding $j:M\to L^M$, which is elementary for quantifier-free assertions.

Another way to say this is that every countable model of set theory is a submodel of a model isomorphic to $L^M$. If we lived inside $M$, then by adding new sets and elements, our universe could be transformed into a copy of the constructible universe $L^M$.

(Plus, the article contains some nice diagrams.)

# A question for the mathematics oracle

At the Workshop on Infinity and Truth in Singapore last year, we had a special session in which the speakers were asked to imagine that they had been granted an audience with an all-knowing mathematical oracle, given the opportunity to ask a single yes-or-no question, to be truthfully answered.  These questions will be gathered together and published in the conference volume.  Here is my account.

## A question for the mathematics oracle

### Joel David Hamkins, The City University of New York

Granted an audience with an all-knowing mathematics oracle, we may ask a single yes-or-no question, to be truthfully answered……

I might mischievously ask the question my six-year-old daughter Hypatia often puts to our visitors:  “Answer yes or no.  Will you answer no’?” They stammer, caught in the liar paradox, as she giggles. But my actual question is:

Are we correct in thinking we have an absolute concept of the finite?

An absolute concept of the finite underlies many mathematician’s understanding of the nature of mathematical truth. Most mathematicians, for example, believe that we have an absolute concept of the finite, which determines the natural numbers as a unique mathematical structure—$0,1,2,$ and so on—in which arithmetic assertions have definitive truth values. We can prove after all that the second-order Peano axioms characterize $\langle\mathbb{N},S,0\rangle$ as the unique inductive structure, determined up to isomorphism by the fact that $0$ is not a successor, the successor function $S$ is one-to-one and every set containing $0$ and closed under $S$ is the whole of $\mathbb{N}$. And to be finite means simply to be equinumerous with a proper initial segment of this structure. Doesn’t this categoricity proof therefore settle the matter?

I don’t think so. The categoricity proof, which takes place in set theory, seems to my way of thinking merely to push the absoluteness question for finiteness off to the absoluteness question for sets instead. And surely this is a murkier realm, where already mathematicians do not universally agree that we have a single absolute background concept of set. We know by forcing and other means how to construct alternative set concepts, which seem fully as legitimate and set-theoretic as the set concepts from which they are derived. Thus, we have a plurality of set concepts, and our confidence in a unique absolute set-theoretic background is weakened. How then can we sensibly base our confidence in an absolute concept of the finite on set theory? Perhaps this absoluteness is altogether illusory.

My worries are put to rest if the oracle should answer positively. A negative answer, meanwhile, would raise alarms. A negative answer could indicate, on the one hand, that our understanding of the finite is simply incoherent, a catastrophe, where our cherished mathematical theories are all inconsistent. But, more likely in my view, a negative answer could also mean that there is an undiscovered plurality of concepts of the finite. I imagine technical developments arising that would provide us with tools to modify the arithmetic of a model of set theory, for example, with the same power and flexibility that forcing currently allows us to modify higher-order features, while not providing us with any reason to prefer one arithmetic to another (unlike our current methods with non-standard models). The discovery of such tools would be an amazing development in mathematics and lead to radical changes in our conception of mathematical truth.

Let’s have some fun—please post your question for the oracle in the comment fields below.

# Moving up and down in the generic multiverse

• J. D. Hamkins and B. Löwe, “Moving up and down in the generic multiverse,” ICLA 2013 LNCS, vol. 7750, pp. 139-147, 2013.
@ARTICLE{HamkinsLoewe:MovingUpAndDownInTheGenericMultiverse,
AUTHOR = {Joel David Hamkins and Benedikt L\"owe},
title = {Moving up and down in the generic multiverse},
journal = {ICLA 2013 LNCS},
year = {2013},
volume = {7750},
number = {},
pages = {139--147},
month = {},
note = {},
url = {http://jdh.hamkins.org/up-and-down-in-the-generic-multiverse},
url = {http://arxiv.org/abs/1208.5061},
eprint = {1208.5061},
abstract = {},
keywords = {},
source = {},
}

In this extended abstract we investigate the modal logic of the generic multiverse, which is a bimodal logic with operators corresponding to the relations “is a forcing extension of”‘ and “is a ground model of”. The fragment of the first relation is the modal logic of forcing and was studied by us in earlier work. The fragment of the second relation is the modal logic of grounds and will be studied here for the first time. In addition, we discuss which combinations of modal logics are possible for the two fragments.

The main theorems are as follows:

Theorem.  If  ZFC is consistent, then there is a model of  ZFC  whose modal logic of forcing and modal logic of grounds are both S4.2.

Theorem.  If  the theory “$L_\delta\prec L+\delta$ is inaccessible” is consistent, then there is a model of set theory whose modal logic of forcing is S4.2 and whose modal logic of grounds is S5.

Theorem.  If  the theory “$L_\delta\prec L+\delta$ is inaccessible” is consistent, then there is a model of set theory whose modal logic of forcing is S5 and whose modal logic of grounds is S4.2.

Theorem. There is no model of set theory such that both its modal logic of forcing and its modal logic of grounds are S5.

The current article is a brief extended abstract (10 pages).  A fuller account with more detailed proofs and further information will be provided in a subsequent articl

eprints:  ar$\chi$iv | NI12059-SAS | Hamburg #450

# Every countable model of set theory embeds into its own constructible universe

• J. D. Hamkins, “Every countable model of set theory embeds into its own constructible universe,” , pp. 1-26. (under review)
@ARTICLE{Hamkins:EveryCountableModelOfSetTheoryEmbedsIntoItsOwnL,
author = {Joel David Hamkins},
title = {Every countable model of set theory embeds into its own constructible universe},
journal = {},
year = {},
volume = {},
number = {},
pages = {1--26},
month = {},
note = {under review},
abstract = {},
keywords = {},
source = {},
eprint = {1207.0963},
url = {http://arxiv.org/abs/1207.0963},
}

In this article, I prove that every countable model of set theory $\langle M,{\in^M}\rangle$, including every well-founded model, is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$. Another way to say this is that there is an embedding
$$j:\langle M,{\in^M}\rangle\to \langle L^M,{\in^M}\rangle$$
that is elementary for quantifier-free assertions in the language of set theory.

Main Theorem 1. Every countable model of set theory $\langle M,{\in^M}\rangle$ is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$.

The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading eventually to what I call the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, which is closely connected with the surreal numbers. The proof shows that $\langle L^M,{\in^M}\rangle$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$, and so in fact this model is universal for all countable acyclic binary relations of this rank. When $M$ is ill-founded, this includes all acyclic binary relations. The method of proof also establishes the following, thereby answering a question posed by Ewan Delanoy.

Main Theorem 2. The countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory $\langle M,{\in^M}\rangle$ and $\langle N,{\in^N}\rangle$, either $M$ is isomorphic to a submodel of $N$ or conversely. Indeed, the countable models of set theory are pre-well-ordered by embeddability in order type exactly $\omega_1+1$.

The proof shows that the embeddability relation on the models of set theory conforms with their ordinal heights, in that any two models with the same ordinals are bi-embeddable; any shorter model embeds into any taller model; and the ill-founded models are all bi-embeddable and universal.

The proof method arises most easily in finite set theory, showing that the nonstandard hereditarily finite sets $\text{HF}^M$ coded in any nonstandard model $M$ of PA or even of $I\Delta_0$ are similarly universal for all acyclic binary relations. This strengthens a classical theorem of Ressayre, while simplifying the proof, replacing a partial saturation and resplendency argument with a soft appeal to graph universality.

Main Theorem 3. If $M$ is any nonstandard model of PA, then every countable model of set theory is isomorphic to a submodel of the hereditarily finite sets $\langle \text{HF}^M,{\in^M}\rangle$ of $M$. Indeed, $\langle\text{HF}^M,{\in^M}\rangle$ is universal for all countable acyclic binary relations.

In particular, every countable model of ZFC and even of ZFC plus large cardinals arises as a submodel of $\langle\text{HF}^M,{\in^M}\rangle$. Thus, inside any nonstandard model of finite set theory, we may cast out some of the finite sets and thereby arrive at a copy of any desired model of infinite set theory, having infinite sets, uncountable sets or even large cardinals of whatever type we like.

The proof, in brief:  for every countable acyclic digraph, consider the partial order induced by the edge relation, and extend this order to a total order, which may be embedded in the rational order $\mathbb{Q}$.  Thus, every countable acyclic digraph admits a $\mathbb{Q}$-grading, an assignmment of rational numbers to nodes such that all edges point upwards. Next, one can build a countable homogeneous, universal, existentially closed $\mathbb{Q}$-graded digraph, simply by starting with nothing, and then adding finitely many nodes at each stage, so as to realize the finite pattern property. The result is a computable presentation of what I call the countable random $\mathbb{Q}$-graded digraph $\Gamma$.  If $M$ is any nonstandard model of finite set theory, then we may run this computable construction inside $M$ for a nonstandard number of steps.  The standard part of this nonstandard finite graph includes a copy of $\Gamma$.  Furthermore, since $M$ thinks it is finite and acyclic, it can perform a modified Mostowski collapse to realize the graph in the hereditary finite sets of $M$.  By looking at the sets corresponding to the nodes in the copy of $\Gamma$, we find a submodel of $M$ that is isomorphic to $\Gamma$, which is universal for all countable acyclic binary relations. So every model of ZFC isomorphic to a submodel of $M$.

The article closes with a number of questions, which I record here (and which I have also asked on mathoverflow:  Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?) Although the main theorem shows that every countable model of set theory embeds into its own constructible universe  $$j:M\to L^M,$$ this embedding $j$ is constructed completely externally to $M$ and there is little reason to expect that $j$ could be a class in $M$ or otherwise amenable to $M$.  To what extent can we prove or refute the possibility that $j$ is a class in $M$? This amounts to considering the matter internally as a question about $V$. Surely it would seem strange to have a class embedding $j:V\to L$ when $V\neq L$, even if it is elementary only for quantifier-free assertions, since such an embedding is totally unlike the sorts of embeddings that one usually encounters in set theory. Nevertheless, I am at a loss to refute the hypothesis, and the possibility that there might be such an embedding is intriguing, if not tantalizing, for one imagines all kinds of constructions that pull structure from $L$ back into $V$.

Question 1.  Can there be an embedding $j:V\to L$ when $V\neq L$?

By embedding, I mean an isomorphism from $\langle V,{\in}\rangle$ to its range in $\langle L,{\in}\rangle$, which is the same as a quantifier-free-elementary map $j:V\to L$. The question is most naturally formalized in Gödel-Bernays set theory, asking whether there can be a GB-class $j$ forming such an embedding.  If one wants $j:V\to L$ to be a definable class, then this of course implies $V=\text{HOD}$, since the definable $L$-order can be pulled back to $V$, via $x\leq y\iff j(s)\leq_L j(y)$. More generally, if $j$ is merely a class in Gödel-Bernays set theory, then the existence of an embedding $j:V\to L$ implies global choice, since from the class $j$ we can pull back the $L$-order. For these reasons, we cannot expect every model of ZFC or of GB to have such embeddings. Can they be added generically? Do they have some large cardinal strength? Are they outright refutable?

It they are not outright refutable, then it would seem natural that these questions might involve large cardinals; perhaps $0^\sharp$ is relevant. But I am unsure which way the answers will go. The existence of large cardinals provides extra strength, but may at the same time make it harder to have the embedding, since it pushes $V$ further away from $L$. For example, it is conceivable that the existence of $0^\sharp$ will enable one to construct the embedding, using the Silver indiscernibles to find a universal submodel of $L$; but it is also conceivable that the non-existence of $0^\sharp$, because of covering and the corresponding essential closeness of $V$ to $L$, may make it easier for such a $j$ to exist. Or perhaps it is simply refutable in any case. The first-order analogue of the question is:

Question 2.  Does every set $A$ admit an embedding $j:\langle A,{\in}\rangle \to \langle L,{\in}\rangle$?  If not, which sets do admit such embeddings?

The main theorem shows that every countable set $A$ embeds into $L$. What about uncountable sets? Let us make the question extremely concrete:

Question 3. Does $\langle V_{\omega+1},{\in}\rangle$ embed into $\langle L,{\in}\rangle$? How about $\langle P(\omega),{\in}\rangle$ or $\langle\text{HC},{\in}\rangle$?

It is also natural to inquire about the nature of $j:M\to L^M$ even when it is not a class in $M$. For example, can one find such an embedding for which $j(\alpha)$ is an ordinal whenever $\alpha$ is an ordinal?  The embedding arising in the proof of the main theorem definitely does not have this feature.

Question 4. Does every countable model $\langle M,{\in^M}\rangle$ of set theory admit an embedding $j:M\to L^M$ that takes ordinals to ordinals?

Probably one can arrange this simply by being a bit more careful with the modified Mostowski procedure in the proof of the main theorem.  And if this is correct, then numerous further questions immediately come to mind, concerning the extent to which we ensure more attractive features for the embeddings $j$ that arise in the main theorems. This will be particularly interesting in the case of well-founded models, as well as in the case of $j:V\to L$, as in question , if that should be possible.

Question 5. Can there be a nontrivial embedding $j:V\to L$ that takes ordinals to ordinals?

Finally, I inquire about the extent to which the main theorems of the article can be extended from the countable models of set theory to the $\omega_1$-like models:

Question 6. Does every $\omega_1$-like model of set theory $\langle M,{\in^M}\rangle$ admit an embedding $j:M\to L^M$ into its own constructible universe? Are the $\omega_1$-like models of set theory linearly pre-ordered by embeddability?

# Singular cardinals and strong extenders

• A. W. Apter, J. Cummings, and J. D. Hamkins, “Singular cardinals and strong extenders,” Central European Journal of Mathematics. (to appear)
@ARTICLE{ApterCummingsHamkins:SingularCardinalsAndStrongExtenders,
author = {Arthur W. Apter and James Cummings and Joel David Hamkins},
title = {Singular cardinals and strong extenders},
journal = {Central European Journal of Mathematics},
year = {},
volume = {},
number = {},
pages = {},
month = {},
url = {http://arxiv.org/abs/1206.3703},
eprint = {1206.3703},
note = {to appear},
abstract = {},
keywords = {},
source = {},
}

Brent Cody asked the question whether the situation can arise that one has an elementary embedding $j:V\to M$ witnessing the $\theta$-strongness of a cardinal $\kappa$, but where $\theta$ is regular in $M$ and singular in $V$.

In this article, we investigate the various circumstances in which this does and does not happen, the circumstances under which there exist a singular cardinal $\mu$ and a short $(\kappa, \mu)$-extender $E$ witnessing “$\kappa$ is $\mu$-strong”, such that $\mu$ is singular in $Ult(V, E)$.

# Is the dream solution of the continuum hypothesis attainable?

• J. D. Hamkins, “Is the dream solution of the continuum hypothesis attainable?,” , pp. 1-10. (under review)
@ARTICLE{Hamkins:IsTheDreamSolutionToTheContinuumHypothesisAttainable,
AUTHOR = {Joel David Hamkins},
TITLE = {Is the dream solution of the continuum hypothesis attainable?},
JOURNAL = {},
YEAR = {},
volume = {},
number = {},
pages = {1--10},
month = {},
note = {under review},
abstract = {},
keywords = {},
source = {},
eprint = {1203.4026},
url = {http://arxiv.org/abs/1203.4026},
}

Many set theorists yearn for a definitive solution of the continuum problem, what I call a  dream solution, one by which we settle the continuum hypothesis (CH) on the basis of a new fundamental principle of set theory, a missing axiom, widely regarded as true, which determines the truth value of CH.  In an earlier article, I have described the dream solution template as proceeding in two steps: first, one introduces the new set-theoretic principle, considered obviously true for sets in the same way that many mathematicians find the axiom of choice or the axiom of replacement to be true; and second, one proves the CH or its negation from this new axiom and the other axioms of set theory. Such a situation would resemble Zermelo’s proof of the ponderous well-order principle on the basis of the comparatively natural axiom of choice and the other Zermelo axioms. If achieved, a dream solution to the continuum problem would be remarkable, a cause for celebration.

In this article, however, I argue that a dream solution of CH has become impossible to achieve. Specifically, what I claim is that our extensive experience in the set-theoretic worlds in which CH is true and others in which CH is false prevents us from looking upon any statement settling CH as being obviously true. We simply have had too much experience by now with the contrary situation. Even if set theorists initially find a proposed new principle to be a natural, obvious truth, nevertheless once it is learned that the principle settles CH, then this preliminary judgement will evaporate in the face of deep experience with the contrary, and set-theorists will look upon the statement merely as an intriguing generalization or curious formulation of CH or $\neg$CH, rather than as a new fundamental truth. In short, success in the second step of the dream solution will inevitably undermine success in the first step.

This article is based upon an argument I gave during the course of a three-lecture tutorial on set-theoretic geology at the summer school Set Theory and Higher-Order Logic: Foundational Issues and Mathematical Development, at the University of London, Birkbeck in August 2011.  Much of the article is adapted from and expands upon the corresponding section of material in my article The set-theoretic multiverse.

# The mate-in-n problem of infinite chess is decidable

• D. Brumleve, J. D. Hamkins, and P. Schlicht, “The mate-in-n problem of infinite chess is decidable,” , S. Cooper, A. Dawar, and B. Löwe, Ed., Springer Berlin Heidelberg, 2012, vol. 7318, pp. 78-88.
@incollection{BrumleveHamkinsSchlicht:TheMateInNProblemOfInfiniteChessIsDecidable,
year={2012},
isbn={978-3-642-30869-7},
booktitle={How the World Computes},
volume={7318},
series={Lecture Notes in Computer Science},
editor={Cooper, S.Barry and Dawar, Anuj and Löwe, Benedikt},
doi={10.1007/978-3-642-30870-3_9},
title={The Mate-in-n Problem of Infinite Chess Is Decidable},
url={http://dx.doi.org/10.1007/978-3-642-30870-3_9},
publisher={Springer Berlin Heidelberg},
author={Brumleve, Dan and Hamkins, Joel David and Schlicht, Philipp},
pages={78-88},
eprint = {1201.5597},
}

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers—*there is a move for white, such that for every black reply, there is a countermove for white*, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth.

Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\rm chess}$ is not known.

Richard Stanley’s question on mathoverflow: Decidability of chess on infinite board?