Category Archives: Publications

Superstrong and other large cardinals are never Laver indestructible

Posted on by
1

[bibtex key=BagariaHamkinsTsaprounisUsuba2016:SuperstrongAndOtherLargeCardinalsAreNeverLaverIndestructible]

Abstract.  Superstrong cardinals are never Laver indestructible. Similarly, almost huge cardinals, huge cardinals, superhuge cardinals, rank-into-rank cardinals, extendible cardinals, $1$-extendible cardinals, $0$-extendible cardinals, weakly superstrong cardinals, uplifting cardinals, pseudo-uplifting cardinals, superstrongly unfoldable cardinals, $\Sigma_n$-reflecting cardinals, $\Sigma_n$-correct cardinals and $\Sigma_n$-extendible cardinals (all for $n\geq 3$) are never Laver indestructible. In fact, all these large cardinal properties are superdestructible: if $\kappa$ exhibits any of them, with corresponding target $\theta$, then in any forcing extension arising from nontrivial strategically ${\lt}\kappa$-closed forcing $\mathbb{Q}\in V_\theta$, the cardinal $\kappa$ will exhibit none of the large cardinal properties with target $\theta$ or larger.

The large cardinal indestructibility phenomenon, occurring when certain preparatory forcing makes a given large cardinal become necessarily preserved by any subsequent forcing from a large class of forcing notions, is pervasive in the large cardinal hierarchy. The phenomenon arose in Laver’s seminal result that any supercompact cardinal $\kappa$ can be made indestructible by ${\lt}\kappa$-directed closed forcing. It continued with the Gitik-Shelah treatment of strong cardinals; the universal indestructibility of Apter and myself, which produced simultaneous indestructibility for all weakly compact, measurable, strongly compact, supercompact cardinals and others; the lottery preparation, which applies generally to diverse large cardinals; work of Apter, Gitik and Sargsyan on indestructibility and the large-cardinal identity crises; the indestructibility of strongly unfoldable cardinals; the indestructibility of Vopenka’s principle; and diverse other treatments of large cardinal indestructibility. Based on these results, one might be tempted to the general conclusion that all the usual large cardinals can be made indestructible.

In this article, my co-authors and I temper that temptation by proving that certain kinds of large cardinals cannot be made nontrivially indestructible. Superstrong cardinals, we prove, are never Laver indestructible. Consequently, neither are almost huge cardinals, huge cardinals, superhuge cardinals, rank-into-rank cardinals, extendible cardinals and $1$-extendible cardinals, to name a few. Even the $0$-extendible cardinals are never indestructible, and neither are weakly superstrong cardinals, uplifting cardinals, pseudo-uplifting cardinals, strongly uplifting cardinals, superstrongly unfoldable cardinals, $\Sigma_n$-reflecting cardinals, $\Sigma_n$-correct cardinals and $\Sigma_n$-extendible cardinals, when $n\geq 3$. In fact, all these large cardinal properties are superdestructible, in the sense that if $\kappa$ exhibits any of them, with corresponding target $\theta$, then in any forcing extension arising from nontrivial strategically ${\lt}\kappa$-closed forcing $\mathbb{Q}\in V_\theta$, the cardinal $\kappa$ will exhibit none of the large cardinal properties with target $\theta$ or larger. Many quite ordinary forcing notions, which one might otherwise have expected to fall under the scope of an indestructibility result, will definitely ruin all these large cardinal properties. For example, adding a Cohen subset to any cardinal $\kappa$ will definitely prevent it from being superstrong—as well as preventing it from being uplifting, $\Sigma_3$-correct, $\Sigma_3$-extendible and so on with all the large cardinal properties mentioned above—in the forcing extension.

Main Theorem. 

  1. Superstrong cardinals are never Laver indestructible.
  2. Consequently, almost huge, huge, superhuge and rank-into-rank cardinals are never Laver indestructible.
  3. Similarly, extendible cardinals, $1$-extendible and even $0$-extendible cardinals are never Laver indestructible.
  4. Uplifting cardinals, pseudo-uplifting cardinals, weakly superstrong cardinals, superstrongly unfoldable cardinals and strongly uplifting cardinals are never Laver indestructible.
  5. $\Sigma_n$-reflecting and indeed $\Sigma_n$-correct cardinals, for each finite $n\geq 3$, are never Laver indestructible.
  6. Indeed—the strongest result here, because it is the weakest notion—$\Sigma_3$-extendible cardinals are never Laver indestructible.

In fact, each of these large cardinal properties is superdestructible. Namely, if $\kappa$ exhibits any of them, with corresponding target $\theta$, then in any forcing extension arising from nontrivial strategically ${\lt}\kappa$-closed forcing $\mathbb{Q}\in V_\theta$, the cardinal $\kappa$ will exhibit none of the mentioned large cardinal properties with target $\theta$ or larger.

The proof makes use of a detailed analysis of the complexity of the definition of the ground model in the forcing extension.  These results are, to my knowledge, the first applications of the ideas of set-theoretic geology not making direct references to set-theoretically geological concerns.

Theorem 10 in the article answers (the main case of) a question I had posed on MathOverflow, namely, Can a model of set theory be realized as a Cohen-subset forcing extension in two different ways, with different grounds and different cardinals?  I had been specifically interested there to know whether a cardinal $\kappa$ necessarily becomes definable after adding a Cohen subset to it, and theorem 10 shows indeed that it does:  after adding a Cohen subset to a cardinal, it becomes $\Sigma_3$-definable in the extension, and this fact can be seen as explaining the main theorem above.

Related MO question | CUNY talk

The least weakly compact cardinal can be unfoldable, weakly measurable and nearly $\theta$-supercompact

Posted on by
3

[bibtex key=CodyGitikHamkinsSchanker2015:LeastWeaklyCompact]

Abstract.   We prove from suitable large cardinal hypotheses that the least weakly compact cardinal can be unfoldable, weakly measurable and even nearly $\theta$-supercompact, for any desired $\theta$. In addition, we prove several global results showing how the entire class of weakly compact cardinals, a proper class, can be made to coincide with the class of unfoldable cardinals, with the class of weakly measurable cardinals or with the class of nearly $\theta_\kappa$-supercompact cardinals $\kappa$, for nearly any desired function $\kappa\mapsto\theta_\kappa$. These results answer several questions that had been open in the literature and extend to these large cardinals the identity-crises phenomenon, first identified by Magidor with the strongly compact cardinals.

In this article, we prove that the least weakly compact cardinal can exhibit any of several much stronger large cardinal properties. Namely, the least weakly compact cardinal can be unfoldable, weakly measurable and nearly $\theta$-supercompact for any desired $\theta$.

Main Theorem.  Assuming a suitable large cardinal hypothesis, the least weakly compact cardinal can be unfoldable, weakly measurable and even nearly $\theta$-supercompact, for any desired $\theta$.

Meanwhile, the least weakly compact cardinal can never exhibit these extra large cardinal properties in $L$, and indeed, the existence of a weakly measurable cardinal in the constructible universe is impossible. Furthermore, in each case the extra properties are strictly stronger than weak compactness in consistency strength.

We show in addition a more global result, that the entire class of weakly compact cardinals can be made to coincide with the class of unfoldable cardinals, with the class of weakly measurable cardinals, and with the class of nearly $\theta_\kappa$-supercompact cardinals $\kappa$, with enormous flexibility in the map $\kappa\mapsto\theta_\kappa$.

