Every countable model of arithmetic or set theory has a pointwise definable end extension

  • [DOI] J. D. Hamkins, “Every countable model of arithmetic or set theory has a pointwise definable end extension,” mathematics arXiv, 2022.
    [Bibtex]
    @ARTICLE{Hamkins:Every-countable-model-of-arithmetic-or-set-theory-has-a-pointwise-definable-end-extension,
    author = {Joel David Hamkins},
    title = {Every countable model of arithmetic or set theory has a pointwise definable end extension},
    journal = {mathematics arXiv},
    year = {2022},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {},
    abstract = {},
    keywords = {},
    source = {},
    doi = {10.48550/ARXIV.2209.12578},
    eprint = {2209.12578},
    archivePrefix={arXiv},
    primaryClass={math.LO},
    url = {http://jdh.hamkins.org/pointwise-definable-end-extensions},
    }

arXiv:2209.12578

Abstract. According to the math tea argument, there must be real numbers that we cannot describe or define, because there are uncountably many real numbers, but only countably many definitions. And yet, the existence of pointwise definable models of set theory, in which every individual is definable without parameters, challenges this conclusion. In this article, I introduce a flexible new method for constructing pointwise definable models of arithmetic and set theory, showing furthermore that every countable model of Zermelo-Fraenkel ZF set theory and of Peano arithmetic PA has a pointwise-definable end extension. In the arithmetic case, I use the universal algorithm and its $\Sigma_n$ generalizations to build a progressively elementary tower making any desired individual $a_n$ definable at each stage $n$, while preserving these definitions through to the limit model, which can thus be arranged to be pointwise definable. A similar method works in set theory, and one can moreover achieve $V=L$ in the extension or indeed any other suitable theory holding in an inner model of the original model, thereby fulfilling the resurrection phenomenon. For example, every countable model of ZF with an inner model with a measurable cardinal has an end extension to a pointwise-definable model of $\text{ZFC}+V=L[\mu]$.

Pointwise definable end-extensions of the universe, Sophia 2022, Salzburg

This will be an online talk for the Salzburg Conference for Young Analytical Philosophy, the SOPhiA 2022 Salzburgiense Concilium Omnibus Philosophis Analyticis, with a special workshop session Reflecting on ten years of the set-theoretic multiverse. The workshop will meet Thursday 8 September 2022 4:00pm – 7:30pm.

The name of the workshop (“Reflecting on ten years…”), I was amazed to learn, refers to the period since my 2012 paper, The set-theoretic multiverse, in the Review of Symbolic Logic, in which I had first introduced my arguments and views concerning set-theoretic pluralism. I am deeply honored by this workshop highlighting my work in this way and focussing on the developments growing out of it.

In this talk, I shall engage in that discussion by presenting some very new work connecting several topics that have been prominent in discussions of the set-theoretic multiverse, namely, set-theoretic potentialism and pointwise definability.

Abstract. Using the universal algorithm and its generalizations, I shall present new work on the possibility of end-extending any given countable model of arithmetic or set theory to a pointwise definable model, one in which every object is definable without parameters. Every countable model of Peano arithmetic, for example, admits an end-extension to a pointwise definable model. And similarly, every countable model of ZF set theory admits an end-extension to a pointwise definable model of ZFC+V=L, as well as to pointwise definable models of other sufficient theories, accommodating large cardinals. I shall discuss the philosophical significance of these results in the philosophy of set theory with a view to potentialism and the set-theoretic multiverse.

Nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength

  • [DOI] J. D. Hamkins, Nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength arXiv, 2022.
    [Bibtex]
    @misc{Hamkins:Nonlinearity-in-the-hierarchy-of-large-cardinal-consistency-strength,
    author = {Joel David Hamkins},
    title = {Nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength},
    publisher = {arXiv},
    year = {2022},
    journal = {},
    volume = {},
    number = {},
    pages = {},
    doi = {10.48550/ARXIV.2208.07445},
    eprint = {2008.07445},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/nonlinearity-in-the-hierarchy-of-consistency-strength},
    }

arXiv:2208.07445

Abstract. Many set theorists point to the linearity phenomenon in the hierarchy of consistency strength, by which natural theories tend to be linearly ordered and indeed well ordered by consistency strength. Why should it be linear? In this paper I present counterexamples, natural instances of nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength, as natural or as nearly natural as I can make them. I present diverse cautious enumerations of ZFC and large cardinal set theories, which exhibit incomparability and illfoundedness in consistency strength, and yet, I argue, are natural. I consider the philosophical role played by “natural” in the linearity phenomenon, arguing ultimately that we should abandon empty naturality talk and aim instead to make precise the mathematical and logical features we had found desirable.

