Infinite chess: the mate-in-n problem is decidable and the omega-one of chess, Cambridge, March 2012

Posted on March 22, 2012 by Joel David Hamkins

I have just taken up a visiting fellow position at the Isaac Newton Institute for mathematical sciences in Cambridge, UK, where I am participating in the program Syntax and Semantics: the legacy of Alan Turing. I was asked to give a brief introduction to some of my current work, and I chose to speak about infinite chess.

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- $𝑛$ 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 $𝑛$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2 𝑛$ 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, in joint work with Dan Brumleve and Philipp Schlicht, confirming a conjecture of myself and C. D. A. Evans, we establish that the mate-in- $𝑛$ problem of infinite chess is computably decidable, uniformly in the position and in $𝑛$ . Furthermore, there is a computable strategy for optimal play from such mate-in- $𝑛$ positions. The proof proceeds by showing that the mate-in- $𝑛$ 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 $𝜔 c h e s s 1$ is not known. I will also discuss recent joint work with C. D. A. Evans and W. Hugh Woodin showing that the omega one of infinite positions in three-dimensional infinite chess is true $𝜔 1$ : every countable ordinal is realized as the game value of such a position.

article | slides | streaming video | program of abstracts

Is the dream solution of the continuum hypothesis attainable?

Posted on March 20, 2012 by Joel David Hamkins

[bibtex key=Hamkins2015:IsTheDreamSolutionToTheContinuumHypothesisAttainable]

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 hierarchy of equivalence relations on $ℕ$ under computable reducibility, New York March 2012

Posted on March 10, 2012 by Joel David Hamkins

I gave a talk at the CUNY MAMLS conference March 9-10, 2012 at the City University of New York.

This talk will be about a generalization of the concept of Turing degrees to the hierarchy of equivalence relations on $ℕ$ under computable reducibility. The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on $ℝ$ under Borel reducibility, a theory which has led to deep insights on the complexity hierarchy of classification problems arising throughout mathematics. In the computable analogue, we consider the corresponding reduction notion in the context of Turing computability for relations on $ℕ$ . Specifically, one relation $𝐸$ is computably reducible to another, $𝐹$ , if there is a computable function $𝑓$ such that $𝑥 𝐸 𝑦$ if and only if $𝑓 (𝑥) 𝐹 𝑓 (𝑦)$ . This is a very different concept from mere Turing reducibility of $𝐸$ to $𝐹$ , for it sheds light on the comparative difficulty of the classification problems corresponding to $𝐸$ and $𝐹$ , rather than on the difficulty of computing the relations themselves. In particular, the theory appears well suited for an analysis of equivalence relations on classes of c.e. structures, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In this regard, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remain. This is joint work with Sam Coskey and Russell Miller.

article | slides | abstract on conference web page | related talk Florida MAMLS 2012 | Sam’s post on this topic

Isaac Newton Institute of Mathematical Sciences, Cambridge, Visiting Fellow, 2012

Posted on March 6, 2012 by Joel David Hamkins

I held a Visiting Fellow position at the Isaac Newton Institute for Mathematical Sciences in Cambridge during March — April and June 2012, where I participated in the workshop on Logical Approaches to Barriers in Complexity II, March 26-30, 2012, a part of the program Semantics and Syntax: A Legacy of Alan Turing.

This visit was extremely productive mathematically for me, and it was at the Isaac Newton Institute that I proved the main part of my theorems on embeddings of countable models of set theory.

Panel discussion on the unity and diversity of logic, New York, March 2012

Posted on February 22, 2012 by Joel David Hamkins

As a part of the Spring 2012 Mid-Atlanatic Mathematical Logic Seminar, to be held March 9-10, 2012 at the CUNY Graduate Center, I shall participate in the following panel discussion.

Panel discussion: The unity and diversity of logic

Abstract. The field of mathematical logic sometimes seems to be fracturing into ever-finer subdisciplines, with little connection between them, and many logicians now identify themselves by their specific subdiscipline. On the other hand, certain new themes have appeared which tend to unify the diverse discoveries of the many subdisciplines. This discussion will address these trends and ask whether one is likely to dominate the other in the long term. Will logic remain a single field, or will it split into many unrelated branches?

The panelists will be Prof. Gregory Cherlin, myself, Prof. Rohit Parikh, and Prof. Jouko Väänänen, with the discussion moderated by Prof. Russell Miller. Questions and participation from the audience are encouraged.

As preparation for this panel discussion, please suggest points or topics that might brought up at the panel discussion, by posting suitable comments below. Perhaps we’ll proceed with our own pre-discussion discussion here!

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

Posted on January 27, 2012 by Joel David Hamkins