Our results therefore extend the `identity-crises’ phenomenon—first identified (and named) by Magidor—which occurs when a given large cardinal property can be made in various models to coincide either with much stronger or with much weaker large cardinal notions. Magidor had proved that the least strongly compact cardinal can be the least supercompact cardinal in one model of set theory and the least measurable cardinal in another. Here, we extend the phenomenon to weak measurability, partial near supercompactness and unfoldability. Specifically, the least weakly measurable cardinal coincides with the least measurable cardinal under the GCH, but it is the least weakly compact cardinal in our main theorem. Similarly, the least cardinal $\kappa$ that is nearly $\kappa^{+}$-supercompact is measurable with nontrivial Mitchell order under the GCH, but it is the least weakly compact cardinal here (and similar remarks apply to near $\kappa^{++}$-supercompactness and so on). The least unfoldable cardinal is strongly unfoldable in $L$, and therefore a $\Sigma_2$-reflecting limit of weakly compact cardinals there, but it is the least weakly compact cardinal in our main theorem. The global results of section 6 show just how malleable these notions are.

Algebraicity and implicit definability in set theory

Posted on by
2

[bibtex key=HamkinsLeahy2016:AlgebraicityAndImplicitDefinabilityInSetTheory]

We aim in this article to analyze the effect of replacing several natural uses of definability in set theory by the weaker model-theoretic notion of algebraicity and its companion concept of implicit definability. In place of the class HOD of hereditarily ordinal definable sets, for example, we consider the class HOA of hereditarily ordinal-algebraic sets. In place of the pointwise definable models of set theory, we examine its (pointwise) algebraic models. And in place of Gödel’s constructible universe L, obtained by iterating the definable power set operation, we introduce the implicitly constructible universe Imp, obtained by iterating the algebraic or implicitly definable power set operation. In each case we investigate how the change from definability to algebraicity affects the nature of the resulting concept. We are especially intrigued by Imp, for it is a new canonical inner model of ZF whose subtler properties are just now coming to light. Open questions about Imp abound.

Before proceeding further, let us review the basic definability definitions. In the model theory of first-order logic, an element $a$ is definable in a structure $M$ if it is the unique object in $M$ satisfying some first-order property $\varphi$ there, that is, if $M\models\varphi[b]$ just in case $b=a$. More generally, an element $a$ is algebraic in $M$ if it has a property $\varphi$ exhibited by only finitely many objects in $M$, so that $\{b\in M \mid M\models\varphi[b]\}$ is a finite set containing $a$. For each class $P\subset M$ we can similarly define what it means for an element to be $P$-definable or $P$-algebraic by allowing the formula $\varphi$ to have parameters from $P$.

In the second-order context, a subset or class $A\subset M^n$ is said to be definable in $M$, if $A=\{\vec a\in M\mid M\models\varphi[\vec a]\}$ for some first-order formula $\varphi$. In particular, $A$ is the unique class in $M^n$ with $\langle M,A\rangle\models\forall \vec x\, [\varphi(\vec x)\iff A(\vec x)]$, in the language where we have added a predicate symbol for $A$. Generalizing this condition, we say that a class $A\subset M^n$ is implicitly definable in $M$ if there is a first-order formula $\psi(A)$ in the expanded language, not necessarily of the form $\forall \vec x\, [\varphi(\vec x)\iff A(\vec x)]$, such that $A$ is unique such that $\langle M,A\rangle\models\psi(A)$. Thus, every (explicitly) definable class is also implicitly definable, but the converse can fail. Even more generally, we say that a class $A\subset M^n$ is algebraic in $M$ if there is a first-order formula $\psi(A)$ in the expanded language such that $\langle M,A\rangle\models\psi(A)$ and there are only finitely many $B\subset M^n$ for which $\langle M,B\rangle\models\psi(B)$. Allowing parameters from a fixed class $P\subset M$ to appear in $\psi$ yields the notions of $P$-definability, implicit $P$-definability, and $P$-algebraicity in $M$. Simplifying the terminology, we say that $A$ is definable, implicitly definable, or algebraic over (rather than in) $M$ if it is $M$-definable, implicitly $M$-definable, or $M$-algebraic in $M$, respectively. A natural generalization of these concepts arises by allowing second-order quantifiers to appear in $\psi$. Thus we may speak of a class $A$ as second-order definable, implicitly second-order definable, or second-order algebraic. Further generalizations are of course possible by allowing $\psi$ to use resources from other strong logics.

The main theorems of the paper are:

Theorem. The class of hereditarily ordinal algebraic sets is the same as the class of hereditarily ordinal definable sets: $$\text{HOA}=\text{HOD}.$$

Theorem. Every pointwise algebraic model of ZF is a pointwise definable model of ZFC+V=HOD.

In the latter part of the paper, we introduce what we view as the natural algebraic analogue of the constructible universe, namely, the implicitly constructible universe, denoted Imp, and built as follows:

$$\text{Imp}_0 = \emptyset$$

$$\text{Imp}_{\alpha + 1} = P_{imp}(\text{Imp}_\alpha)$$

$$\text{Imp}_\lambda = \bigcup_{\alpha < \lambda} \text{Imp}_\alpha, \text{ for limit }\lambda$$

$$\text{Imp} = \bigcup_\alpha \text{Imp}_\alpha.$$

Theorem.  Imp is an inner model of ZF with $L\subset\text{Imp}\subset\text{HOD}$.

Theorem.  It is relatively consistent with ZFC that $\text{Imp}\neq L$.

Theorem. In any set-forcing extension $L[G]$ of $L$, there is a further extension $L[G][H]$ with $\text{gImp}^{L[G][H]}=\text{Imp}^{L[G][H]}=L$.

Open questions about Imp abound. Can $\text{Imp}^{\text{Imp}}$ differ from $\text{Imp}$? Does $\text{Imp}$ satisfy the axiom of choice? Can $\text{Imp}$ have measurable cardinals? Must $0^\sharp$ be in $\text{Imp}$ when it exists? (An affirmative answer arose in conversation with Menachem Magidor and Gunter Fuchs, and we hope that $\text{Imp}$ will subsume further large cardinal features. We anticipate a future article on the implicitly constructible universe.)  Which large cardinals are absolute to $\text{Imp}$? Does $\text{Imp}$ have fine structure? Should we hope for any condensation-like principle? Can CH or GCH fail in $\text{Imp}$? Can reals be added at uncountable construction stages of $\text{Imp}$? Can we separate $\text{Imp}$ from HOD? How much can we control $\text{Imp}$ by forcing? Can we put arbitrary sets into the $\text{Imp}$ of a suitable forcing extension? What can be said about the universe $\text{Imp}(\mathbb{R})$ of sets implicitly constructible relative to $\mathbb{R}$ and, more generally, about $\text{Imp}(X)$ for other sets $X$? Here we hope at least to have aroused interest in these questions.

This article arose from a question posed on MathOverflow by my co-author Cole Leahy and our subsequent engagement with it.

Transfinite game values in infinite chess

Posted on by
16

[bibtex key=EvansHamkins2014:TransfiniteGameValuesInInfiniteChess]

In this article, C. D. A. Evans  and I investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values—the omega one of chess—denoted by $\omega_1^{\mathfrak{Ch}}$ in the context of finite positions and by $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we present specific positions with transfinite game values of $\omega$, $\omega^2$, $\omega^2\cdot k$ and $\omega^3$. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true $\omega_1$.

The article is 38 pages, with 18 figures detailing many interesting positions of infinite chess. My co-author Cory Evans holds the chess title of U.S. National Master.

Wästlund’s MathOverflow question | My answer there

Let’s display here a few of the interesting positions.

First, a simple new position with value $\omega$.  The main line of play here calls for black to move his center rook up to arbitrary height, and then white slowly rolls the king into the rook for checkmate. For example, 1…Re10 2.Rf5+ Ke6 3.Qd5+ Ke7 4.Rf7+ Ke8 5.Qd7+ Ke9 6.Rf9#.  By playing the rook higher on the first move, black can force this main line of play have any desired finite length.  We have further variations with more black rooks and white king.

Value omega

Next, consider an infinite position with value $\omega^2$. The central black rook, currently attacked by a pawn, may be moved up by black arbitrarily high, where it will be captured by a white pawn, which opens a hole in the pawn column. White may systematically advance pawns below this hole in order eventually to free up the pieces at the bottom that release the mating material. But with each white pawn advance, black embarks on an arbitrarily long round of harassing checks on the white king.

Value omega squared

Here is a similar position with value $\omega^2$, which we call, “releasing the hordes”, since white aims ultimately to open the portcullis and release the queens into the mating chamber at right. The black rook ascends to arbitrary height, and white aims to advance pawns, but black embarks on arbitrarily long harassing check campaigns to delay each white pawn advance.

Releasing the hoards

Next, by iterating this idea, we produce a position with value $\omega^2\cdot 4$.  We have in effect a series of four such rook towers, where each one must be completed before the next is activated, using the “lock and key” concept explained in the paper.

Omega-squared-times-4

We can arrange the towers so that black may in effect choose how many rook towers come into play, and thus he can play to a position with value $\omega^2\cdot k$ for any desired $k$, making the position overall have value $\omega^3$.

Value omega cubed

Another interesting thing we noticed is that there is a computable position in infinite chess, such that in the category of computable play, it is a win for white—white has a computable strategy defeating any computable strategy of black—but in the category of arbitrary play, both players have a drawing strategy. Thus, our judgment of whether a position is a win or a draw depends on whether we insist that players play according to a deterministic computable procedure or not.

The basic idea for this is to have a computable tree with no computable infinite branch. When black plays computably, he will inevitably be trapped in a dead-end.

Infinite tree

In the paper, we conjecture that the omega one of chess is as large as it can possibly be, namely, the Church-Kleene ordinal $\omega_1^{CK}$ in the context of finite positions, and true $\omega_1$ in the context of all positions.

Our idea for proving this conjecture, unfortunately, does not quite fit into two-dimensional chess geometry, but we were able to make the idea work in infinite **three-dimensional** chess. In the last section of the article, we prove:

Theorem. Every countable ordinal arises as the game value of an infinite position of infinite three-dimensional chess. Thus, the omega one of infinite three dimensional chess is as large as it could possibly be, true $\omega_1$.

Here is a part of the position. Imagine the layers stacked atop each other, with $\alpha$ at the bottom and further layers below and above. The black king had entered at $\alpha$e4, was checked from below and has just moved to $\beta$e5. Pushing a pawn with check, white continues with 1.$\alpha$e4+ K$\gamma$e6 2.$\beta$e5+ K$\delta$e7 3.$\gamma$e6+ K$\epsilon$e8 4.$\delta$e7+, forcing black to climb the stairs (the pawn advance 1.$\alpha$e4+ was protected by a corresponding pawn below, since black had just been checked at $\alpha$e4).

Climbing the stairs

The overall argument works in higher dimensional chess, as well as three-dimensional chess that has only finite extent in the third dimension $\mathbb{Z}\times\mathbb{Z}\times k$, for $k$ above 25 or so.

A multiverse perspective on the axiom of constructiblity

Posted on by
19

[bibtex key=Hamkins2014:MultiverseOnVeqL]

This article expands on an argument that I made during my talk at the Asian Initiative for Infinity: Workshop on Infinity and Truth, held July 25–29, 2011 at the Institute for Mathematical Sciences, National University of Singapore, and will be included in a proceedings volume that is being prepared for that conference.

Abstract. I argue that the commonly held $V\neq L$ via maximize position, which rejects the axiom of constructibility $V=L$ on the basis that it is restrictive, implicitly takes a stand in the pluralist debate in the philosophy of set theory by presuming an absolute background concept of ordinal. The argument appears to lose its force, in contrast, on an upwardly extensible concept of set, in light of the various facts showing that models of set theory generally have extensions to models of $V=L$ inside larger set-theoretic universes.

In section two, I provide a few new criticisms of Maddy’s proposed concept of `restrictive’ theories, pointing out that her concept of fairly interpreted in is not a transitive relation: there is a first theory that is fairly interpreted in a second, which is fairly interpreted in a third, but the first is not fairly interpreted in the third.  The same example (and one can easily construct many similar natural examples) shows that neither the maximizes over relation, nor the properly maximizes over relation, nor the strongly maximizes over relation is transitive.  In addition, the theory ZFC + “there are unboundedly many inaccessible cardinals” comes out as formally restrictive, since it is strongly maximized by the theory ZF + “there is a measurable cardinal, with no worldly cardinals above it.”

To support the main philosophical thesis of the article, I survey a series of mathemtical results,  which reveal various senses in which the axiom of constructibility $V=L$ is compatible with strength in set theory, particularly if one has in mind the possibility of moving from one universe of set theory to a much larger one.  Among them are the following, which I prove or sketch in the article:

Observation. The constructible universe $L$ and $V$ agree on the consistency of any constructible theory. They have models of the same constructible theories.

Theorem. The constructible universe $L$ and $V$ have transitive models of exactly the same constructible theories in the language of set theory.

Corollary. (Levy-Shoenfield absoluteness theorem)  In particular, $L$ and $V$ satisfy the same $\Sigma_1$ sentences, with parameters hereditarily countable in $L$. Indeed, $L_{\omega_1^L}$ and $V$ satisfy the same such sentences.

Theorem. Every countable transitive set is a countable transitive set in the well-founded part of an $\omega$-model of V=L.

Theorem. If there are arbitrarily large $\lambda<\omega_1^L$ with $L_\lambda\models\text{ZFC}$, then every countable transitive set $M$ is a countable transitive set inside a structure $M^+$  that is a pointwise-definable model of ZFC + V=L, and $M^+$ is well founded as high in the countable ordinals as desired.

Theorem. (Barwise)  Every countable model of  ZF has an end-extension to a model of ZFC + V=L.

Theorem. (Hamkins, see here)  Every countable model of set theory $\langle M,{\in^M}\rangle$, including every transitive model, is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$. In other words,  there is an embedding $j:M\to L^M$, which is elementary for quantifier-free assertions.

Another way to say this is that every countable model of set theory is a submodel of a model isomorphic to $L^M$. If we lived inside $M$, then by adding new sets and elements, our universe could be transformed into a copy of the constructible universe $L^M$.

(Plus, the article contains some nice diagrams.)

Related Singapore links:

A question for the mathematics oracle

Posted on by
12

At the Workshop on Infinity and Truth in Singapore last year, we had a special session in which the speakers were asked to imagine that they had been granted an audience with an all-knowing mathematical oracle, given the opportunity to ask a single yes-or-no question, to be truthfully answered.  These questions will be gathered together and published in the conference volume.  Here is my account.

 

A question for the mathematics oracle

Joel David Hamkins, The City University of New York

 

Granted an audience with an all-knowing mathematics oracle, we may ask a single yes-or-no question, to be truthfully answered……

I might mischievously ask the question my six-year-old daughter Hypatia often puts to our visitors:  “Answer yes or no.  Will you answer `no’?” They stammer, caught in the liar paradox, as she giggles. But my actual question is:

Are we correct in thinking we have an absolute concept of the finite?

An absolute concept of the finite underlies many mathematician’s understanding of the nature of mathematical truth. Most mathematicians, for example, believe that we have an absolute concept of the finite, which determines the natural numbers as a unique mathematical structure—$0,1,2,$ and so on—in which arithmetic assertions have definitive truth values. We can prove after all that the second-order Peano axioms characterize $\langle\mathbb{N},S,0\rangle$ as the unique inductive structure, determined up to isomorphism by the fact that $0$ is not a successor, the successor function $S$ is one-to-one and every set containing $0$ and closed under $S$ is the whole of $\mathbb{N}$. And to be finite means simply to be equinumerous with a proper initial segment of this structure. Doesn’t this categoricity proof therefore settle the matter?

I don’t think so. The categoricity proof, which takes place in set theory, seems to my way of thinking merely to push the absoluteness question for finiteness off to the absoluteness question for sets instead. And surely this is a murkier realm, where already mathematicians do not universally agree that we have a single absolute background concept of set. We know by forcing and other means how to construct alternative set concepts, which seem fully as legitimate and set-theoretic as the set concepts from which they are derived. Thus, we have a plurality of set concepts, and our confidence in a unique absolute set-theoretic background is weakened. How then can we sensibly base our confidence in an absolute concept of the finite on set theory? Perhaps this absoluteness is altogether illusory.

My worries are put to rest if the oracle should answer positively. A negative answer, meanwhile, would raise alarms. A negative answer could indicate, on the one hand, that our understanding of the finite is simply incoherent, a catastrophe, where our cherished mathematical theories are all inconsistent. But, more likely in my view, a negative answer could also mean that there is an undiscovered plurality of concepts of the finite. I imagine technical developments arising that would provide us with tools to modify the arithmetic of a model of set theory, for example, with the same power and flexibility that forcing currently allows us to modify higher-order features, while not providing us with any reason to prefer one arithmetic to another (unlike our current methods with non-standard models). The discovery of such tools would be an amazing development in mathematics and lead to radical changes in our conception of mathematical truth.

Let’s have some fun—please post your question for the oracle in the comment fields below.

A question for the math oracle (pdf) | My talk at the Workshop

Moving up and down in the generic multiverse

Posted on by
3

[bibtex key=HamkinsLoewe2013:MovingUpAndDownInTheGenericMultiverse]

In this extended abstract we investigate the modal logic of the generic multiverse, which is a bimodal logic with operators corresponding to the relations “is a forcing extension of”‘ and “is a ground model of”. The fragment of the first relation is the modal logic of forcing and was studied by us in earlier work. The fragment of the second relation is the modal logic of grounds and will be studied here for the first time. In addition, we discuss which combinations of modal logics are possible for the two fragments.

The main theorems are as follows:

Theorem.  If  ZFC is consistent, then there is a model of  ZFC  whose modal logic of forcing and modal logic of grounds are both S4.2.

Theorem.  If  the theory “$L_\delta\prec L+\delta$ is inaccessible” is consistent, then there is a model of set theory whose modal logic of forcing is S4.2 and whose modal logic of grounds is S5.

Theorem.  If  the theory “$L_\delta\prec L+\delta$ is inaccessible” is consistent, then there is a model of set theory whose modal logic of forcing is S5 and whose modal logic of grounds is S4.2.

Theorem. There is no model of set theory such that both its modal logic of forcing and its modal logic of grounds are S5.

The current article is a brief extended abstract (10 pages).  A fuller account with more detailed proofs and further information will be provided in a subsequent articl

eprints:  ar$\chi$iv | NI12059-SAS | Hamburg #450

Structural connections between a forcing class and its modal logic

Posted on by
2

[bibtex key=HamkinsLeibmanLoewe2015:StructuralConnectionsForcingClassAndItsModalLogic]

The modal logic of forcing arises when one considers a model of set theory in the context of all its forcing extensions, interpreting $\square$ as “in all forcing extensions” and $\Diamond$ as “in some forcing extension”. In this modal language one may easily express sweeping general forcing principles, such as $\Diamond\square\varphi\to\square\Diamond\varphi$, the assertion that every possibly necessary statement is necessarily possible, which is valid for forcing, or $\Diamond\square\varphi\to\varphi$, the assertion that every possibly necessary statement is true, which is the maximality principle, a forcing axiom independent of but equiconsistent with ZFC (see A simple maximality principle).

Every definable forcing class similarly gives rise to the corresponding forcing modalities, for which one considers extensions only by forcing notions in that class. In previous work, we proved that if ZFC is consistent, then the ZFC-provably valid principles of the class of all forcing are precisely the assertions of the modal theory S4.2 (see The modal logic of forcing). In this article, we prove that the provably valid principles of collapse forcing, Cohen forcing and other classes are in each case exactly S4.3; the provably valid principles of c.c.c. forcing, proper forcing, and others are each contained within S4.3 and do not contain S4.2; the provably valid principles of countably closed forcing, CH-preserving forcing and others are each exactly S4.2; and the provably valid principles of $\omega_1$-preserving forcing are contained within S4.tBA. All these results arise from general structural connections we have identified between a forcing class and the modal logic of forcing to which it gives rise, including the connection between various control statements, such as buttons, switches and ratchets, and their corresponding forcing validities. These structural connections therefore support a forcing-only analysis of other diverse forcing classes.

Preprints available at:  ar$\chi$iv | NI12055-SAS | UvA ILLC PP-2012-19 | HBM 446

Every countable model of set theory embeds into its own constructible universe

Posted on by
19

[bibtex key=Hamkins2013:EveryCountableModelOfSetTheoryEmbedsIntoItsOwnL]

In this article, I prove that every countable model of set theory $\langle M,{\in^M}\rangle$, including every well-founded model, is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$. Another way to say this is that there is an embedding
$$j:\langle M,{\in^M}\rangle\to \langle L^M,{\in^M}\rangle$$
that is elementary for quantifier-free assertions in the language of set theory.

Main Theorem 1. Every countable model of set theory $\langle M,{\in^M}\rangle$ is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$.

The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading eventually to what I call the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, which is closely connected with the surreal numbers. The proof shows that $\langle L^M,{\in^M}\rangle$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$, and so in fact this model is universal for all countable acyclic binary relations of this rank. When $M$ is ill-founded, this includes all acyclic binary relations. The method of proof also establishes the following, thereby answering a question posed by Ewan Delanoy.

Main Theorem 2. The countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory $\langle M,{\in^M}\rangle$ and $\langle N,{\in^N}\rangle$, either $M$ is isomorphic to a submodel of $N$ or conversely. Indeed, the countable models of set theory are pre-well-ordered by embeddability in order type exactly $\omega_1+1$.

The proof shows that the embeddability relation on the models of set theory conforms with their ordinal heights, in that any two models with the same ordinals are bi-embeddable; any shorter model embeds into any taller model; and the ill-founded models are all bi-embeddable and universal.

The proof method arises most easily in finite set theory, showing that the nonstandard hereditarily finite sets $\text{HF}^M$ coded in any nonstandard model $M$ of PA or even of $I\Delta_0$ are similarly universal for all acyclic binary relations. This strengthens a classical theorem of Ressayre, while simplifying the proof, replacing a partial saturation and resplendency argument with a soft appeal to graph universality.

Main Theorem 3. If $M$ is any nonstandard model of PA, then every countable model of set theory is isomorphic to a submodel of the hereditarily finite sets $\langle \text{HF}^M,{\in^M}\rangle$ of $M$. Indeed, $\langle\text{HF}^M,{\in^M}\rangle$ is universal for all countable acyclic binary relations.

In particular, every countable model of ZFC and even of ZFC plus large cardinals arises as a submodel of $\langle\text{HF}^M,{\in^M}\rangle$. Thus, inside any nonstandard model of finite set theory, we may cast out some of the finite sets and thereby arrive at a copy of any desired model of infinite set theory, having infinite sets, uncountable sets or even large cardinals of whatever type we like.

The proof, in brief:  for every countable acyclic digraph, consider the partial order induced by the edge relation, and extend this order to a total order, which may be embedded in the rational order $\mathbb{Q}$.  Thus, every countable acyclic digraph admits a $\mathbb{Q}$-grading, an assignmment of rational numbers to nodes such that all edges point upwards. Next, one can build a countable homogeneous, universal, existentially closed $\mathbb{Q}$-graded digraph, simply by starting with nothing, and then adding finitely many nodes at each stage, so as to realize the finite pattern property. The result is a computable presentation of what I call the countable random $\mathbb{Q}$-graded digraph $\Gamma$.  If $M$ is any nonstandard model of finite set theory, then we may run this computable construction inside $M$ for a nonstandard number of steps.  The standard part of this nonstandard finite graph includes a copy of $\Gamma$.  Furthermore, since $M$ thinks it is finite and acyclic, it can perform a modified Mostowski collapse to realize the graph in the hereditary finite sets of $M$.  By looking at the sets corresponding to the nodes in the copy of $\Gamma$, we find a submodel of $M$ that is isomorphic to $\Gamma$, which is universal for all countable acyclic binary relations. So every model of ZFC isomorphic to a submodel of $M$.

The article closes with a number of questions, which I record here (and which I have also asked on mathoverflow:  Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?) Although the main theorem shows that every countable model of set theory embeds into its own constructible universe  $$j:M\to L^M,$$ this embedding $j$ is constructed completely externally to $M$ and there is little reason to expect that $j$ could be a class in $M$ or otherwise amenable to $M$.  To what extent can we prove or refute the possibility that $j$ is a class in $M$? This amounts to considering the matter internally as a question about $V$. Surely it would seem strange to have a class embedding $j:V\to L$ when $V\neq L$, even if it is elementary only for quantifier-free assertions, since such an embedding is totally unlike the sorts of embeddings that one usually encounters in set theory. Nevertheless, I am at a loss to refute the hypothesis, and the possibility that there might be such an embedding is intriguing, if not tantalizing, for one imagines all kinds of constructions that pull structure from $L$ back into $V$.

Question 1.  Can there be an embedding $j:V\to L$ when $V\neq L$?

By embedding, I mean an isomorphism from $\langle V,{\in}\rangle$ to its range in $\langle L,{\in}\rangle$, which is the same as a quantifier-free-elementary map $j:V\to L$. The question is most naturally formalized in Gödel-Bernays set theory, asking whether there can be a GB-class $j$ forming such an embedding.  If one wants $j:V\to L$ to be a definable class, then this of course implies $V=\text{HOD}$, since the definable $L$-order can be pulled back to $V$, via $x\leq y\iff j(s)\leq_L j(y)$. More generally, if $j$ is merely a class in Gödel-Bernays set theory, then the existence of an embedding $j:V\to L$ implies global choice, since from the class $j$ we can pull back the $L$-order. For these reasons, we cannot expect every model of ZFC or of GB to have such embeddings. Can they be added generically? Do they have some large cardinal strength? Are they outright refutable?

It they are not outright refutable, then it would seem natural that these questions might involve large cardinals; perhaps $0^\sharp$ is relevant. But I am unsure which way the answers will go. The existence of large cardinals provides extra strength, but may at the same time make it harder to have the embedding, since it pushes $V$ further away from $L$. For example, it is conceivable that the existence of $0^\sharp$ will enable one to construct the embedding, using the Silver indiscernibles to find a universal submodel of $L$; but it is also conceivable that the non-existence of $0^\sharp$, because of covering and the corresponding essential closeness of $V$ to $L$, may make it easier for such a $j$ to exist. Or perhaps it is simply refutable in any case. The first-order analogue of the question is:

Question 2.  Does every set $A$ admit an embedding $j:\langle A,{\in}\rangle \to \langle L,{\in}\rangle$?  If not, which sets do admit such embeddings?

The main theorem shows that every countable set $A$ embeds into $L$. What about uncountable sets? Let us make the question extremely concrete:

Question 3. Does $\langle V_{\omega+1},{\in}\rangle$ embed into $\langle L,{\in}\rangle$? How about $\langle P(\omega),{\in}\rangle$ or $\langle\text{HC},{\in}\rangle$?

It is also natural to inquire about the nature of $j:M\to L^M$ even when it is not a class in $M$. For example, can one find such an embedding for which $j(\alpha)$ is an ordinal whenever $\alpha$ is an ordinal?  The embedding arising in the proof of the main theorem definitely does not have this feature.

Question 4. Does every countable model $\langle M,{\in^M}\rangle$ of set theory admit an embedding $j:M\to L^M$ that takes ordinals to ordinals?

Probably one can arrange this simply by being a bit more careful with the modified Mostowski procedure in the proof of the main theorem.  And if this is correct, then numerous further questions immediately come to mind, concerning the extent to which we ensure more attractive features for the embeddings $j$ that arise in the main theorems. This will be particularly interesting in the case of well-founded models, as well as in the case of $j:V\to L$, as in question , if that should be possible.

Question 5. Can there be a nontrivial embedding $j:V\to L$ that takes ordinals to ordinals?

Finally, I inquire about the extent to which the main theorems of the article can be extended from the countable models of set theory to the $\omega_1$-like models:

Question 6. Does every $\omega_1$-like model of set theory $\langle M,{\in^M}\rangle$ admit an embedding $j:M\to L^M$ into its own constructible universe? Are the $\omega_1$-like models of set theory linearly pre-ordered by embeddability?

Singular cardinals and strong extenders

Posted on by
Reply

[bibtex key=ApterCummingsHamkins2013:SingularCardinalsAndStrongExtenders]

Brent Cody asked the question whether the situation can arise that one has an elementary embedding $j:V\to M$ witnessing the $\theta$-strongness of a cardinal $\kappa$, but where $\theta$ is regular in $M$ and singular in $V$.

In this article, we investigate the various circumstances in which this does and does not happen, the circumstances under which there exist a singular cardinal $\mu$ and a short $(\kappa, \mu)$-extender $E$ witnessing “$\kappa$ is $\mu$-strong”, such that $\mu$ is singular in $Ult(V, E)$.

Is the dream solution of the continuum hypothesis attainable?

Posted on by
3

[bibtex key=Hamkins2015:IsTheDreamSolutionToTheContinuumHypothesisAttainable]

Many set theorists yearn for a definitive solution of the continuum problem, what I call a  dream solution, one by which we settle the continuum hypothesis (CH) on the basis of a new fundamental principle of set theory, a missing axiom, widely regarded as true, which determines the truth value of CH.  In an earlier article, I have described the dream solution template as proceeding in two steps: first, one introduces the new set-theoretic principle, considered obviously true for sets in the same way that many mathematicians find the axiom of choice or the axiom of replacement to be true; and second, one proves the CH or its negation from this new axiom and the other axioms of set theory. Such a situation would resemble Zermelo’s proof of the ponderous well-order principle on the basis of the comparatively natural axiom of choice and the other Zermelo axioms. If achieved, a dream solution to the continuum problem would be remarkable, a cause for celebration.

In this article, however, I argue that a dream solution of CH has become impossible to achieve. Specifically, what I claim is that our extensive experience in the set-theoretic worlds in which CH is true and others in which CH is false prevents us from looking upon any statement settling CH as being obviously true. We simply have had too much experience by now with the contrary situation. Even if set theorists initially find a proposed new principle to be a natural, obvious truth, nevertheless once it is learned that the principle settles CH, then this preliminary judgement will evaporate in the face of deep experience with the contrary, and set-theorists will look upon the statement merely as an intriguing generalization or curious formulation of CH or $\neg$CH, rather than as a new fundamental truth. In short, success in the second step of the dream solution will inevitably undermine success in the first step.

This article is based upon an argument I gave during the course of a three-lecture tutorial on set-theoretic geology at the summer school Set Theory and Higher-Order Logic: Foundational Issues and Mathematical Development, at the University of London, Birkbeck in August 2011.  Much of the article is adapted from and expands upon the corresponding section of material in my article The set-theoretic multiverse.

The mate-in-n problem of infinite chess is decidable

Posted on by
15

[bibtex key=BrumleveHamkinsSchlicht2012:TheMateInNProblemOfInfiniteChessIsDecidable]

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers—*there is a move for white, such that for every black reply, there is a countermove for white*, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth.

Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\frak{Ch}}$ is not known.

Richard Stanley’s question on mathoverflow: Decidability of chess on infinite board?

Inner models with large cardinal features usually obtained by forcing

Posted on by
1

[bibtex key=ApterGitmanHamkins2012:InnerModelsWithLargeCardinals]

We construct a variety of inner models exhibiting features usually obtained by forcing over universes with large cardinals. For example, if there is a supercompact cardinal, then there is an inner model with a Laver indestructible supercompact cardinal. If there is a supercompact cardinal, then there is an inner model with a supercompact cardinal $\kappa$ for which $2^\kappa=\kappa^+$, another for which $2^\kappa=\kappa^{++}$ and another in which the least strongly compact cardinal is supercompact. If there is a strongly compact cardinal, then there is an inner model with a strongly compact cardinal, for which the measurable cardinals are bounded below it and another inner model $W$ with a strongly compact cardinal $\kappa$, such that $H_{\kappa^+}^V\subseteq HOD^W$. Similar facts hold for supercompact, measurable and strongly Ramsey cardinals. If a cardinal is supercompact up to a weakly iterable cardinal, then there is an inner model of the Proper Forcing Axiom and another inner model with a supercompact cardinal in which GCH+V=HOD holds. Under the same hypothesis, there is an inner model with level by level equivalence between strong compactness and supercompactness, and indeed, another in which there is level by level inequivalence between strong compactness and supercompactness. If a cardinal is strongly compact up to a weakly iterable cardinal, then there is an inner model in which the least measurable cardinal is strongly compact. If there is a weakly iterable limit $\delta$ of ${\lt}\delta$-supercompact cardinals, then there is an inner model with a proper class of Laver-indestructible supercompact cardinals. We describe three general proof methods, which can be used to prove many similar results.

What is the theory ZFC without power set?

Posted on by
7

[bibtex key=”GitmanHamkinsJohnstone2016:WhatIsTheTheoryZFC-Powerset?”]

This is joint work with Victoria Gitman and Thomas Johnstone.

We show that the theory ZFC-, consisting of the usual axioms of ZFC but with the power set axiom removed-specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well-ordered-is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context. For example, there are models of ZFC- in which $\omega_1$ is singular, in which every set of reals is countable, yet $\omega_1$ exists, in which there are sets of reals of every size $\aleph_n$, but none of size $\aleph_\omega$, and therefore, in which the collection axiom sceme fails; there are models of ZFC- for which the Los theorem fails, even when the ultrapower is well-founded and the measure exists inside the model; there are models of ZFC- for which the Gaifman theorem fails, in that there is an embedding $j:M\to N$ of ZFC- models that is $\Sigma_1$-elementary and cofinal, but not elementary; there are elementary embeddings $j:M\to N$ of ZFC- models whose cofinal restriction $j:M\to \bigcup j“M$ is not elementary. Moreover, the collection of formulas that are provably equivalent in ZFC- to a $\Sigma_1$-formula or a $\Pi_1$-formula is not closed under bounded quantification. Nevertheless, these deficits of ZFC- are completely repaired by strengthening it to the theory $\text{ZFC}^-$, obtained by using collection rather than replacement in the axiomatization above. These results extend prior work of Zarach.

See Victoria Gitman’s summary post on the article