# 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. (manuscript 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 = {manuscript under review},
url = {http://jdh.hamkins.org/arithmetic-potentialism-and-the-universal-algorithm},
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.

# The universal finite set

• J. D. Hamkins and 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 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},
}

# Inner-model reflection principles

• N. Barton, A. E. Caicedo, G. Fuchs, J. D. Hamkins, and J. Reitz, “Inner-model reflection principles,” ArXiv e-prints, 2017. (manuscript under review)
@ARTICLE{BartonCaicedoFuchsHamkinsReitz:Inner-model-reflection-principles,
author = {Neil Barton and Andr\'es Eduardo Caicedo and Gunter Fuchs and Joel David Hamkins and Jonas Reitz},
title = {Inner-model reflection principles},
journal = {ArXiv e-prints},
year = {2017},
volume = {},
number = {},
pages = {},
month = {},
note = {manuscript under review},
abstract = {},
keywords = {under-review},
source = {},
doi = {},
eprint = {1708.06669},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/inner-model-reflection-principles},
}

Abstract. We introduce and consider the inner-model reflection principle, which asserts that whenever a statement $\varphi(a)$ in the first-order language of set theory is true in the set-theoretic universe $V$, then it is also true in a proper inner model $W\subsetneq V$. A stronger principle, the ground-model reflection principle, asserts that any such $\varphi(a)$ true in $V$ is also true in some nontrivial ground model of the universe with respect to set forcing. These principles each express a form of width reflection in contrast to the usual height reflection of the Lévy-Montague reflection theorem. They are each equiconsistent with ZFC and indeed $\Pi_2$-conservative over ZFC, being forceable by class forcing while preserving any desired rank-initial segment of the universe. Furthermore, the inner-model reflection principle is a consequence of the existence of sufficient large cardinals, and lightface formulations of the reflection principles follow from the maximality principle MP and from the inner-model hypothesis IMH.

Every set theorist is familiar with the classical Lévy-Montague reflection principle, which explains how truth in the full set-theoretic universe $V$ reflects down to truth in various rank-initial segments $V_\theta$ of the cumulative hierarchy. Thus, the Lévy-Montague reflection principle is a form of height-reflection, in that truth in $V$ is reflected vertically downwards to truth in some $V_\theta$.

In this brief article, in contrast, we should like to introduce and consider a form of width-reflection, namely, reflection to nontrivial inner models. Specifically, we shall consider the following reflection principles.

Definition.

1. The inner-model reflection principle asserts that if a statement $\varphi(a)$ in the first-order language of set theory is true in the set-theoretic universe $V$, then there is a proper inner model $W$, a transitive class model of ZF containing all ordinals, with $a\in W\subsetneq V$ in which $\varphi(a)$ is true.
2. The ground-model reflection principle asserts that if $\varphi(a)$ is true in $V$, then there is a nontrivial ground model $W\subsetneq V$ with $a\in W$ and $W\models\varphi(a)$.
3. Variations of the principles arise by insisting on inner models of a particular type, such as ground models for a particular type of forcing, or by restricting the class of parameters or formulas that enter into the scheme.
4. The lightface forms of the principles, in particular, make their assertion only for sentences, so that if $\sigma$ is a sentence true in $V$, then $\sigma$ is true in some proper inner model or ground $W$, respectively.

We explain how to force the principles, how to separate them, how they are consequences of various large cardinal assumptions, consequences of the maximality principle and of the inner model hypothesis. Kindly proceed to the article (pdf available at the arxiv) for more.

• N. Barton, A. E. Caicedo, G. Fuchs, J. D. Hamkins, and J. Reitz, “Inner-model reflection principles,” ArXiv e-prints, 2017. (manuscript under review)
@ARTICLE{BartonCaicedoFuchsHamkinsReitz:Inner-model-reflection-principles,
author = {Neil Barton and Andr\'es Eduardo Caicedo and Gunter Fuchs and Joel David Hamkins and Jonas Reitz},
title = {Inner-model reflection principles},
journal = {ArXiv e-prints},
year = {2017},
volume = {},
number = {},
pages = {},
month = {},
note = {manuscript under review},
abstract = {},
keywords = {under-review},
source = {},
doi = {},
eprint = {1708.06669},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/inner-model-reflection-principles},
}

This article grew out of an exchange held by the authors on math.stackexchange
in response to an inquiry posted by the first author concerning the nature of width-reflection in comparison to height-reflection:  What is the consistency strength of width reflection?

# The inner-model and ground-model reflection principles, CUNY Set Theory seminar, September 2017

This will be a talk for the CUNY Set Theory seminar on September 1, 2017, 10 am. GC 6417.

Abstract.  The inner model reflection principle asserts that whenever a statement $\varphi(a)$ in the first-order language of set theory is true in the set-theoretic universe $V$, then it is also true in a proper inner model $W\subsetneq V$. A stronger principle, the ground-model reflection principle, asserts that any such $\varphi(a)$ true in $V$ is also true in some nontrivial ground model of the universe with respect to set forcing. Both of these principles, expressing a form of width-reflection in constrast to the usual height-reflection, are equiconsistent with ZFC and an outright consequence of the existence of sufficient large cardinals, as well as a consequence (in lightface form) of the maximality principle and also of the inner-model hypothesis.  This is joint work with Neil Barton, Andrés Eduardo Caicedo, Gunter Fuchs, myself and Jonas Reitz.

# George Leibman

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

George Leibman

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

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

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

# The necessary maximality principle for c.c.c. forcing is equiconsistent with a weakly compact cardinal

• J. D. Hamkins and W. Woodin, “The necessary maximality principle for c.c.c.~forcing is equiconsistent with a weakly compact cardinal,” MLQ Math.~Log.~Q., vol. 51, iss. 5, pp. 493-498, 2005.
@ARTICLE{HamkinsWoodin2005:NMPccc,
AUTHOR = {Joel David Hamkins and W.~Hugh Woodin},
TITLE = {The necessary maximality principle for c.c.c.~forcing is equiconsistent with a weakly compact cardinal},
JOURNAL = {MLQ Math.~Log.~Q.},
FJOURNAL = {MLQ.~Mathematical Logic Quarterly},
VOLUME = {51},
YEAR = {2005},
NUMBER = {5},
PAGES = {493--498},
ISSN = {0942-5616},
MRCLASS = {03E65 (03E55)},
MRNUMBER = {2163760 (2006f:03082)},
MRREVIEWER = {Tetsuya Ishiu},
DOI = {10.1002/malq.200410045},
URL = {},
eprint = {math/0403165},
archivePrefix = {arXiv},
primaryClass = {math.LO},
file = F,
}

The Necessary Maximality Principle for c.c.c. forcing asserts that any statement about a real in a c.c.c. extension that could become true in a further c.c.c. extension and remain true in all subsequent c.c.c. extensions, is already true in the minimal extension containing the real. We show that this principle is equiconsistent with the existence of a weakly compact cardinal.

See related article on the Maximality Principle

# A simple maximality principle

• J. D. Hamkins, “A simple maximality principle,” J.~Symbolic Logic, vol. 68, iss. 2, pp. 527-550, 2003.
@article{Hamkins2003:MaximalityPrinciple,
AUTHOR = {Hamkins, Joel David},
TITLE = {A simple maximality principle},
JOURNAL = {J.~Symbolic Logic},
FJOURNAL = {The Journal of Symbolic Logic},
VOLUME = {68},
YEAR = {2003},
NUMBER = {2},
PAGES = {527--550},
ISSN = {0022-4812},
CODEN = {JSYLA6},
MRCLASS = {03E35 (03E40)},
MRNUMBER = {1976589 (2005a:03094)},
MRREVIEWER = {Ralf-Dieter Schindler},
DOI = {10.2178/jsl/1052669062},
URL = {http://jdh.hamkins.org/maximalityprinciple/},
month = {June},
eprint = {math/0009240},
archivePrefix = {arXiv},
primaryClass = {math.LO},
}

In this paper, following an idea of Christophe Chalons, I propose a new kind of forcing axiom, the Maximality Principle, which asserts that any sentence$\varphi$ holding in some forcing extension $V^{\mathbb{P}}$ and all subsequent extensions $V^{\mathbb{P}*\mathbb{Q}}$ holds already in $V$. It follows, in fact, that such sentences must also hold in all forcing extensions of $V$. In modal terms, therefore, the Maximality Principle is expressed by the scheme $(\Diamond\Box\varphi)\to\Box\varphi$, and is equivalent to the modal theory S5. In this article, I prove that the Maximality Principle is relatively consistent with ZFC. A boldface version of the Maximality Principle, obtained by allowing real parameters to appear in $\varphi$, is equiconsistent with the scheme asserting that $V_\delta$ is an elementary substructure of $V$ for an inaccessible cardinal $\delta$, which in turn is equiconsistent with the scheme asserting that ORD is Mahlo. The strongest principle along these lines is the Necessary Maximality Principle, which asserts that the boldface MP holds in V and all forcing extensions. From this, it follows that $0^\sharp$ exists, that $x^\sharp$ exists for every set $x$, that projective truth is invariant by forcing, that Woodin cardinals are consistent and much more. Many open questions remain.