Thomas Johnstone

Posted on August 12, 2012 by Joel David Hamkins

Thomas Johnstone earned his Ph.D. under my supervision in June, 2007 at the CUNY Graduate Center. Tom likes to get thoroughly to the bottom of a problem, and this indeed is what he did in his dissertation work on the forcing-theoretic aspects of unfoldable cardinals. He seemed to want always to dig deeper, seeking out the unstated general phenomenon behind the results. His characteristic style of giving a seminar talk—pure mathematical pleasure to attend—is to explain not only why the mathematical fact is true, but also why the proof must be the way that it is. Thomas holds a tenure-track position at the New York City College of Technology of CUNY.

Thomas A. Johnstone

Thomas A. Johnstone, “Strongly unfoldable cardinals made indestructible,” Ph.D. dissertation, The Graduate Center of the City University of New York, June 2007.

Abstract. I provide indestructibility results for weakly compact, indescribable and strongly unfoldable cardinals. In order to make these large cardinals indestructible, I assume the existence of a strongly unfoldable cardinal $\kappa$, which is a hypothesis consistent with $V=L$. The main result shows that any strongly unfoldable cardinal $\kappa$ can be made indestructible by all ${<}\kappa$-closed forcing which does not collapse $\kappa^{+}$. As strongly unfoldable cardinals strengthen both indescribable and weakly compact cardinals, I obtain indestructibility for these cardinals also, thereby reducing the large cardinal hypothesis of previously known indestructibility results for these cardinals significantly. Finally, I use the developed methods to show the consistency of a weakening of the Proper Forcing Axiom $\rm PFA$ relative to the existence of a strongly unfoldable cardinal.

Jonas Reitz

Posted on August 12, 2012 by Joel David Hamkins

Jonas Reitz earned his Ph.D under my supervision in June, 2006 at the CUNY Graduate Center. He was truly a pleasure to supervise. From the earliest days of his dissertation research, he had his own plan for the topic of the work: he wanted to “undo” forcing, to somehow force backwards, from the extension to the ground model. At first I was skeptical, but in time, ideas crystalized around the ground axiom (now with its own Wikipedia entry), formulated using a recent-at-the-time result of Richard Laver. Along with Laver’s theorem, Jonas’s dissertation was the beginning of the body of work now known as set-theoretic geology. Jonas holds a tenured position at the New York City College of Technology of CUNY.

Jonas Reitz

Jonas Reitz, “The ground axiom,” Ph.D. dissertation, CUNY Graduate Center, June, 2006. ar$\chi$iv

Abstract. A new axiom is proposed, the Ground Axiom, asserting that the universe is not a nontrivial set-forcing extension of any inner model. The Ground Axiom is first-order expressible, and any model of ZFC has a class-forcing extension which satisfies it. The Ground Axiom is independent of many well-known set-theoretic assertions including the Generalized Continuum Hypothesis, the assertion V=HOD that every set is ordinal definable, and the existence of measurable and supercompact cardinals. The related Bedrock Axiom, asserting that the universe is a set-forcing extension of a model satisfying the Ground Axiom, is also first-order expressible, and its negation is consistent. As many of these results rely on forcing with proper classes, an appendix is provided giving an exposition of the underlying theory of proper class forcing.

George Leibman

Posted on August 11, 2012 by Joel David Hamkins

George Joseph Leibman earned his Ph.D. under my supervision in June, 2004 at the CUNY Graduate Center. He was my first Ph.D. student. Being very interested both in forcing and in modal logic, it was natural for him to throw himself into the emerging developments at the common boundary of these topics. He worked specifically on the natural extensions of the maximality principle where when one considers a fixed definable class $\Gamma$ of forcing notions. This research engaged with fundamental questions about the connection between the forcing-theoretic properties of the forcing class $\Gamma$ and the modal logic of its forcing validities, and was a precursor of later work, including joint work, on the modal logic of forcing.

George Leibman

web page | math genealogy | MathSciNet | ar$\chi$iv | related posts

George Leibman, “Consistency Strengths of Modified Maximality Principles,” Ph.D. thesis, CUNY Graduate Center, 2004. ar$\chi$iv