Set theory inside out: realizing every inner model theory in an end extension, European Set Theory Conference, September 2022

This will be a talk for the European Set Theory Conference 2022 in Turin, Italy 29 August – 2 September 2022.

Abstract. Every countable model of ZFC set theory with an inner model satisfying a sufficient theory must also have an end-extension satisfying that theory. For example, every countable model with a measurable cardinal has an end-extension to a model of $V=L[\mu]$; every model with extender-based large cardinals has an end-extension to a model of $V=L[\vec E]$; every model with infinitely many Woodin cardinals and a measurable above has an end-extension to a model of $\text{ZF}+\text{DC}+V=L(\mathbb{R})+\text{AD}$. These results generalize the famous Barwise extension theorem, of course, asserting that every countable model of ZF set theory admits an end-extension to a model of $\text{ZFC}+{V=L}$, a theorem which was simultaneously a technical culmination of Barwise’s pioneering methods in admissible set theory and infinitary logic and also one of those rare mathematical theorems that is saturated with philosophical significance. In this talk, I shall describe a new proof of the Barwise theorem that omits any need for infinitary logic and relies instead only on classical methods of descriptive set theory, while also providing the generalization I mentioned. This proof furthermore leads directly to the universal finite sequence, a $\Sigma_1$-definable finite sequence, which can be extended arbitrarily as desired in suitable end-extensions of the universe, a result holding important consequences for the nature of set-theoretic potentialism.  This work is joint with Kameryn J. Williams.

  • [DOI] J. D. Hamkins and K. J. Williams, “The $\Sigma_1$-definable universal finite sequence,” Journal of Symbolic Logic, 2021.
    [Bibtex]
    @ARTICLE{HamkinsWilliams2021:The-universal-finite-sequence,
    author = {Joel David Hamkins and Kameryn J. Williams},
    title = {The $\Sigma_1$-definable universal finite sequence},
    journal = {Journal of Symbolic Logic},
    year = {2021},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {},
    abstract = {},
    keywords = {},
    eprint = {1909.09100},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    source = {},
    doi = {10.1017/jsl.2020.59},
    }

Set-theoretic and arithmetic potentialism: the state of current developments, CACML 2020

This will be a plenary talk for the Chinese Annual Conference on Mathematical Logic (CACML 2020), held online 13-15 November 2020. My talk will be held 14 November 17:00 Beijing time (9 am GMT).

Potentialist perspectives

Abstract. Recent years have seen a flurry of mathematical activity in set-theoretic and arithmetic potentialism, in which we investigate a collection of models under various natural extension concepts. These potentialist systems enable a modal perspective—a statement is possible in a model, if it is true in some extension, and necessary, if it is true in all extensions. We consider the models of ZFC set theory, for example, with respect to submodel extensions, rank-extensions, forcing extensions and others, and these various extension concepts exhibit different modal validities. In this talk, I shall describe the state of current developments, including the most recent tools and results.

A new proof of the Barwise extension theorem, and the universal finite sequence, Barcelona Set Theory Seminar, 28 October 2020

This will be a talk for the Barcelona Set Theory Seminar, 28 October 2020 4 pm CET (3 pm UK). Contact Joan Bagaria bagaria@ub.edu for the access link.

Abstract. The Barwise extension theorem, asserting that every countable model of ZF set theory admits an end-extension to a model of ZFC+V=L, is both a technical culmination of the pioneering methods of Barwise in admissible set theory and infinitary logic and also one of those rare mathematical theorems that is saturated with philosophical significance. In this talk, I shall describe a new proof of the theorem that omits any need for infinitary logic and relies instead only on classical methods of descriptive set theory. This proof leads directly to the universal finite sequence, a Sigma_1 definable finite sequence, which can be extended arbitrarily as desired in suitable end-extensions of the universe. The result has strong consequences for the nature of set-theoretic potentialism.  This work is joint with Kameryn J. Williams.

Article: The $\Sigma_1$-definable universal finite sequence

The $\Sigma_1$-definable universal finite sequence

  • [DOI] J. D. Hamkins and K. J. Williams, “The $\Sigma_1$-definable universal finite sequence,” Journal of Symbolic Logic, 2021.
    [Bibtex]
    @ARTICLE{HamkinsWilliams2021:The-universal-finite-sequence,
    author = {Joel David Hamkins and Kameryn J. Williams},
    title = {The $\Sigma_1$-definable universal finite sequence},
    journal = {Journal of Symbolic Logic},
    year = {2021},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {},
    abstract = {},
    keywords = {},
    eprint = {1909.09100},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    source = {},
    doi = {10.1017/jsl.2020.59},
    }

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,” Mathematics ArXiv, p. 1–16, 2017.
      [Bibtex]
      @ARTICLE{HamkinsWoodin:The-universal-finite-set,
      author = {Joel David Hamkins and W. Hugh Woodin},
      title = {The universal finite set},
      journal = {Mathematics ArXiv},
      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,” Mathematics ArXiv, p. 1–35, 2018.
      [Bibtex]
      @ARTICLE{Hamkins:The-modal-logic-of-arithmetic-potentialism,
      author = {Joel David Hamkins},
      title = {The modal logic of arithmetic potentialism and the universal algorithm},
      journal = {Mathematics ArXiv},
      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


Computational self-reference and the universal algorithm, Queen Mary University of London, June 2019

This will be a talk for the Theory Seminar for the theory research group in Theoretical Computer Science at Queen Mary University of London. The talk will be held 4 June 2019 1:00 pm, ITL first floor.

Abstract. Curious, often paradoxical instances of self-reference inhabit deep parts of computability theory, from the intriguing Quine programs and Ouroboros programs to more profound features of the Gödel phenomenon. In this talk, I shall give an elementary account of the universal algorithm, showing how the capacity for self-reference in arithmetic gives rise to a Turing machine program $e$, which provably enumerates a finite set of numbers, but which can in principle enumerate any finite set of numbers, when it is run in a suitable model of arithmetic. In this sense, every function becomes computable, computed all by the same universal program, if only it is run in the right world. Furthermore, the universal algorithm can successively enumerate any desired extension of the sequence, when run in a suitable top-extension of the universe. An analogous result holds in set theory, where Woodin and I have provided a universal locally definable finite set, which can in principle be any finite set, in the right universe, and which can furthermore be successively extended to become any desired finite superset of that set in a suitable top-extension of that universe.

The modal logic of potentialism, ILLC Amsterdam, May 2019

This will be a talk at the Institute of Logic, Language and Computation (ILLC) at the University of Amsterdam for events May 11-12, 2019. See Joel David Hamkins in Amsterdam 2019.

Job Adriaenszoon Berckheyde [Public domain]

Abstract: Potentialism can be seen as a fundamentally model-theoretic notion, in play for any class of mathematical structures with an extension concept, a notion of substructure by which one model extends to another. Every such model-theoretic context can be seen as a potentialist framework, a Kripke model whose modal validities one can investigate. In this talk, I’ll explain the tools we have for analyzing the potentialist validities of such a system, with examples drawn from the models of arithmetic and set theory, using the universal algorithm and the universal definition.

Potentialism and implicit actualism in the foundations of mathematics, Jowett Society lecture, Oxford, February 2019

This will be a talk for the Jowett Society on 8 February, 2019. The talk will take place in the Oxford Faculty of Philosophy, 3:30 – 5:30pm, in the Lecture Room of the Radcliffe Humanities building.

Abstract. Potentialism is the view, originating in the classical dispute between actual and potential infinity, that one’s mathematical universe is never fully completed, but rather unfolds gradually as new parts of it increasingly come into existence or become accessible or known to us. Recent work emphasizes the modal aspect of potentialism, while decoupling it from arithmetic and from infinity: the essence of potentialism is about approximating a larger universe by means of universe fragments, an idea that applies to set-theoretic as well as arithmetic foundations. The modal language and perspective allows one precisely to distinguish various natural potentialist conceptions in the foundations of mathematics, whose exact modal validities are now known. Ultimately, this analysis suggests a refocusing of potentialism on the issue of convergent inevitability in comparison with radical branching. I shall defend the theses, first, that convergent potentialism is implicitly actualist, and second, that we should understand ultrafinitism in modal terms as a form of potentialism, one with surprising parallels to the case of arithmetic potentialism.

Jowett Society talk entry | my posts on potentialism | Slides

Parallels in universality between the universal algorithm and the universal finite set, Oxford Math Logic Seminar, October 2018

This will be a talk for the Logic Seminar in Oxford at the Mathematics Institute in the Andrew Wiles Building on October 9, 2018, at 4:00 pm, with tea at 3:30.

Abstract. The universal algorithm is a Turing machine program $e$ that can in principle enumerate any finite sequence of numbers, if run in the right model of PA, and furthermore, can always enumerate any desired extension of that sequence in a suitable end-extension of that model. The universal finite set is a set-theoretic analogue, a locally verifiable definition that can in principle define any finite set, in the right model of set theory, and can always define any desired finite extension of that set in a suitable top-extension of that model. Recent work has uncovered a $\Sigma_1$-definable version that works with respect to end-extensions. I shall give an account of all three results, which have a parallel form, and describe applications to the model theory of arithmetic and set theory.

Slides

Set-theoretic potentialism and the universal finite set, Scandinavian Logic Symposium, June 2018

This will be an invited talk at the Scandinavian Logic Symposium SLS 2018, held at the University of Gothenburg in Sweden, June 11-13, 2018.

Abstract. Providing a set-theoretic analogue of the universal algorithm, I shall define a certain finite set in set theory
$$\{x\mid\varphi(x)\}$$
and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $\varphi$ has complexity $\Sigma_2$ and therefore any instance of it $\varphi(x)$ is locally verifiable inside any sufficiently large $V_\theta$; the set is empty in any transitive model; and if $\varphi$ defines the set $y$ in some countable model $M$ of ZFC and $y\subset z$ for some finite set $z$ in $M$, then there is a top-extension of $M$ to a model $N$ of ZFC in which $\varphi$ defines the new set $z$. I shall draw out consequences of the universal finite set for set-theoretic potentialism and discuss several issues it raises in the philosophy of set theory.

The talk will include joint work with W. Hugh Woodin, Øystein Linnebo and others.

Slides: Set-theoretic potentialism and universal finite set SLS 2018

The universal finite set, Rutgers Logic Seminar, April 2018

This will be a talk for the Rutgers Logic Seminar, April 2, 2018. Hill Center, Busch campus.

Abstract. I shall define a certain finite set in set theory $$\{x\mid\varphi(x)\}$$ and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $\varphi$ has complexity $\Sigma_2$ and therefore any instance of it $\varphi(x)$ is locally verifiable inside any sufficient $V_\theta$; the set is empty in any transitive model and others; and if $\varphi$ defines the set $y$ in some countable model $M$ of ZFC and $y\subset z$ for some finite set $z$ in $M$, then there is a top-extension of $M$ to a model $N$ in which $\varphi$ defines the new set $z$.  The definition can be thought of as an idealized diamond sequence, and there are consequences for the philosophical theory of set-theoretic top-extensional potentialism.

This is joint work with W. Hugh Woodin.

The modal logic of arithmetic potentialism and the universal algorithm

  • J. D. Hamkins, “The modal logic of arithmetic potentialism and the universal algorithm,” Mathematics ArXiv, p. 1–35, 2018.
    [Bibtex]
    @ARTICLE{Hamkins:The-modal-logic-of-arithmetic-potentialism,
    author = {Joel David Hamkins},
    title = {The modal logic of arithmetic potentialism and the universal algorithm},
    journal = {Mathematics ArXiv},
    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 = {},
    }

Abstract. Natural potentialist systems arise from the models of arithmetic when they are considered under their various natural extension concepts, such as end-extensions, arbitrary extension, $\Sigma_n$-elementary extensions, conservative extensions and more. For these potentialist systems, I prove, a propositional modal assertion is valid in a model of arithmetic, with respect to assertions in the language of arithmetic with parameters, exactly when it is an assertion of S4. Meanwhile, with respect to sentences, the validities of a model are always between S4 and S5, and these bounds are sharp in that both endpoints are realized. The models validating exactly S5 are the models of the arithmetic maximality principle, which asserts that every possibly necessary statement is already true, and these models are equivalently characterized as those satisfying a maximal $\Sigma_1$ theory. The main proof makes fundamental use of the universal algorithm, of which this article provides a self-contained account.

 

In this article, I consider the models of arithmetic under various natural extension concepts, including end-extensions, arbitrary extensions, $\Sigma_n$-elementary extensions, conservative extensions and more. Each extension concept gives rise to an arithmetic potentialist system, a Kripke model of possible arithmetic worlds, and the main goal is to discover the modal validities of these systems.

For most of the extension concepts, a modal assertion is valid with respect to assertions in the language of arithmetic, allowing parameters, exactly when it is an assertion of the modal theory S4. For sentences, however, the modal validities form a theory between S4 and S5, with both endpoints being realized. A model of arithmetic validates S5 with respect to sentences just in case it is a model of the arithmetic maximality principle, and these models are equivalently characterized as those realizing a maximal $\Sigma_1$ theory.

The main argument relies fundamentally on the universal algorithm, the theorem due to Woodin that there is a Turing machine program that can enumerate any finite sequence in the right model of arithmetic, and furthermore this model can be end-extended so as to realize any further extension of that sequence available in the model. In the paper, I give a self-contained account of this theorem using my simplified proof.

The paper concludes with philosophical remarks on the nature of potentialism, including a discussion of how the linear inevitability form of potentialism is actually much closer to actualism than the more radical forms of potentialism, which exhibit branching possibility. I also propose to view the philosphy of ultrafinitism in modal terms as a form of potentialism, pushing the issue of branching possibility in ultrafinitism to the surface.

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

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

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

Ouroboros Bonn 2018 Conference Poster | Slides