[bibtex key=BrumleveHamkinsSchlicht2012:TheMateInNProblemOfInfiniteChessIsDecidable]

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- $𝑛$ 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 $𝑛$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2 𝑛$ 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- $𝑛$ problem of infinite chess is computably decidable, uniformly in the position and in $𝑛$ . Furthermore, there is a computable strategy for optimal play from such mate-in- $𝑛$ positions. The proof proceeds by showing that the mate-in- $𝑛$ 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- $𝑛$ 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 $𝜔 ℭ 𝔥 1$ is not known.

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

Climb into Cantor's attic

Posted on January 4, 2012 by Joel David Hamkins

Please climb into Cantor’s attic, where you will find infinities of all sizes. The site aims to be a comprehensive resource for the mathematical logic community, containing information about all mathematical concepts of infinity, including especially detailed information about the large cardinal hierarchy, as well as information about all other prominent specific ordinals and cardinals in mathematical logic and set theory, and how they are related. We aim that Cantor’s attic will be the definitive on-line home of these various notions. Please link to us whenever you need to link to a large cardinal or ordinal concept.

Cantor’s attic is the result of a community effort, and you can help improve this resource by joining our community. We welcome contributions from knowledgeable experts in mathematical logic. Please come and make a contribution! You can create new pages, edit existing pages, add references, all using the same mediawiki software that powers wikipedia. Further information about how to help is available at the Cantor’s attic community portal.

Cantor’s attic was founded in December 2011 by myself and Victoria Gitman. We have only just begun, and it is a good time to get involved. Feel free to contact me for advice or specific suggestions about how you might contribute.

Philosophy of set theory, Fall 2011, NYU PH GA 1180

Posted on November 12, 2011 by Joel David Hamkins

I taught a course in Fall 2011 at NYU entitled Topics in Logic: set theory and the philosophy of set theory, aimed at graduate students in philosophy and others who want to gain greater understanding of some of the set-theoretic topics central to work in the philosophy of set theory. The course began with a review of the mathematical ideas, including a presentation of large cardinals, strong axioms of infinity and their associated elementary embeddings of the universe, and forcing, emphasizing the connection with the Boolean ultrapower and Boolean-valued models, but discussing the alternative formalizations. The second part of the course covers some of the philosophical literature, including what it means to accept or believe mathematical axioms, whether mathematics needs new axioms, the criteria one might use when adopting new axioms, and the question of pluralism and categoricity in set theory.

Here is a partial list of our readings:

1. Mathematical background.

Thomas Jech, Set Theory.
Akihiro Kanamori, The Higher Infinite.
Timothy Chow, “A beginner’s guide to forcing,” from Contemporary Mathematics. http://arxiv.org/abs/0712.1320. (for mathematical review)
My rather sloppy Tutorial lecture notes.
My article Well-founded Boolean ultrapowers as large cardinals embeddings, with Daniel Seabold, which introduces the fundamentals of the Boolean ultrapower.
My lecture notes “An introduction to the Boolean ultrapower” for the Young Set Theorists workshop in Bonn, 2011.

2. Penelope Maddy, “Believing the axioms”, in two parts. JSL vols. 52 and 53. Part 1, Part 2

3. Chris Freiling, “Axioms of Symmetry: throwing darts at the real number line,”
JSL, vol. 51. http://www.jstor.org/stable/2273955

4. W. N. Reinhardt, “Remarks on reflection principles, large cardinals, and elementary embeddings,” Proceedings of Symposia in Pure Mathematics, Vol 13, Part II, 1974, pp. 189-205.

5. Donald Martin, “Multiple universes of sets and indeterminate truth values,” Topoi 20, 5–16, 2001.

6. Hartry Field, “Which undecidable mathematical sentences have determinate truth values,” as reprinted in his book Truth and the Absence of Fact, Oxford University Press, 2001.

7. A brief selection from Marc Balaguer, Platonism and Anti-Platonism in Mathematics, Oxford University Press, 1998, describing the plenitudinous Platonism position.

8. Daniel Isaacson, “The reality of mathematics and the case of set theory,” 2007.

9. J. D. Hamkins, “The set-theoretic multiverse,” to appear in the Review of Symbolic Logic.

10. Solomon Feferman, Does mathematics need new axioms? Text of an invited AMS-MAA joint meeting, San Diego, January, 1997.

11. Solomon Feferman, Is the continuum hypothesis a definite mathematical problem? Draft article for the Exploring the Frontiers of Independence lecture series at Harvard University, October, 2011.

12. Peter Koellner, Feferman On the Indefiniteness of CH, a commentary on Feferman’s EFI article.