Abstract. The Maximality Principle MP is a scheme which states that if a sentence of the language of ZFC is true in some forcing extension $V^{\mathbb{P}}$, and remains true in any further forcing extension of $V^{\mathbb{P}}$, then it is true in all forcing extensions of $V$. A modified maximality principle $\text{MP}_\Gamma$ arises when considering forcing with a particular class $\Gamma$ of forcing notions. A parametrized form of such a principle, $\text{MP}_\Gamma(X)$, considers formulas taking parameters; to avoid inconsistency such parameters must be restricted to a specific set $X$ which depends on the forcing class $\Gamma$ being considered. A stronger necessary form of such a principle, $\square\text{MP}_\Gamma(X)$, occurs when it continues to be true in all $\Gamma$ forcing extensions.

This study uses iterated forcing, modal logic, and other techniques to establish consistency strengths for various modified maximality principles restricted to various forcing classes, including ccc, COHEN, COLL (the forcing notions that collapse ordinals to $\omega$), ${\lt}\kappa$ directed closed forcing notions, etc., both with and without parameter sets. Necessary forms of these principles are also considered.

More students (on whose thesis committees I’ve served)

Posted on August 10, 2012 by Joel David Hamkins

I have served as a member of the dissertation or thesis committee for each the following students.

Konstantinos Tsaprounis, Ph.D. 2012, Universitat de Barcelona, Departament de Lògica, Història i Filosofia de la Ciència, Programa de doctorat de Lògica Pura i Aplicada, Facultat de Filosofia. Barcelona Research Group in Set Theory

Director: Joan Bagaria i Pigrau

Dissertation: Large cardinals and resurrection axioms

In his dissertation, Kostas develops the theory of $C^{(n)}$-tall cardinals, $C^{(n)}$-superstrong, $C^{(n)}$-strong, $C^{(n)}$-strongly compact, $C^{(n)}$-Woodin, $C^{(n)}$-supercompact and $C^{(n)}$-extendible cardinals, particularly with a view to finding upper bounds in consistency strength via an elementary chain construction. In addition, he investigates various resurrection axioms, including RA(stationary-preserving).

Shoshana Friedman

Shoshana Friedman, Ph.D. 2010, CUNY Graduate Center, math genealogy | MathSciNet

Supervisor: Arthur W. Apter

Dissertation: Aspects of supercompactness, HOD and set-theoretic geology

Abstract. In this thesis, we study HOD, primarily in the context of large cardinals and GCH. Chapter 1 contains our introductory comments and preliminary remarks. In Chapter 2, we extend a property of HOD-supercompactness due to Sargsyan to various models of set theory containing supercompact cardinals. In doing so, we develop a new method for coding sets while preserving GCH. In Chapter 3, we extend this alternative method of coding. This allows us to produce models of V = HOD and GCH in the presence of large cardinals (including supercompact cardinals). In the remaining chapters, we use this coding to extend a variety of earlier results. In Chapter 4, we generalize theorems about the Ground Axiom to models with supercompact cardinals that satisfy GCH. In Chapter 5, we extend results in set theoretic geology to models that satisfy GCH. Finally, in Chapter 6, we use the coding to produce a model of the Wholeness Axiom, V = HOD and GCH.

Paul Ellis, Ph.D. 2009, Rutgers University, math genealogy | MathSciNet

Supervisor: Simon Thomas

Dissertation: The classification problem for finite rank dimension groups

Abstract. There has been much work done in the study of the Borel complexity of various naturally occurring classification problems. In particular, Hjorth and Thomas have shown that the Borel complexity of the classification problem for torsion-free abelian groups of finite rank increases strictly with rank. In this thesis, we extend this result to dimension groups of finite rank. As these groups are naturally characterized by Bratteli diagrams, we obtain a similar theorem for Bratteli diagrams. We also obtain a similar result for a class of countable simple locally finite groups which are also characterized by Bratteli diagrams.

Scott Schneider, Ph.D. 2009, Rutgers University, math genealogy | MathSciNet

Supervisor: Simon Thomas

Dissertation: Borel superrigidity for actions of low rank lattices

Abstract. A major recent theme in Descriptive Set Theory has been the study of countable Borel equivalence relations on standard Borel spaces, including their structure under the partial ordering of Borel reducibility. We shall contribute to this study by proving Borel incomparability results for the orbit equivalence relations arising from Bernoulli, profinite, and linear actions of certain subgroups of $\text{PSL}_2(\mathbb{R})$. We employ the techniques and general strategy pioneered by Adams and Kechris, and develop purely Borel versions of cocycle superrigidity results arising in the dynamical theory of semisimple groups.

Specifically, using Zimmer’s cocycle superrigidity theorems, we will prove Borel superrigidity results for suitably chosen actions of groups of the form $\text{PSL}_2(\mathcal{O})$, where $\mathcal{O}$ is the ring of integers inside a multi-quadratic number field. In particular, for suitable primes $p\neq q$, we prove that the orbit equivalence relations arising from the natural actions of $\text{PSL}_2(\mathbb{Z}[\sqrt{q}])$ on the $p$-adic projective lines are incomparable with respect to Borel reducibility as $p, q$ vary. Furthermore, we also obtain Borel non-reducibility results for orbit equivalence relations arising from Bernoulli actions of the groups $\text{PSL}_2(\mathcal{O})$. In particular, we show that if $E_p$ denotes the orbit equivalence relation arising from a nontrivial Bernoulli action of $\text{PSL}_2(\mathbb{Z}[\sqrt{p}])$, then $E_p$ and $E_q$ are incomparable with respect to Borel reducibility whenever $p \neq q$.

Sam Coskey, Ph.D. 2008, Rutgers University, math genealogy | MathSciNet

Supervisor: Simon Thomas

Dissertation: Descriptive aspects of torsion-free abelian groups

Abstract. In recent years, a major theme in descriptive set theory has been the study of the Borel complexity of naturally occurring classification problems. For example, Hjorth and Thomas have shown that the Borel complexity of the isomorphism problem for the torsion-free abelian groups of rank $n$ increases strictly with the rank $n$. In this thesis, we present some new applications of the theory of countable Borel equivalence relations to various classification problems for the $p$-local torsion-free abelian groups of finite rank. Our main result is that when $n\geq 3$, the isomorphism and quasi-isomorphism problems for the $p$-local torsion-free abelian groups of rank $n$ have incomparable Borel complexities. (Here two abelian groups $A$ and $B$ are said to be quasi-isomorphic if $A$ is abstractly commensurable with $B$.) We also introduce a new invariant, the divisible rank, for the class of $p$-local torsion-free abelian groups of finite rank; and we prove that if $n\geq 3$ and $1 \leq k\leq n − 1$, then the isomorphism problems for the $p$-local torsion-free abelian groups of rank $n$ and divisible rank $k$ have incomparable Borel complexities as $k$ varies. Our proofs rely on the framework developed by Adams and Kechris, whereby cocycle superrigidity results from measurable group theory are applied in the purely Borel setting. In particular, we make use of the recent cocycle superrigidity theorem, due to Ioana, for free ergodic profinite actions of Kazhdan groups. More

Joost Winter, M.Sc. 2007, Universiteit van Amsterdam

Supervisor: Benedikt Löwe

M.Sc. thesis: Space compexity in infinite time Turing machines pdf

Can Baskent, M.Sc. 2007, Universiteit van Amsterdam

Supervisor: Benedikt Löwe

M.Sc. Thesis: Topics in subset space logic

Yurii Khomskii, M.Sc. 2007, Universiteit van Amsterdam

Supervisor: Benedikt Löwe

M.Sc. Thesis: Regularity properties and determinacy

Erez Shochat, Ph.D. 2006, CUNY Graduate Center, math genealogy | MathSciNet

Supervisor: Roman Kossak

Dissertation: Countable short recursively saturated models of arithemtic

Abstract. Short recursively saturated models of arithmetic are exactly the elementary initial segments of recursively saturated models of arithmetic. Since any countable recursively saturated model of arithmetic has continuum many elementary initial segments which are already recursively saturated, we turn our attention to the (countably many) initial segments which are not recursively saturated. We first look at properties of countable short recursively saturated models of arithmetic and show that although these models cannot be cofinally resplendent (an expandability property slightly weaker than resplendency), these models have non-definable expansions which are still short recursively saturated.

Federico Marulanda Rey, Ph.D. 2007, Columbia University, DBLP | Proquest | Google Books

Supervisor: Haim Gaifman (I was the outside reader)

Dissertation: Contradiction, Paraconsistency, and Dialetheism

Abstract. The deductive closure of a set of sentences is trivial, i.e., it includes every well-formed sentence, if this set contains a contradiction and the consequence relation employed is either classical or intuitionistic. Over the past few decades, a number of paraconsistent logics, or logics specifically designed not to trivialize inconsistent theories, have been developed. The present work investigates philosophical issues arising from the development of paraconsistent formal systems. In the introductory chapter, as well as on a chapter that extracts learnings from Wittgenstein’s career-long preoccupation with contradiction, I endeavor to determine just what is the problem with contradictions, as they arise in both natural and formal languages. I then consider in detail two kinds of paraconsistent logic: their formal characteristics, the motivation for their formulation, their possible applications, and objections that may be raised against them. Special attention is devoted to a logical system that deliberately permits the evaluation of certain contradictions as being true, as well as to the attendant philosophical position, known as dialetheism, according to which there are, in fact, true contradictions. I raise a number of objections to this strong (and resilient) form of paraconsisteney, which, taken together, constitute a rebuttal of the view, thus carrying out a task that a number of authors have signaled as pressing, but which has not so far been undertaken in detail in the literature.

Ivan Welty, Ph.D. 2006, Columbia University, Philpapers | Google Books

Supervisor: Haim Gaifman

Dissertation: Frege Against Hilbert on the Foundations of Geometry

Abstract. This dissertation is a close study of the Frege-Hilbert dispute over the foundations of geometry. The dispute has been the subject of active debate recently, with opinion divided as to the merits of Frege’s position. In this dissertation I aim at a comprehensive assessment of Frege’s position, its motivations, and its major consequences. I find that: (1) Frege’s objections to Hilbert’s Foundations of Geometry do not represent a mere misunderstanding of Hilbert’s work, but stem from considerations of serious philosophical interest; (2) The same considerations that motivated Frege’s objections suggest a conception of geometry—and a reading of the history of geometry—radically different from Hilbert’s; (3) That conception of geometry—and reading of the history of geometry—are not obviously wrong, and indeed merit further investigation; (4) Part of Frege’s objection to Hilbert’s Foundations is that he gives no philosophical analysis of geometry, analogous to Frege’s analysis of number in Foundations of Arithmetic; (5) The basic framework for such an analysis can be found in Frege’s philosophical work, although it is far from obvious whether and how it can be carried through. The principal contributions of this dissertation lie in its clarification of the import of the Frege-Hilbert dispute for our understanding of the history of geometry, in particular the emergence of non-Euclidean and projective geometries; in its clarification of Frege’s objections to Hilbert’s independence proofs; and in its outline of a Fregean analysis of geometry, analogous to the analysis of number in Foundations of Arithmetic.

Sidney Raffer, Ph.D. 1999, CUNY Graduate Center

Supervisor: Roman Kossak

math genealogy | MathSciNet

Dissertation: Some Diophantine properties of ordered polynomial rings

Every countable model of set theory embeds into its own constructible universe, Fields Institute, Toronto, August 2012

Posted on August 10, 2012 by Joel David Hamkins

This will be a talk for the Toronto set theory seminar at the Fields Institute, University of Toronto, on August 24, 2012.

Abstract. Every countable model of set theory $M$, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding $j:M\to L^M$ that is elementary for quantifier-free assertions. The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected Image: Igougo.com with the surreal numbers. The proof shows that $L^M$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other. Indeed, the bi-embeddability classes form a well-ordered chain of length $\omega_1+1$. Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory $M$ is universal for all countable well-founded binary relations of rank at most $\text{Ord}^M$; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if $M$ is any nonstandard model of PA, then every countable model of set theory—in particular, every model of ZFC—is isomorphic to a submodel of the hereditarily finite sets $HF^M$ of $M$. Indeed, $HF^M$ is universal for all countable acyclic binary relations.

Article | my profile at set theory talks | Toronto Set Theory Seminar post

Fields Institute, Toronto, Scientific Researcher, 2012

Posted on August 8, 2012 by Joel David Hamkins

During August 2012, I was a visiting Scientific Researcher at the Fields Institute at the University of Toronto, participating in their thematic program on Forcing and it Applications.

Structural connections between a forcing class and its modal logic

Posted on July 25, 2012 by Joel David Hamkins

[bibtex key=HamkinsLeibmanLoewe2015:StructuralConnectionsForcingClassAndItsModalLogic]

