Forcing as a computational process, Kobe Set Theory Workshop, March 2021

This will be a talk for the Kobe Set Theory Workshop, held on the occasion of Sakaé Fuchino’s retirement, 9-11 March 2021.

Abstract. I shall discuss senses in which set-theoretic forcing can be seen as a computational process on the models of set theory. Given an oracle for the atomic or elementary diagram of a model of set theory $\langle M,\in^M\rangle$, for example, one may in various senses compute $M$-generic filters $G\subset P\in M$ and the corresponding forcing extensions $M[G]$. Meanwhile, no such computational process is functorial, for there must always be isomorphic alternative presentations of the same model of set theory $M$ that lead by the computational process to non-isomorphic forcing extensions $M[G]\not\cong M[G’]$. Indeed, there is no Borel function providing generic filters that is functorial in this sense.

This is joint work with Russell Miller and Kameryn Williams.

Forcing as a computational process

  • J. D. Hamkins, R. Miller, and K. J. Williams, “Forcing as a computational process,” Mathematics arXiv, 2020. (Under review)  
    @ARTICLE{HamkinsMillerWilliams:Forcing-as-a-computational-process,
    author = {Joel David Hamkins and Russell Miller and Kameryn J. Williams},
    title = {Forcing as a computational process},
    journal = {Mathematics arXiv},
    year = {2020},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    url = {http://jdh.hamkins.org/forcing-as-a-computational-process},
    eprint = {2007.00418},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Nonlinearity in the hierarchy of large cardinal consistency strength

This is currently a draft version only of my article-in-progress on the topic of linearity in the hierarchy of consistency strength, especially with large cardinals. Comments are very welcome, since I am still writing the article. Please kindly send me comments by email or just post here.

This article will be the basis of the Weeks 7 & 8 discussion in the Graduate Philosophy of Logic seminar I am currently running with Volker Halbach at Oxford in Hilary term 2021.

I present instances of nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength—as natural or as nearly natural as I can make them—and consider philosophical aspects of the question of naturality with regard to this phenomenon.

It is a mystery often mentioned in the foundations of mathematics, a fundamental phenomenon to be explained, that our best and strongest mathematical theories seem to be linearly ordered and indeed well-ordered by consistency strength. Given any two of the familiar large cardinal hypotheses, for example, generally one of them will prove the consistency of the other.

Why should it be linear? Why should the large cardinal notions line up like this, when they often arise from completely different mathematical matters? Measurable cardinals arise from set-theoretic issues in measure theory; Ramsey cardinals generalize ideas in graph coloring combinatorics; compact cardinals arise with compactness properties of infinitary logic. Why should these disparate considerations lead to principles that are linearly related by direct implication and consistency strength?

The phenomenon is viewed by many in the philosophy of mathematics as significant in our quest for mathematical truth. In light of Gödel incompleteness, after all, we must eternally seek to strengthen even our best and strongest theories. Is the linear hierarchy of consistency strength directing us along the elusive path, the “one road upward” as John Steel describes it, toward the final, ultimate mathematical truth? That is the tantalizing possibility.

Meanwhile, we do know as a purely formal matter that the hierarchy of consistency strength is not actually well-ordered—it is ill-founded, densely ordered, and nonlinear. The statements usually used to illustrate these features, however, are weird self-referential assertions constructed in the Gödelian manner via the fixed-point lemma—logic-game trickery, often dismissed as unnatural.

Many set theorists claim that amongst the natural assertions, consistency strengths remain linearly ordered and indeed well ordered. H. Friedman refers to “the apparent comparability of naturally occurring logical strengths as one of the great mysteries of [the foundations of mathematics].” Andrés Caicedo says,

It is a remarkable empirical phenomenon that we indeed have comparability for natural theories. We expect this to always be the case, and a significant amount of work in inner model theory is guided by this belief.

Stephen G. Simpson writes:

It is striking that a great many foundational theories are linearly ordered by <. Of course it is possible to construct pairs of artificial theories which are incomparable under <. However, this is not the case for the “natural” or non-artificial theories which are usually regarded as significant in the foundations of mathematics. The problem of explaining this observed regularity is a challenge for future foundational research.

John Steel writes “The large cardinal hypotheses [the ones we know] are themselves wellordered by consistency strength,” and he formulates what he calls the “vague conjecture” asserting that

If T is a natural extension of ZFC, then there is an extension H axiomatized by large cardinal hypotheses such that T ≡ Con H. Moreover, ≤ Con is a prewellorder of the natural extensions of ZFC. In particular, if T and U are natural extensions of ZFC, then either T ≤ Con U or U ≤ Con T.

Peter Koellner writes

Remarkably, it turns out that when one restricts to those theories that “arise in nature” the interpretability ordering is quite simple: There are no descending chains and there are no incomparable elements—the interpretability ordering on theories that “arise in nature” is a wellordering.

Let me refer to this position as the natural linearity position, the assertion that all natural assertions of mathematics are linearly ordered by consistency strength. The strong form of the position, asserted by some of those whom I have cited above, asserts that the natural assertions of mathematics are indeed well-ordered by consistency strength. By all accounts, this view appears to be widely held in large cardinal set theory and the philosophy of set theory.

Despite the popularity of this position, I should like in this article to explore the contrary view and directly to challenge the natural linearity position.

Main Question. Can we find natural instances of nonlinearity and illfoundedness in the hierarchy of consistency strength?

I shall try my best.

You have to download the article to see my candidates for natural instances of nonlinearity in the hierarchy of large cardinal consistency strength, but I can tease you a little by mentioning that there are various cautious enumerations of the ZFC axioms which actually succeed in enumerating all the ZFC axioms, but with a strictly weaker consistency strength than the usual (incautious) enumeration. And similarly there are various cautious versions of the large cardinal hypothesis, which are natural, but also incomparable in consistency strength.

(Please note that it was Uri Andrews, rather than Uri Abraham, who settled question 16 with the result of theorem 17. I have corrected this from an earlier draft.)

Proof and the Art of Mathematics: Examples and Extensions

A companion volume to my proof-writing book, Proof and the Art of Mathematics.

  • J. D. Hamkins, Proof and the Art of Mathematics: Examples and Extensions, MIT Press, 2021.  
    @BOOK{Hamkins2021:Proof-and-the-art-examples,
    author = {Joel David Hamkins},
    editor = {},
    title = {{Proof and the Art of Mathematics: Examples and Extensions}},
    publisher = {MIT Press},
    year = {2021},
    volume = {},
    number = {},
    series = {},
    address = {},
    edition = {},
    month = {},
    note = {},
    abstract = {},
    isbn = {9780262542203},
    price = {},
    keywords = {book},
    source = {},
    }

Now available!

From the Preface:

The best way to learn mathematics is to dive in and do it. Don’t just listen passively to a lecture or read a book—you have got to take hold of the mathematical ideas yourself! Mount your own mathematical analysis. Formulate your own mathematical assertions. Consider your own mathematical examples. I recommend play—adopt an attitude of playful curiosity about mathematical ideas; grasp new concepts by exploring them in particular cases; try them out; understand how the mathematical constructions from your proofs manifest in your examples; explore all facets, going beyond whatever had been expected. You will find vast new lands of imagination. Let one example generalize to a whole class of examples; have favorite examples. Ask questions about the examples or about the mathematical idea you are investigating. Formulate conjectures and test them with your examples. Try to prove the conjectures—when you succeed, you will have proved a theorem. The essential mathematical activity is to make clear claims and provide sound reasons for them. Express your mathematical ideas to others, and practice the skill of stating matters well, succinctly, with accuracy and precision. Don’t be satisfied with your initial account, even when it is sound, but seek to improve it. Find alternative arguments, even when you already have a solid proof. In this way, you will come to a deeper understanding. Test the statements of others; ask for further explanation. Look into the corner cases of your results to probe the veracity of your claims. Set yourself the challenge either to prove or to refute a given statement. Aim to produce clear and correct mathematical arguments that logically establish their conclusions, with whatever insight and elegance you can muster.

This book is offered as a companion volume to my book Proof and the Art of Mathematics, which I have described as a mathematical coming-of-age book for students learning how to write mathematical proofs.

Spanning diverse topics from number theory and graph theory to game theory and real analysis, Proof and the Art shows how to prove a mathematical theorem, with advice and tips for sound mathematical habits and practice, as well as occasional reflective philosophical discussions about what it means to undertake mathematical proof. In Proof and the Art, I offer a few hundred mathematical exercises, challenges to the reader to prove a given mathematical statement, each a small puzzle to figure out; the intention is for students to develop their mathematical skills with these challenges of mathematical reasoning and proof.

Here in this companion volume, I provide fully worked-out solutions to all of the odd-numbered exercises, as well as a few of the even-numbered exercises. In many cases, the solutions here explore beyond the exercise question itself to natural extensions of the ideas. My attitude is that, once you have solved a problem, why not push the ideas harder to see what further you can prove with them? These solutions are examples of how one might write a mathematical proof. I hope that you will learn from them; let us go through them together. The mathematical development of this text follows the main book, with the same chapter topics in the same order, and all theorem and exercise numbers in this text refer to the corresponding statements of the main text.

Lectures on the Philosophy of Mathematics

  • J. D. Hamkins, Lectures on the Philosophy of Mathematics, MIT Press, 2021.  
    @BOOK{Hamkins2021:Lectures-on-the-philosophy-of-mathematics,
    author = {Joel David Hamkins},
    editor = {},
    title = {{Lectures on the Philosophy of Mathematics}},
    publisher = {MIT Press},
    year = {2021},
    volume = {},
    number = {},
    series = {},
    address = {},
    edition = {},
    month = {},
    note = {},
    abstract = {},
    isbn = {9780262542234},
    price = {},
    keywords = {book},
    source = {},
    }

Now available for preorder!

From the Preface:

Philosophical conundrums pervade mathematics, from fundamental questions of mathematical ontology—What is a number? What is infinity?—to questions about the relations among truth, proof, and meaning. What is the role of figures in geometric argument? Do mathematical objects exist that we cannot construct? Can every mathematical question be solved in principle by computation? Is every truth of mathematics true for a reason? Can every mathematical truth be proved?

This book is an introduction to the philosophy of mathematics, in which we shall consider all these questions and more. I come to the subject from mathematics, and I have strived in this book for what I hope will be a fresh approach to the philosophy of mathematics—one grounded in mathematics, motivated by mathematical inquiry or mathematical practice. I have strived to treat philosophical issues as they arise organically in mathematics. Therefore, I have organized the book by mathematical themes, such as number, infinity, geometry, and computability, and I have included some mathematical arguments and elementary proofs when they bring philosophical issues to light.

Modal model theory

This is joint work with Wojciech Aleksander Wołoszyn, who is about to begin as a DPhil student with me in mathematics here in Oxford. We began and undertook this work over the past year, while he was a visitor in Oxford under the Recognized Student program.

  • J. D. Hamkins and W. A. Wołoszyn, “Modal model theory,” Mathematics arXiv, 2020.  
    @ARTICLE{HamkinsWoloszyn:Modal-model-theory,
    title={Modal model theory},
    author={Joel David Hamkins and Wojciech Aleksander Wołoszyn},
    journal = {Mathematics arXiv},
    year={2020},
    eprint={2009.09394},
    archivePrefix={arXiv},
    primaryClass={math.LO}
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    }

Abstract. We introduce the subject of modal model theory, where one studies a mathematical structure within a class of similar structures under an extension concept that gives rise to mathematically natural notions of possibility and necessity. A statement $\varphi$ is possible in a structure (written $\Diamond\varphi$) if $\varphi$ is true in some extension of that structure, and $\varphi$ is necessary (written $\Box\varphi$) if it is true in all extensions of the structure. A principal case for us will be the class $\text{Mod}(T)$ of all models of a given theory $T$—all graphs, all groups, all fields, or what have you—considered under the substructure relation. In this article, we aim to develop the resulting modal model theory. The class of all graphs is a particularly insightful case illustrating the remarkable power of the modal vocabulary, for the modal language of graph theory can express connectedness, $k$-colorability, finiteness, countability, size continuum, size $\aleph_1$, $\aleph_2$, $\aleph_\omega$, $\beth_\omega$, first $\beth$-fixed point, first $\beth$-hyper-fixed-point and much more. A graph obeys the maximality principle $\Diamond\Box\varphi(a)\to\varphi(a)$ with parameters if and only if it satisfies the theory of the countable random graph, and it satisfies the maximality principle for sentences if and only if it is universal for finite graphs.

Follow through the arXiv for a pdf of the article.

  • J. D. Hamkins and W. A. Wołoszyn, “Modal model theory,” Mathematics arXiv, 2020.  
    @ARTICLE{HamkinsWoloszyn:Modal-model-theory,
    title={Modal model theory},
    author={Joel David Hamkins and Wojciech Aleksander Wołoszyn},
    journal = {Mathematics arXiv},
    year={2020},
    eprint={2009.09394},
    archivePrefix={arXiv},
    primaryClass={math.LO}
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    }

Categorical large cardinals and the tension between categoricity and set-theoretic reflection

  • J. D. Hamkins and R. Solberg, “Categorical large cardinals and the tension between categoricity and set-theoretic reflection,” Mathematics arXiv, 2020. (Under review)  
    @ARTICLE{HamkinsSolberg:Categorical-large-cardinals,
    author = {Joel David Hamkins and Robin Solberg},
    title = {Categorical large cardinals and the tension between categoricity and set-theoretic reflection},
    journal = {Mathematics arXiv},
    year = {2020},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    url = {http://jdh.hamkins.org/categorical-large-cardinals/},
    source = {},
    doi = {},
    eprint = {2009.07164},
    archivePrefix ={arXiv},
    primaryClass = {math.LO}
    }

Abstract. Inspired by Zermelo’s quasi-categoricity result characterizing the models of second-order Zermelo-Fraenkel set theory $\text{ZFC}_2$, we investigate when those models are fully categorical, characterized by the addition to $\text{ZFC}_2$ either of a first-order sentence, a first-order theory, a second-order sentence or a second-order theory. The heights of these models, we define, are the categorical large cardinals. We subsequently consider various philosophical aspects of categoricity for structuralism and realism, including the tension between categoricity and set-theoretic reflection, and we present (and criticize) a categorical characterization of the set-theoretic universe $\langle V,\in\rangle$ in second-order logic.

Categorical accounts of various mathematical structures lie at the very core of structuralist mathematical practice, enabling mathematicians to refer to specific mathematical structures, not by having carefully to prepare and point at specially constructed instances—preserved like the one-meter iron bar locked in a case in Paris—but instead merely by mentioning features that uniquely characterize the structure up to isomorphism.

The natural numbers $\langle \mathbb{N},0,S\rangle$, for example, are uniquely characterized by the Dedekind axioms, which assert that $0$ is not a successor, that the successor function $S$ is one-to-one, and that every set containing $0$ and closed under successor contains every number. We know what we mean by the natural numbers—they have a definite realness—because we can describe features that completely determine the natural number structure. The real numbers $\langle\mathbb{R},+,\cdot,0,1\rangle$ similarly are characterized up to isomorphism as the unique complete ordered field. The complex numbers $\langle\mathbb{C},+,\cdot\rangle$ form the unique algebraically closed field of characteristic $0$ and size continuum, or alternatively, the unique algebraic closure of the real numbers. In fact all our fundamental mathematical structures enjoy such categorical characterizations, where a theory is categorical if it identifies a unique mathematical structure up to isomorphism—any two models of the theory are isomorphic. In light of the Löwenheim-Skolem theorem, which prevents categoricity for infinite structures in first-order logic, these categorical theories are generally made in second-order logic.

In set theory, Zermelo characterized the models of second-order Zermelo-Fraenkel set theory $\text{ZFC}_2$ in his famous quasi-categoricity result:

Theorem. (Zermelo, 1930) The models of $\text{ZFC}_2$ are precisely those isomorphic to a rank-initial segment $\langle V_\kappa,\in\rangle$ of the cumulative set-theoretic universe $V$ cut off at an inaccessible cardinal $\kappa$.

It follows that for any two models of $\text{ZFC}_2$, one of them is isomorphic to an initial segment of the other. These set-theoretic models $V_\kappa$ have now come to be known as Zermelo-Grothendieck universes, in light of Grothendieck’s use of them in category theory (a rediscovery several decades after Zermelo); they feature in the universe axiom, which asserts that every set is an element of some such $V_\kappa$, or equivalently, that there are unboundedly many inaccessible cardinals.

In this article, we seek to investigate the extent to which Zermelo’s quasi-categoricity analysis can rise fully to the level of categoricity, in light of the observation that many of the $V_\kappa$ universes are categorically characterized by their sentences or theories.

Question. Which models of $\text{ZFC}_2$ satisfy fully categorical theories?

If $\kappa$ is the smallest inaccessible cardinal, for example, then up to isomorphism $V_\kappa$ is the unique model of $\text{ZFC}_2$ satisfying the first-order sentence “there are no inaccessible cardinals.” The least inaccessible cardinal is therefore an instance of what we call a first-order sententially categorical cardinal. Similar ideas apply to the next inaccessible cardinal, and the next, and so on for quite a long way. Many of the inaccessible universes thus satisfy categorical theories extending $\text{ZFC}_2$ by a sentence or theory, either in first or second order, and we should like to investigate these categorical extensions of $\text{ZFC}_2$.

In addition, we shall discuss the philosophical relevance of categoricity and point particularly to the philosophical problem posed by the tension between the widespread support for categoricity in our fundamental mathematical structures with set-theoretic ideas on reflection principles, which are at heart anti-categorical.

Our main theme concerns these notions of categoricity:

Main Definition.

  • A cardinal $\kappa$ is first-order sententially categorical, if there is a first-order sentence $\sigma$ in the language of set theory, such that $V_\kappa$ is categorically characterized by $\text{ZFC}_2+\sigma$.
  • A cardinal $\kappa$ is first-order theory categorical, if there is a first-order theory $T$ in the language of set theory, such that $V_\kappa$ is categorically characterized by $\text{ZFC}_2+T$.
  • A cardinal $\kappa$ is second-order sententially categorical, if there is a second-order sentence $\sigma$ in the language of set theory, such that $V_\kappa$ is categorically characterized by $\text{ZFC}_2+\sigma$.
  • A cardinal $\kappa$ is second-order theory categorical, if there is a second-order theory $T$ in the language of set theory, such that $V_\kappa$ is categorically characterized by $\text{ZFC}_2+T$.

Follow through to the arxiv for the pdf to read more:

  • J. D. Hamkins and R. Solberg, “Categorical large cardinals and the tension between categoricity and set-theoretic reflection,” Mathematics arXiv, 2020. (Under review)  
    @ARTICLE{HamkinsSolberg:Categorical-large-cardinals,
    author = {Joel David Hamkins and Robin Solberg},
    title = {Categorical large cardinals and the tension between categoricity and set-theoretic reflection},
    journal = {Mathematics arXiv},
    year = {2020},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    url = {http://jdh.hamkins.org/categorical-large-cardinals/},
    source = {},
    doi = {},
    eprint = {2009.07164},
    archivePrefix ={arXiv},
    primaryClass = {math.LO}
    }

Related talk: Categorical cardinals, CUNY Set Theory Seminar, June 2020

Choiceless large cardinals and set-theoretic potentialism

  • R. Cutolo and J. D. Hamkins, “Choiceless large cardinals and set-theoretic potentialism,” , p. 10 pages, 2020. (Under review)  
    @ARTICLE{CutoloHamkins:Choiceless-large-cardinals-and-set-theoretic-potentialism,
    author = {Raffaella Cutolo and Joel David Hamkins},
    title = {Choiceless large cardinals and set-theoretic potentialism},
    journal = {},
    year = {2020},
    volume = {},
    number = {},
    pages = {10 pages},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    url = {http://jdh.hamkins.org/choiceless-large-cardinals-and-set-theoretic-potentialism},
    eprint = {2007.01690},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Abstract. We define a potentialist system of ZF-structures, that is, a collection of possible worlds in the language of ZF connected by a binary accessibility relation, achieving a potentialist account of the full background set-theoretic universe $V$. The definition involves Berkeley cardinals, the strongest known large cardinal axioms, inconsistent with the Axiom of Choice. In fact, as background theory we assume just ZF. It turns out that the propositional modal assertions which are valid at every world of our system are exactly those in the modal theory S4.2. Moreover, we characterize the worlds satisfying the potentialist maximality principle, and thus the modal theory S5, both for assertions in the language of ZF and for assertions in the full potentialist language.

Forcing as a computational process

  • J. D. Hamkins, R. Miller, and K. J. Williams, “Forcing as a computational process,” Mathematics arXiv, 2020. (Under review)  
    @ARTICLE{HamkinsMillerWilliams:Forcing-as-a-computational-process,
    author = {Joel David Hamkins and Russell Miller and Kameryn J. Williams},
    title = {Forcing as a computational process},
    journal = {Mathematics arXiv},
    year = {2020},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    url = {http://jdh.hamkins.org/forcing-as-a-computational-process},
    eprint = {2007.00418},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Abstract. We investigate how set-theoretic forcing can be seen as a computational process on the models of set theory. Given an oracle for information about a model of set theory $\langle M,\in^M\rangle$, we explain senses in which one may compute $M$-generic filters $G\subseteq\mathbb{P}\in M$ and the corresponding forcing extensions $M[G]$. Specifically, from the atomic diagram one may compute $G$, from the $\Delta_0$-diagram one may compute $M[G]$ and its $\Delta_0$-diagram, and from the elementary diagram one may compute the elementary diagram of $M[G]$. We also examine the information necessary to make the process functorial, and conclude that in the general case, no such computational process will be functorial. For any such process, it will always be possible to have different isomorphic presentations of a model of set theory $M$ that lead to different non-isomorphic forcing extensions $M[G]$. Indeed, there is no Borel function providing generic filters that is functorial in this sense.

My view of Univ

Appearing in The Martlet, Issue 11, Spring 2020, University College, Oxford.

My view of Univ

“I came to Oxford last year, leaving an established career in New York, and found a welcoming new home, an ideal environment for research and intellectual stimulation. Through the big wooden door to the Main Quad, I enter the College each day to find fascinating new conversations with historians, classicists, geologists, political scientists, medical scientists, mathematicians, philosophers, artists and even Egyptologists. What a life! I take on Oxford like a fine wool coat, enveloping me, suiting me perfectly.”


Professor Joel David Hamkins, Sir Peter Strawson Fellow in Philosophy at Univ and Professor of Logic at Oxford

Proof and the Art of Mathematics

A coming-of-age book for mathematicians aspiring to write proofs.

  • J. D. Hamkins, Proof and the Art of Mathematics, MIT Press, 2020.  
    @BOOK{Hamkins2020:Proof-and-the-art-of-mathematics,
    author = {Joel David Hamkins},
    title = {Proof and the {Art} of {Mathematics}},
    publisher = {MIT Press},
    year = {2020},
    isbn = {978-0-262-53979-1},
    keywords = {book},
    url = {https://mitpress.mit.edu/books/proof-and-art-mathematics},
    }

Now available!

From the Preface:

This is a mathematical coming-of-age book, for students on the cusp, who are maturing into mathematicians, aspiring to communicate mathematical truths to other mathematicians in the currency of mathematics, which is: proof. This is a book for students who are learning—perhaps for the first time in a serious way—how to write a mathematical proof. I hope to show how a mathematician makes an argument establishing a mathematical truth.

Proofs tell us not only that a mathematical statement is true, but also why it is true, and they communicate this truth. The best proofs give us insight into the nature of mathematical reality. They lead us to those sublime yet elusive Aha! moments, a joyous experience for any mathematician, occurring when a previously opaque, confounding issue becomes transparent and our mathematical gaze suddenly penetrates completely through it, grasping it all in one take. So let us learn together how to write proofs well, producing clear and correct mathematical arguments that logically establish their conclusions, with whatever insight and elegance we can muster. We shall do so in the context of the diverse mathematical topics that I have gathered together here in this book for the purpose.

Bi-interpretation in weak set theories

  • A. R. Freire and J. D. Hamkins, “Bi-interpretation in weak set theories,” Mathematics arXiv, 2020. (Under review)  
    @ARTICLE{FreireHamkins:Bi-interpretation-in-weak-set-theories,
    author = {Alfredo Roque Freire and Joel David Hamkins},
    title = {Bi-interpretation in weak set theories},
    journal = {Mathematics arXiv},
    year = {2020},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    url = {http://jdh.hamkins.org/bi-interpretation-in-weak-set-theories},
    eprint = {2001.05262},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Abstract. In contrast to the robust mutual interpretability phenomenon in set theory, Ali Enayat proved that bi-interpretation is absent: distinct theories extending ZF are never bi-interpretable and models of ZF are bi-interpretable only when they are isomorphic. Nevertheless, for natural weaker set theories, we prove, including Zermelo-Fraenkel set theory $\newcommand\ZFCm{\text{ZFC}^-}\ZFCm$ without power set and Zermelo set theory Z, there are nontrivial instances of bi-interpretation. Specifically, there are well-founded models of ZFC- that are bi-interpretable, but not isomorphic — even $\langle H_{\omega_1},\in\rangle$ and $\langle H_{\omega_2},\in\rangle$ can be bi-interpretable — and there are distinct bi-interpretable theories extending ZFC-. Similarly, using a construction of Mathias, we prove that every model of ZF is bi-interpretable with a model of Zermelo set theory in which the replacement axiom fails.

Set theory exhibits a robust mutual interpretability phenomenon: in a given model of set theory, we can define diverse other interpreted models of set theory. In any model of Zermelo-Fraenkel ZF set theory, for example, we can define an interpreted model of ZFC + GCH, via the constructible universe, as well as definable interpreted models of ZF + ¬AC, of ZFC + MA + ¬CH, of ZFC + $\mathfrak{b}<\mathfrak{d}$, and so on for hundreds of other theories. For these latter theories, set theorists often use forcing to construct outer models of the given model; but nevertheless the Boolean ultrapower method provides definable interpreted models of these theories inside the original model (explained in theorem 7). Similarly, in models of ZFC with large cardinals, one can define fine-structural canonical inner models with large cardinals and models of ZF satisfying various determinacy principles, and vice versa. In this way, set theory exhibits an abundance of natural mutually interpretable theories.

Do these instances of mutual interpretation fulfill the more vigourous conception of bi-interpretation? Two models or theories are mutually interpretable, when merely each is interpreted in the other, whereas bi-interpretation requires that the interpretations are invertible in a sense after iteration, so that if one should interpret one model or theory in the other and then re-interpret the first theory inside that, then the resulting model should be definably isomorphic to the original universe (precise definitions in sections 2 and 3). The interpretations mentioned above are not bi-interpretations, for if we start in a model of ZFC+¬CH and then go to L in order to interpret a model of ZFC+GCH, then we’ve already discarded too much set-theoretic information to expect that we could get a copy of our original model back by interpreting inside L. This problem is inherent, in light of the following theorem of Ali Enayat, showing that indeed there is no nontrivial bi-interpretation phenomenon to be found amongst the set-theoretic models and theories satisfying ZF. In interpretation, one must inevitably discard set-theoretic information.

Theorem. (Enayat 2016)

  1. ZF is solid: no two models of ZF are bi-interpretable.
  2. ZF is tight: no two distinct theories extending ZF are bi-interpretable.

The proofs of these theorems, provided in section 6, seem to use the full strength of ZF, and Enayat had consequently inquired whether the solidity/tightness phenomenon somehow required the strength of ZF set theory. In this paper, we shall find support for that conjecture by establishing nontrivial instances of bi-interpretation in various natural weak set theories, including Zermelo-Fraenkel theory $\ZFCm$, without the power set axiom, and Zermelo set theory Z, without the replacement axiom.

Main Theorems

  1. $\ZFCm$ is not solid: there are well-founded models of $\ZFCm$ that are bi-interpretable, but not isomorphic.
  2. Indeed, it is relatively consistent with ZFC that $\langle H_{\omega_1},\in\rangle$ and $\langle H_{\omega_2},\in\rangle$ are bi-interpretable.
  3. $\ZFCm$ is not tight: there are distinct bi-interpretable extensions of $\ZFCm$.
  4. Z is not solid: there are well-founded models of Z that are bi-interpretable, but not isomorphic.
  5. Indeed, every model of ZF is bi-interpretable with a transitive inner model of Z in which the replacement axiom fails.
  6. Z is not tight: there are distinct bi-interpretable extensions of Z.

    These claims are made and proved in theorems 20, 17, 21 and 22. We shall in addition prove the following theorems on this theme:

  7. Well-founded models of ZF set theory are never mutually interpretable.
  8. The Väänänen internal categoricity theorem does not hold for $\ZFCm$, not even for well-founded models.

These are theorems 14 and 16. Statement (8) concerns the existence of a model $\langle M,\in,\bar\in\rangle$ satisfying $\ZFCm(\in,\bar\in)$, meaning $\ZFCm$ in the common language with both predicates, using either $\in$ or $\bar\in$ as the membership relation, such that $\langle M,\in\rangle$ and $\langle M,\bar\in\rangle$ are not isomorphic.

Read more in the full article:

  • A. R. Freire and J. D. Hamkins, “Bi-interpretation in weak set theories,” Mathematics arXiv, 2020. (Under review)  
    @ARTICLE{FreireHamkins:Bi-interpretation-in-weak-set-theories,
    author = {Alfredo Roque Freire and Joel David Hamkins},
    title = {Bi-interpretation in weak set theories},
    journal = {Mathematics arXiv},
    year = {2020},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    source = {},
    doi = {},
    url = {http://jdh.hamkins.org/bi-interpretation-in-weak-set-theories},
    eprint = {2001.05262},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

The $\Sigma_1$-definable universal finite sequence

  • J. D. Hamkins and K. J. Williams, “The $\Sigma_1$-definable universal finite sequence,” ArXiv e-prints, 2019. (Under review)  
    @ARTICLE{HamkinsWilliams:The-universal-finite-sequence,
    author = {Joel David Hamkins and Kameryn J. Williams},
    title = {The $\Sigma_1$-definable universal finite sequence},
    journal = {ArXiv e-prints},
    year = {2019},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Under review},
    abstract = {},
    keywords = {under-review},
    eprint = {1909.09100},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    source = {},
    doi = {},
    }

Abstract. We introduce the $\Sigma_1$-definable universal finite sequence and prove that it exhibits the universal extension property amongst the countable models of set theory under end-extension. That is, (i) the sequence is $\Sigma_1$-definable and provably finite; (ii) the sequence is empty in transitive models; and (iii) if $M$ is a countable model of set theory in which the sequence is $s$ and $t$ is any finite extension of $s$ in this model, then there is an end extension of $M$ to a model in which the sequence is $t$. Our proof method grows out of a new infinitary-logic-free proof of the Barwise extension theorem, by which any countable model of set theory is end-extended to a model of $V=L$ or indeed any theory true in a suitable submodel of the original model. The main theorem settles the modal logic of end-extensional potentialism, showing that the potentialist validities of the models of set theory under end-extensions are exactly the assertions of S4. Finally, we introduce the end-extensional maximality principle, which asserts that every possibly necessary sentence is already true, and show that every countable model extends to a model satisfying it.

  • The universal algorithm,
    • J. D. Hamkins and H. W. Woodin, “The universal finite set,” ArXiv e-prints, pp. 1-16, 2017. (Manuscript under review)  
      @ARTICLE{HamkinsWoodin:The-universal-finite-set,
      author = {Joel David Hamkins and W. Hugh Woodin},
      title = {The universal finite set},
      journal = {ArXiv e-prints},
      year = {2017},
      volume = {},
      number = {},
      pages = {1--16},
      month = {},
      note = {Manuscript under review},
      abstract = {},
      keywords = {under-review},
      source = {},
      doi = {},
      eprint = {1711.07952},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      url = {http://jdh.hamkins.org/the-universal-finite-set},
      }
  • The modal logic of arithmetic potentialism,
    • J. D. Hamkins, “The modal logic of arithmetic potentialism and the universal algorithm,” ArXiv e-prints, pp. 1-35, 2018. (Under review)  
      @ARTICLE{Hamkins:The-modal-logic-of-arithmetic-potentialism,
      author = {Joel David Hamkins},
      title = {The modal logic of arithmetic potentialism and the universal algorithm},
      journal = {ArXiv e-prints},
      year = {2018},
      volume = {},
      number = {},
      pages = {1--35},
      month = {},
      eprint = {1801.04599},
      archivePrefix = {arXiv},
      primaryClass = {math.LO},
      note = {Under review},
      url = {http://wp.me/p5M0LV-1Dh},
      abstract = {},
      keywords = {under-review},
      source = {},
      doi = {},
      }
  • A new proof of the Barwise extension theorem
  • Kameryn’s blog post about the paper


Representing Ordinal Numbers with Arithmetically Interesting Sets of Real Numbers

  • D. D. Blair, J. D. Hamkins, and K. O’Bryant, “Representing Ordinal Numbers with Arithmetically Interesting Sets of Real Numbers,” Integers, vol. 20A, 2020. (Paper~A3, \url{http://math.colgate.edu/~integers/vol20a.html})  
    @ARTICLE{BlairHamkinsOBryant2020:Representing-ordinal-numbers-with-arithmetically-interesting-sets-of-real-numbers,
    author = {D. Dakota Blair and Joel David Hamkins and Kevin O'Bryant},
    title = {Representing Ordinal Numbers with Arithmetically Interesting Sets of Real Numbers},
    journal = {Integers},
    FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
    year = {2020},
    volume = {20A},
    number = {},
    pages = {},
    month = {},
    note = {Paper~A3, \url{http://math.colgate.edu/~integers/vol20a.html}},
    abstract = {},
    keywords = {},
    source = {},
    doi = {},
    url = {https://wp.me/p5M0LV-1Tg},
    eprint = {1905.13123},
    archivePrefix = {arXiv},
    primaryClass = {math.NT},
    }

Abstract. For a real number $x$ and set of natural numbers $A$, define $x∗A = \{xa \mod 1 \mid a \in A\}\subseteq [0,1)$. We consider relationships between $x$, $A$, and the order-type of $x∗A$. For example, for every irrational $x$ and order-type $\alpha$, there is an $A$ with $x ∗ A \simeq\alpha$, but if $\alpha$ is an ordinal, then $A$ must be a thin set. If, however, $A$ is restricted to be a subset of the powers of $2$, then not every order type is possible, although arbitrarily large countable well orders arise.

Kelley-Morse set theory does not prove the class Fodor principle

      • V. Gitman, J. D. Hamkins, and A. Karagila, “Kelley-Morse set theory does not prove the class Fodor theorem,” ArXiv e-prints, 2019. (Manuscript under review)  
        @ARTICLE{GitmanHamkinsKaragila:KM-set-theory-does-not-prove-the-class-Fodor-theorem,
        author = {Victoria Gitman and Joel David Hamkins and Asaf Karagila},
        title = {Kelley-Morse set theory does not prove the class {F}odor theorem},
        journal = {ArXiv e-prints},
        year = {2019},
        volume = {},
        number = {},
        pages = {},
        month = {},
        note = {Manuscript under review},
        abstract = {},
        keywords = {under-review},
        eprint = {1904.04190},
        archivePrefix = {arXiv},
        primaryClass = {math.LO},
        source = {},
        doi = {},
        url = {http://wp.me/p5M0LV-1RD},
        }

Abstract.
We show that Kelley-Morse (KM) set theory does not prove the class Fodor principle, the assertion that every regressive class function $F:S\to\newcommand\Ord{\text{Ord}}\Ord$ defined on a stationary class $S$ is constant on a stationary subclass. Indeed, it is relatively consistent with KM for any infinite $\lambda$ with $\omega\leq\lambda\leq\Ord$ that there is a class function $F:\Ord\to\lambda$ that is not constant on any stationary class. Strikingly, it is consistent with KM that there is a class $A\subseteq\omega\times\Ord$, such that each section $A_n=\{\alpha\mid (n,\alpha)\in A\}$ contains a class club, but $\bigcap_n A_n$ is empty. Consequently, it is relatively consistent with KM that the class club filter is not $\sigma$-closed.

The class Fodor principle is the assertion that every regressive class function $F:S\to\Ord$ defined on a stationary class $S$ is constant on a stationary subclass of $S$. This statement can be expressed in the usual second-order language of set theory, and the principle can therefore be sensibly considered in the context of any of the various second-order set-theoretic systems, such as Gödel-Bernays (GBC) set theory or Kelley-Morse (KM) set theory. Just as with the classical Fodor’s lemma in first-order set theory, the class Fodor principle is equivalent, over a weak base theory, to the assertion that the class club filter is normal. We shall investigate the strength of the class Fodor principle and try to find its place within the natural hierarchy of second-order set theories. We shall also define and study weaker versions of the class Fodor principle.

If one tries to prove the class Fodor principle by adapting one of the classical proofs of the first-order Fodor’s lemma, then one inevitably finds oneself needing to appeal to a certain second-order class-choice principle, which goes beyond the axiom of choice and the global choice principle, but which is not available in Kelley-Morse set theory. For example, in one standard proof, we would want for a given $\Ord$-indexed sequence of non-stationary classes to be able to choose for each member of it a class club that it misses. This would be an instance of class-choice, since we seek to choose classes here, rather than sets. The class choice principle $\text{CC}(\Pi^0_1)$, it turns out, is sufficient for us to make these choices, for this principle states that if every ordinal $\alpha$ admits a class $A$ witnessing a $\Pi^0_1$-assertion $\varphi(\alpha,A)$, allowing class parameters, then there is a single class $B\subseteq \Ord\times V$, whose slices $B_\alpha$ witness $\varphi(\alpha,B_\alpha)$; and the property of being a class club avoiding a given class is $\Pi^0_1$ expressible.

Thus, the class Fodor principle, and consequently also the normality of the class club filter, is provable in the relatively weak second-order set theory $\text{GBC}+\text{CC}(\Pi^0_1)$. This theory is known to be weaker in consistency strength than the theory $\text{GBC}+\Pi^1_1$-comprehension, which is itself strictly weaker in consistency strength than KM.

But meanwhile, although the class choice principle is weak in consistency strength, it is not actually provable in KM; indeed, even the weak fragment $\text{CC}(\Pi^0_1)$ is not provable in KM. Those results were proved several years ago by the first two authors, but they can now be seen as consequences of the main result of this article (see corollary 15. In light of that result, however, one should perhaps not have expected to be able to prove the class Fodor principle in KM.

Indeed, it follows similarly from arguments of the third author in his dissertation that if $\kappa$ is an inaccessible cardinal, then there is a forcing extension $V[G]$ with a symmetric submodel $M$ such that $V_\kappa^M=V_\kappa$, which implies that $\mathcal M=(V_\kappa,\in, V^M_{\kappa+1})$ is a model of Kelley-Morse, and in $\mathcal M$, the class Fodor principle fails in a very strong sense.

In this article, adapting the ideas of Karagila to the second-order set-theoretic context and using similar methods as in Gitman and Hamkins’s previous work on KM, we shall prove that every model of KM has an extension in which the class Fodor principle fails in that strong sense: there can be a class function $F:\Ord\to\omega$, which is not constant on any stationary class. In particular, in these models, the class club filter is not $\sigma$-closed: there is a class $B\subseteq\omega\times\Ord$, each of whose vertical slices $B_n$ contains a class club, but $\bigcap B_n$ is empty.

Main Theorem. Kelley-Morse set theory KM, if consistent, does not prove the class Fodor principle. Indeed, if there is a model of KM, then there is a model of KM with a class function $F:\Ord\to \omega$, which is not constant on any stationary class; in this model, therefore, the class club filter is not $\sigma$-closed.

We shall also investigate various weak versions of the class Fodor principle.

Definition.

  1. For a cardinal $\kappa$, the class $\kappa$-Fodor principle asserts that every class function $F:S\to\kappa$ defined on a stationary class $S\subseteq\Ord$ is constant on a stationary subclass of $S$.
  2. The class ${<}\Ord$-Fodor principle is the assertion that the $\kappa$-class Fodor principle holds for every cardinal $\kappa$.
  3. The bounded class Fodor principle asserts that every regressive class function $F:S\to\Ord$ on a stationary class $S\subseteq\Ord$ is bounded on a stationary subclass of $S$.
  4. The very weak class Fodor principle asserts that every regressive class function $F:S\to\Ord$ on a stationary class $S\subseteq\Ord$ is constant on an unbounded subclass of $S$.

We shall separate these principles as follows.

Theorem. Suppose KM is consistent.

  1. There is a model of KM in which the class Fodor principle fails, but the class ${<}\Ord$-Fodor principle holds.
  2. There is a model of KM in which the class $\omega$-Fodor principle fails, but the bounded class Fodor principle holds.
  3. There is a model of KM in which the class $\omega$-Fodor principle holds, but the bounded class Fodor principle fails.
  4. $\text{GB}^-$ proves the very weak class Fodor principle.

Finally, we show that the class Fodor principle can neither be created nor destroyed by set forcing.

Theorem. The class Fodor principle is invariant by set forcing over models of $\text{GBC}^-$. That is, it holds in an extension if and only if it holds in the ground model.

Let us conclude this brief introduction by mentioning the following easy negative instance of the class Fodor principle for certain GBC models. This argument seems to be a part of set-theoretic folklore. Namely, consider an $\omega$-standard model of GBC set theory $M$ having no $V_\kappa^M$ that is a model of ZFC. A minimal transitive model of ZFC, for example, has this property. Inside $M$, let $F(\kappa)$ be the least $n$ such that $V_\kappa^M$ fails to satisfy $\Sigma_n$-collection. This is a definable class function $F:\Ord^M\to\omega$ in $M$, but it cannot be constant on any stationary class in $M$, because by the reflection theorem there is a class club of cardinals $\kappa$ such that $V_\kappa^M$ satisfies $\Sigma_n$-collection.

Read more by going to the full article:

  • V. Gitman, J. D. Hamkins, and A. Karagila, “Kelley-Morse set theory does not prove the class Fodor theorem,” ArXiv e-prints, 2019. (Manuscript under review)  
    @ARTICLE{GitmanHamkinsKaragila:KM-set-theory-does-not-prove-the-class-Fodor-theorem,
    author = {Victoria Gitman and Joel David Hamkins and Asaf Karagila},
    title = {Kelley-Morse set theory does not prove the class {F}odor theorem},
    journal = {ArXiv e-prints},
    year = {2019},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {Manuscript under review},
    abstract = {},
    keywords = {under-review},
    eprint = {1904.04190},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    source = {},
    doi = {},
    url = {http://wp.me/p5M0LV-1RD},
    }

 

 

The axiom of well-ordered replacement is equivalent to full replacement over Zermelo + foundation


In recent work, Alfredo Roque Freire and I have realized that the axiom of well-ordered replacement is equivalent to the full replacement axiom, over the Zermelo set theory with foundation.

The well-ordered replacement axiom is the scheme asserting that if $I$ is well-ordered and every $i\in I$ has unique $y_i$ satisfying a property $\phi(i,y_i)$, then $\{y_i\mid i\in I\}$ is a set. In other words, the image of a well-ordered set under a first-order definable class function is a set.

Alfredo had introduced the theory Zermelo + foundation + well-ordered replacement, because he had noticed that it was this fragment of ZF that sufficed for an argument we were mounting in a joint project on bi-interpretation. At first, I had found the well-ordered replacement theory a bit awkward, because one can only apply the replacement axiom with well-orderable sets, and without the axiom of choice, it seemed that there were not enough of these to make ordinary set-theoretic arguments possible.

But now we know that in fact, the theory is equivalent to ZF.

Theorem. The axiom of well-ordered replacement is equivalent to full replacement over Zermelo set theory with foundation.

$$\text{ZF}\qquad = \qquad\text{Z} + \text{foundation} + \text{well-ordered replacement}$$

Proof. Assume Zermelo set theory with foundation and well-ordered replacement.

Well-ordered replacement is sufficient to prove that transfinite recursion along any well-order works as expected. One proves that every initial segment of the order admits a unique partial solution of the recursion up to that length, using well-ordered replacement to put them together at limits and overall.

Applying this, it follows that every set has a transitive closure, by iteratively defining $\cup^n x$ and taking the union. And once one has transitive closures, it follows that the foundation axiom can be taken either as the axiom of regularity or as the $\in$-induction scheme, since for any property $\phi$, if there is a set $x$ with $\neg\phi(x)$, then let $A$ be the set of elements $a$ in the transitive closure of $\{x\}$ with $\neg\phi(a)$; an $\in$-minimal element of $A$ is a set $a$ with $\neg\phi(a)$, but $\phi(b)$ for all $b\in a$.

Another application of transfinite recursion shows that the $V_\alpha$ hierarchy exists. Further, we claim that every set $x$ appears in the $V_\alpha$ hierarchy. This is not immediate and requires careful proof. We shall argue by $\in$-induction using foundation. Assume that every element $y\in x$ appears in some $V_\alpha$. Let $\alpha_y$ be least with $y\in V_{\alpha_y}$. The problem is that if $x$ is not well-orderable, we cannot seem to collect these various $\alpha_y$ into a set. Perhaps they are unbounded in the ordinals? No, they are not, by the following argument. Define an equivalence relation $y\sim y’$ iff $\alpha_y=\alpha_{y’}$. It follows that the quotient $x/\sim$ is well-orderable, and thus we can apply well-ordered replacement in order to know that $\{\alpha_y\mid y\in x\}$ exists as a set. The union of this set is an ordinal $\alpha$ with $x\subseteq V_\alpha$ and so $x\in V_{\alpha+1}$. So by $\in$-induction, every set appears in some $V_\alpha$.

The argument establishes the principle: for any set $x$ and any definable class function $F:x\to\text{Ord}$, the image $F\mathrel{\text{”}}x$ is a set. One proves this by defining an equivalence relation $y\sim y’\leftrightarrow F(y)=F(y’)$ and observing that $x/\sim$ is well-orderable.

We can now establish the collection axiom, using a similar idea. Suppose that $x$ is a set and every $y\in x$ has a witness $z$ with $\phi(y,z)$. Every such $z$ appears in some $V_\alpha$, and so we can map each $y\in x$ to the smallest $\alpha_y$ such that there is some $z\in V_{\alpha_y}$ with $\phi(y,z)$. By the observation of the previous paragraph, the set of $\alpha_y$ exists and so there is an ordinal $\alpha$ larger than all of them, and thus $V_\alpha$ serves as a collecting set for $x$ and $\phi$, verifying this instance of collection.

From collection and separation, we can deduce the replacement axiom $\Box$

I’ve realized that this allows me to improve an argument I had made some time ago, concerning Transfinite recursion as a fundamental principle. In that argument, I had proved that ZC + foundation + transfinite recursion is equivalent to ZFC, essentially by showing that the principle of transfinite recursion implies replacement for well-ordered sets. The new realization here is that we do not need the axiom of choice in that argument, since transfinite recursion implies well-ordered replacement, which gives us full replacement by the argument above.

Corollary. The principle of transfinite recursion is equivalent to the replacement axiom over Zermelo set theory with foundation.

$$\text{ZF}\qquad = \qquad\text{Z} + \text{foundation} + \text{transfinite recursion}$$

There is no need for the axiom of choice.