13. Interpretability of theories, the interpretability degrees and Orey sentences in set theory and arithmetic. Some of the basic material is found in Per Lindström’s book Aspects of Incompleteness, available at http://projecteuclid.org/euclid.lnl/1235416274, particularly chapter 6, and some later chapters.

14. Haim Gaifman, “On ontology and realism in mathematics,” to appear in the Review of Symbolic Logic (special issue connected with the NYU philosophy of mathematics conference 2009).

15. Saharon Shelah, “Logical dreams,” Bulletin of the AMS, 40(20):203–228, 2003. (Pre-publication version available at:http://arxiv.org/abs/math.LO/0211398)

16. For mathematical/philosophical amusement, Philip Welch and Leon Horsten, “The aftermath.”

It’s been a great semester!

Inner models with large cardinal features usually obtained by forcing

Posted on November 3, 2011 by Joel David Hamkins

[bibtex key=ApterGitmanHamkins2012:InnerModelsWithLargeCardinals]

We construct a variety of inner models exhibiting features usually obtained by forcing over universes with large cardinals. For example, if there is a supercompact cardinal, then there is an inner model with a Laver indestructible supercompact cardinal. If there is a supercompact cardinal, then there is an inner model with a supercompact cardinal $𝜅$ for which $2 𝜅 = 𝜅 +$ , another for which $2 𝜅 = 𝜅 + +$ and another in which the least strongly compact cardinal is supercompact. If there is a strongly compact cardinal, then there is an inner model with a strongly compact cardinal, for which the measurable cardinals are bounded below it and another inner model $𝑊$ with a strongly compact cardinal $𝜅$ , such that $𝐻 𝑉 𝜅 + \subseteq 𝐻 𝑂 𝐷 𝑊$ . Similar facts hold for supercompact, measurable and strongly Ramsey cardinals. If a cardinal is supercompact up to a weakly iterable cardinal, then there is an inner model of the Proper Forcing Axiom and another inner model with a supercompact cardinal in which GCH+V=HOD holds. Under the same hypothesis, there is an inner model with level by level equivalence between strong compactness and supercompactness, and indeed, another in which there is level by level inequivalence between strong compactness and supercompactness. If a cardinal is strongly compact up to a weakly iterable cardinal, then there is an inner model in which the least measurable cardinal is strongly compact. If there is a weakly iterable limit $𝛿$ of $< 𝛿$ -supercompact cardinals, then there is an inner model with a proper class of Laver-indestructible supercompact cardinals. We describe three general proof methods, which can be used to prove many similar results.

The hierarchy of equivalence relations on $ℕ$ under computable reducibility, Florida, 2012

Posted on October 21, 2011 by Joel David Hamkins

This is a talk at the Alan Turing centenary conference at Florida Atlantic University, January 13-15, 2012, sponsored by MAMLS, and part of the 2012 Alan Turing Year of events in celebration of the one hundredth year of the birth of Alan Turing.

This talk will be about a recent generalization of the concept of Turing degrees to the hierarchy of equivalence relations on $ℕ$ under computable reducibility. The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on $ℝ$ under Borel reducibility, a theory which has led to deep insights on the complexity hierarchy of classification problems arising throughout mathematics. In our computable analogue, we consider the corresponding reduction notion in the context of Turing computability for relations on $ℕ$ . Specifically, one relation $𝐸$ is computably reducible to another, $𝐹$ , if there is a computable function $𝑓$ such that $𝑥 𝐸 𝑦$ if and only if $𝑓 (𝑥) 𝐹 𝑓 (𝑦)$ . This is a very different concept from mere Turing reducibility of $𝐸$ to $𝐹$ , for it sheds light on the comparative difficulty of the classification problems corresponding to $𝐸$ and $𝐹$ , rather than on the difficulty of computing the relations themselves. In particular, the theory appears well suited for an analysis of equivalence relations on classes of c.e. structures, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In this regard, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remain. This is joint work with Sam Coskey and Russell Miller.

Article | Sam’s post on this topic | Slides

What is the theory ZFC without power set?

Posted on October 13, 2011 by Joel David Hamkins

[bibtex key=”GitmanHamkinsJohnstone2016:WhatIsTheTheoryZFC-Powerset?”]

This is joint work with Victoria Gitman and Thomas Johnstone.

We show that the theory ZFC-, consisting of the usual axioms of ZFC but with the power set axiom removed-specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well-ordered-is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context. For example, there are models of ZFC- in which $𝜔 1$ is singular, in which every set of reals is countable, yet $𝜔 1$ exists, in which there are sets of reals of every size $ℵ 𝑛$ , but none of size $ℵ 𝜔$ , and therefore, in which the collection axiom sceme fails; there are models of ZFC- for which the Los theorem fails, even when the ultrapower is well-founded and the measure exists inside the model; there are models of ZFC- for which the Gaifman theorem fails, in that there is an embedding $𝑗 : 𝑀 \to 𝑁$ of ZFC- models that is $Σ 1$ -elementary and cofinal, but not elementary; there are elementary embeddings $𝑗 : 𝑀 \to 𝑁$ of ZFC- models whose cofinal restriction $𝑗 : 𝑀 \to ⋃ 𝑗 ‶ 𝑀$ is not elementary. Moreover, the collection of formulas that are provably equivalent in ZFC- to a $Σ 1$ -formula or a $Π 1$ -formula is not closed under bounded quantification. Nevertheless, these deficits of ZFC- are completely repaired by strengthening it to the theory $Z F C -$ , obtained by using collection rather than replacement in the axiomatization above. These results extend prior work of Zarach.

See Victoria Gitman’s summary post on the article

The Logic Bike

Posted on October 6, 2011 by Joel David Hamkins

In 2004 I was a Mercator Gastprofessor at Universität Mün ster, Institut für mathematische Logik und Grundlagenforschung, where I was involved with interesting mathematics, particularly with Ralf Schindler and Gunter Fuchs, who is now at CUNY.

At that time, I had bought a bicycle, and celebrated Münster’s incredible bicycle culture, a city where the number of registered bicycles significantly exceeds the number of inhabitants. I have long thought that Münster gets something fundamentally right about how to live in a city with bicycles, and the rest of the world should take note. I am pleased to say that in recent years, New York City is becoming far more bicycle-friendly, although we don’t hold a candle to Münster.

At the end of my position, I donated the bicycle to the Logic Institute, where it has now become known as the Logic Bike, and where I have recently learned that over the years it has now been ridden by a large number of prominent set theorists; it must be one of the few bicycles in the world to have its own web page!

Set theory: universe or multiverse? Vienna, 2011

Posted on September 28, 2011 by Joel David Hamkins

This talk was held as part of the Logic Cafe series at the Institute of Philosophy at the University of Vienna, October 31, 2011.

A traditional Platonist view in set theory, what I call the universe view, holds that there is an absolute background concept of set and a corresponding absolute background set-theoretic universe in which every set-theoretic assertion has a final, definitive truth value. On the multiverse view, in constrast, there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe, and a corresponding pluralism of set-theoretic truths. In this talk, after framing the debate, I shall argue that the multiverse position explains our experience with the enormous diversity of set-theoretic possibilities, a phenomenon that challenges the universe view. In particular, I shall argue that the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for.

Slides | Article | Logic Cafe, Uni. Wien

Must there be non-definable numbers? Pointwise definability and the math-tea argument, KGRC, Vienna 2011

Posted on September 27, 2011 by Joel David Hamkins

This talk will be a part of the “Advanced Introduction” series for graduate students at the the Kurt Gödel Research Center, November 4, 2011.

An old argument, heard perhaps at math tea, proceeds: “there must be some real numbers that we can neither describe nor define, since there are uncountably many reals, but only countably many definitions.” Does it withstand scrutiny? In this talk, I will discuss the phenomenon of pointwise definable models of set theory, in which every object is definable without parameters. In addition to classical and folklore results on the existence of pointwise definable models of set theory, the main new theorem is that every countable model of ZFC and indeed of GBC has an extension to a model of set theory with the same ordinals, in which every set and class is definable without parameters. This is joint work with Jonas Reitz and David Linetsky, and builds on work of S. Simpson, R. Kossak, J. Schmerl, S. Friedman and A. Enayat.

Slides | Article

Generalizations of the Kunen inconsistency, KGRC, Vienna 2011

Posted on September 27, 2011 by Joel David Hamkins

This is a talk at the research seminar of the Kurt Gödel Research Center, November 3, 2011.

I shall present several generalizations of the well-known Kunen inconsistency that there is no nontrivial elementary embedding from the set-theoretic universe V to itself, including generalizations-of-generalizations previously established by Woodin and others. For example, there is no nontrivial elementary embedding from the universe V to a set-forcing extension V[G], or conversely from V[G] to V, or more generally from one ground model of the universe to another, or between any two models that are eventually stationary correct, or from V to HOD, or conversely from HOD to V, or from V to the gHOD, or conversely from gHOD to V; indeed, there can be no nontrivial elementary embedding from any definable class to V. Other results concern generic embeddings, definable embeddings and results not requiring the axiom of choice. I will aim for a unified presentation that weaves together previously known unpublished or folklore results along with some new contributions. This is joint work with Greg Kirmayer and Norman Perlmutter.

Slides | Article

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share: