A course in infinitary computability, Fall 2012, CUNY Graduate Center, CSC 85020

Posted on by
4

In Fall 2012 I will teach a graduate course on infinitary computability theory in the Computer Science program at the CUNY Graduate Center.   This course will be aimed at graduate students in computer science and mathematics who are interested in infinitary computational processes.

Infinitary computability, CSC 85020, Mondays, 9:30 – 11:30 am
CS course listings | this listing

This course will explore all the various infinitary theories of computability, including infinite time Turing machines, Blum-Shub-Smale computability, Büchi automata, ordinal register machines and others. The focus will be on introducing the computability models and comparing them to each other and to standard concepts of computability. In the early part of the course, we shall review the standard finitary computational models, before investigating the infinitary supertask analogues.

Students wishing to prepare for the course should review their understanding of Turing machines and the other theoretical machine models of computation.

Some of my articles on infinitary computability | Student talks on their infinitary computability term papers

Fun and paradox with large numbers, logic and infinity, Philadelphia 2012

Posted on by
Reply

This is a fun talk I will give at Temple University for the mathematics undergraduates in the Senior Problem Solving forum.  We’ll be exploring some of the best puzzles and paradoxes I know of that arise with large numbers and infinity.  Many of these paradoxes are connected with deep issues surrounding the nature of mathematical truth, and my intention is to convey some of that depth, while still being accessible and entertaining.

Abstract:  Are there some real numbers that in principle cannot be described?  What is the largest natural number that can be written or described  in ordinary type on a 3×5 index card?  Which is bigger, a googol-bang-plex or a googol-plex-bang? Is every natural number interesting?  Is every true statement provable? Does every mathematical problem ultimately reduce to a computational procedure?  Is every sentence either true or false or neither true nor false?  Can one complete a task involving infinitely many steps?  We will explore these and many other puzzles and paradoxes involving large numbers, logic and infinity, and along the way, learn some interesting mathematics.

What happens when one iteratively computes the automorphism group of a group? Temple University, Philadelphia 2012

Posted on by
Reply

This is a talk I shall give for the Mathematics Colloquium at Temple University, April 23, 2012.

The automorphism tower of a group is obtained by computing its automorphism group, the automorphism group of that group, and so on, iterating transfinitely. The question, known as the automorphism tower problem, is whether the tower ever terminates, whether there is eventually a fixed point, a group that is isomorphic to its automorphism group by the natural map. Wielandt (1939) proved the classical result that the automorphism tower of any finite centerless group terminates in finitely many steps. This was successively generalized to larger and larger collections of groups until Thomas (1985) proved that every centerless group has a terminating automorphism tower.  Building on this, I proved (1997) that every group has a terminating automorphism tower.  After giving an account of this theorem, I will give an overview of work with Simon Thomas and newer work with Gunter Fuchs and work of Philipp Lücke, which reveal a set-theoretic essence for the automorphism tower of a group: the very same group can have wildly different towers in different models of set theory.

slides | list of my articles on automorphism towers | announcement poster

The automorphism tower problem for groups, Bristol 2012

Posted on by
2

Isaac Newton 20th Anniversary Lecture.  This is a talk I shall give at the University of Bristol, School of Mathematics, April 17, 2012, at the invitation of Philip Welch.

The automorphism tower of a group is obtained by computing its automorphism group, the automorphism group of that group, and so on, iterating transfinitely. The question, known as the automorphism tower problem, is whether the tower ever terminates, whether there is eventually a fixed point, a group that is isomorphic to its automorphism group by the natural map. Wielandt (1939) proved the classical result that the automorphism tower of any finite centerless group terminates in finitely many steps. This was successively generalized to larger and larger collections of groups until Thomas (1985) proved that every centerless group has a terminating automorphism tower.  Building on this, I proved (1997) that every group has a terminating automorphism tower.  After giving an account of this theorem, I will give an overview of my work with Simon Thomas, as well as newer work with Gunter Fuchs and work of Philipp Lücke, which reveal a set-theoretic essence for the automorphism tower of a group: the very same group can have wildly different towers in different models of set theory.

slides | list of my articles on automorphism towers | abstract at Bristol

The hierarchy of equivalence relations on the natural numbers under computable reducibility, Cambridge, March 2012

Posted on by
Reply

This is a talk I shall give at 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 at the Isaac Newton Institute for Mathematical Sciences in Cambridge, where I am currently a Visiting Fellow.

Many of the naturally arising equivalence relations in mathematics, such as isomorphism relations on various types of countable structures, turn out to be equivalence relations on a standard Borel space, and these relations form an intensely studied hierarchy under Borel reducibility.  The topic of this talk is to introduce and explore the computable analogue of this robust theory, by studying the corresponding hierarchy of equivalence relations on the natural numbers under computable reducibility.  Specifically, one relation $E$ is computably reducible to another $F$ , if there is a unary computable function $f$ such that $x\mathrel{E}y$ if and only if $f(x)\mathrel{F}f(y)$.  This gives rise to a very different hierarchy than the Turing degrees on such relations, since it is connected with the difficulty of the corresponding classification problems, rather than with the difficulty of computing the relations themselves.  The theory is 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.  An abundance of open questions remain, and the subject is an attractive mix of methods from mathematical logic, computability, set theory, particularly descriptive set theory, and the rest of mathematics, subjects in which many of the equivalence relations arise.  This is joint work with Sam Coskey and Russell Miller.

Slides | Slides (longer version, from a similar talk) | Article | Conference abstract | Video

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

Posted on by
Reply

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-$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, 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-$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.  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 $\omega_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 by
3

[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 $\mathbb{N}$ under computable reducibility, New York March 2012

Posted on by
Reply

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 $\mathbb{N}$ under computable reducibility.  The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on $\mathbb{R}$ 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 $\mathbb{N}$.  Specifically, one relation $E$ is computably reducible to another, $F$, if there is a computable function $f$ such that $x\mathrel{E} y$ if and only if $f(x)\mathrel{F} f(y)$.  This is a very different concept from mere Turing reducibility of $E$ to $F$, for it sheds light on the comparative difficulty of the classification problems corresponding to $E$ and $F$, 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 by
Reply

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 by
4

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 by
15

[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-$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^{\frak{Ch}}$ is not known.

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

Climb into Cantor's attic

Posted on by
16

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 by
9

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.

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 by
1

[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 $\kappa$ for which $2^\kappa=\kappa^+$, another for which $2^\kappa=\kappa^{++}$ 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 $W$ with a strongly compact cardinal $\kappa$, such that $H_{\kappa^+}^V\subseteq HOD^W$. 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 $\delta$ of ${\lt}\delta$-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 $\mathbb{N}$ under computable reducibility, Florida, 2012

Posted on by
1

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 $\mathbb{N}$ under computable reducibility.  The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on $\mathbb{R}$ 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 $\mathbb{N}$.  Specifically, one relation $E$ is computably reducible to another, $F$, if there is a computable function $f$ such that $x\mathrel{E} y$ if and only if $f(x)\mathrel{F} f(y)$.  This is a very different concept from mere Turing reducibility of $E$ to $F$, for it sheds light on the comparative difficulty of the classification problems corresponding to $E$ and $F$, 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