Category Archives: Publications

The subseries number

Posted on by
2

[bibtex key=”BrendleBrianHamkins2019:The-subseries-number”]

Abstract. Every conditionally convergent series of real numbers has a divergent  subseries. How many subsets of the natural numbers are needed so that every conditionally convergent series diverges on the subseries corresponding to one of these sets? The answer to this question is defined to be the subseries number, a new cardinal characteristic of the continuum. This cardinal is bounded below by $\aleph_1$ and  above by the cardinality of the continuum, but it is not provably equal to either. We define three natural variants of the subseries number, and compare them with each other, with their corresponding rearrangement numbers, and with several well-studied cardinal characteristics of the continuum. Many consistency results are obtained from these comparisons, and we obtain another by computing the value of the subseries number in the Laver model.

This paper grew naturally out of our previous paper, The rearrangement number, which considered the minimal number of permutations of $\mathbb{N}$ which suffice to reveal the conditional convergence of all conditionally convergent series. I had defined the subseries number in my answer to a MathOverflow question, On Hamkins’s answer to a question of Michael Hardy’s, asked by M. Rahman in response to the earlier MO questions on the rearrangement number.

In the paper, we situation the subseries number ß (German sharp s) with respect to other cardinal characteristics, including the rearrangement numbers.

The modal logic of arithmetic potentialism and the universal algorithm

Posted on by
5

[bibtex key=”Hamkins:The-modal-logic-of-arithmetic-potentialism”]

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.

The universal finite set

Posted on by
6

[bibtex key=”HamkinsWoodin: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.

[bibtex key=”HamkinsWoodin:The-universal-finite-set”]

The set-theoretic universe is not necessarily a class-forcing extension of HOD

Posted on by
Reply

[bibtex key=”HamkinsReitz:The-set-theoretic-universe-is-not-necessarily-a-forcing-extension-of-HOD”]

Abstract. In light of the celebrated theorem of Vopěnka, proving in ZFC that every set is generic over $\newcommand\HOD{\text{HOD}}\HOD$, it is natural to inquire whether the set-theoretic universe $V$ must be a class-forcing extension of $\HOD$ by some possibly proper-class forcing notion in $\HOD$. We show, negatively, that if ZFC is consistent, then there is a model of ZFC that is not a class-forcing extension of its $\HOD$ for any class forcing notion definable in $\HOD$ and with definable forcing relations there (allowing parameters). Meanwhile, S. Friedman (2012) showed, positively, that if one augments $\HOD$ with a certain ZFC-amenable class $A$, definable in $V$, then the set-theoretic universe $V$ is a class-forcing extension of the expanded structure $\langle\HOD,\in,A\rangle$. Our result shows that this augmentation process can be necessary. The same example shows that $V$ is not necessarily a class-forcing extension of the mantle, and the method provides a counterexample to the intermediate model property, namely, a class-forcing extension $V\subseteq V[G]$ by a certain definable tame forcing and a transitive intermediate inner model $V\subseteq W\subseteq V[G]$ with $W\models\text{ZFC}$, such that $W$ is not a class-forcing extension of $V$ by any class forcing notion with definable forcing relations in $V$. This improves upon a previous example of Friedman (1999) by omitting the need for $0^\sharp$.

 

In 1972, Vopěnka proved the following celebrated result.

Theorem. (Vopěnka) If $V=L[A]$ where $A$ is a set of ordinals, then $V$ is a forcing extension of the inner model $\HOD$.

The result is now standard, appearing in Jech (Set Theory 2003, p. 249) and elsewhere, and the usual proof establishes a stronger result, stated in ZFC simply as the assertion: every set is generic over $\HOD$. In other words, for every set $a$ there is a forcing notion $\mathbb{B}\in\HOD$ and a $\HOD$-generic filter $G\subseteq\mathbb{B}$ for which $a\in\HOD[G]\subseteq V$. The full set-theoretic universe $V$ is therefore the union of all these various set-forcing generic extensions $\HOD[G]$.

It is natural to wonder whether these various forcing extensions $\HOD[G]$ can be unified or amalgamated to realize $V$ as a single class-forcing extension of $\HOD$ by a possibly proper class forcing notion in $\HOD$. We expect that it must be a very high proportion of set theorists and set-theory graduate students, who upon first learning of Vopěnka’s theorem, immediately ask this question.

Main Question. Must the set-theoretic universe $V$ be a class-forcing extension of $\HOD$?

We intend the question to be asking more specifically whether the universe $V$ arises as a bona-fide class-forcing extension of $\HOD$, in the sense that there is a class forcing notion $\mathbb{P}$, possibly a proper class, which is definable in $\HOD$ and which has definable forcing relation $p\Vdash\varphi(\tau)$ there for any desired first-order formula $\varphi$, such that $V$ arises as a forcing extension $V=\HOD[G]$ for some $\HOD$-generic filter $G\subseteq\mathbb{P}$, not necessarily definable.

In this article, we shall answer the question negatively, by providing a model of ZFC that cannot be realized as such a class-forcing extension of its $\HOD$.

Main Theorem. If ZFC is consistent, then there is a model of ZFC which is not a forcing extension of its $\HOD$ by any class forcing notion definable in that $\HOD$ and having a definable forcing relation there.

Throughout this article, when we say that a class is definable, we mean that it is definable in the first-order language of set theory allowing set parameters.

The main theorem should be placed in contrast to the following result of Sy Friedman.

Theorem. (Friedman 2012) There is a definable class $A$, which is strongly amenable to $\HOD$, such that the set-theoretic universe $V$ is a generic extension of $\langle \HOD,\in,A\rangle$.

This is a postive answer to the main question, if one is willing to augment $\HOD$ with a class $A$ that may not be definable in $\HOD$. Our main theorem shows that in general, this kind of augmentation process is necessary.

It is natural to ask a variant of the main question in the context of set-theoretic geology.

Question. Must the set-theoretic universe $V$ be a class-forcing extension of its mantle?

The mantle is the intersection of all set-forcing grounds, and so the universe is close in a sense to the mantle, perhaps one might hope that it is close enough to be realized as a class-forcing extension of it. Nevertheless, the answer is negative.

Theorem. If ZFC is consistent, then there is a model of ZFC that does not arise as a class-forcing extension of its mantle $M$ by any class forcing notion with definable forcing relations in $M$.

We also use our results to provide some counterexamples to the intermediate-model property for forcing. In the case of set forcing, it is well known that every transitive model $W$ of ZFC set theory that is intermediate $V\subseteq W\subseteq V[G]$ a ground model $V$ and a forcing extension $V[G]$, arises itself as a forcing extension $W=V[G_0]$.

In the case of class forcing, however, this can fail.

Theorem. If ZFC is consistent, then there are models of ZFC set theory $V\subseteq W\subseteq V[G]$, where $V[G]$ is a class-forcing extension of $V$ and $W$ is a transitive inner model of $V[G]$, but $W$ is not a forcing extension of $V$ by any class forcing notion with definable forcing relations in $V$.

Theorem. If ZFC + Ord is Mahlo is consistent, then one can form such a counterexample to the class-forcing intermediate model property $V\subseteq W\subseteq V[G]$, where $G\subset\mathbb{B}$ is $V$-generic for an Ord-c.c. tame definable complete class Boolean algebra $\mathbb{B}$, but nevertheless $W$ does not arise by class forcing over $V$ by any definable forcing notion with a definable forcing relation.

More complete details, please go to the paper (click through to the arxiv for a pdf). [bibtex key=”HamkinsReitz:The-set-theoretic-universe-is-not-necessarily-a-forcing-extension-of-HOD”]

Inner-model reflection principles

Posted on by
1

[bibtex key=”BartonCaicedoFuchsHamkinsReitzSchindler2020: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. [bibtex key=”BartonCaicedoFuchsHamkinsReitz: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 modal logic of set-theoretic potentialism and the potentialist maximality principles

Posted on by
2

Joint work with Øystein Linnebo, University of Oslo.

[bibtex key=”HamkinsLinnebo:Modal-logic-of-set-theoretic-potentialism”]

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.

[bibtex key=”HamkinsLinnebo:Modal-logic-of-set-theoretic-potentialism”]

Boolean ultrapowers, the Bukovský-Dehornoy phenomenon, and iterated ultrapowers

Posted on by
Reply

[bibtex key=”FuchsHamkins:TheBukovskyDehornoyPhenomenonForBooleanUltrapowers”]

Abstract. We show that while the length $\omega$ iterated ultrapower by a normal ultrafilter is a Boolean ultrapower by the Boolean algebra of Příkrý forcing, it is consistent that no iteration of length greater than $\omega$ (of the same ultrafilter and its images) is a Boolean ultrapower. For longer iterations, where different ultrafilters are used, this is possible, though, and we give Magidor forcing and a generalization of Příkrý forcing as examples. We refer to the discovery that the intersection of the finite iterates of the universe by a normal measure is the same as the generic extension of the direct limit model by the critical sequence as the Bukovský-Dehornoy phenomenon, and we develop a criterion (the existence of a simple skeleton) for when a version of this phenomenon holds in the context of Boolean ultrapowers.

The exact strength of the class forcing theorem

Posted on by
2

[bibtex key=”GitmanHamkinsHolySchlichtWilliams2020:The-exact-strength-of-the-class-forcing-theorem”]

Abstract. The class forcing theorem, which asserts that every class forcing notion $\newcommand\P{\mathbb{P}}\P$ admits a forcing relation $\newcommand\forces{\Vdash}\forces_\P$, that is, a relation satisfying the forcing relation recursion — it follows that statements true in the corresponding forcing extensions are forced and forced statements are true — is equivalent over Gödel-Bernays set theory GBC to the principle of elementary transfinite recursion $\newcommand\Ord{\text{Ord}}\newcommand\ETR{\text{ETR}}\ETR_{\Ord}$ for class recursions of length $\Ord$. It is also equivalent to the existence of truth predicates for the infinitary languages $\mathcal{L}_{\Ord,\omega}(\in,A)$, allowing any class parameter $A$; to the existence of truth predicates for the language $\mathcal{L}_{\Ord,\Ord}(\in,A)$; to the existence of $\Ord$-iterated truth predicates for first-order set theory $\mathcal{L}_{\omega,\omega}(\in,A)$; to the assertion that every separative class partial order $\P$ has a set-complete class Boolean completion; to a class-join separation principle; and to the principle of determinacy for clopen class games of rank at most $\Ord+1$. Unlike set forcing, if every class forcing relation $\P$ has a forcing relation merely for atomic formulas, then every such $\P$ has a uniform forcing relation that applies uniformly to all formulas. Our results situate the class forcing theorem in the rich hierarchy of theories between GBC and Kelley-Morse set theory KM.

We shall characterize the exact strength of the class forcing theorem, which asserts that every class forcing notion $\P$ has a corresponding forcing relation $\forces_\P$, a relation satisfying the forcing relation recursion. When there is such a forcing relation, then statements true in any corresponding forcing extension are forced and forced statements are true in those extensions.

Unlike the case of set forcing, where one may prove in ZFC that every set forcing notion has corresponding forcing relations, for class forcing it is consistent with Gödel-Bernays set theory GBC that there is a proper class forcing notion lacking a corresponding forcing relation, even merely for the atomic formulas. For certain forcing notions, the existence of an atomic forcing relation implies Con(ZFC) and much more, and so the consistency strength of the class forcing theorem strictly exceeds GBC, if this theory is consistent. Nevertheless, the class forcing theorem is provable in stronger theories, such as Kelley-Morse set theory. What is the exact strength of the class forcing theorem?

Our project here is to identify the strength of the class forcing theorem by situating it in the rich hierarchy of theories between GBC and KM, displayed in part in the figure above, with the class forcing theorem highlighted in blue. It turns out that the class forcing theorem is equivalent over GBC to an attractive collection of several other natural set-theoretic assertions; it is a robust axiomatic principle.

Hierarchy between GBC and KM

The main theorem is naturally part of the emerging subject we call the reverse mathematics of second-order set theory, a higher analogue of the perhaps more familiar reverse mathematics of second-order arithmetic. In this new research area, we are concerned with the hierarchy of second-order set theories between GBC and KM and beyond, analyzing the strength of various assertions in second-order set theory, such as the principle ETR of elementary transfinite recursion, the principle of $\Pi^1_1$-comprehension or the principle of determinacy for clopen class games. We fit these set-theoretic principles into the hierarchy of theories over the base theory GBC. The main theorem of this article does exactly this with the class forcing theorem by finding its exact strength in relation to nearby theories in this hierarchy.

Main Theorem. The following are equivalent over Gödel-Bernays set theory.

  1. The atomic class forcing theorem: every class forcing notion admits forcing relations for atomic formulas $$p\forces\sigma=\tau\qquad\qquad p\forces\sigma\in\tau.$$
  2. The class forcing theorem scheme: for each first-order formula $\varphi$ in the forcing language, with finitely many class names $\dot \Gamma_i$, there is a forcing relation applicable to this formula and its subformulas
    $$p\forces\varphi(\vec \tau,\dot\Gamma_0,\ldots,\dot\Gamma_m).$$
  3. The uniform first-order class forcing theorem: every class forcing notion $\P$ admits a uniform forcing relation $$p\forces\varphi(\vec \tau),$$ applicable to all assertions $\varphi$ in the first-order forcing language with finitely many class names $\mathcal{L}_{\omega,\omega}(\in,V^\P,\dot\Gamma_0,\ldots,\dot\Gamma_m)$.
  4. The uniform infinitary class forcing theorem: every class forcing notion $\P$ admits a uniform forcing relation $$p\forces\varphi(\vec \tau),$$ applicable to all assertions $\varphi$ in the infinitary forcing language with finitely many class names $\mathcal{L}_{\Ord,\Ord}(\in,V^\P,\dot\Gamma_0,\ldots,\dot\Gamma_m)$.
  5. Names for truth predicates: every class forcing notion $\P$ has a class name $\newcommand\T{{\rm T}}\dot\T$ and a forcing relation for which $1\forces\dot\T$ is a truth-predicate for the first-order forcing language with finitely many class names $\mathcal{L}_{\omega,\omega}(\in,V^\P,\dot\Gamma_0,\ldots,\dot\Gamma_m)$.
  6. Every class forcing notion $\P$, that is, every separative class partial order, admits a Boolean completion $\mathbb{B}$, a set-complete class Boolean algebra into which $\P$ densely embeds.
  7. The class-join separation principle plus $\ETR_{\Ord}$-foundation.
  8. For every class $A$, there is a truth predicate for $\mathcal{L}_{\Ord,\omega}(\in,A)$.
  9. For every class $A$, there is a truth predicate for $\mathcal{L}_{\Ord,\Ord}(\in,A)$.
  10. For every class $A$, there is an $\Ord$-iterated truth predicate for $\mathcal{L}_{\omega,\omega}(\in,A)$.
  11. The principle of determinacy for clopen class games of rank at most $\Ord+1$.
  12. The principle $\ETR_{\Ord}$ of elementary transfinite recursion for $\Ord$-length recursions of first-order properties, using any class parameter.

Implication cycle 12

We prove the theorem by establishing the complete cycle of indicated implications. The red arrows indicate more difficult or substantive implications, while the blue arrows indicate easier or nearly immediate implications. The green dashed implication from statement (12) to statement (1), while not needed for the completeness of the implication cycle, is nevertheless used in the proof that (12) implies (4). The proof of (12) implies (7) also uses (8), which follows from the fact that (12) implies (9) implies (8).

For more, download the paper from the arxiv: [bibtex key=”GitmanHamkinsHolySchlichtWilliams:The-exact-strength-of-the-class-forcing-theorem”]

See also Victoria’s post, Kameryn’s post.

When does every definable nonempty set have a definable element?

Posted on by
5

[bibtex key=”DoraisHamkins:When-does-every-definable-nonempty-set-have-a-definable-element”]

Abstract. The assertion that every definable set has a definable element is equivalent over ZF to the principle $V=\newcommand\HOD{\text{HOD}}\HOD$, and indeed, we prove, so is the assertion merely that every $\Pi_2$-definable set has an ordinal-definable element. Meanwhile, every model of ZFC has a forcing extension satisfying $V\neq\HOD$ in which every $\Sigma_2$-definable set has an ordinal-definable element. Similar results hold for $\HOD(\mathbb{R})$ and $\HOD(\text{Ord}^\omega)$ and other natural instances of $\HOD(X)$.

It is not difficult to see that the models of ZF set theory in which every definable nonempty set has a definable element are precisely the models of $V=\HOD$. Namely, if $V=\HOD$, then there is a definable well-ordering of the universe, and so the $\HOD$-least element of any definable nonempty set is definable; and conversely, if $V\neq\HOD$, then the set of minimal-rank non-OD sets is definable, but can have no definable element.

In this brief article, we shall identify the limit of this elementary observation in terms of the complexity of the definitions. Specifically, we shall prove that $V=\HOD$ is equivalent to the assertion that every $\Pi_2$-definable nonempty set contains an ordinal-definable element, but that one may not replace $\Pi_2$-definability here by $\Sigma_2$-definability.

Theorem. The following are equivalent in any model $M$ of ZF:

  1. $M$ is a model of $\text{ZFC}+\text{V}=\text{HOD}$.
  2. $M$ thinks there is a definable well-ordering of the universe.
  3. Every definable nonempty set in $M$ has a definable element.
  4. Every definable nonempty set in $M$ has an ordinal-definable element.
  5. Every ordinal-definable nonempty set in $M$ has an ordinal-definable element.
  6. Every $\Pi_2$-definable nonempty set in $M$ has an ordinal-definable element.

Theorem. Every model of ZFC has a forcing extension satisfying $V\neq\HOD$, in which every $\Sigma_2$-definable set has a definable element.

The proof of this latter theorem is reminiscent of several proofs of the maximality principle (see A simple maximality principle), where one undertakes a forcing iteration attempting at each stage to force and then preserve a given $\Sigma_2$ assertion.

This inquiry grew out of a series of questions and answers posted on MathOverflow and the exchange of the authors there.

A model of the generic Vopěnka principle in which the ordinals are not $\Delta_2$-Mahlo

Posted on by
Reply

[bibtex key=”GitmanHamkins2018:A-model-of-the-generic-Vopenka-principle-in-which-the-ordinals-are-not-Mahlo”]

Abstract. The generic Vopěnka principle, we prove, is relatively consistent with the ordinals being non-Mahlo. Similarly, the generic Vopěnka scheme is relatively consistent with the ordinals being definably non-Mahlo. Indeed, the generic Vopěnka scheme is relatively consistent with the existence of a $\Delta_2$-definable class containing no regular cardinals. In such a model, there can be no $\Sigma_2$-reflecting cardinals and hence also no remarkable cardinals. This latter fact answers negatively a question of Bagaria, Gitman and Schindler.

 

The Vopěnka principle is the assertion that for every proper class of first-order structures in a fixed language, one of the structures embeds elementarily into another. This principle can be formalized as a single second-order statement in Gödel-Bernays set-theory GBC, and it has a variety of useful equivalent characterizations. For example, the Vopěnka principle holds precisely when for every class $A$, the universe has an $A$-extendible cardinal, and it is also equivalent to the assertion that for every class $A$, there is a stationary proper class of $A$-extendible cardinals (see theorem 6 in my paper The Vopěnka principle is inequivalent to but conservative over the Vopěnka scheme) In particular, the Vopěnka principle implies that ORD is Mahlo: every class club contains a regular cardinal and indeed, an extendible cardinal and more.

To define these terms, recall that a cardinal $\kappa$ is extendible, if for every $\lambda>\kappa$, there is an ordinal $\theta$ and an elementary embedding $j:V_\lambda\to V_\theta$ with critical point $\kappa$. It turns out that, in light of the Kunen inconsistency, this weak form of extendibility is equivalent to a stronger form, where one insists also that $\lambda<j(\kappa)$; but there is a subtle issue about this that comes up with the virtual forms of these axioms, where the virtual weak and virtual strong forms are no longer equivalent. Relativizing to a class parameter, a cardinal $\kappa$ is $A$-extendible for a class $A$, if for every $\lambda>\kappa$, there is an elementary embedding
$$j:\langle V_\lambda, \in, A\cap V_\lambda\rangle\to \langle V_\theta,\in,A\cap V_\theta\rangle$$
with critical point $\kappa$, and again one may equivalently insist also that $\lambda<j(\kappa)$. Every such $A$-extendible cardinal is therefore extendible and hence inaccessible, measurable, supercompact and more. These are amongst the largest large cardinals.

In the first-order ZFC context, set theorists commonly consider a first-order version of the Vopěnka principle, which we call the Vopěnka scheme, the scheme making the Vopěnka assertion of each definable class separately, allowing parameters. That is, the Vopěnka scheme asserts, of every formula $\varphi$, that for any parameter $p$, if $\{\,x\mid \varphi(x,p)\,\}$ is a proper class of first-order structures in a common language, then one of those structures elementarily embeds into another.

The Vopěnka scheme is naturally stratified by the assertions $\text{VP}(\Sigma_n)$, for the particular natural numbers $n$ in the meta-theory, where $\text{VP}(\Sigma_n)$ makes the Vopěnka assertion for all $\Sigma_n$-definable classes. Using the definable $\Sigma_n$-truth predicate, each assertion $\text{VP}(\Sigma_n)$ can be expressed as a single first-order statement in the language of set theory.

In my previous paper, The Vopěnka principle is inequivalent to but conservative over the Vopěnka scheme, I proved that the Vopěnka principle is not provably equivalent to the Vopěnka scheme, if consistent, although they are equiconsistent over GBC and furthermore, the Vopěnka principle is conservative over the Vopěnka scheme for first-order assertions. That is, over GBC the two versions of the Vopěnka principle have exactly the same consequences in the first-order language of set theory.

In this article, Gitman and I are concerned with the virtual forms of the Vopěnka principles. The main idea of virtualization, due to Schindler, is to weaken elementary-embedding existence assertions to the assertion that such embeddings can be found in a forcing extension of the universe. Gitman and Schindler had emphasized that the remarkable cardinals, for example, instantiate the virtualized form of supercompactness via the Magidor characterization of supercompactness. This virtualization program has now been undertaken with various large cardinals, leading to fruitful new insights.

Carrying out the virtualization idea with the Vopěnka principles, we define the generic Vopěnka principle to be the second-order assertion in GBC that for every proper class of first-order structures in a common language, one of the structures admits, in some forcing extension of the universe, an elementary embedding into another. That is, the structures themselves are in the class in the ground model, but you may have to go to the forcing extension in order to find the elementary embedding.

Similarly, the generic Vopěnka scheme, introduced by Bagaria, Gitman and Schindler, is the assertion (in ZFC or GBC) that for every first-order definable proper class of first-order structures in a common language, one of the structures admits, in some forcing extension, an elementary embedding into another.

On the basis of their work, Bagaria, Gitman and Schindler had asked the following question:

Question. If the generic Vopěnka scheme holds, then must there be a proper class of remarkable cardinals?

There seemed good reason to expect an affirmative answer, even assuming only $\text{gVP}(\Sigma_2)$, based on strong analogies with the non-generic case. Specifically, in the non-generic context Bagaria had proved that $\text{VP}(\Sigma_2)$ was equivalent to the existence of a proper class of supercompact cardinals, while in the virtual context, Bagaria, Gitman and Schindler proved that the generic form $\text{gVP}(\Sigma_2)$ was equiconsistent with a proper class of remarkable cardinals, the virtual form of supercompactness. Similarly, higher up, in the non-generic context Bagaria had proved that $\text{VP}(\Sigma_{n+2})$ is equivalent to the existence of a proper class of $C^{(n)}$-extendible cardinals, while in the virtual context, Bagaria, Gitman and Schindler proved that the generic form $\text{gVP}(\Sigma_{n+2})$ is equiconsistent with a proper class of virtually $C^{(n)}$-extendible cardinals.

But further, they achieved direct implications, with an interesting bifurcation feature that specifically suggested an affirmative answer to the question above. Namely, what they showed at the $\Sigma_2$-level is that if there is a proper class of remarkable cardinals, then $\text{gVP}(\Sigma_2)$ holds, and conversely if $\text{gVP}(\Sigma_2)$ holds, then there is either a proper class of remarkable cardinals or a proper class of virtually rank-into-rank cardinals. And similarly, higher up, if there is a proper class of virtually $C^{(n)}$-extendible cardinals, then $\text{gVP}(\Sigma_{n+2})$ holds, and conversely, if $\text{gVP}(\Sigma_{n+2})$ holds, then either there is a proper class of virtually $C^{(n)}$-extendible cardinals or there is a proper class of virtually rank-into-rank cardinals. So in each case, the converse direction achieves a disjunction with the target cardinal and the virtually rank-into-rank cardinals. But since the consistency strength of the virtually rank-into-rank cardinals is strictly stronger than the generic Vopěnka principle itself, one can conclude on consistency-strength grounds that it isn’t always relevant, and for this reason, it seemed natural to inquire whether this second possibility in the bifurcation could simply be removed. That is, it seemed natural to expect an affirmative answer to the question, even assuming only $\text{gVP}(\Sigma_2)$, since such an answer would resolve the bifurcation issue and make a tighter analogy with the corresponding results in the non-generic/non-virtual case.

In this article, however, we shall answer the question negatively. The details of our argument seem to suggest that a robust analogy with the non-generic/non-virtual principles is achieved not with the virtual $C^{(n)}$-cardinals, but with a weakening of that property that drops the requirement that $\lambda<j(\kappa)$. Indeed, our results seems to offer an illuminating resolution of the bifurcation aspect of the results we mentioned from Bagaria, Gitmand and Schindler, because it provides outright virtual large-cardinal equivalents of the stratified generic Vopěnka principles. Because the resulting virtual large cardinals are not necessarily remarkable, however, our main theorem shows that it is relatively consistent with even the full generic Vopěnka principle that there are no $\Sigma_2$-reflecting cardinals and therefore no remarkable cardinals.

Main Theorem.

  1. It is relatively consistent that GBC and the generic Vopěnka principle holds, yet ORD is not Mahlo.
  2. It is relatively consistent that ZFC and the generic Vopěnka scheme holds, yet ORD is not definably Mahlo, and not even $\Delta_2$-Mahlo. In such a model, there can be no $\Sigma_2$-reflecting cardinals and therefore also no remarkable cardinals.

For more, go to the arcticle:

[bibtex key=”GitmanHamkins2018:A-model-of-the-generic-Vopenka-principle-in-which-the-ordinals-are-not-Mahlo”]

The inclusion relations of the countable models of set theory are all isomorphic

Posted on by
4

[bibtex key=”HamkinsKikuchi:The-inclusion-relations-of-the-countable-models-of-set-theory-are-all-isomorphic”]

mereology type

Abstract. The structures $\langle M,\newcommand\of{\subseteq}\of^M\rangle$ arising as the inclusion relation of a countable model of sufficient set theory $\langle M,\in^M\rangle$, whether well-founded or not, are all isomorphic. These structures $\langle M,\of^M\rangle$ are exactly the countable saturated models of the theory of set-theoretic mereology: an unbounded atomic relatively complemented distributive lattice. A very weak set theory suffices, even finite set theory, provided that one excludes the $\omega$-standard models with no infinite sets and the $\omega$-standard models of set theory with an amorphous set. Analogous results hold also for class theories such as Gödel-Bernays set theory and Kelley-Morse set theory.

Set-theoretic mereology is the study of the inclusion relation $\of$ as it arises within set theory. In any set-theoretic context, with the set membership relation $\in$, one may define the corresponding inclusion relation $\of$ and investigate its properties. Thus, every model of set theory $\langle M,\in^M\rangle$ gives rise to a corresponding model of set-theoretic mereology $\langle M,\of^M\rangle$, the reduct to the inclusion relation.

In our previous article,

J. D. Hamkins and M. Kikuchi, Set-theoretic mereology, Logic and Logical Philosophy, special issue “Mereology and beyond, part II”, vol. 25, iss. 3, pp. 1-24, 2016.

we had identified exactly the complete theory of these mereological structures $\langle M,\of^M\rangle$. Namely, if $\langle M,\in^M\rangle$ is a model of set theory, even for extremely weak theories, including set theory without the infinity axiom, then the corresponding mereological reduct $\langle M,\of^M\rangle$ is an unbounded atomic relatively complemented distributive lattice. We call this the theory of set-theoretic mereology. By a quantifier-elimination argument that we give in our earlier paper, partaking of Tarski’s Boolean-algebra invariants and Ersov’s work on lattices, this theory is complete, finitely axiomatizable and decidable.  We had proved among other things that $\in$ is never definable from $\of$ in any model of set theory and furthermore, some models of set-theoretic mereology can arise as the inclusion relation of diverse models of set theory, with different theories. Furthermore, we proved that $\langle\text{HF},\subseteq\rangle\prec\langle V,\subseteq\rangle$.

After that work, we found it natural to inquire:

Question. Which models of set-theoretic mereology arise as the inclusion relation $\of$ of a model of set theory?

More precisely, given a model $\langle M,\newcommand\sqof{\sqsubseteq}\sqof\rangle$ of set-theoretic mereology, under what circumstances can we place a binary relation $\in^M$ on $M$ in such a way that $\langle M,\in^M\rangle$ is a model of set theory and the inclusion relation $\of$ defined in $\langle M,\in^M\rangle$ is precisely the given relation $\sqof$? One can view this question as seeking a kind of Stone-style representation of the mereological structure $\langle M,\sqof\rangle$, because such a model $M$ would provide a representation of $\langle M,\sqof\rangle$ as a relative field of sets via the model of set theory $\langle M,\in^M\rangle$.

A second natural question was to wonder how much of the theory of the original model of set theory can be recovered from the mereological reduct.

Question. If $\langle M,\of^M\rangle$ is the model of set-theoretic mereology arising as the inclusion relation $\of$ of a model of set theory $\langle M,\in^M\rangle$, what part of the theory of $\langle M,\in^M\rangle$ is determined by the structure $\langle M,\of^M\rangle$?

In the case of the countable models of ZFC, these questions are completely answered by our main theorems.

Main Theorems.

  1. All countable models of set theory $\langle M,\in^M\rangle\models\text{ZFC}$ have isomorphic reducts $\langle M,\of^M\rangle$ to the inclusion relation.
  2. The same holds for models of considerably weaker theories such as KP and even finite set theory, provided one excludes the $\omega$-standard models without infinite sets and the $\omega$-standard models having an amorphous set.
  3. These inclusion reducts $\langle M,\of^M\rangle$ are precisely the countable saturated models of set-theoretic mereology.
  4. Similar results hold for class theory: all countable models of Gödel-Bernays set theory have isomorphic reducts to the inclusion relation, and this reduct is precisely the countably infinite saturated atomic Boolean algebra.

Specifically, we show that the mereological reducts $\langle M,\of^M\rangle$ of the models of sufficient set theory are always $\omega$-saturated, and from this it follows on general model-theoretic grounds that they are all isomorphic, establishing statements (1) and (2). So a countable model $\langle M,\sqof\rangle$ of set-theoretic mereology arises as the inclusion relation of a model of sufficient set theory if and only if it is $\omega$-saturated, establishing (3) and answering the first question. Consequently, in addition, the mereological reducts $\langle M,\of^M\rangle$ of the countable models of sufficient set theory know essentially nothing of the theory of the structure $\langle M,\in^M\rangle$ from which they arose, since $\langle M,\of^M\rangle$ arises equally as the inclusion relation of other models $\langle M,\in^*\rangle$ with any desired sufficient alternative set theory, a fact which answers the second question. Our analysis works with very weak set theories, even finite set theory, provided one excludes the $\omega$-standard models with no infinite sets and the $\omega$-standard models with an amorphous set, since the inclusion reducts of these models are not $\omega$-saturated. We also prove that most of these results do not generalize to uncountable models, nor even to the $\omega_1$-like models.

Our results have some affinity with the classical results in models of arithmetic concerned with the additive reducts of models of PA. Restricting a model of set theory to the inclusion relation $\of$ is, after all, something like restricting a model of arithmetic to its additive part. Lipshitz and Nadel (1978) proved that a countable model of Presburger arithmetic (with $+$ only) can be expanded to a model of PA if and only if it is computably saturated. We had hoped at first to prove a corresponding result for the mereological reducts of the models of set theory. In arithmetic, the additive reducts are not all isomorphic, since the standard system of the PA model is fully captured by the additive reduct. Our main result for the countable models of set theory, however, turned out to be stronger than we had expected, since the inclusion reducts are not merely computably saturated, but fully $\omega$-saturated, and this is why they are all isomorphic. Meanwhile, Lipshitz and Nadel point out that their result does not generalize to uncountable models of arithmetic, and similarly ours also does not generalize to uncountable models of set theory.

The work leaves the following question open:

Question. Are the mereological reducts $\langle M,\of^M\rangle$ of all the countable models $\langle M,\in^M\rangle$ of ZF with an amorphous set all isomorphic?

We expect the answer to come from a deeper understanding of the Tarski-Ersov invariants for the mereological structures combined with knowledge of models of ZF with amorphous sets.

This is joint work with Makoto Kikuchi.

Computable quotient presentations of models of arithmetic and set theory

Posted on by
2

[bibtex key=GodziszewskiHamkins2017:Computable-quotient-presentations-of-models-of-arithmetic-and-set-theory]

Abstract. We prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+,\cdot,\leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation. 

A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle\newcommand\N{\mathbb{N}}\N,\star,\ast,\dots\rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\N$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle\N,\star,\ast,\dots\rangle/E$ is isomorphic to $\mathcal A$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure. In a language with relations, it is also natural to relax the concept somewhat by considering the computably enumerable quotient presentations, which allow the pre-quotient relations to be merely computably enumerable, rather than insisting that they must be computable.

At the 2016 conference Mathematical Logic and its Applications at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. In his talk (see his slides), he outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation $E$ or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo $E$.

In this article, we engage specifically with two conjectures that Khoussainov had made at the meeting.

Conjecture. (Khoussainov)

  1. No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
  2. Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.

We prove the first conjecture and refute several natural variations of the second conjecture, although a further natural variation, perhaps the central case, remains open. In addition, we consider and settle the natural analogues of the conjectures for models of set theory.

The implicitly constructible universe

Posted on by
Reply

[bibtex key=”GroszekHamkins2019:The-implicitly-constructible-universe”]

Abstract. We answer several questions posed by Hamkins and Leahy concerning the implicitly constructible universe $\newcommand\Imp{\text{Imp}}\Imp$, which they introduced in their paper, Algebraicity and implicit definability in set theory. Specifically, we show that it is relatively consistent with ZFC that $\Imp \models \neg \text{CH}$, that $\Imp \neq \text{HOD}$, and that $\Imp \models V \neq \Imp$, or in other words, that $(\Imp)^{\Imp} \neq \Imp$.

The rearrangement number

Posted on by
3

[bibtex key=BlassBrendleBrianHamkinsHardyLarson2020:TheRearrangementNumber]

Abstract.  How many permutations of the natural numbers are needed so that every conditionally convergent series of real numbers can be rearranged to no longer converge to the same sum? We show that the minimum number of permutations needed for this purpose, which we call the rearrangement number, is uncountable, but whether it equals the cardinal of the continuum is independent of the usual axioms of
set theory. We compare the rearrangement number with several natural variants, for example one obtained by requiring the rearranged series to still converge but to a new, finite limit. We also compare the rearrangement number with several well-studied
cardinal characteristics of the continuum. We present some new forcing constructions designed to add permutations that rearrange series from the ground model in particular ways, thereby obtaining consistency results going beyond those that follow from comparisons with familiar cardinal characteristics. Finally we deal briefly with some variants concerning rearrangements by a special sort of permutations and with rearranging some divergent series to become (conditionally) convergent.

This project started with Michael Hardy’s question on MathOverflow, How many rearrangements must fail to alter the value of a sum before you conclude that none do? I had proposed in my answer that we should think of the cardinal in question as a cardinal characteristic of the continuum, the rearrangement number, since we could prove that it was uncountable and that it was the continuum under MA, and had begun to separate it from other familiar cardinal characteristics. Eventually, the research effort grew into the collaboration of this paper. What a lot of fun!

Colloquium talk at Vassar | Lecture notes | talk at CUNY | the original MathOverflow question

The lecture notes are for an introductory talk on the topic I had given at the Vassar College Mathematics Colloquium.

Ord is not definably weakly compact

Posted on by
2

[bibtex key=EnayatHamkins2018:Ord-is-not-definably-weakly-compact]

In ZFC the class of all ordinals is very like a large cardinal.  Being closed under exponentiation, for example, Ord is a strong limit.  Indeed, it is a beth fixed point. And Ord is regular with respect to definable classes by the replacement axiom.  In this sense, ZFC therefore proves that Ord is definably inaccessible.  Which other large cardinal properties are exhibited by Ord? Perhaps you wouldn’t find it unreasonable for Ord to exhibit, at least consistently with ZFC, the definable proper class analogues of other much stronger large cardinal properties?

Meanwhile, the main results of this paper, joint between myself and Ali Enayat, show that such an expectation would be misplaced, even for comparatively small large cardinal properties. Specifically, in a result that surprised me, it turns out that the class of ordinals NEVER exhibits the definable proper class analogue of weak compactness in any model of ZFC.

Theorem. The class of ordinals is not definably weakly compact. In every model of ZFC:

  1. The definable tree property fails; there is a definable Ord-tree with no definable cofinal branch.
  2. The definable partition property fails; there is a definable 2-coloring of a definable proper class, with no homogeneous definable proper subclass.
  3. The definable compactness property fails for $\mathcal{L}_{\mathrm{Ord,\omega}}$; there is a definable theory in this logic, all of whose set-sized subtheories are satisfiable, but the whole theory has no definable class model.

The proof uses methods from the model theory of set theory, including especially the fact that no model of ZFC has a conservative $\Sigma_3$-elementary end-extension.

Theorem. The definable $\Diamond _{\mathrm{Ord}}$ principle holds in a model of ZFC if and only if the model has a definable well-ordering.

We close the paper by proving that the theory of the spartan models of Gödel-Bernays set theory GB — those equipped with only their definable classes — is $\Pi^1_1$-complete.

Theorem. The set of sentences true in all spartan models of GB is $\Pi_{1}^{1}$-complete.