The modal logic of forcing arises when one considers a model of set theory in the context of all its forcing extensions, interpreting $\square$ as “in all forcing extensions” and $\Diamond$ as “in some forcing extension”. In this modal language one may easily express sweeping general forcing principles, such as $\Diamond\square\varphi\to\square\Diamond\varphi$, the assertion that every possibly necessary statement is necessarily possible, which is valid for forcing, or $\Diamond\square\varphi\to\varphi$, the assertion that every possibly necessary statement is true, which is the maximality principle, a forcing axiom independent of but equiconsistent with ZFC (see A simple maximality principle).

Every definable forcing class similarly gives rise to the corresponding forcing modalities, for which one considers extensions only by forcing notions in that class. In previous work, we proved that if ZFC is consistent, then the ZFC-provably valid principles of the class of all forcing are precisely the assertions of the modal theory S4.2 (see The modal logic of forcing). In this article, we prove that the provably valid principles of collapse forcing, Cohen forcing and other classes are in each case exactly S4.3; the provably valid principles of c.c.c. forcing, proper forcing, and others are each contained within S4.3 and do not contain S4.2; the provably valid principles of countably closed forcing, CH-preserving forcing and others are each exactly S4.2; and the provably valid principles of $\omega_1$-preserving forcing are contained within S4.tBA. All these results arise from general structural connections we have identified between a forcing class and the modal logic of forcing to which it gives rise, including the connection between various control statements, such as buttons, switches and ratchets, and their corresponding forcing validities. These structural connections therefore support a forcing-only analysis of other diverse forcing classes.

Preprints available at: ar$\chi$iv | NI12055-SAS | UvA ILLC PP-2012-19 | HBM 446

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

Posted on July 5, 2012 by Joel David Hamkins

[bibtex key=Hamkins2013:EveryCountableModelOfSetTheoryEmbedsIntoItsOwnL]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Well-founded Boolean ultrapowers as large cardinal embeddings

Posted on June 26, 2012 by Joel David Hamkins

[bibtex key=HamkinsSeabold:BooleanUltrapowers]

Boolean ultrapowers extend the classical ultrapower construction to work with ultrafilters on any complete Boolean algebra, rather than only on a power set algebra. When they are well-founded, the associated Boolean ultrapower embeddings exhibit a large cardinal nature, and the Boolean ultrapower construction thereby unifies two central themes of set theory—forcing and large cardinals—by revealing them to be two facets of a single underlying construction, the Boolean ultrapower.

The topic of this article was the focus of my tutorial lecture series at the Young Set Theorists Workshop at the Hausdorff Center for Mathematics in Königswinter near Bonn, Germany, March 21-25, 2011.

Singular cardinals and strong extenders

Posted on June 26, 2012 by Joel David Hamkins

[bibtex key=ApterCummingsHamkins2013:SingularCardinalsAndStrongExtenders]

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

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

The mate-in-n problem of infinite chess is decidable, Cambridge, June 2012

Posted on June 4, 2012 by Joel David Hamkins

This will be a contributed talk at the Turing Centenary Conference CiE 2012 held June 18-23, 2012 in Cambridge, UK.

Abstract. The mate-in-$n$ problem of infinite chess—chess played on an infinite edgeless board—is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. Although a straightforward formulation of this problem leads to assertions of high arithmetic complexity, with $2n$ alternating quantifiers, the main theorem of this article nevertheless confirms a conjecture of the second author and C. D. A. Evans by establishing that it 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 $\frak{Ch}$, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. The structure is also definable in Presburger arithmetic. 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.

Article | Slides | CiE 2012 | Contributed talk schedule

The hierarchy of equivalence relations on the natural numbers under computable reducibility, Chicheley Hall, June 2012

Posted on June 4, 2012 by Joel David Hamkins

This will be a talk at The Incomputable, a workshop held June 12-15, 2012 at the Kavli Royal Society International Centre at Chicheley Hall as a part of the program Semantics and Syntax: A Legacy of Alan Turing organized by the Isaac Newton Institute of Mathematical Sciences in Cambridge, UK.

Abstract. I will speak on the computable analogue of the theory of equivalence relations on the reals under Borel reducibility. The Borel theory has been enormously successful in clarifying the hierarchy of classification problems arising throughout mathematics. The computable analogue, meanwhile, appears to be particularly well-suited for an analysis of the c.e. instances of those problems, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In particular, every equivalence relation on countable structures has its natural restriction to the c.e. instances, which may be viewed as an equivalence relation on the indices of those c.e. sets. Specifically, one equivalence relation E on the natural numbers is computably reducible to another F, if there is a computable function f such that n E m if and only if f(n) F f(m). This reduction notion has been introduced and studied independently by several different researchers and research groups. In this talk, I will describe recent joint work with Sam Coskey and Russell Miller that fills out parts of the hierarchy. An abundance of questions remain open.

