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,” 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 = {},
}

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.

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

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

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

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

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

Slides

The universal finite set

• 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},
}

Abstract. We 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$, so that any affirmative instance of it $\varphi(x)$ is verified in any sufficiently large rank-initial segment of the universe $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\subseteq 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$. Thus, the set shows that no model of set theory can realize a maximal $\Sigma_2$ theory with its natural number parameters, although this is possible without parameters. Using the universal finite set, we prove that the validities of top-extensional set-theoretic potentialism, the modal principles valid in the Kripke model of all countable models of set theory, each accessing its top-extensions, are precisely the assertions of S4. Furthermore, if ZFC is consistent, then there are models of ZFC realizing the top-extensional maximality principle.

Woodin had established the universal algorithm phenomenon, showing that there is a Turing machine program with a certain universal top-extension property in models of arithmetic (see also work of Blanck and Enayat 2017 and upcoming paper of mine with Gitman and Kossak; also my post The universal algorithm: a new simple proof of Woodin’s theorem). Namely, the program provably enumerates a finite set of natural numbers, but it is relatively consistent with PA that it enumerates any particular desired finite set of numbers, and furthermore, if $M$ is any model of PA in which the program enumerates the set $s$ and $t$ is any (possibly nonstandard) finite set in $M$ with $s\subseteq t$, then there is a top-extension of $M$ to a model $N$ in which the program enumerates exactly the new set $t$. So it is a universal finite computably enumerable set, which can in principle be any desired finite set of natural numbers in the right arithmetic universe and become any desired larger finite set in a suitable larger arithmetic universe.

I had inquired whether there is a set-theoretic analogue of this phenomenon, using $\Sigma_2$ definitions in set theory in place of computable enumerability (see The universal definition — it can define any mathematical object you like, in the right set-theoretic universe). The idea was that just as a computably enumerable set is one whose elements are gradually revealed as the computation proceeds, a $\Sigma_2$-definable set in set theory is precisely one whose elements become verified at some level $V_\theta$ of the cumulative set-theoretic hierarchy as it grows. In this sense, $\Sigma_2$ definability in set theory is analogous to computable enumerability in arithmetic.

Main Question. Is there a universal $\Sigma_2$ definition in set theory, one which can define any desired particular set in some model of \ZFC\ and always any desired further set in a suitable top-extension?

I had noticed in my earlier post that one can do this using a $\Pi_3$ definition, or with a $\Sigma_2$ definition, if one restricts to models of a certain theory, such as $V\neq\text{HOD}$ or the eventual GCH, or if one allows $\{x\mid\varphi(x)\}$ sometimes to be a proper class.

Here, we provide a fully general affirmative answer with the following theorem.

Main Theorem. There is a formula $\varphi(x)$ of complexity $\Sigma_2$ in the language of set theory, provided in the proof, with the following properties:

1. ZFC proves that $\{x\mid \varphi(x)\}$ is a finite set.
2. In any transitive model of \ZFC\ and others, this set is empty.
3. If $M$ is a countable model of ZFC in which $\varphi$ defines the set $y$ and $z\in M$ is any finite set in $M$ with $y\subseteq z$, then there is a top-extension of $M$ to a model $N$ in which $\varphi$ defines exactly $z$.

By taking the union of the set defined by $\varphi$, an arbitrary set can be achieved; so the finite-set result as stated in the main theorem implies the arbitrary set case as in the main question. One can also easily deduce a version of the theorem to give a universal countable set or a universal set of some other size (for example, just take the union of the countable elements of the universal set). One can equivalently formulate the main theorem in terms of finite sequences, rather than sets, so that the sequence is extended as desired in the top-extension. The sets $y$ and $z$ in statement (3) may be nonstandard finite, if $M$ if $\omega$-nonstandard.

We use this theorem to establish the fundamental validities of top-extensional set-theoretic potentialism. Specifically, in the potentialist system consisting of the countable models of ZFC, with each accessing its top extensions, the modal validities with respect to substitution instances in the language of set theory, with parameters, are exactly the assertions of S4. When only sentences are considered, the validities are between S4 and S5, with both endpoints realized.

In particular, we prove that if ZFC is consistent, then there is a model $M$ of ZFC with the top-extensional maximality principle: any sentence $\sigma$ in the language of set theory which is true in some top extension $M^+$ and all further top extensions of $M^+$, is already true in $M$.

This principle is true is any model of set theory with a maximal $\Sigma_2$ theory, but it is never true when $\sigma$ is allowed to have natural-number parameters, and in particular, it is never true in any $\omega$-standard model of set theory.

Click through to the arXiv for more, the full article in pdf.

• 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},
}

A universal finite set, CUNY Logic Workshop, November 2017

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

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

This is joint work with W. Hugh Woodin.

Set-theoretic potentialism, CUNY Logic Workshop, September, 2016

This will be a talk for the CUNY Logic Workshop, September 16, 2016, at the CUNY Graduate Center, Room 6417, 2-3:30 pm.

Abstract.  In analogy with the ancient views on potential as opposed to actual infinity, set-theoretic potentialism is the philosophical position holding that the universe of set theory is never fully completed, but rather has a potential character, with greater parts of it becoming known to us as it unfolds. In this talk, I should like to undertake a mathematical analysis of the modal commitments of various specific natural accounts of set-theoretic potentialism. After developing a general model-theoretic framework for potentialism and describing how the corresponding modal validities are revealed by certain types of control statements, which we call buttons, switches, dials and ratchets, I apply this analysis to the case of set-theoretic potentialism, including the modalities of true-in-all-larger-$V_\beta$, true-in-all-transitive-sets, true-in-all-Grothendieck-Zermelo-universes, true-in-all-countable-transitive-models and others. Broadly speaking, the height-potentialist systems generally validate exactly S4.3 and the height-and-width-potentialist systems generally validate exactly S4.2. Each potentialist system gives rise to a natural accompanying maximality principle, which occurs when S5 is valid at a world, so that every possibly necessary statement is already true.  For example, a Grothendieck-Zermelo universe $V_\kappa$, with $\kappa$ inaccessible, exhibits the maximality principle with respect to assertions in the language of set theory using parameters from $V_\kappa$ just in case $\kappa$ is a $\Sigma_3$-reflecting cardinal, and it exhibits the maximality principle with respect to assertions in the potentialist language of set theory with parameters just in case it is fully reflecting $V_\kappa\prec V$.

This is current joint work with Øystein Linnebo, in progress, which builds on some of my prior work with George Leibman and Benedikt Löwe in the modal logic of forcing.

CUNY Logic Workshop abstract | link to article will be posted later

The modal logic of set-theoretic potentialism, Kyoto, September 2016

This will be a talk for the workshop conference Mathematical Logic and Its Applications, which will be held at the Research Institute for Mathematical Sciences, Kyoto University, Japan, September 26-29, 2016, organized by Makoto Kikuchi. The workshop is being held in memory of Professor Yuzuru Kakuda, who was head of the research group in logic at Kobe University during my stay there many years ago.

Abstract.  Set-theoretic potentialism is the ontological view in the philosophy of mathematics that the universe of set theory is never fully completed, but rather has a potential character, with greater parts of it becoming known to us as it unfolds. In this talk, I should like to undertake a mathematical analysis of the modal commitments of various specific natural accounts of set-theoretic potentialism. After developing a general model-theoretic framework for potentialism and describing how the corresponding modal validities are revealed by certain types of control statements, which we call buttons, switches, dials and ratchets, I apply this analysis to the case of set-theoretic potentialism, including the modalities of true-in-all-larger-$V_\beta$, true-in-all-transitive-sets, true-in-all-Grothendieck-Zermelo-universes, true-in-all-countable-transitive-models and others. Broadly speaking, the height-potentialist systems generally validate exactly S4.3 and the height-and-width-potentialist systems validate exactly S4.2. Each potentialist system gives rise to a natural accompanying maximality principle, which occurs when S5 is valid at a world, so that every possibly necessary statement is already true.  For example, a Grothendieck-Zermelo universe $V_\kappa$, with $\kappa$ inaccessible, exhibits the maximality principle with respect to assertions in the language of set theory using parameters from $V_\kappa$ just in case $\kappa$ is a $\Sigma_3$-reflecting cardinal, and it exhibits the maximality principle with respect to assertions in the potentialist language of set theory with parameters just in case it is fully reflecting $V_\kappa\prec V$.

This is joint work with Øystein Linnebo, which builds on some of my prior work with George Leibman and Benedikt Löwe in the modal logic of forcing. Our research article is currently in progress.