A position in infinite chess with game value $\omega^4$

  • C.~D.~A.~Evans, J. D. Hamkins, and N. L. Perlmutter, “A position in infinite chess with game value $\omega^4$,” to appear in Integers, vol. 17, 2017. (Newton Institute preprint ni15065)  
    @ARTICLE{EvansHamkinsPerlmutter:APositionInInfiniteChessWithGameValueOmega^4,
    author = {C.~D.~A.~Evans and Joel David Hamkins and Norman Lewis Perlmutter},
    title = {A position in infinite chess with game value $\omega^4$},
    journal = {to appear in Integers},
    FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
    year = {2017},
    volume = {17},
    number = {},
    pages = {},
    eprint = {1510.08155},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/a-position-in-infinite-chess-with-game-value-omega-to-the-4},
    month = {},
    note = {Newton Institute preprint ni15065},
    abstract = {},
    keywords = {},
    source = {},
    }

Abstract.  We present a position in infinite chess exhibiting an ordinal game value of $\omega^4$, thereby improving on the previously largest-known values of $\omega^3$ and $\omega^3\cdot 4$.

This is a joint work with Cory Evans and Norman Perlmutter, continuing the research program of my previous article with Evans, Transfinite game values in infinite chess, namely, the research program of finding positions in infinite chess with large transfinite ordinal game values. In the previous article, Cory and I presented a position with game value $\omega^3$. In the current paper, with Norman Perlmutter now having joined us accompanied by some outstanding ideas, we present a new position having game value $\omega^4$, breaking the previous record.

Full position value omega^4

A position in infinite chess with value $\omega^4$

In the new position, above, the kings sit facing each other in the throne room, an uneasy détente, while white makes steady progress in the rook towers. Meanwhile, at every step black, doomed, mounts increasingly desperate bouts of long forced play using the bishop cannon battery, with bishops flying with force out of the cannons, and then each making a long series of forced-reply moves in the terminal gateways. Ultimately, white wins with value omega^4, which exceeds the previously largest known values of omega^3.

In the throne room, if either black or white places a bishop on the corresponding diagonal entryway, then checkmate is very close. A key feature is that for white to place a white-square white bishop on the diagonal marked in red, it is immediate checkmate, whereas if black places a black-square black bishop on the blue diagonal, then checkmate comes three moves later.  The bishop cannon battery arrangement works because black threatens to release a bishop into the free region, and if white does not reply to those threats, then black will be three steps ahead, but otherwise, only two.

           The throne room

The rook towers are similar to the corresponding part of the previous $\omega^3$ position, and this is where white undertakes most of his main line progress towards checkmate.  Black will move the key bishop out as far as he likes on the first move, past $n$ rook towers, and the resulting position will have value $\omega^3\cdot n$.  These towers are each activated in turn, leading to a long series of play for white, interrupted at every opportunity by black causing a dramatic spectacle of forced-reply moves down in the bishop cannon battery.

Rook towers

            The rook towers

At every opportunity, black mounts a long distraction down in the bishop cannon battery.  Shown here is one bishop cannon. The cannonballs fire out of the cannon with force, in the sense that when each green bishop fires out, then white must reply by moving the guard pawns into place.

Bishop cannon

Bishop cannon

Upon firing, each bishop will position itself so as to attack the entrance diagonal of a long bishop gateway terminal wing.  This wing is arranged so that black can make a series of forced-reply threats successively, by moving to the attack squares (marked with the blue squares). Black is threatening to exit through the gateway doorway (in brown), but white can answer the threat by moving the white bishop guards (red) into position. Thus, each bishop coming out of a cannon (with force) can position itself at a gateway terminal of length $g$, making $g$ forced-reply moves in succession.  Since black can initiate firing with an arbitrarily large cannon, this means that at any moment, black can cause a forced-reply delay with game value $\omega^2$. Since the rook tower also has value $\omega^2$ by itself, the overall position has value $\omega^4=\omega^2\cdot\omega^2$.

Bishop gateway terminal wing

With future developments in mind, we found that one can make a more compact arrangement of the bishop cannon battery, freeing up a quarter board for perhaps another arrangement that might lead to a higher ordinal values.

Alternative compact version of bishop cannon battery

 

Read more about it in the article, which is available at the arxiv (pdf).

 

See also:

Open determinacy for class games

  • V. Gitman and J. D. Hamkins, “Open determinacy for class games,” in Foundations of Mathematics, Logic at Harvard, Essays in Honor of Hugh Woodin’s 60th Birthday, A. E. Caicedo, J. Cummings, P. Koellner, and P. Larson, Eds., American Mathematical Society, 2016. (also available as Newton Institute preprint ni15064)  
    @INCOLLECTION{GitmanHamkins2016:OpenDeterminacyForClassGames,
    author = {Victoria Gitman and Joel David Hamkins},
    title = {Open determinacy for class games},
    booktitle = {Foundations of Mathematics, Logic at Harvard, Essays in Honor of Hugh Woodin's 60th Birthday},
    publisher = {American Mathematical Society},
    year = {2016},
    editor = {Andr\'es E. Caicedo and James Cummings and Peter Koellner and Paul Larson},
    volume = {},
    number = {},
    series = {Contemporary Mathematics},
    type = {},
    chapter = {},
    pages = {},
    address = {},
    edition = {},
    month = {},
    note = {also available as Newton Institute preprint ni15064},
    url = {http://jdh.hamkins.org/open-determinacy-for-class-games},
    eprint = {1509.01099},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    abstract = {},
    keywords = {},
    }

Abstract. The principle of open determinacy for class games — two-player games of perfect information with plays of length $\omega$, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Godel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates $\text{Tr}_\alpha$ for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of transfinite recursion over well-founded class relations. Meanwhile, the principle of open determinacy for class games is provable in the stronger theory GBC$+\Pi^1_1$-comprehension, a proper fragment of Kelley-Morse set theory KM.

See my earlier posts on part of this material:

 

A mathematician’s year in Japan

  • J. D. Hamkins, A Mathematician’s Year in Japan, author-published, via Amazon Kindle Direct Publishing, 2015. (ASIN:B00U618LM2, 156 pages, http://www.amazon.com/dp/B00U618LM2)  
    @BOOK{Hamkins2015:AMathematiciansYearInJapan,
    author = {Joel David Hamkins},
    title = {A {Mathematician's} {Year} in {Japan}},
    publisher = {author-published, via Amazon Kindle Direct Publishing},
    year = {2015},
    month = {March},
    url = {http://www.amazon.com/dp/B00U618LM2},
    note = {ASIN:B00U618LM2, 156 pages, http://www.amazon.com/dp/B00U618LM2},
    }

Years ago, when I was still a junior professor, I had the pleasure to live for a year in Japan, working as a research fellow at Kobe University. During that formative year, I recorded brief moments of my Japanese experience, and every two weeks or so—this was well before the current blogging era—I sent my descriptive missives by email to friends back home. I have now collected together those vignettes of my life in Japan, each a morsel of my experience. The book is now out!


A Mathematician's Year in Japan, by Joel David Hamkins, available on Amazon Kindle BooksA Mathematician’s Year in Japan
Joel David Hamkins

Glimpse into the life of a professor of logic as he fumbles his way through Japan.

A Mathematician’s Year in Japan is a lighthearted, though at times emotional account of how one mathematician finds himself in a place where everything seems unfamiliar, except his beloved research on the nature of infinity, yet even with that he experiences a crisis.

Available on Amazon $4.49.

Please be so kind as to write a review there.
jo eh ru

Ehrenfeucht's lemma in set theory

  • G. Fuchs, V. Gitman, and J. D. Hamkins, “Ehrenfeucht’s lemma in set theory,” to appear in Notre Dame Journal of Formal Logic.  
    @ARTICLE{FuchsGitmanHamkins:EhrenfeuchtsLemmaInSetTheory,
    author = {Gunter Fuchs and Victoria Gitman and Joel David Hamkins},
    title = {Ehrenfeucht's lemma in set theory},
    journal = {to appear in Notre Dame Journal of Formal Logic},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    eprint = {1501.01918},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    note = {},
    url = {http://jdh.hamkins.org/ehrenfeuchts-lemma-in-set-theory},
    abstract = {},
    keywords = {},
    source = {},
    }

This is joint work with Gunter Fuchs and Victoria Gitman. $\newcommand\HOD{\text{HOD}}\newcommand\Ehrenfeucht{\text{EL}}$

Abstract. Ehrenfeucht’s lemma asserts that whenever one element of a model of Peano arithmetic is definable from another, then they satisfy different types. We consider here the analogue of Ehrenfeucht’s lemma for models of set theory. The original argument applies directly to the ordinal-definable elements of any model of set theory, and in particular, Ehrenfeucht’s lemma holds fully for models of set theory satisfying $V=\HOD$. We show that the lemma can fail, however, in models of set theory with $V\neq\HOD$, and it necessarily fails in the forcing extension to add a generic Cohen real. We go on to formulate a scheme of natural parametric generalizations of Ehrenfeucht’s lemma, namely, the principles of the form $\Ehrenfeucht(A,P,Q)$, which asserts that whenever an object $b$ is definable in $M$ from some $a\in A$ using parameters in $P$, with $b\neq a$, then the types of $a$ and $b$ over $Q$ in $M$ are different. We also consider various analogues of Ehrenfeucht’s lemma obtained by using algebraicity in place of definability, where a set $b$ is \emph{algebraic} in $a$ if it is a member of a finite set definable from $a$ (as in J. D. Hamkins and C. Leahy, Algebraicity and implicit definability in set theory). Ehrenfeucht’s lemma holds for the ordinal-algebraic sets, we prove, if and only if the ordinal-algebraic and ordinal-definable sets coincide. Using similar analysis, we answer two open questions posed in my paper with Leahy, by showing that (i) algebraicity and definability need not coincide in models of set theory and (ii) the internal and external notions of being ordinal algebraic need not coincide.

Incomparable $\omega_1$-like models of set theory

  • G. Fuchs, V. Gitman, and J. D. Hamkins, “Incomparable ω1-like models of set theory,” Mathematical Logic Quarterly, pp. 1-11, 2017.  
    @article {FuchsGitmanHamkins2017:IncomparableOmega1-likeModelsOfSetTheory,
    author = {Fuchs, Gunter and Gitman, Victoria and Hamkins, Joel David},
    title = {Incomparable ω1-like models of set theory},
    journal = {Mathematical Logic Quarterly},
    issn = {1521-3870},
    url = {http://dx.doi.org/10.1002/malq.201500002},
    doi = {10.1002/malq.201500002},
    pages = {1--11},
    year = {2017},
    month = {March},
    eprint = {1501.01022},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/incomparable-omega-one-like-models-of-set-theory},
    }

This is joint work with Gunter Fuchs and Victoria Gitman.

Abstract. We show that the analogues of the Hamkins embedding theorems, proved for the countable models of set theory, do not hold when extended to the uncountable realm of $\omega_1$-like models of set theory. Specifically, under the $\diamondsuit$ hypothesis and suitable consistency assumptions, we show that there is a family of $2^{\omega_1}$ many $\omega_1$-like models of $\text{ZFC}$, all with the same ordinals, that are pairwise incomparable under embeddability; there can be a transitive $\omega_1$-like model of ZFC that does not embed into its own constructible universe; and there can be an $\omega_1$-like model of PA whose structure of hereditarily finite sets is not universal for the $\omega_1$-like models of set theory.

In this article, we consider the question of whether the embedding theorems of my article, Every countable model of set theory embeds into its own constructible universe, which concern the countable models of set theory, might extend to the realm of uncountable models. Specifically, in that paper I had proved that (1) any two countable models of set theory are comparable by embeddability; indeed, (2) one countable model of set theory embeds into another just in case the ordinals of the first order-embed into the ordinals of the second; consequently, (3) every countable model of set theory embeds into its own constructible universe; and furthermore, (4) every countable model of set theory embeds into the hereditarily finite sets $\langle\text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{PA}$. The question we consider here is, do the analogous results hold for uncountable models? Our answer is that they do not. Indeed, we shall prove that the corresponding statements do not hold even in the special case of $\omega_1$-like models of set theory, which otherwise among uncountable models often exhibit a special affinity with the countable models. Specifically, we shall construct large families of pairwise incomparable $\omega_1$-like models of set theory, even though they all have the same ordinals; we shall construct $\omega_1$-like models of set theory that do not embed into their own $L$; and we shall construct $\omega_1$-like models of \PA\ that are not universal for all $\omega_1$-like models of set theory.

The embedding theorems are expressed collectively in the theorem below. An embedding of one model $\langle M,{\in^M}\rangle$ of set theory into another $\langle N,{\in^N}\rangle$ is simply a function $j:M\to N$ for which $x\in^My\longleftrightarrow j(x)\in^Nj(y)$, for all $x,y\in M$, and in this case we say that $\langle M,{\in^M}\rangle$ embeds into $\langle N,{\in^N}\rangle$; note by extensionality that every embedding is injective. Thus, an embedding is simply an isomorphism of $\langle M,{\in^M}\rangle$ with its range, which is a submodel of $\langle N,{\in^N}\rangle$. Although this is the usual model-theoretic embedding concept for relational structures, the reader should note that it is a considerably weaker embedding concept than commonly encountered in set theory, because this kind of embedding need not be elementary nor even $\Delta_0$-elementary, although clearly every embedding as just defined is elementary at least for quantifier-free assertions. So we caution the reader not to assume a greater degree of elementarity beyond quantifier-free elementarity for the embeddings appearing in this paper.

Theorem.

1. For any two countable models of set theory $\langle M,\in^M\rangle$ and $\langle N,\in^N\rangle$, one of them embeds into the other.

2. Indeed, such an $\langle M,{\in^M}\rangle$ embeds into $\langle N,{\in^N}\rangle$ if and only if the ordinals of $M$ order-embed into the ordinals of $N$.

3. Consequently, every countable model $\langle M,\in^M\rangle$ of set theory embeds into its own constructible universe $\langle L^M,\in^M\rangle$.

4. Furthermore, every countable model of set theory embeds into the hereditary finite sets $\langle \text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{PA}$. Indeed, $\text{HF}^M$ is universal for all countable acyclic binary relations.

One can begin to get an appreciation for the difference in embedding concepts by observing that ZFC proves that there is a nontrivial embedding $j:V\to V$, namely, the embedding recursively defined as follows $$j(y)=\bigl\{\ j(x)\ \mid\ x\in y\ \bigr\}\cup\bigl\{\{\emptyset,y\}\bigr\}.$$

We leave it as a fun exercise to verify that $x\in y\longleftrightarrow j(x)\in j(y)$ for the embedding $j$ defined by this recursion. (See my paper Every countable model of set theory embeds into its own constructible universe; but to give a hint here for the impatient, note that every $j(y)$ is nonempty and also $\emptyset\notin j(y)$; it follows that inside $j(y)$ we may identify the pair $\{\emptyset,y\}\in j(y)$; it follows that $j$ is injective and furthermore, the only way to have $j(x)\in j(y)$ is from $x\in y$.} Contrast this situation with the well-known Kunen inconsistency, which asserts that there can be no nontrivial $\Sigma_1$-elementary embedding $j:V\to V$. Similarly, the same recursive definition applied in $L$ leads to nontrivial embeddings $j:L\to L$, regardless of whether $0^\sharp$ exists. But again, the point is that embeddings are not necessarily even $\Delta_0$-elementary, and the familiar equivalence of the existence of $0^\sharp$ with a nontrivial “embedding” $j:L\to L$ actually requires a $\Delta_0$-elementary embedding.)

We find it interesting to note in contrast to the theorem above that there is no such embedding phenomenon in the the context of the countable models of Peano arithmetic (where an embedding of models of arithmetic is a function preserving all atomic formulas in the language of arithmetic). Perhaps the main reason for this is that embeddings between models of PA are automatically $\Delta_0$-elementary, as a consequence of the MRDP theorem, whereas this is not true for models of set theory, as the example above of the recursively defined embedding $j:V\to V$ shows, since this is an embedding, but it is not $\Delta_0$-elementary, in light of $j(\emptyset)\neq\emptyset$. For countable models of arithmetic $M,N\models\text{PA}$, one can show that there is an embedding $j:M\to N$ if and only if $N$ satisfies the $\Sigma_1$-theory of $M$ and the standard system of $M$ is contained in the standard system of $N$. It follows that there are many instances of incomparability. Meanwhile, it is a consequence of statement (4) that the embedding phenomenon recurs with the countable models of finite set theory $\text{ZFC}^{\neg\infty}$, that is, with $\langle\text{HF},{\in}\rangle^M$ for $M\models\text{PA}$, since all nonstandard such models are universal for all countable acyclic binary relations, and so in the context of countable models of $\text{ZFC}^{\neg\infty}$ there are precisely two bi-embeddability classes, namely, the standard model, which is initial, and the nonstandard countable models, which are universal.

Our main theorems are as follows.

Theorem.

1. If $\diamondsuit$ holds and ZFC is consistent, then there is a family $\mathcal C$ of $2^{\omega_1}$ many pairwise incomparable $\omega_1$-like models of ZFC, meaning that there is no embedding between any two distinct models in $\mathcal C$.

2. The models in statement (1) can be constructed so that their ordinals order-embed into each other and indeed, so that the ordinals of each model is a universal $\omega_1$-like linear order. If ZFC has an $\omega$-model, then the models of statement (1) can be constructed so as to have precisely the same ordinals.

3. If $\diamondsuit$ holds and ZFC is consistent, then there is an $\omega_1$-like model $M\models\text{ZFC}$ and an $\omega_1$-like model $N\models\text{PA}$ such that $M$ does not embed into $\langle\text{HF},{\in}\rangle^N$.

4. If there is a Mahlo cardinal, then in a forcing extension of $L$, there is a transitive $\omega_1$-like model $M\models\text{ZFC}$ that does not embed into its own constructible universe $L^M$.

Note that the size of the family $\mathcal C$ in statement (1) is as large as it could possibly be, given that any two elements in a pairwise incomparable family of structures must be non-isomorphic and there are at most $2^{\omega_1}$ many isomorphism types of $\omega_1$-like models of set theory or indeed of structures of size $\omega_1$ in any first-order finite language. Statement (2) shows that the models of the family $\mathcal C$ serve as $\omega_1$-like counterexamples to the assertion that one model of set theory embeds into another whenever the ordinals of the first order-embed into the ordinals of the second.

Large cardinals need not be large in HOD

  • Y. Cheng, S. Friedman, and J. D. Hamkins, “Large cardinals need not be large in HOD,” Annals of Pure and Applied Logic, vol. 166, iss. 11, pp. 1186-1198, 2015.  
    @ARTICLE{ChengFriedmanHamkins2015:LargeCardinalsNeedNotBeLargeInHOD,
    title = "Large cardinals need not be large in {HOD} ",
    journal = "Annals of Pure and Applied Logic ",
    volume = "166",
    number = "11",
    pages = "1186 - 1198",
    year = "2015",
    note = "",
    issn = "0168-0072",
    doi = "10.1016/j.apal.2015.07.004",
    eprint = {1407.6335},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/large-cardinals-need-not-be-large-in-hod},
    author = "Yong Cheng and Sy-David Friedman and Joel David Hamkins",
    keywords = "Large cardinals",
    keywords = "HOD",
    keywords = "Forcing",
    keywords = "Absoluteness ",
    abstract = "Abstract We prove that large cardinals need not generally exhibit their large cardinal nature in HOD. For example, a supercompact cardinal κ need not be weakly compact in HOD, and there can be a proper class of supercompact cardinals in V, none of them weakly compact in HOD, with no supercompact cardinals in HOD. Similar results hold for many other types of large cardinals, such as measurable and strong cardinals. "
    }

Abstract. We prove that large cardinals need not generally exhibit their large cardinal nature in HOD. For example, a supercompact cardinal $\kappa$ need not be weakly compact in HOD, and there can be a proper class of supercompact cardinals in $V$, none of them weakly compact in HOD, with no supercompact cardinals in HOD. Similar results hold for many other types of large cardinals, such as measurable and strong cardinals.

In this article, we prove that large cardinals need not generally exhibit their large cardinal nature in HOD, the inner model of hereditarily ordinal-definable sets, and there can be a divergence in strength between the large cardinals of the ambient set-theoretic universe $V$ and those of HOD. Our general theme concerns the questions:

Questions.

1. To what extent must a large cardinal in $V$ exhibit its large cardinal properties in HOD?

2. To what extent does the existence of large cardinals in $V$ imply the existence of large cardinals in HOD?

For large cardinal concepts beyond the weakest notions, we prove, the answers are generally negative. In Theorem 4, for example, we construct a model with a supercompact cardinal that is not weakly compact in HOD, and Theorem 9 extends this to a proper class of supercompact cardinals, none of which is weakly compact in HOD, thereby providing some strongly negative instances of (1). The same model has a proper class of supercompact cardinals, but no supercompact cardinals in HOD, providing a negative instance of (2). The natural common strengthening of these situations would be a model with a proper class of supercompact cardinals, but no weakly compact cardinals in HOD. We were not able to arrange that situation, however, and furthermore it would be ruled out by Conjecture 13, an intriguing positive instance of (2) recently proposed by W. Hugh Woodin, namely, that if there is a supercompact cardinal, then there is a measurable cardinal in HOD. Many other natural possibilities, such as a proper class of measurable cardinals with no weakly compact cardinals in HOD, remain as open questions.

CUNY talkRutgers talk | Luminy talk

Strongly uplifting cardinals and the boldface resurrection axioms

  • J. D. Hamkins and T. Johnstone, “Strongly uplifting cardinals and the boldface resurrection axioms,” Archive for Mathematical Logic, vol. 56, iss. 7, pp. 1115-1133, 2017.  
    @ARTICLE{HamkinsJohnstone2017:StronglyUpliftingCardinalsAndBoldfaceResurrection,
    author = {Joel David Hamkins and Thomas Johnstone},
    title = {Strongly uplifting cardinals and the boldface resurrection axioms},
    journal="Archive for Mathematical Logic",
    year="2017",
    month="Nov",
    day="01",
    volume="56",
    number="7",
    pages="1115--1133",
    eprint = {1403.2788},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    issn="1432-0665",
    doi="10.1007/s00153-017-0542-y",
    url = {http://jdh.hamkins.org/strongly-uplifting-cardinals-and-boldface-resurrection},
    abstract="We introduce the strongly uplifting cardinals, which are equivalently characterized, we prove, as the superstrongly unfoldable cardinals and also as the almost-hugely unfoldable cardinals, and we show that their existence is equiconsistent over ZFC with natural instances of the boldface resurrection axiom, such as the boldface resurrection axiom for proper forcing.",
    keywords = {},
    source = {},
    }

Abstract. We introduce the strongly uplifting cardinals, which are equivalently characterized, we prove, as the superstrongly unfoldable cardinals and also as the almost hugely unfoldable cardinals, and we show that their existence is equiconsistent over ZFC with natural instances of the boldface resurrection axiom, such as the boldface resurrection axiom for proper forcing.

The strongly uplifting cardinals, which we introduce in this article, are a boldface analogue of the uplifting cardinals introduced in our previous paper, Resurrection axioms and uplifting cardinals, and are equivalently characterized as the superstrongly unfoldable cardinals and also as the almost hugely unfoldable cardinals. In consistency strength, these new large cardinals lie strictly above the weakly compact, totally indescribable and strongly unfoldable cardinals and strictly below the subtle cardinals, which in turn are weaker in consistency than the existence of $0^\sharp$. The robust diversity of equivalent characterizations of this new large cardinal concept enables constructions and techniques from much larger large cardinal contexts, such as Laver functions and forcing iterations with applications to forcing axioms. Using such methods, we prove that the existence of a strongly uplifting cardinal (or equivalently, a superstrongly unfoldable or almost hugely unfoldable cardinal) is equiconsistent over ZFC with natural instances of the boldface resurrection axioms, including the boldface resurrection axiom for proper forcing, for semi-proper forcing, for c.c.c. forcing and others. Thus, whereas in our prior article we proved that the existence of a mere uplifting cardinal is equiconsistent with natural instances of the (lightface) resurrection axioms, here we adapt both of these notions to the boldface context.

Definitions.

  • An inaccessible cardinal $\kappa$ is strongly uplifting if for every ordinal $\theta$ it is strongly $\theta$-uplifting, which is to say that for every $A\subset V_\kappa$ there is an inaccessible cardinal $\gamma\geq\theta$ and a set $A^*\subset V_\gamma$ such that $\langle V_\kappa,{\in},A\rangle\prec\langle V_\gamma,{\in},A^*\rangle$ is a proper elementary extension.
  • A cardinal $\kappa$ is superstrongly unfoldable, if for every ordinal $\theta$ it is superstrongly $\theta$-unfoldable, which is to say that for each $A\in H_{\kappa^+}$ there is a $\kappa$-model $M$ with $A\in M$ and a transitive set $N$ with an elementary embedding $j:M\to N$ with critical point $\kappa$ and $j(\kappa)\geq\theta$ and $V_{j(\kappa)}\subset N$.
  • A cardinal $\kappa$ is almost-hugely unfoldable, if for every ordinal $\theta$ it is almost-hugely $\theta$-unfoldable, which is to say that for each $A\in H_{\kappa^+}$ there is a $\kappa$-model $M$ with $A\in M$ and a transitive set $N$ with an elementary embedding $j:M\to N$ with critical point $\kappa$ and $j(\kappa)\geq\theta$ and $N^{<j(\kappa)}\subset N$.

Remarkably, these different-seeming large cardinal concepts turn out to be exactly equivalent to one another. A cardinal $\kappa$ is strongly uplifting if and only if it is superstrongly unfoldable, if and only if it is almost hugely unfoldable. Furthermore, we prove that the existence of such a cardinal is equiconsistent with several natural instances of the boldface resurrection axiom.

Theorem. The following theories are equiconsistent over ZFC.

  • There is a strongly uplifting cardinal.
  • There is a superstrongly unfoldable cardinal.
  • There is an almost hugely unfoldable cardinal.
  • The boldface resurrection axiom for all forcing.
  • The boldface resurrection axiom for proper forcing.
  • The boldface resurrection axiom for semi-proper forcing.
  • The boldface resurrection axiom for c.c.c. forcing.
  • The weak boldface resurrection axiom for countably-closed forcing, axiom-A forcing, proper forcing and semi-proper forcing, plus $\neg\text{CH}$.

 

 

Satisfaction is not absolute

  • J. D. Hamkins and R. Yang, “Satisfaction is not absolute,” to appear in the Review of Symbolic Logic, pp. 1-34.  
    @ARTICLE{HamkinsYang:SatisfactionIsNotAbsolute,
    author = {Joel David Hamkins and Ruizhi Yang},
    title = {Satisfaction is not absolute},
    journal = {to appear in the Review of Symbolic Logic},
    year = {},
    volume = {},
    number = {},
    pages = {1--34},
    month = {},
    note = {},
    abstract = {},
    keywords = {},
    source = {},
    eprint = {1312.0670},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/satisfaction-is-not-absolute},
    doi = {},
    }

$\newcommand\N{\mathbb{N}}\newcommand\satisfies{\models}$

Abstract. We prove that the satisfaction relation $\mathcal{N}\satisfies\varphi[\vec a]$ of first-order logic is not absolute between models of set theory having the structure $\mathcal{N}$ and the formulas $\varphi$ all in common. Two models of set theory can have the same natural numbers, for example, and the same standard model of arithmetic $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$, yet disagree on their theories of arithmetic truth; two models of set theory can have the same natural numbers and the same arithmetic truths, yet disagree on their truths-about-truth, at any desired level of the iterated truth-predicate hierarchy; two models of set theory can have the same natural numbers and the same reals, yet disagree on projective truth; two models of set theory can have the same $\langle H_{\omega_2},{\in}\rangle$ or the same rank-initial segment $\langle V_\delta,{\in}\rangle$, yet disagree on which assertions are true in these structures.

On the basis of these mathematical results, we argue that a philosophical commitment to the determinateness of the theory of truth for a structure cannot be seen as a consequence solely of the determinateness of the structure in which that truth resides. The determinate nature of arithmetic truth, for example, is not a consequence of the determinate nature of the arithmetic structure $\N=\{ 0,1,2,\ldots\}$ itself, but rather, we argue, is an additional higher-order commitment requiring its own analysis and justification.

Many mathematicians and philosophers regard the natural numbers $0,1,2,\ldots\,$, along with their usual arithmetic structure, as having a privileged mathematical existence, a Platonic realm in which assertions have definite, absolute truth values, independently of our ability to prove or discover them. Although there are some arithmetic assertions that we can neither prove nor refute—such as the consistency of the background theory in which we undertake our proofs—the view is that nevertheless there is a fact of the matter about whether any such arithmetic statement is true or false in the intended interpretation. The definite nature of arithmetic truth is often seen as a consequence of the definiteness of the structure of arithmetic $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$ itself, for if the natural numbers exist in a clear and distinct totality in a way that is unambiguous and absolute, then (on this view) the first-order theory of truth residing in that structure—arithmetic truth—is similarly clear and distinct.

Feferman provides an instance of this perspective when he writes (Feferman 2013, Comments for EFI Workshop, p. 6-7) :

In my view, the conception [of the bare structure of the natural numbers] is completely clear, and thence all arithmetical statements are definite.

It is Feferman’s `thence’ to which we call attention.  Martin makes a similar point (Martin, 2012, Completeness or incompleteness of basic mathematical concepts):

What I am suggesting is that the real reason for confidence in first-order completeness is our confidence in the full determinateness of the concept of the natural numbers.

Many mathematicians and philosophers seem to share this perspective. The truth of an arithmetic statement, to be sure, does seem to depend entirely on the structure $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$, with all quantifiers restricted to $\N$ and using only those arithmetic operations and relations, and so if that structure has a definite nature, then it would seem that the truth of the statement should be similarly definite.

Nevertheless, in this article we should like to tease apart these two ontological commitments, arguing that the definiteness of truth for a given mathematical structure, such as the natural numbers, the reals or higher-order structures such as $H_{\omega_2}$ or $V_\delta$, does not follow from the definite nature of the underlying structure in which that truth resides. Rather, we argue that the commitment to a theory of truth for a structure is a higher-order ontological commitment, going strictly beyond the commitment to a definite nature for the underlying structure itself.

We make our argument in part by proving that different models of set theory can have a structure identically in common, even the natural numbers, yet disagree on the theory of truth for that structure.

Theorem.

  • Two models of set theory can have the same structure of arithmetic $$\langle\N,{+},{\cdot},0,1,{\lt}\rangle^{M_1}=\langle\N,{+},{\cdot},0,1,{\lt}\rangle^{M_2},$$yet disagree on the theory of arithmetic truth.
  • Two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree about whether it is a well-order.
  • Two models of set theory that have the same natural numbers and the same reals, yet disagree on projective truth.
  • Two models of set theory can have a transitive rank initial segment in common $$\langle V_\delta,{\in}\rangle^{M_1}=\langle V_\delta,{\in}\rangle^{M_2},$$yet disagree about whether it is a model of ZFC.

The proofs use only elementary classical methods, and might be considered to be a part of the folklore of the subject of models of arithmetic. The paper includes many further examples of the phenomenon, and concludes with a philosophical discussion of the issue of definiteness, concerning the question of whether one may deduce definiteness-of-truth from definiteness-of-objects and definiteness-of-structure.

 

The foundation axiom and elementary self-embeddings of the universe

  • A. S. Daghighi, M. Golshani, J. Hamkins, and E. Jeřábek, “The foundation axiom and elementary self-embeddings of the universe,” in Infinity, computability, and metamathematics: Festschrift celebrating the 60th birthdays of Peter Koepke and Philip Welch, S. Geschke, B. Löwe, and P. Schlicht, Eds., Coll. Publ., London, 2014, vol. 23, pp. 89-112.  
    @incollection {DaghighiGolshaniHaminsJerabek2013:TheFoundationAxiomAndElementarySelfEmbeddingsOfTheUniverse,
    AUTHOR = {Daghighi, Ali Sadegh and Golshani, Mohammad and Hamkins, Joel
    David and Je{\v{r}}{\'a}bek, Emil},
    TITLE = {The foundation axiom and elementary self-embeddings of the
    universe},
    BOOKTITLE = {Infinity, computability, and metamathematics:
    Festschrift celebrating the 60th birthdays of Peter Koepke
    and Philip Welch},
    SERIES = {Tributes},
    VOLUME = {23},
    PAGES = {89--112},
    PUBLISHER = {Coll. Publ., London},
    EDITOR = {Geschke, Stefan and L\"owe, Benedikt and Schlicht, Philipp},
    YEAR = {2014},
    MRCLASS = {03E70 (03E30)},
    MRNUMBER = {3307881},
    eprint = {1311.0814},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/the-role-of-foundation-in-the-kunen-inconsistency/},
    }

$\newcommand\ZFC{\text{ZFC}}\newcommand\ZFCf{\ZFC^{\rm-f}}\newcommand\AFA{\text{AFA}}\newcommand\BAFA{\text{BAFA}}$

Festschrift celebrating 60th birthdays of Peter Koepke and Philip Welch
In this article, we examine the role played by the axiom of foundation in the well-known Kunen inconsistency, the theorem asserting that there is no nontrivial elementary embedding of the set-theoretic universe to itself. All the standard proofs of the Kunen inconsistency make use of the axiom of foundation (see Kanamori’s books and also Generalizations of the Kunen inconsistency), and this use is essential, assuming that $\ZFC$ is consistent, because as we shall show there are models of $\ZFCf$ that admit nontrivial elementary self-embeddings and even nontrivial definable automorphisms. Meanwhile, a fragment of the Kunen inconsistency survives without foundation as the claim in $\ZFCf$ that there is no nontrivial elementary self-embedding of the class of well-founded sets. Nevertheless, some of the commonly considered anti-foundational theories, such as the Boffa theory $\BAFA$, prove outright the existence of nontrivial automorphisms of the set-theoretic universe, thereby refuting the Kunen assertion in these theories.  On the other hand, several other common anti-foundational theories, such as Aczel’s anti-foundational theory $\ZFCf+\AFA$ and Scott’s theory $\ZFCf+\text{SAFA}$, reach the opposite conclusion by proving that there are no nontrivial elementary embeddings from the set-theoretic universe to itself. Our summary conclusion, therefore, is that the resolution of the Kunen inconsistency in set theory without foundation depends on the specific nature of one’s anti-foundational stance.

This is joint work with Ali Sadegh Daghighi, Mohammad Golshani, myself and Emil Jeřábek, which grew out of our interaction on Ali’s question on MathOverflow, Is there any large cardinal beyond the Kunen inconsistency?

Resurrection axioms and uplifting cardinals

  • J. D. Hamkins and T. Johnstone, “Resurrection axioms and uplifting cardinals,” Archive for Mathematical Logic, vol. 53, iss. 3-4, p. p.~463–485, 2014.  
    @ARTICLE{HamkinsJohnstone2014:ResurrectionAxiomsAndUpliftingCardinals,
    AUTHOR = "Joel David Hamkins and Thomas Johnstone",
    TITLE = "Resurrection axioms and uplifting cardinals",
    JOURNAL = "Archive for Mathematical Logic",
    publisher= {Springer Berlin Heidelberg},
    YEAR = "2014",
    volume = "53",
    number = "3-4",
    pages = "p.~463--485",
    month = "",
    note = "",
    url = "http://jdh.hamkins.org/resurrection-axioms-and-uplifting-cardinals",
    eprint = "1307.3602",
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    doi= "10.1007/s00153-014-0374-y",
    issn= {0933-5846},
    abstract = "",
    keywords = "",
    source = "",
    file = F }

Abstract. We introduce the resurrection axioms, a new class of forcing axioms, and the uplifting cardinals, a new large cardinal notion, and prove that various instances of the resurrection axioms are equiconsistent over ZFC with the existence of uplifting cardinal.

Many classical forcing axioms can be viewed, at least informally, as the claim that the universe is existentially closed in its forcing extensions, for the axioms generally assert that certain kinds of filters, which could exist in a forcing extension $V[G]$, exist already in $V$. In several instances this informal perspective is realized more formally: Martin’s axiom is equivalent to the assertion that $H_{\frak{c}}$ is existentially closed in all c.c.c. forcing extensions of the universe, meaning that $H_{\frak{c}}\prec_{\Sigma_1}V[G]$ for all such extensions; the bounded proper forcing axiom is equivalent to the assertion that $H_{\omega_2}$ is existentially closed in all proper forcing extensions, or $H_{\omega_2}\prec_{\Sigma_1}V[G]$; and there are other similar instances.

In model theory, a submodel $M\subset N$ is existentially closed in $N$ if existential assertions true in $N$ about parameters in $M$ are true already in $M$, that is, if $M$ is a $\Sigma_1$-elementary substructure of $N$, which we write as $M\prec_{\Sigma_1} N$. Furthermore, in a general model-theoretic setting, existential closure is tightly connected with resurrection, the theme of this article.

Elementary Fact. If $\mathcal{M}$ is a submodel of $\mathcal{N}$, then the following are equivalent.

  1. The model $\mathcal{M}$ is existentially closed in $\mathcal{N}$.
  2. $\mathcal{M}\subset \mathcal{N}$ has resurrection. That is, there is a further extension $\mathcal{M}\subset\mathcal{N}\subset\mathcal{M}^+$ for which $\mathcal{M}\prec\mathcal{M}^+$.

We call this resurrection because although certain truths in $\mathcal{M}$ may no longer hold in the extension $\mathcal{N}$, these truths are nevertheless revived in light of $\mathcal{M}\prec\mathcal{M}^+$ in the further extension to $\mathcal{M}^+$.

In the context of forcing axioms, we are more interested in the case of forcing extensions than in the kind of arbitrary extension $\mathcal{M}^+$ arising in the fact, and in this context the equivalence of (1) and (2) breaks own, although the converse implication $(2)\to(1)$ always holds, and every instance of resurrection implies the corresponding instance of existential closure. This key observation leads us to the main unifying theme of this article, the idea that

resurrection may allow us to formulate more robust forcing axioms 

than existential closure or than combinatorial assertions about filters and dense sets. We therefore introduce in this paper a spectrum of new forcing axioms utilizing the resurrection concept.

Main Definition. Let $\Gamma$ be a fixed definable class of forcing notions.

  1. The resurrection axiom $\text{RA}(\Gamma)$ is the assertion that for every forcing notion $\mathbb{Q}\in\Gamma$ there is further forcing $\mathbb{R}$, with $\vdash_{\mathbb{Q}}\mathbb{R}\in\Gamma$, such that if $g\ast h\subset\mathbb{Q}\ast\mathbb{R}$ is $V$-generic, then $H_{\frak{c}}\prec H_{\frak{c}}^{V[g\ast h]}$.
  2. The weak resurrection axiom $\text{wRA}(\Gamma)$ is the assertion that for every $\mathbb{Q}\in\Gamma$ there is further forcing $\mathbb{R}$, such that if $g\ast h\subset\mathbb{Q}\ast\mathbb{R}$ is $V$-generic, then $H_{\frak{c}}\prec H_{\frak{c}}^{V[g\ast h]}$.

The main result is to prove that various formulations of the resurrection axioms are equiconsistent with the existence of an uplifting cardinal, where an inaccessible cardinal $\kappa$ is uplifting, if there are arbitrarily large inaccessible cardinals $\gamma$ for which $H_\kappa\prec H_\gamma$.  This is a rather weak large cardinal notion, having consistency strength strictly less than the existence of a Mahlo cardinal, which is traditionally considered to be very low in the large cardinal hierarchy.  One highlight of the article is our development of “the world’s smallest Laver function,” the Laver function concept for uplifting cardinals, and we perform an analogue of the Laver preparation in order to achieve the resurrection axiom for c.c.c. forcing.

Main Theorem. The following theories are equiconsistent over ZFC:

  1. There is an uplifting cardinal.
  2. $\text{RA}(\text{all})$.
  3. $\text{RA}(\text{ccc})$.
  4. $\text{RA}(\text{semiproper})+\neg\text{CH}$.
  5. $\text{RA}(\text{proper})+\neg\text{CH}$.
  6. For some countable ordinal $\alpha$, the axiom $\text{RA}(\alpha\text{-proper})+\neg\text{CH}$.
  7. $\text{RA}(\text{axiom-A})+\neg\text{CH}$.
  8. $\text{wRA}(\text{semiproper})+\neg\text{CH}$.
  9. $\text{wRA}(\text{proper})+\neg\text{CH}$.
  10. For some countable ordinal $\alpha$, the axiom $\text{wRA}(\alpha\text{-proper})+\neg\text{CH}$.
  11. $\text{wRA}(\text{axiom-A})+\neg\text{CH}$.
  12. $\text{wRA}(\text{countably closed})+\neg\text{CH}$.

The proof outline proceeds in two directions: on the one hand, the resurrection axioms generally imply that the continuum $\frak{c}$ is uplifting in $L$; and conversely, given any uplifting cardinal $\kappa$, we may perform a suitable lottery iteration of $\Gamma$ forcing to obtain the resurrection axiom for $\Gamma$ in a forcing extension with $\kappa=\frak{c}$.

In a follow-up article, currently nearing completion, we treat the boldface resurrection axioms, which allow a predicate $A\subset\frak{c}$ and ask for extensions of the form $\langle H_{\frak{c}},{\in},A\rangle\prec\langle H_{\frak{c}}^{V[g\ast h]},{\in},A^\ast\rangle$, for some $A^\ast\subset\frak{c}^{V[g\ast h]}$ in the extension.  In that article, we prove the equiconsistency of various formulations of boldface resurrection with the existence of a strongly uplifting cardinal, which we prove is the same as a superstrongly unfoldable cardinal.

Superstrong and other large cardinals are never Laver indestructible

  • J. Bagaria, J. D. Hamkins, K. Tsaprounis, and T. Usuba, “Superstrong and other large cardinals are never Laver indestructible,” to appear in Archive for Mathematical Logic (special issue in honor of Richard Laver).  
    @ARTICLE{BagariaHamkinsTsaprounisUsuba:SuperstrongAndOtherLargeCardinalsAreNeverLaverIndestructible,
    author = {Joan Bagaria and Joel David Hamkins and Konstantinos Tsaprounis and Toshimichi Usuba},
    title = {Superstrong and other large cardinals are never {Laver} indestructible},
    journal = {to appear in Archive for Mathematical Logic (special issue in honor of Richard Laver)},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {},
    abstract = {},
    keywords = {},
    eprint = {1307.3486},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/superstrong-never-indestructible/},
    comment = {http://jdh.hamkins.org/superstrong-never-indestructible/},
    source = {},
    }

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

  • B. Cody, M. Gitik, J. D. Hamkins, and J. A. Schanker, “The least weakly compact cardinal can be unfoldable, weakly measurable and nearly $\theta$-supercompact,” Archive for Mathematical Logic, pp. 1-20, 2015.  
    @article{CodyGitikHamkinsSchanker2015:LeastWeaklyCompact, year= {2015}, issn=
    {0933-5846}, journal= {Archive for Mathematical Logic}, doi=
    {10.1007/s00153-015-0423-1}, title= {The least weakly compact cardinal can be
    unfoldable, weakly measurable and nearly {$\theta$}-supercompact}, publisher=
    {Springer Berlin Heidelberg}, keywords= {Weakly compact; Unfoldable; Weakly
    measurable; Nearly supercompact; Identity crisis; Primary 03E55; 03E35},
    author= {Cody, Brent and Gitik, Moti and Hamkins, Joel David and Schanker,
    Jason A.}, pages= {1--20}, language= {English}, eprint = {1305.5961},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url= {http://jdh.hamkins.org/least-weakly-compact}, }

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

  • J. D. Hamkins and C. Leahy, “Algebraicity and Implicit Definability in Set Theory,” Notre Dame J. Formal Logic, vol. 57, iss. 3, pp. 431-439, 2016.  
    @article{HamkinsLeahy2016:AlgebraicityAndImplicitDefinabilityInSetTheory,
    author = "Hamkins, Joel David and Leahy, Cole",
    doi = "10.1215/00294527-3542326",
    fjournal = "Notre Dame Journal of Formal Logic",
    journal = "Notre Dame J. Formal Logic",
    number = "3",
    pages = "431--439",
    publisher = "Duke University Press",
    title = "Algebraicity and Implicit Definability in Set Theory",
    volume = "57",
    year = "2016",
    url = {http://jdh.hamkins.org/algebraicity-and-implicit-definability},
    eprint = {1305.5953},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    ISSN = {0029-4527},
    MRCLASS = {03E47 (03C55)},
    MRNUMBER = {3521491},
    URL = {http://dx.doi.org/10.1215/00294527-3542326},
    }

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&ouml;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

  • C.~D.~A.~Evans and J. D. Hamkins, “Transfinite game values in infinite chess,” Integers, vol. 14, p. Paper No.~G2, 36, 2014.  
    @ARTICLE{EvansHamkins2014:TransfiniteGameValuesInInfiniteChess,
    AUTHOR = {C.~D.~A.~Evans and Joel David Hamkins},
    TITLE = {Transfinite game values in infinite chess},
    JOURNAL = {Integers},
    FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
    YEAR = {2014},
    volume = {14},
    number = {},
    pages = {Paper No.~G2, 36},
    month = {},
    note = {},
    eprint = {1302.4377},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/game-values-in-infinite-chess},
    ISSN = {1553-1732},
    MRCLASS = {03Exx (91A46)},
    MRNUMBER = {3225916},
    abstract = {},
    keywords = {},
    source = {},
    }

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

  • J. D. Hamkins, “A multiverse perspective on the axiom of constructibility,” in Infinity and truth, World Sci. Publ., Hackensack, NJ, 2014, vol. 25, pp. 25-45.  
    @incollection {Hamkins2014:MultiverseOnVeqL,
    AUTHOR = {Hamkins, Joel David},
    TITLE = {A multiverse perspective on the axiom of constructibility},
    BOOKTITLE = {Infinity and truth},
    SERIES = {Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap.},
    VOLUME = {25},
    PAGES = {25--45},
    PUBLISHER = {World Sci. Publ., Hackensack, NJ},
    YEAR = {2014},
    MRCLASS = {03E45 (03A05)},
    MRNUMBER = {3205072},
    DOI = {10.1142/9789814571043_0002},
    url = {http://jdh.hamkins.org/multiverse-perspective-on-constructibility/},
    eprint = {1210.6541},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

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: