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.

 

Inner-model reflection principles

  • N. Barton, A. E. Caicedo, G. Fuchs, J. D. Hamkins, and J. Reitz, “Inner-model reflection principles.” (\href{arXiv:1708.06669}{http://arxiv.org/abs/1708.06669}, 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 = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {\href{arXiv:1708.06669}{http://arxiv.org/abs/1708.06669}, manuscript under review},
    abstract = {},
    keywords = {},
    source = {},
    doi = {},
    eprint = {1708.06669},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/inner-model-reflection-principles},
    }

World_Trade_Center,_New_York,_NY,_USA_-_panoramio_(5)

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.” (\href{arXiv:1708.06669}{http://arxiv.org/abs/1708.06669}, 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 = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {\href{arXiv:1708.06669}{http://arxiv.org/abs/1708.06669}, manuscript under review},
    abstract = {},
    keywords = {},
    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.

World_Trade_Center,_New_York,_NY,_USA_-_panoramio_(5)

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

 

web page | math genealogy | MathSciNet | ar$\chi$iv | related posts

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

  • W. Hamkins Joel D.~and 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 = {Hamkins, Joel D.~and Woodin, W.~Hugh},
    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 = {http://dx.doi.org/10.1002/malq.200410045},
    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://projecteuclid.org/getRecord?id=euclid.jsl/1052669062},
    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.