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.

The universal definition — it can define any mathematical object you like, in the right set-theoretic universe

Alex_wong_2015_(Unsplash) (1)In set theory, we have the phenomenon of the universal definition. This is a property $\phi(x)$, first-order expressible in the language of set theory, that necessarily holds of exactly one set, but which can in principle define any particular desired set that you like, if one should simply interpret the definition in the right set-theoretic universe. So $\phi(x)$ could be defining the set of real numbes $x=\mathbb{R}$ or the integers $x=\mathbb{Z}$ or the number $x=e^\pi$ or a certain group or a certain topological space or whatever set you would want it to be. For any mathematical object $a$, there is a set-theoretic universe in which $a$ is the unique object $x$ for which $\phi(x)$.

The universal definition can be viewed as a set-theoretic analogue of the universal algorithm, a topic on which I have written several recent posts:

Let’s warm up with the following easy instance.

Theorem. Any particular real number $r$ can become definable in a forcing extension of the universe.

Proof. By Easton’s theorem, we can control the generalized continuum hypothesis precisely on the regular cardinals, and if we start (by forcing if necessary) in a model of GCH, then there is a forcing extension where $2^{\aleph_n}=\aleph_{n+1}$ just in case the $n^{th}$ binary digit of $r$ is $1$. In the resulting forcing extension $V[G]$, therefore, the real $r$ is definable as: the real whose binary digits conform with the GCH pattern on the cardinals $\aleph_n$. QED

Since this definition can be settled in a rank-initial segment of the universe, namely, $V_{\omega+\omega}$, the complexity of the definition is $\Delta_2$. See my post on Local properties in set theory to see how I think about locally verifiable and locally decidable properties in set theory.

If we push the argument just a little, we can go beyond the reals.

Theorem. There is a formula $\psi(x)$, of complexity $\Sigma_2$, such that for any particular object $a$, there is a forcing extension of the universe in which $\psi$ defines $a$.

Proof. Fix any set $a$. By the axiom of choice, we may code $a$ with a set of ordinals $A\subset\kappa$ for some cardinal $\kappa$. (One well-orders the transitive closure of $\{a\}$ and thereby finds a bijection $\langle\mathop{tc}(\{a\}),\in\rangle\cong\langle\kappa,E\rangle$ for some $E\subset\kappa\times\kappa$, and then codes $E$ to a set $A$ by an ordinal pairing function. The set $A$ tells you $E$, which tells you $\mathop{tc}(\{a\})$ by the Mostowski collapse, and from this you find $a$.) By Easton’s theorem, there is a forcing extension $V[G]$ in which the GCH holds at all $\aleph_{\lambda+1}$ for a limit ordinal $\lambda<\kappa$, but fails at $\aleph_{\kappa+1}$, and such that $\alpha\in A$ just in case $2^{\alpha_{\alpha+2}}=\aleph_{\alpha+3}$ for $\alpha<\kappa$. That is, we manipulate the GCH pattern to exactly code both $\kappa$ and the elements of $A\subset\kappa$. Let $\phi(x)$ assert that $x$ is the set that is decoded by this process: look for the first stage where the GCH fails at $\aleph_{\lambda+2}$, and then extract the set $A$ of ordinals, and then check if $x$ is the set coded by $A$. The assertion $\phi(x)$ did not depend on $a$, and since it can be verified in any sufficiently large $V_\theta$, the assertion $\phi(x)$ has complexity $\Sigma_2$. QED

Let’s try to make a better universal definition. As I mentioned at the outset, I have been motivated to find a set-theoretic analogue of the universal algorithm, and in that computable context, we had a universal algorithm that could not only produce any desired finite set, when run in the right universe, but which furthermore had a robust interaction between models of arithmetic and their top-extensions: any set could be extended to any other set for which the algorithm enumerated it in a taller universe. Here, I’d like to achieve the same robustness of interaction with the universal definition, as one moves from one model of set theory to a taller model. We say that one model of set theory $N$ is a top-extension of another $M$, if all the new sets of $N$ have rank totally above the ranks occuring in $M$. Thus, $M$ is a rank-initial segment of $N$. If there is a least new ordinal $\beta$ in $N\setminus M$, then this is equivalent to saying that $M=V_\beta^N$.

Theorem. There is a formula $\phi(x)$, such that

  1. In any model of ZFC, there is a unique set $a$ satisfying $\phi(a)$.
  2. For any countable model $M\models\text{ZFC}$ and any $a\in M$, there is a top-extension $N$ of $M$ such that $N\models \phi(a)$.

Thus, $\phi(x)$ is the universal definition: it always defines some set, and that set can be any desired set, even when moving from a model $M$ to a top-extension $N$.

Proof. The previous manner of coding will not achieve property 2, since the GCH pattern coding started immediately, and so it would be preserved to any top extension. What we need to do is to place the coding much higher in the universe, so that in the top extension $N$, it will occur in the part of $N$ that is totally above $M$.

But consider the following process. In any model of set theory, let $\phi(x)$ assert that $x$ is the empty set unless the GCH holds at all sufficiently large cardinals, and indeed $\phi(x)$ is false unless there is a cardinal $\delta$ and ordinal $\gamma<\delta^+$ such that the GCH holds at all cardinals above $\aleph_{\delta+\gamma}$. In this case, let $\delta$ be the smallest such cardinal for which that is true, and let $\gamma$ be the smallest ordinal working with this $\delta$. So both $\delta$ and $\gamma$ are definable. Now, let $A\subset\gamma$ be the set of ordinals $\alpha$ for which the GCH holds at $\aleph_{\delta+\alpha+1}$, and let $\phi(x)$ assert that $x$ is the set coded by the set $A$.

It is clear that $\phi(x)$ defines a unique set, in any model of ZFC, and so (1) holds. For (2), suppose that $M$ is a countable model of ZFC and $a\in M$. It is a fact that every countable model of ZFC has a top-extension, by the definable ultrapower method. Let $N_0$ be a top extension of $M$. Let $N=N_0[G]$ be a forcing extension of $N_0$ in which the set $a$ is coded into the GCH pattern very high up, at cardinals totally above $M$, and such that the GCH holds above this coding, in such a way that the process described in the previous paragraph would define exactly the set $a$. So $\phi(a)$ holds in $N$, which is a top-extension of $M$ as no new sets of small rank are added by the forcing. So statement (2) also holds. QED

The complexity of the definition is $\Pi_3$, mainly because in order to know where to look for the coding, one needs to know the ordinals $\delta$ and $\gamma$, and so one needs to know that the GCH always holds above that level. This is a $\Pi_3$ property, since it cannot be verified locally only inside some $V_\theta$.

A stronger analogue with the universal algorithm — and this is a question that motivated my thinking about this topic — would be something like the following:

Question. Is there is a $\Sigma_2$ formula $\varphi(x)$, that is, a locally verifiable property, with the following properties?

  1. In any model of ZFC, the class $\{x\mid\varphi(x)\}$ is a set.
  2. It is consistent with ZFC that $\{x\mid\varphi(x)\}$ is empty.
  3. In any countable model $M\models\text{ZFC}$ in which $\{x\mid\varphi(x)\}=a$ and any set $b\in M$ with $a\subset b$, then there is a top-extension $N$ of $M$ in which $\{x\mid\varphi(x)\}=b$.

An affirmative answer would be a very strong analogue with the universal algorithm and Woodin’s theorem about which I wrote previously. The idea is that the $\Sigma_2$ properties $\varphi(x)$ in set theory are analogous to the computably enumerable properties in computability theory. Namely, to verify that an object has a certain computably enumerable property, we run a particular computable process and then sit back, waiting for the process to halt, until a stage of computation arrives at which the property is verified. Similarly, in set theory, to verify that a set has a particular $\Sigma_2$ property, we sit back watching the construction of the cumulative set-theoretic universe, until a stage $V_\beta$ arrives that provides verification of the property. This is why in statement (3) we insist that $a\subset b$, since the $\Sigma_2$ properties are always upward absolute to top-extensions; once an object is placed into $\{x\mid\varphi(x)\}$, then it will never be removed as one makes the universe taller.

So the hope was that we would be able to find such a universal $\Sigma_2$ definition, which would serve as a set-theoretic analogue of the universal algorithm used in Woodin’s theorem.

If one drops the first requirement, and allows $\{x\mid \varphi(x)\}$ to sometimes be a proper class, then one can achieve a positive answer as follows.

Theorem. There is a $\Sigma_2$ formula $\varphi(x)$ with the following properties.

  1. If the GCH holds, then $\{x\mid\varphi(x)\}$ is empty.
  2. For any countable model $M\models\text{ZFC}$ where $a=\{x\mid \varphi(x)\}$ and any $b\in M$ with $a\subset b$, there is a top extension $N$ of $M$ in which $N\models\{x\mid\varphi(x)\}=b$.

Proof. Let $\varphi(x)$ assert that the set $x$ is coded into the GCH pattern. We may assume that the coding mechanism of a set is marked off by certain kinds of failures of the GCH at odd-indexed alephs, with the pattern at intervening even-indexed regular cardinals forming the coding pattern.  This is $\Sigma_2$, since any large enough $V_\theta$ will reveal whether a given set $x$ is coded in this way. And because of the manner of coding, if the GCH holds, then no set is coded. Also, if the GCH holds eventually, then only a set-sized collection is coded. Finally, any countable model $M$ where only a set is coded can be top-extended to another model $N$ in which any desired superset of that set is coded. QED

Update.  Originally, I had proposed an argument for a negative answer to the question, and I was actually a bit disappointed by that, since I had hoped for a positive answer. However, it now seems to me that the argument I had written is wrong, and I am grateful to Ali Enayat for his remarks on this in the comments. I have now deleted the incorrect argument.

Meanwhile, here is a positive answer to the question in the case of models of $V\neq\newcommand\HOD{\text{HOD}}\HOD$.

Theorem. There is a $\Sigma_2$ formula $\varphi(x)$ with the following properties:

  1. In any model of $\newcommand\ZFC{\text{ZFC}}\ZFC+V\neq\HOD$, the class $\{x\mid\varphi(x)\}$ is a set.
  2. It is relatively consistent with $\ZFC$ that $\{x\mid\varphi(x)\}$ is empty; indeed, in any model of $\ZFC+\newcommand\GCH{\text{GCH}}\GCH$, the class $\{x\mid\varphi(x)\}$ is empty.
  3. If $M\models\ZFC$ thinks that $a=\{x\mid\varphi(x)\}$ is a set and $b\in M$ is a larger set $a\subset b$, then there is a top-extension $N$ of $M$ in which $\{x\mid \varphi(x)\}=b$.

Proof. Let $\varphi(x)$ hold, if there is some ordinal $\alpha$ such that every element of $V_\alpha$ is coded into the GCH pattern below some cardinal $\delta_\alpha$, with $\delta_\alpha$ as small as possible with that property, and $x$ is the next set coded into the GCH pattern above $\delta_\alpha$. This is a $\Sigma_2$ property, since it can be verified in any sufficiently large $V_\theta$.

In any model of $\ZFC+V\neq\HOD$, there must be some sets that are no coded into the $\GCH$ pattern, for if every set is coded that way then there would be a definable well-ordering of the universe and we would have $V=\HOD$. So in any model of $V\neq\HOD$, there is a bound on the ordinals $\alpha$ for which $\delta_\alpha$ exists, and therefore $\{x\mid\varphi(x)\}$ is a set. So statement (1) holds.

Statement (2) holds, because we may arrange it so that the GCH itself implies that no set is coded at all, and so $\varphi(x)$ would always fail.

For statement (3), suppose that $M\models\ZFC+\{x\mid\varphi(x)\}=a\subseteq b$ and $M$ is countable. In $M$, there must be some minimal rank $\alpha$ for which there is a set of rank $\alpha$ that is not coded into the GCH pattern. Let $N$ be an elementary top-extension of $M$, so $N$ agrees that $\alpha$ is that minimal rank. Now, by forcing over $N$, we can arrange to code all the sets of rank $\alpha$ into the GCH pattern above the height of the original model $M$, and we can furthermore arrange so as to code any given element of $b$ just above that coding. And so on, we can iterate it so as to arrange the coding above the height of $M$ so that exactly the elements of $b$ now satisfy $\varphi(x)$, but no more. In this way, we will ensure that $N\models\{x\mid\varphi(x)\}=b$, as desired. QED

I find the situation unusual, in that often results from the models-of-arithmetic context generalize to set theory with models of $V=\HOD$, because the global well-order means that models of $V=\HOD$ have definable Skolem functions, which is true in every model of arithmetic and which sometimes figures implicitly in constructions. But here, we have the result of Woodin’s theorem generalizing from models of arithmetic to models of $V\neq\HOD$.  Perhaps this suggests that we should expect a fully positive solution for models of set theory.