Category Archives: Talks

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 xEy if and only if f(x)Ff(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 ω1chess 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

The hierarchy of equivalence relations on 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 N under computable reducibility.  The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on 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 N.  Specifically, one relation E is computably reducible to another, F, if there is a computable function f such that xEy if and only if f(x)Ff(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

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 hierarchy of equivalence relations on 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 N under computable reducibility.  The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on 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 N.  Specifically, one relation E is computably reducible to another, F, if there is a computable function f such that xEy if and only if f(x)Ff(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

Set theory: universe or multiverse? Vienna, 2011

Posted on by
Reply

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

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

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

The set-theoretical multiverse: a natural context for set theory, Japan 2009

Posted on by
2

Joel David Hamkins, “The Set-theoretic Multiverse : A Natural Context for Set Theory”, Annals of the Japan Association for Philosophy of Science, ISSN 0453-0691, the Japan Association for Philosophy of Science, 2011, vol 19, 37055. DOI:10.4288/jafpos.19.0_37

This article is based on a talk I gave at the conference in honor of the retirement of Yuzuru Kakuda in Kobe, Japan, March 7, 2009. I would like to express my gratitude to Kakuda-sensei and the rest of the logic group in Kobe for the opportunities provided to me to participate in logic in Japan. In particular, my time as a JSPS Fellow in the logic group at Kobe University in 1998 was a formative experience. I was part of a vibrant research group in Kobe; I enjoyed Japanese life, learned to speak a little Japanese and made many friends. Mathematically, it was a productive time, and after years away how pleasant it is for me to see that ideas planted at that time, small seedlings then, have grown into tall slender trees.

Set theorists often take their subject as constituting a foundation for the rest of mathematics, in the sense that other abstract mathematical objects can be construed fundamentally as sets. In this way, they regard the set-theoretic universe as the universe of all mathematics. And although many set-theorists affirm the Platonic view that there is just one universe of all sets, nevertheless the most powerful set-theoretic tools developed over the past half century are actually methods of constructing alternative universes. With forcing and other methods, we can now produce diverse models of ZFC set theory having precise, exacting features. The fundamental object of study in set theory has thus become the model of set theory, and the subject consequently begins to exhibit a category-theoretic second-order nature. We have a multiverse of set-theoretic worlds, connected by forcing and large cardinal embeddings like constellations in a dark sky. In this article, I will discuss a few emerging developments illustrating this second-order nature. The work engages pleasantly with various philosophical views on the nature of mathematical existence.

 

Kakuda 2009 talkDownload

 

The Ground Axiom

Posted on by
Reply

[bibtex key=Hamkins2005:TheGroundAxiom]

This is an extended abstract for a talk I gave at the 2005 Workshop in Set Theory at the Mathematisches Forschungsinstitut Oberwolfach.

Oberwolfach Research Report 55/2005 | Ground Axiom on Wikipedia

The multiverse perspective on determinateness in set theory, Harvard, 2011

Posted on by
1

This talk, taking place October 19, 2011, is part of the year-long Exploring the Frontiers of Incompleteness (EFI) series at Harvard University, a workshop focused on the question of determinateness in set theory, a central question in the philosophy of set theory. JDH at Harvard Streaming video will be available on-line, and each talk will be associated with an on-line discussion forum, to which links will be made here later.

In this talk, I will discuss the multiverse perspective on determinateness in set theory.  The multiverse view in set theory is the view that there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe. The universe view, in contrast, asserts that there is an absolute background set concept, with a corresponding absolute set-theoretic universe in which every set-theoretic question has a definite answer.  The multiverse position, I argue, 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.

Workshop materials | Article | Slides | EFI discussion forum | Video Stream

The multiverse view in set theory, Singapore 2011

Posted on by
4

A talk at the Asian Initive for Infinity: Workshop on Infinity and Truth, July 25-29, 2011, National University of Singapore.

I shall outline and defend the Multiverse view in set theory, the view that there are many set-theoretic universes, each instantiating its own concept of set, and contrast it with the Universe view, the view that there is an absolute background set-theoretic universe.  In addition, I will discuss some recent set-theoretic developments that have been motivated and informed by a multiverse perspective, including the modal logic of forcing and the emergence of set-theoretic geology.

Slides  |  Article