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

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

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