On the strengths of the class forcing theorem and clopen class game determinacy, Prague set theory seminar, January 2018

Posted on December 27, 2017 by Joel David Hamkins

This will be a talk for the Prague set theory seminar, January 24, 11:00 am to about 2pm (!).

Abstract. The class forcing theorem is the assertion that every class forcing notion admits corresponding forcing relations. This assertion is not provable in Zermelo-Fraenkel ZFC set theory or Gödel-Bernays GBC set theory, if these theories are consistent, but it is provable in stronger second-order set theories, such as Kelley-Morse KM set theory. In this talk, I shall discuss the exact strength of this theorem, which turns out to be equivalent to the principle of elementary transfinite recursion ETRord for class recursions on the ordinals. The principle of clopen determinacy for class games, in contrast, is strictly stronger, equivalent over GBC to the full principle of ETR for class recursions over arbitrary class well-founded relations. These results and others mark the beginnings of the emerging subject I call the reverse mathematics of second-order set theory.

The exact strength of the class forcing theorem | Open determinacy for class games

Self reference in computability theory and the universal algorithm, Ouroboros: Formal Criteria of Self-Reference in Mathematics and Philosophy, Bonn, February 2018

Posted on December 26, 2017 by Joel David Hamkins

This will be a talk for the conference: Ouroboros: Formal Criteria of Self-Reference in Mathematics and Philosophy, held in Bonn, February 16-18, 2018.

Abstract. I shall give an elementary account of the universal algorithm, due to Woodin, showing how the capacity for self-reference in arithmetic gives rise to a Turing machine program $e$, which provably enumerates a finite set of numbers, but which can in principle enumerate any finite set of numbers, when it is run in a suitable model of arithmetic. Furthermore, the algorithm can successively enumerate any desired extension of the sequence, when run in a suitable top-extension of the universe. Thus, the algorithm sheds some light on the debate between free will and determinism, if one should imagine extending the universe into a nonstandard time scale. An analogous result holds in set theory, where Woodin and I have provided a universal locally definable finite set, which can in principle be any finite set, in the right universe, and which can furthermore be successively extended to become any desired finite superset of that set in a suitable top-extension of that universe.

Ouroboros Bonn 2018 Conference Poster | Slides

The universal algorithm and the universal finite set, Prague 2018

Posted on December 24, 2017 by Joel David Hamkins

This will be a talk at the Prague Gathering of Logicians & Beauty of Logic 2018, January 25-27, 2018.

Abstract. The universal algorithm is a Turing machine program $e$ that can in principle enumerate any finite sequence of numbers, if run in the right model of PA, and furthermore, can always enumerate any desired extension of that sequence in a suitable end-extension of that model. The universal finite set is a $\Sigma_2$ definition that can in principle define any finite set, in the right model of set theory, and can always define any desired finite extension of that set in a suitable top-extension of that model. I shall give an account of both results and describe applications to the model theory of arithmetic and set theory.

Slides | Lecture notes

Set-theoretic potentialism, Winter School in Abstract Analysis 2018, Hejnice, Czech Republic

Posted on December 24, 2017 by Joel David Hamkins

This will be a tutorial lecture series for the Winter School in Abstract Analysis 2018, held in Hejnice of the Czech Republic.

Abstract. I shall introduce and develop the theory of set-theoretic potentialism. A potentialist system is a collection of first-order structures, all in the same language $\mathcal{L}$, equipped with an accessibility relation refining the inclusion relation. Any such system, viewed as an inflationary-domain Kripke model, provides a natural interpretation for the modal extension of the underlying language $\mathcal{L}$ to include the modal operators. We seek to understand a given potentialist system by analyzing which modal assertions are valid in it.

Set theory exhibits an enormous variety of natural potentialist systems. For example, with forcing potentialism, one considers the models of set theory, each accessing its forcing extensions; with rank potentialism, one considers the collection of of rank-initial segments $V_\alpha$ of a given set-theoretic universe; with Grothendieck-Zermelo potentialism, one has the collection of $V_\kappa$ for (a proper class of) inaccessible cardinals $\kappa$; with top-extensional potentialism, one considers the collection of countable models of ZFC under the top-extension relation; and so on with many other natural examples.

In this tutorial, we shall settle the precise potentialist validities of each of these potentialist systems and others, and we shall develop the general tools that enable one to determine the modal theory of a given potentialist system. Many of these arguments proceed by building connections between certain sweeping general features of the models in the potentialist system and certain finite combinatorial objects such as trees or lattices. A key step involves finding certain kinds of independent control statements — buttons, switches, ratchets and rail-switches — in the collection of models.

Slides

A universal finite set, CUNY Logic Workshop, November 2017

Posted on November 10, 2017 by Joel David Hamkins

This will be a talk for the CUNY Logic Workshop, November 17, 2017, 2pm GC Room 6417.

Abstract. I shall define a certain finite set in set theory $$\{x\mid\varphi(x)\}$$ and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $\varphi$ has complexity $\Sigma_2$ and therefore any instance of it $\varphi(x)$ is locally verifiable inside any sufficient $V_\theta$; the set is empty in any transitive model and others; and if $\varphi$ defines the set $y$ in some countable model $M$ of ZFC and $y\subset z$ for some finite set $z$ in $M$, then there is a top-extension of $M$ to a model $N$ in which $\varphi$ defines the new set $z$. In particular, although there are models of set theory with maximal $\Sigma_2$ theories, nevertheless no model of set theory realizes a maximal $\Sigma_2$ theory with its natural-number parameters. Using the universal finite set, it follows that the validities of top-extensional set-theoretic potentialism, the modal principles valid in the Kripke model of all countable models of set theory, each accessing its top-extensions, are precisely the assertions of S4. Furthermore, if ZFC is consistent, then there are models of ZFC realizing the top-extensional maximality principle.

This is joint work with W. Hugh Woodin.

The hierarchy of second-order set theories between GBC and KM and beyond

Posted on September 9, 2017 by Joel David Hamkins

This was a talk at the upcoming International Workshop in Set Theory at the Centre International de Rencontres Mathématiques at the Luminy campus in Marseille, France, October 9-13, 2017.

Abstract. Recent work has clarified how various natural second-order set-theoretic principles, such as those concerned with class forcing or with proper class games, fit into a new robust hierarchy of second-order set theories between Gödel-Bernays GBC set theory and Kelley-Morse KM set theory and beyond. For example, the principle of clopen determinacy for proper class games is exactly equivalent to the principle of elementary transfinite recursion ETR, strictly between GBC and GBC+$\Pi^1_1$-comprehension; open determinacy for class games, in contrast, is strictly stronger; meanwhile, the class forcing theorem, asserting that every class forcing notion admits corresponding forcing relations, is strictly weaker, and is exactly equivalent to the fragment $\text{ETR}_{\text{Ord}}$ and to numerous other natural principles. What is emerging is a higher set-theoretic analogue of the familiar reverse mathematics of second-order number theory.

Slides

https://plus.google.com/u/0/+JoelDavidHamkins1/posts/ekgdakenadv

Arithmetic potentialism and the universal algorithm, CUNY Logic Workshop, September 2017

Posted on August 26, 2017 by Joel David Hamkins

This will be a talk for the CUNY Logic Workshop at the CUNY Graduate Center, September 8, 2017, 2-3:30, room GC 6417.

Abstract. Consider the collection of all the models of arithmetic under the end-extension relation, which forms a potentialist system for arithmetic, a collection of possible arithmetic worlds or universe fragments, with a corresponding potentialist modal semantics. What are the modal validities? I shall prove that every model of arithmetic validates exactly S4 with respect to assertions in the language of arithmetic allowing parameters, but if one considers sentences only (no parameters), then some models can validate up to S5, thereby fulfilling the arithmetic maximality principle, which asserts for a model $M$ that whenever an arithmetic sentence is true in some end-extension of $M$ and all subsequent end-extensions, then it is already true in $M$. (We also consider other accessibility relations, such as arbitrary extensions or $\Sigma_n$-elementary extensions or end-extensions.)

The proof makes fundamental use of what I call the universal algorithm, a fascinating result due to W. Hugh Woodin, asserting that there is a computable algorithm that can in principle enumerate any desired finite sequence, if only it is undertaken in the right universe, and furthermore any given model of arithmetic can be end-extended so as to realize any desired additional behavior for that universal program. I shall give a simple proof of the universal algorithm theorem and explain how it can be used to determine the potentialist validities of a model of arithmetic. This is current joint work in progress with Victoria Gitman and Roman Kossak, and should be seen as an arithmetic analogue of my recent work on set-theoretic potentialism with Øystein Linnebo. The mathematical program is strongly motivated by philosophical ideas arising in the distinction between actual and potential infinity.

The modal principles of potentialism in mathematics, Logic and Metaphysics Workshop, CUNY, November 2017

Posted on August 10, 2017 by Joel David Hamkins

This will be a talk on November 6, 2017 for the Logic and Metaphysics workshop at the CUNY Graduate Center, run by Graham Priest. Room GC 3209.

The modal principles of potentialism in mathematics

Abstract. Potentialism is the view in the philosophy of mathematics that one’s mathematical universe, whether in arithmetic or set theory, is never fully completed, but rather unfolds gradually as new parts of it increasingly come into existence or become accessible or known to us. As in the classical dispute between actual versus potential infinity, the potentialist holds that objects in the upper or outer reaches have potential as opposed to actual existence, in the sense that one can imagine forming or discovering always more objects from that realm, as many as desired, but the task is never completed. Recent work has emphasized the modal aspect of potentialism, and in this talk, I shall describe a general model-theoretic account of the modal logic of potentialism, identifying specific modal principles that hold or fail depending on features of the potentialist system under consideration. This work makes use of modal control statements, such as buttons, switches, dials and ratchets and the connection of these kinds of statements with the modal theories S4, S4.2, S4.3 and S5. I shall take the various natural kinds of arithmetic and set-theoretic potentialism as illustrative cases.

This is joint work with Øystein Linnebo, University of Oslo (see our paper The modal logic of set-theoretic potentialism and the potentialist maximality principles), and further joint work in progress with Victoria Gitman and Roman Kossak, and very recent joint work in progress with W. Hugh Woodin.

Lecture Notes

All countable models of set theory have the same inclusion relation up to isomorphism, CUNY Logic Workshop, April 2017

Posted on April 13, 2017 by Joel David Hamkins

This will be a talk for the CUNY Logic Workshop, April 28, 2:00-3:30 in room 6417 at the CUNY Graduate Center.

Abstract. Take any countable model of set theory $\langle M,\in^M\rangle\models\text{ZFC}$, whether well-founded or not, and consider the corresponding inclusion relation $\langle M,\newcommand\of{\subseteq}\of^M\rangle$. All such models, we prove, are isomorphic. Indeed, if $\langle M,\in^M\rangle$ is a countable model of set theory — a very weak theory suffices, including finite set theory, if one excludes the $\omega$-standard models with no infinite sets and the $\omega$-standard models with an amorphous set — then the corresponding inclusion reduct $\langle M,\of^M\rangle$ is an $\omega$-saturated model of the theory we have called set-theoretic mereology. Since this is a complete theory, it follows by the back-and-forth construction that all such countable saturated models are isomorphic. Thus, the inclusion relation $\langle M,\of^M\rangle$ knows essentially nothing about the theory of the set-theoretic structure $\langle M,\in^M\rangle$ from which it arose. Analogous results hold also for class theories such as Gödel-Bernays set theory and Kelley-Morse set theory.

This is joint work with Makoto Kikuchi, and our paper is available at

J. D. Hamkins and M. Kikuchi, The inclusion relations of the countable models of set theory are all isomorphic, manuscript under review.

Our previous work, upon which these results build, is available at:

J. D. Hamkins and M. Kikuchi, Set-theoretic mereology, Logic and Logical Philosophy, special issue “Mereology and beyond, part II”, vol. 25, iss. 3, pp. 1-24, 2016.

Open and clopen determinacy for proper class games, VCU MAMLS April 2017

Posted on February 25, 2017 by Joel David Hamkins

This will be a talk for the Mid-Atlantic Mathematical Logic Seminar at Virginia Commonwealth University, a conference to be held April 1-2, 2017.

Abstract. The principle of open determinacy for class games — two-player games of perfect information with plays of length $\omega$, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Gödel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates $\text{Tr}_\alpha$ for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of elementary transfinite recursion ETR over well-founded class relations. Meanwhile, the principle of open determinacy for class games is provable in the stronger theory GBC+$\Pi^1_1$-comprehension, a proper fragment of Kelley-Morse set theory KM. New work by Hachtman and Sato, respectively has clarified the separation of clopen and open determinacy for class games.

Lewis Chessmen This is joint work with Victoria Gitman. See our article, Open determinacy for class games.

Slides

Computable quotient presentations of models of arithmetic and set theory, CUNY set theory seminar, March 2017

Posted on February 25, 2017 by Joel David Hamkins

This will be a talk for the CUNY Set Theory Seminar on March 10, 2017, 10:00 am in room 6417 at the CUNY Graduate Center.

Abstract. I shall prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+,\cdot,\leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation. This is joint work with Michał Tomasz Godziszewski.

A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle\newcommand\N{\mathbb{N}}\N,\star,\ast,\dots\rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\N$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle\N,\star,\ast,\dots\rangle/E$ is isomorphic to $\mathcal A$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure. In a language with relations, it is also natural to relax the concept somewhat by considering the computably enumerable quotient presentations, which allow the pre-quotient relations to be merely computably enumerable, rather than insisting that they must be computable.

At the 2016 conference Mathematical Logic and its Applications at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. In his talk (see his slides), he outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation $E$ or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo $E$.

In my talk, I shall engage specifically with two conjectures that Khoussainov had made at the meeting.

Conjecture. (Khoussainov)

No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.

We prove the first conjecture and refute several natural variations of the second conjecture, although a further natural variation, perhaps the central case, remains open. In addition, we consider and settle the natural analogues of the conjectures for models of set theory.

Set-theoretic geology and the downward directed grounds hypothesis, Bonn, January 2017

Posted on January 10, 2017 by Joel David Hamkins

This will be a talk for the University of Bonn Logic Seminar, Friday, January 13, 2017, at the Hausdorff Center for Mathematics.

Abstract. Set-theoretic geology is the study of the set-theoretic universe $V$ in the context of all its ground models and those of its forcing extensions. For example, a bedrock of the universe is a minimal ground model of it and the mantle is the intersection of all grounds. In this talk, I shall explain some recent advances, including especially the breakthrough result of Toshimichi Usuba, who proved the strong downward directed grounds hypothesis: for any set-indexed family of grounds, there is a deeper common ground below them all. This settles a large number of formerly open questions in set-theoretic geology, while also leading to new questions. It follows, for example, that the mantle is a model of ZFC and provably the largest forcing-invariant definable class. Strong downward directedness has also led to an unexpected connection between large cardinals and forcing: if there is a hyper-huge cardinal $\kappa$, then the universe indeed has a bedrock and all grounds use only $\kappa$-small forcing.

Slides

Transfinite game values in infinite chess, including new progress, Bonn, January 2017

Posted on January 3, 2017 by Joel David Hamkins

This will be a talk January 10, 2017 for the Basic Notions Seminar, aimed at students, post-docs, faculty and guests of the Mathematics Institute, University of Bonn.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess — chess played on an infinite edgeless chessboard — as a central example. Since chess, when won, is won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values. I shall exhibit several interesting positions in infinite chess with very high transfinite game values. The precise value of the omega one of chess is an open mathematical question. This talk will include some of the latest progress, which includes a position with game value $\omega^4$.

It happens that I shall be in Bonn also for the dissertation defense of Regula Krapf, who will defend the same week, and who is one of the organizers of the seminar.

Transfinite game values in infinite chess | The mate-in-$n$ problem of infinite chess is decidable | A position in infinite chess with game value $\omega^4$ | more on infinite chess | Slides

Joel David Hamkins

mathematics and philosophy of the infinite

Category Archives: Talks

On the strengths of the class forcing theorem and clopen class game determinacy, Prague set theory seminar, January 2018

Self reference in computability theory and the universal algorithm, Ouroboros: Formal Criteria of Self-Reference in Mathematics and Philosophy, Bonn, February 2018

The universal algorithm and the universal finite set, Prague 2018

A universal finite set, CUNY Logic Workshop, November 2017

The hierarchy of second-order set theories between GBC and KM and beyond

All countable models of set theory have the same inclusion relation up to isomorphism, CUNY Logic Workshop, April 2017

Open and clopen determinacy for proper class games, VCU MAMLS April 2017

Computable quotient presentations of models of arithmetic and set theory, CUNY set theory seminar, March 2017

Set-theoretic geology and the downward directed grounds hypothesis, Bonn, January 2017

Transfinite game values in infinite chess, including new progress, Bonn, January 2017

Share:

Share:

Share:

Share:

Share:

Share:

Share:

The modal principles of potentialism in mathematics

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share: