Open class determinacy is preserved by forcing

  • J. D. Hamkins and H. W. Woodin, “Open class determinacy is preserved by forcing,” ArXiv e-prints, pp. 1-14, 2018. (under review)  
    @ARTICLE{HamkinsWoodin2018:Open-class-determinacy-is-preserved-by-forcing,
    author = {Joel David Hamkins and W. Hugh Woodin},
    title = {Open class determinacy is preserved by forcing},
    journal = {ArXiv e-prints},
    year = {2018},
    volume = {},
    number = {},
    pages = {1--14},
    month = {},
    note = {under review},
    abstract = {},
    eprint = {1806.11180},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    keywords = {under-review},
    source = {},
    doi = {},
    url = {http://wp.me/p5M0LV-1KF},
    }

Abstract. The principle of open class determinacy is preserved by pre-tame class forcing, and after such forcing, every new class well-order is isomorphic to a ground-model class well-order. Similarly, the principle of elementary transfinite recursion ETR${}_\Gamma$ for a fixed class well-order $\Gamma$ is preserved by pre-tame class forcing. The full principle ETR itself is preserved by countably strategically closed pre-tame class forcing, and after such forcing, every new class well-order is isomorphic to a ground-model class well-order. Meanwhile, it remains open whether ETR is preserved by all forcing, including the forcing merely to add a Cohen real.

 

The principle of elementary transfinite recursion ETR — according to which every first-order class recursion along any well-founded class relation has a solution — has emerged as a central organizing concept in the hierarchy of second-order set theories from Gödel-Bernays set theory GBC up to Kelley-Morse set theory KM and beyond. Many of the principles in the hierarchy can be seen as asserting that certain class recursions have solutions.

In addition, many of these principles, including ETR and its variants, are equivalently characterized as determinacy principles for certain kinds of class games. Thus, the hierarchy is also fruitfully unified and organized by determinacy ideas.

This hierarchy of theories is the main focus of study in the reverse mathematics of second-order set theory, an emerging subject aiming to discover the precise axiomatic principles required for various arguments and results in second-order set theory. The principle ETR itself, for example, is equivalent over GBC to the principle of clopen determinacy for class games and also to the existence of iterated elementary truth predicates (see Open determinacy for class games); since every clopen game is also an open game, the principle ETR is naturally strengthened by the principle of open determinacy for class games, and this is a strictly stronger principle (see Hachtman and Sato); the weaker principle ETR${}_\text{Ord}$, meanwhile, asserting solutions to class recursions of length Ord, is equivalent to the class forcing theorem, which asserts that every class forcing notion admits a forcing relation, to the existence of set-complete Boolean completions of any class partial order, to the existence of Ord-iterated elementary truth predicates, to the determinacy of clopen games of rank at most Ord+1, and to other natural set-theoretic principles (see The exact strength of the class forcing theorem).

Since one naturally seeks in any subject to understand how one’s fundamental principles and tools interact, we should like in this article to consider how these second-order set-theoretic principles are affected by forcing. These questions originated in previous work of Victoria Gitman and myself, and question 1 also appears in the dissertation of Kameryn Williams, which was focused on the structure of models of second-order set theories.

It is well-known, of course, that ZFC, GBC, and KM are preserved by set forcing and by tame class forcing, and this is true for other theories in the hierarchy, such as GBC$+\Pi^1_n$-comprehension and higher levels of the second-order comprehension axiom. The corresponding forcing preservation theorem for ETR and for open class determinacy, however, has not been known.

Question 1. Is ETR preserved by forcing?

Question 2. Is open class determinacy preserved by forcing?

We intend to ask in each case about class forcing as well as set forcing. Question 1 is closely connected with the question of whether forcing can create new class well-order order types, longer than any class well-order in the ground model. Specifically, Victoria Gitman and I had observed earlier that ETR${}_\Gamma$ for a specific class well-order $\Gamma$ is preserved by pre-tame class forcing, and this would imply that the full principle ETR would also be preserved, if no fundamentally new class well-orders are created by the forcing. In light of the fact that forcing over models of ZFC adds no new ordinals, that would seem reasonable, but proof is elusive, and the question remains open. Can forcing add new class well-orders, perhaps very tall ones that are not isomorphic to any ground model class well-order? Perhaps there are some very strange models of GBC that gain new class well-order order types in a forcing extension.

Question 3. Assume GBC. After forcing, must every new class well-order be isomorphic to a ground-model class well-order? Does ETR imply this?

The main theorem of this article provides a full affirmative answer to question 2, and partial affirmative answers to questions 2 and 3.

Main Theorem.

  1. Open class determinacy is preserved by pre-tame class forcing. After such forcing, every new class well-order is isomorphic to a ground-model class well-order.
  2. The principle ETR${}_\Gamma$, for any fixed class well order $\Gamma$, is preserved by pre-tame class forcing.
  3. The full principle ETR is preserved by countably strategically closed pre-tame class forcing. After such forcing, every new class well-order is isomorphic to a ground-model class well-order.

We should like specifically to highlight the fact that questions 1 and 3 remain open even in the case of the forcing to add a Cohen real. Is ETR preserved by the forcing to add a Cohen real? After adding a Cohen real, is every new class well-order isomorphic to a ground-model class well-order? One naturally expects affirmative answers, especially in a model of ETR.

For more, click through the arxiv for a pdf of the full article.

  • J. D. Hamkins and H. W. Woodin, “Open class determinacy is preserved by forcing,” ArXiv e-prints, pp. 1-14, 2018. (under review)  
    @ARTICLE{HamkinsWoodin2018:Open-class-determinacy-is-preserved-by-forcing,
    author = {Joel David Hamkins and W. Hugh Woodin},
    title = {Open class determinacy is preserved by forcing},
    journal = {ArXiv e-prints},
    year = {2018},
    volume = {},
    number = {},
    pages = {1--14},
    month = {},
    note = {under review},
    abstract = {},
    eprint = {1806.11180},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    keywords = {under-review},
    source = {},
    doi = {},
    url = {http://wp.me/p5M0LV-1KF},
    }

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.

A conference in honor of W. Hugh Woodin’s 60th birthday, March 2015

I am pleased to announce the upcoming conference at Harvard celebrating the 60th birthday of W. Hugh Woodin.  See the conference web site for more information. Click on the image below for a large-format poster.

woodin_conference_poster

The ground axiom is consistent with $V\ne{\rm HOD}$

  • J. D. Hamkins, J. Reitz, and W. Woodin, “The ground axiom is consistent with $V\ne{\rm HOD}$,” Proc.~Amer.~Math.~Soc., vol. 136, iss. 8, pp. 2943-2949, 2008.  
    @ARTICLE{HamkinsReitzWoodin2008:TheGroundAxiomAndVequalsHOD,
    AUTHOR = {Hamkins, Joel David and Reitz, Jonas and Woodin, W.~Hugh},
    TITLE = {The ground axiom is consistent with {$V\ne{\rm HOD}$}},
    JOURNAL = {Proc.~Amer.~Math.~Soc.},
    FJOURNAL = {Proceedings of the American Mathematical Society},
    VOLUME = {136},
    YEAR = {2008},
    NUMBER = {8},
    PAGES = {2943--2949},
    ISSN = {0002-9939},
    CODEN = {PAMYAR},
    MRCLASS = {03E35 (03E45 03E55)},
    MRNUMBER = {2399062 (2009b:03137)},
    MRREVIEWER = {P{\'e}ter Komj{\'a}th},
    DOI = {10.1090/S0002-9939-08-09285-X},
    URL = {http://wp.me/p5M0LV-3j},
    file = F,
    }

Abstract. The Ground Axiom asserts that the universe is not a nontrivial set-forcing extension of any inner model. Despite the apparent second-order nature of this assertion, it is first-order expressible in set theory. The previously known models of the Ground Axiom all satisfy strong forms of $V=\text{HOD}$. In this article, we show that the Ground Axiom is relatively consistent with $V\neq\text{HOD}$. In fact, every model of ZFC has a class-forcing extension that is a model of $\text{ZFC}+\text{GA}+V\neq\text{HOD}$. The method accommodates large cardinals: every model of ZFC with a supercompact cardinal, for example, has a class-forcing extension with $\text{ZFC}+\text{GA}+V\neq\text{HOD}$ in which this supercompact cardinal is preserved.

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,” Math.~Logic 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 = {Math.~Logic Q.},
    FJOURNAL = {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://wp.me/s5M0LV-nmpccc},
    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

Small forcing creates neither strong nor Woodin cardinals

  • J. D. Hamkins and W. Woodin, “Small forcing creates neither strong nor Woodin cardinals,” Proc.~Amer.~Math.~Soc., vol. 128, iss. 10, pp. 3025-3029, 2000.  
    @article {HamkinsWoodin2000:SmallForcing,
    AUTHOR = {Hamkins, Joel David and Woodin, W.~Hugh},
    TITLE = {Small forcing creates neither strong nor {W}oodin cardinals},
    JOURNAL = {Proc.~Amer.~Math.~Soc.},
    FJOURNAL = {Proceedings of the American Mathematical Society},
    VOLUME = {128},
    YEAR = {2000},
    NUMBER = {10},
    PAGES = {3025--3029},
    ISSN = {0002-9939},
    CODEN = {PAMYAR},
    MRCLASS = {03E35 (03E55)},
    MRNUMBER = {1664390 (2000m:03121)},
    MRREVIEWER = {Carlos A.~Di Prisco},
    DOI = {10.1090/S0002-9939-00-05347-8},
    URL = {http://jdh.hamkins.org/smallforcing-w/},
    eprint = {math/9808124},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

After small forcing, almost every strongness embedding is the lift of a strongness embedding in the ground model. Consequently, small forcing creates neither strong nor Woodin cardinals.

Quoted in Science News

I was quoted briefly in Infinite Wisdom: A new approach to one of mathematics’ most notorious problems, Science News, by Erica Klarrreich, August 30, 2003, in an article about Woodin’s attempted solution of the continuum hypothesis.