Article | Slides | Workshop abstract

The countable models of ZFC, up to isomorphism, are linearly pre-ordered by the submodel relation; indeed, every countable model of ZFC, including every transitive model, is isomorphic to a submodel of its own $L$, New York, 2012

Posted on April 30, 2012 by Joel David Hamkins

This will be a talk on May 18, 2012 for the CUNY Logic Workshop on some extremely new work. The proof uses finitary digraph combinatorics, including the countable random digraph and higher analogues involving uncountable Fraisse limits, the surreal numbers and the hypnagogic digraph.

The story begins with Ressayre’s remarkable 1983 result that if $M$ is any nonstandard model of PA, with $\langle\text{HF}^M,{\in^M}\rangle$ the corresponding nonstandard hereditary finite sets of $M$, then for any consistent computably axiomatized theory $T$ in the language of set theory, with $T\supset ZF$, there is a submodel $N\subset\langle\text{HF}^M,{\in^M}\rangle$ such that $N\models T$. In particular, one may find models of ZFC or even ZFC + large cardinals as submodels of $\text{HF}^M$, a land where everything is thought to be finite. Incredible! Ressayre’s proof uses partial saturation and resplendency to prove that one can find the submodel of the desired theory $T$.

My new theorem strengthens Ressayre’s theorem, while simplifying the proof, by removing the theory $T$. We need not assume $T$ is computable, and we don’t just get one model of $T$, but rather all models—the fact is that the nonstandard models of set theory are universal for all countable acyclic binary relations. So every model of set theory is a submodel of $\langle\text{HF}^M,{\in^M}\rangle$.

Theorem.(JDH) Every countable model of set theory is isomorphic to a submodel of any nonstandard model of finite set theory. Indeed, every nonstandard model of finite set theory is universal for all countable acyclic binary relations.

The proof involves the construction of what I call the countable random $\mathbb{Q}$-graded digraph, a countable homogeneous acyclic digraph that is universal for all countable acyclic digraphs, and proving that it is realized as a submodel of the nonstandard model $\langle M,\in^M\rangle$. Having then realized a universal object as a submodel, it follows that every countable structure with an acyclic binary relation, including every countable model of ZFC, is realized as a submodel of $M$.

The proof idea adapts, with complications, to the case of well-founded models, via the countable random $\lambda$-graded digraph, as well as the internal construction of what I call the hypnagogic digraph, a proper class homogeneous surreal-numbers-graded digraph, which is universal for all class acyclic digraphs.

Theorem.(JDH) Every countable model $\langle M,\in^M\rangle$ of ZFC, including the transitive models, is isomorphic to a submodel of its own constructible universe $\langle L^M,\in^M\rangle$. In other words, there is an embedding $j:M\to L^M$ that is quantifier-free-elementary.

The proof is guided by the idea of finding a universal submodel inside $L^M$. The embedding $j$ is constructed completely externally to $M$.

Corollary.(JDH) The countable models of ZFC are linearly ordered and even well-ordered, up to isomorphism, by the submodel relation. Namely, any two countable models of ZFC with the same well-founded height are bi-embeddable as submodels of each other, and all models embed into any nonstandard model.

The work opens up numerous questions on the extent to which we may expect in ZFC that $V$ might be isomorphic to a subclass of $L$. To what extent can we expect to have or to refute embeddings $j:V\to L$, elementary for quantifier-free assertions?

Article | CUNY Logic Workshop

The omega one of infinite chess, New York, 2012

Posted on April 28, 2012 by Joel David Hamkins

This will be a talk on May 18, 2012 for the CUNY Set Theory Seminar.

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. An equivalent account of the result arises from the realization that the structure of chess is interpretable in the standard model of Presburger arithmetic $\langle\mathbb{N},+\rangle$. 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

Must there be numbers we cannot describe or define? Pointwise definability and the Math Tea argument, Bristol, April 2012

Posted on April 12, 2012 by Joel David Hamkins

This is a talk I plan to give to the set theory seminar at the University of Bristol on April 18, 2012.

An old argument, heard at a good 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

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share: