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. (undeer 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 = {undeer 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


Modal model theory

Let me introduce to you the topic of modal model theory, injecting some ideas from modal logic into the traditional subject of model theory in mathematical logic.

For example, we may consider the class of all models of some first-order theory, such as the class of all graphs, or the class of all groups, or all fields or what have you. In general, we have $\newcommand\Mod{\text{Mod}}\Mod(T)$, where $T$ is a first-order theory in some language $L$.

We may consider $\Mod(T)$ as a potentialist system, a Kripke model of possible worlds, where each model accesses the larger models, of which it is a submodel. So $\newcommand\possible{\Diamond}\possible\varphi$ is true at a model $M$, if there is a larger model $N$ in which $\varphi$ holds, and $\newcommand\necessary{\Box}\necessary\varphi$ is true at $M$, if $\varphi$ holds in all larger models.

In this way, we enlarge the language $L$ to include these modal operators. Let $\possible(L)$ be the language obtained by closing $L$ under the modal operators and Boolean connectives; and let $L^\possible$ also close under quantification. The difference is whether a modal operator falls under the scope of a quantifier.

Recently, in a collaborative project with Wojciech Aleksander Wołoszyn, we made some progress, which I’d like to explain. (We also have many further results, concerning the potentialist validities of various natural instances of $\Mod(T)$, but those will wait for another post.)

Theorem. If models $M$ and $N$ are elementarily equivalent, that is, if they have the same theory in the language of $L$, then they also have the same theory in the modal language $\possible(L)$.

Proof. We show that whenever $M\equiv N$ in the language of $L$, then $M\models\varphi\iff N\models\varphi$ for sentences $\varphi$ in the modal language $\possible(L)$, by induction on $\varphi$.

Of course, by assumption the statement is true for sentences $\varphi$ in the base language $L$. And the property is clearly preserved by Boolean combinations. What remains is the modal case. Suppose that $M\equiv N$ and $M\models\possible\varphi$. So there is some extension model $M\subset W\models\varphi$.

Since $M\equiv N$, it follows by the Keisler-Shelah theorem that $M$ and $N$ have isomorphic ultrapowers $\prod_\mu M\cong\prod_\mu N$, for some ultrafilter $\mu$. It is easy to see that isomorphic structures satisfy exactly the same modal assertions in the class of all models of a theory. Since $M\subset W$, it follows that the ultrapower of $M$ is extended to (a copy of) the ultrapower of $W$, and so $\prod_\mu M\models\possible\varphi$, and therefore also $\prod_\mu N\models\possible\varphi$. From this, since $N$ embeds into its ultrapower $\prod_\mu N$, it follows also that $N\models\possible\varphi$, as desired. $\Box$

Corollary. If one model elementarily embeds into another $M\prec N$, in the language $L$ of these structures, then this embedding is also elementary in the language $\possible(L)$.

Proof. To say $M\prec N$ in language $L$ is the same as saying that $M\equiv N$ in the language $L_M$, where we have added constants for every element of $M$, and interpreted these constants in $N$ via the embedding. Thus, by the theorem, it follows that $M\equiv N$ in the language $\possible(L_M)$, as desired. $\Box$

For example, every model $M$ is elementarily embedding into its ultrapowers $\prod_\mu M$, in the language $\possible(L)$.

We’d like to point out next that these results do not extend to elementary equivalence in the full modal language $L^\possible$.

For a counterexample, let’s work in the class of all simple graphs, in the language with a binary predicate for the edge relation. (We’ll have no parallel edges, and no self-edges.) So the accessibility relation here is the induced subgraph relation.

Lemma. The 2-colorability of a graph is expressible in $\possible(L)$. Similarly for $k$-colorability for any finite $k$.

Proof. A graph is 2-colorable if we can partition its vertices into two sets, such that a vertex is in one set if and only if all its neighbors are in the other set. This can be effectively coded by adding two new vertices, call them red and blue, such that every node (other than red and blue) is connected to exactly one of these two points, and a vertex is connected to red if and only if all its neighbors are connected to blue, and vice versa. If the graph is $2$-colorable, then there is an extension realizing this statement, and if there is an extension realizing the statement, then (even if more than two points were added) the original graph must be $2$-colorable. $\Box$

A slightly more refined observation is that for any vertex $x$ in a graph, we can express the assertion, “the component of $x$ is $2$-colorable” by a formula in the language $\possible(L)$. We simply make the same kind of assertion, but drop the requirement that every node gets a color, and insist only that $x$ gets a color and the coloring extends from a node to any neighbor of the node, thereby ensuring the full connected component will be colored.

Theorem. There are two graphs that are elementary equivalent in the language $L$ of graph theory, and hence also in the language $\possible(L)$, but they are not elementarily equivalent in the full modal language $L^\possible$.

Proof. Let $M$ be a graph consisting of disjoint copies of a 3-cycle, a 5-cycle, a 7-cycle, and so on, with one copy of every odd-length cycle. Let $M^*$ be an ultrapower of $M$ by a nonprincipal ultrafilter.

Thus, $M^*$ will continue to have one 3-cycle, one 5-cycle, one 7-cycle and on on, for all the finite odd-length cycles, but then $M^*$ will have what it thinks are non-standard odd-length cycles, except that it cannot formulate the concept of “odd”. What it actually has are a bunch of $\mathbb{Z}$-chains.

In particular, $M^*$ thinks that there is an $x$ whose component is $2$-colorable, since a $\mathbb{Z}$-chain is $2$-colorable.

But $M$ does not think that there is an $x$ whose component is $2$-colorable, because an odd-length finite cycle is not $2$-colorable. $\Box$.

Since we used an ultrapower, the same example also shows that the corollary above does not generalize to the full modal language. That is, we have $M$ embedding elementarily into its ultrapower $M^*$, but it is not elementary in the language $L^\possible$.

Let us finally notice that the Łoś theorem for ultraproducts fails even in the weaker modal language $\possible(L)$.

Theorem. There are models $M_i$ for $i\in\mathbb{N}$ and a sentence $\varphi$ in the language of these models, such that every nonprincipal ultraproduct $\prod_\mu M_i$ satisfies $\possible\varphi$, but no $M_i$ satisfies $\possible\varphi$. .

Proof. In the class of all graphs, using the language of graph theory, let the $M_i$ be all the odd-length cycles. The ultraproduct $\prod_\mu M_i$ consists entirely of $\mathbb{Z}$-chains. In particular, the ultraproduct graph is $2$-colorable, but none of the $M_i$ are $2$-colorable. $\Box$

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

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.

Modal principles of potentialism, Oxford, January 2018

This was a talk I gave at University College Oxford to the philosophy faculty.

Abstract. One of my favorite situations occurs when philosophical ideas or issues inspire a bit of mathematical analysis, which in turn raises further philosophical questions and ideas, in a fruitful cycle. The topic of potentialism originates, after all, in the classical dispute between actual and potential infinity. Linnebo and Shapiro and others have emphasized the modal nature of potentialism, de-coupling it from infinity: the essence of potentialism is about approximating a larger universe or structure by means of partial structures or universe fragments. In several mathematical projects, my co-authors and I have found the exact modal validities of several natural potentialist concepts arising in the foundations of mathematics, including several kinds of set-theoretic and arithmetic potentialism. Ultimately, the variety of kinds of potentialism suggest a refocusing of potentialism on the issue of convergent inevitability in comparison with radical branching. I defended 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 suprising parallels to the case of arithmetic potentialism.

Here are my lecture notes that I used as a basis for the talk:

https://photos.app.goo.gl/DcaXV3sLVU4enaxv8

For a fuller, more technical account of potentialism, see the three-lecture tutorial series I gave for the Logic Winter School 2018 in Hejnice: Set-theoretic potentialism, and follow the link to the slides.

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.

Arithmetic potentialism and the universal algorithm, CUNY Logic Workshop, September 2017

This will be a talk for the CUNY Logic Workshop at the CUNY Graduate Center, September 8, 2017, 2-3:30, room GC 6417.

Empire_State_Building_New_York_March_2015

Abstract. Consider the collection of all the models of arithmetic under the end-extension relation, which forms a potentialist system for arithmetic, a collection of possible arithmetic worlds or universe fragments, with a corresponding potentialist modal semantics. What are the modal validities? I shall prove that every model of arithmetic validates exactly S4 with respect to assertions in the language of arithmetic allowing parameters, but if one considers sentences only (no parameters), then some models can validate up to S5, thereby fulfilling the arithmetic maximality principle, which asserts for a model $M$ that whenever an arithmetic sentence is true in some end-extension of $M$ and all subsequent end-extensions, then it is already true in $M$. (We also consider other accessibility relations, such as arbitrary extensions or $\Sigma_n$-elementary extensions or end-extensions.)

The proof makes fundamental use of what I call the universal algorithm, a fascinating result due to W. Hugh Woodin, asserting that there is a computable algorithm that can in principle enumerate any desired finite sequence, if only it is undertaken in the right universe, and furthermore any given model of arithmetic can be end-extended so as to realize any desired additional behavior for that universal program. I shall give a simple proof of the universal algorithm theorem and explain how it can be used to determine the potentialist validities of a model of arithmetic. This is current joint work in progress with Victoria Gitman and Roman Kossak, and should be seen as an arithmetic analogue of my recent work on set-theoretic potentialism with Øystein Linnebo. The mathematical program is strongly motivated by philosophical ideas arising in the distinction between actual and potential infinity.

 

The modal principles of potentialism in mathematics, Logic and Metaphysics Workshop, CUNY, November 2017

This will be a talk on November 6, 2017 for the Logic and Metaphysics workshop at the CUNY Graduate Center, run by Graham Priest. Room GC 3209.

Morning_Fog_at_GGB

The modal principles of potentialism in mathematics

Abstract. Potentialism is the view in the philosophy of mathematics that one’s mathematical universe, whether in arithmetic or set theory, is never fully completed, but rather unfolds gradually as new parts of it increasingly come into existence or become accessible or known to us. As in the classical dispute between actual versus potential infinity, the potentialist holds that objects in the upper or outer reaches have potential as opposed to actual existence, in the sense that one can imagine forming or discovering always more objects from that realm, as many as desired, but the task is never completed.  Recent work has emphasized the modal aspect of potentialism, and in this talk, I shall describe a general model-theoretic account of the modal logic of potentialism, identifying specific modal principles that hold or fail depending on features of the potentialist system under consideration. This work makes use of modal control statements, such as buttons, switches, dials and ratchets and the connection of these kinds of statements with the modal theories S4, S4.2, S4.3 and S5. I shall take the various natural kinds of arithmetic and set-theoretic potentialism as illustrative cases.

This is joint work with Øystein Linnebo, University of Oslo (see our paper The modal logic of set-theoretic potentialism and the potentialist maximality principles), and further joint work in progress with Victoria Gitman and Roman Kossak, and very recent joint work in progress with W. Hugh Woodin.

Lecture Notes

The modal logic of set-theoretic potentialism and the potentialist maximality principles

Joint work with Øystein Linnebo, University of Oslo.

  • J. D. Hamkins and Ø. Linnebo, “The modal logic of set-theoretic potentialism and the potentialist maximality principles,” to appear in Review of Symbolic Logic, 2018.  
    @ARTICLE{HamkinsLinnebo:Modal-logic-of-set-theoretic-potentialism,
    author = {Hamkins, Joel David and Linnebo, \O{}ystein},
    title = {The modal logic of set-theoretic potentialism and the potentialist maximality principles},
    journal = {to appear in Review of Symbolic Logic},
    year = {2018},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {},
    abstract = {},
    keywords = {to-appear},
    source = {},
    eprint = {1708.01644},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://wp.me/p5M0LV-1zC},
    doi = {},
    }

Abstract. We analyze the precise modal commitments of several natural varieties of set-theoretic potentialism, using tools we develop for a general model-theoretic account of potentialism, building on those of Hamkins, Leibman and Löwe (Structural connections between a forcing class and its modal logic), including the use of buttons, switches, dials and ratchets. Among the potentialist conceptions we consider are: rank potentialism (true in all larger $V_\beta$); Grothendieck-Zermelo potentialism (true in all larger $V_\kappa$ for inaccessible cardinals $\kappa$); transitive-set potentialism (true in all larger transitive sets); forcing potentialism (true in all forcing extensions); countable-transitive-model potentialism (true in all larger countable transitive models of ZFC); countable-model potentialism (true in all larger countable models of ZFC); and others. In each case, we identify lower bounds for the modal validities, which are generally either S4.2 or S4.3, and an upper bound of S5, proving in each case that these bounds are optimal. The validity of S5 in a world is a potentialist maximality principle, an interesting set-theoretic principle of its own. The results can be viewed as providing an analysis of the modal commitments of the various set-theoretic multiverse conceptions corresponding to each potentialist account.

Set-theoretic potentialism is the view in the philosophy of mathematics that the universe of set theory is never fully completed, but rather unfolds gradually as parts of it increasingly come into existence or become accessible to us. On this view, the outer reaches of the set-theoretic universe have merely potential rather than actual existence, in the sense that one can imagine “forming” or discovering always more sets from that realm, as many as desired, but the task is never completed. For example, height potentialism is the view that the universe is never fully completed with respect to height: new ordinals come into existence as the known part of the universe grows ever taller. Width potentialism holds that the universe may grow outwards, as with forcing, so that already existing sets can potentially gain new subsets in a larger universe. One commonly held view amongst set theorists is height potentialism combined with width actualism, whereby the universe grows only upward rather than outward, and so at any moment the part of the universe currently known to us is a rank initial segment $V_\alpha$ of the potential yet-to-be-revealed higher parts of the universe. Such a perspective might even be attractive to a Platonistically inclined large-cardinal set theorist, who wants to hold that there are many large cardinals, but who also is willing at any moment to upgrade to a taller universe with even larger large cardinals than had previously been mentioned. Meanwhile, the width-potentialist height-actualist view may be attractive for those who wish to hold a potentialist account of forcing over the set-theoretic universe $V$. On the height-and-width-potentialist view, one views the universe as growing with respect to both height and width. A set-theoretic monist, in contrast, with an ontology having only a single fully existing universe, will be an actualist with respect to both width and height. The second author has described various potentialist views in previous work.

Although we are motivated by the case of set-theoretic potentialism, the potentialist idea itself is far more general, and can be carried out in a general model-theoretic context. For example, the potentialist account of arithmetic is deeply connected with the classical debates surrounding potential as opposed to actual infinity, and indeed, perhaps it is in those classical debates where one finds the origin of potentialism. More generally, one can provide a potentialist account of truth in the context of essentially any kind of structure in any language or theory.

Our project here is to analyze and understand more precisely the modal commitments of various set-theoretic potentialist views.  After developing a general model-theoretic account of the semantics of potentialism and providing tools for establishing both lower and upper bounds on the modal validities for various kinds of potentialist contexts, we shall use those tools to settle exactly the propositional modal validities for several natural kinds of set-theoretic height and width potentialism.

Here is a summary account of the modal logics for various flavors of set-theoretic potentialism.

Flavours of potentialism

In each case, the indicated lower and upper bounds are realized in particular worlds, usually in the strongest possible way that is consistent with the stated inclusions, although in some cases, this is proved only under additional mild technical hypotheses. Indeed, some of the potentialist accounts are only undertaken with additional set-theoretic assumptions going beyond ZFC. For example, the Grothendieck-Zermelo account of potentialism is interesting mainly only under the assumption that there are a proper class of inaccessible cardinals, and countable-transitive-model potentialism is more robust under the assumption that every real is an element of a countable transitive model of set theory, which can be thought of as a mild large-cardinal assumption.

The upper bound of S5, when it is realized, constitutes a potentialist maximality principle, for in such a case, any statement that could possibly become actually true in such a way that it remains actually true as the universe unfolds, is already actually true. We identify necessary and sufficient conditions for each of the concepts of potentialism for a world to fulfill this potentialist maximality principle. For example, in rank-potentialism, a world $V_\kappa$ satisfies S5 with respect to the language of set theory with arbitrary parameters if and only if $\kappa$ is $\Sigma_3$-correct. And it satisfies S5 with respect to the potentialist language of set theory with parameters if and only if it is $\Sigma_n$-correct for every $n$.  Similar results hold for each of the potentialist concepts.

Finally, let me mention the strong affinities between set-theoretic potentialism and set-theoretic pluralism, particularly with the various set-theoretic multiverse conceptions currently in the literature. Potentialists may regard themselves mainly as providing an account of truth ultimately for a single universe, gradually revealed, the limit of their potentialist system. Nevertheless, the universe fragments of their potentialist account can often naturally be taken as universes in their own right, connected by the potentialist modalities, and in this way, every potentialist system can be viewed as a multiverse. Indeed, the potentialist systems we analyze in this article—including rank potentialism, forcing potentialism, generic-multiverse potentialism, countable-transitive-model potentialism, countable-model potentialism—each align with corresponding natural multiverse conceptions. Because of this, we take the results of this article as providing not only an analysis of the modal commitments of set-theoretic potentialism, but also an analysis of the modal commitments of various particular set-theoretic multiverse conceptions. Indeed, one might say that it is possible (ahem), in another world, for this article to have been entitled, “The modal logic of various set-theoretic multiverse conceptions.”

For more, please follow the link to the arxiv where you can find the full article.

  • J. D. Hamkins and Ø. Linnebo, “The modal logic of set-theoretic potentialism and the potentialist maximality principles,” to appear in Review of Symbolic Logic, 2018.  
    @ARTICLE{HamkinsLinnebo:Modal-logic-of-set-theoretic-potentialism,
    author = {Hamkins, Joel David and Linnebo, \O{}ystein},
    title = {The modal logic of set-theoretic potentialism and the potentialist maximality principles},
    journal = {to appear in Review of Symbolic Logic},
    year = {2018},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {},
    abstract = {},
    keywords = {to-appear},
    source = {},
    eprint = {1708.01644},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://wp.me/p5M0LV-1zC},
    doi = {},
    }