Abstract We discuss the accuracy of the attribution commonly given to Turing (1936, Proceedings of the London Mathematical Society, 42.3, 230–265) for the computable undecidability of the halting problem, coming eventually to a nuanced conclusion.

Abstract After reviewing various natural bi-interpretations in urelement set theory, including second-order set theories with urelements, we explore the strength of second-order reflection in these contexts. Ultimately, we prove that second-order reflection with the abundant atom axiom is bi-interpretable and hence also equiconsistent with the existence of a supercompact cardinal. The proof relies on a reflection characterization of supercompactness, namely, a cardinal $\kappa $ is supercompact if and only if every $\Pi ^1_1$ sentence true in a structure M (of any size) containing $\kappa $ in a language of size less than $\kappa $ is also true in a substructure $m\prec M$ of size less than $\kappa $ with $m\cap \kappa \in \kappa $ .

Abstract We introduce the $\Sigma _1$ -definable universal finite sequence and prove that it exhibits the universal extension property amongst the countable models of set theory under end-extension. That is, (i) the sequence is $\Sigma _1$ -definable and provably finite; (ii) the sequence is empty in transitive models; and (iii) if M is a countable model of set theory in which the sequence is s and t is any finite extension of s in this model, then there is an end-extension of M to a model in which the sequence is t. Our proof method grows out of a new infinitary-logic-free proof of the Barwise extension theorem, by which any countable model of set theory is end-extended to a model of $V=L$ or indeed any theory true in a suitable submodel of the original model. The main theorem settles the modal logic of end-extensional potentialism, showing that the potentialist validities of the models of set theory under end-extensions are exactly the assertions of S4. Finally, we introduce the end-extensional maximality principle, which asserts that every possibly necessary sentence is already true, and show that every countable model extends to a model satisfying it.

Abstract In contrast to the robust mutual interpretability phenomenon in set theory, Ali Enayat proved that bi-interpretation is absent: distinct theories extending ZF are never bi-interpretable and models of ZF are bi-interpretable only when they are isomorphic. Nevertheless, for natural weaker set theories, we prove, including Zermelo–Fraenkel set theory $\mathrm {ZFC}^{-}$ without power set and Zermelo set theory Z, there are nontrivial instances of bi-interpretation. Specifically, there are well-founded models of $\mathrm {ZFC}^{-}$ that are bi-interpretable, but not isomorphic—even $\langle H_{\omega _1},\in \rangle $ and $ \langle H_{\omega _2},\in \rangle $ can be bi-interpretable—and there are distinct bi-interpretable theories extending $\mathrm {ZFC}^{-}$ . Similarly, using a construction of Mathias, we prove that every model of ZF is bi-interpretable with a model of Zermelo set theory in which the replacement axiom fails.

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

Abstract We answer several questions posed by Hamkins and Leahy concerning the implicitly constructible universe Imp, which they introduced in [5]. Specifically, we show that it is relatively consistent with ZFC that $$Imp = \neg {\rm{CH}}$$ , that $Imp \ne {\rm{HOD}}$ , and that $$Imp \models V \ne Imp$$ , or in other words, that $\left( {Imp} \right)^{Imp} \ne Imp$ .

Abstract In ZFC, the class Ord of ordinals is easily seen to satisfy the definable version of strong inaccessibility. Here we explore deeper ZFC-verifiable combinatorial properties of Ord, as indicated in Theorems A & B below. Note that Theorem A shows the unexpected result that Ord is never definably weakly compact in any model of ZFC. Theorem A. Let ${\cal M}$ be any model of ZFC. (1) The definable tree property fails in ${\cal M}$ : There is an ${\cal M}$ -definable Ord-tree with no ${\cal M}$ -definable cofinal branch. (2) The definable partition property fails in ${\cal M}$ : There is an ${\cal M}$ -definable 2-coloring $f:{[X]^2} \to 2$ for some ${\cal M}$ -definable proper class X such that no ${\cal M}$ -definable proper classs is monochromatic for f. (3) The definable compactness property for ${{\cal L}_{\infty ,\omega }}$ fails in ${\cal M}$ : There is a definable theory ${\rm{\Gamma }}$ in the logic ${{\cal L}_{\infty ,\omega }}$ (in the sense of ${\cal M}$ ) of size Ord such that every set-sized subtheory of ${\rm{\Gamma }}$ is satisfiable in ${\cal M}$ , but there is no ${\cal M}$ -definable model of ${\rm{\Gamma }}$ . Theorem B. The definable ⋄Ordprinciple holds in a model ${\cal M}$ of ZFC iff ${\cal M}$ carries an ${\cal M}$ -definable global well-ordering. Theorems A and B above can be recast as theorem schemes in ZFC, or as asserting that a single statement in the language of class theory holds in all ‘spartan’ models of GB (Gödel-Bernays class theory); where a spartan model of GB is any structure of the form $\left( {{\cal M},{D_{\cal M}}} \right)$ , where ${\cal M} \models {\rm{ZF}}$ and

Abstract A pointwise definable model is one in which every object is definable without parameters. In a model of set theory, this property strengthens V = HOD, but is not first-order expressible. Nevertheless, if ZFC is consistent, then there are continuum many pointwise definable models of ZFC. If there is a transitive model of ZFC, then there are continuum many pointwise definable transitive models of ZFC. What is more, every countable model of ZFC has a class forcing extension that is pointwise definable. Indeed, for the main contribution of this article, every countable model of Gödel-Bernays set theory has a pointwise definable extension, in which every set and class is first-order definable without parameters.

Abstract We investigate various strong notions of rigidity for Souslin trees, separating them under ⟡ into a hierarchy. Applying our methods to the automorphism tower problem in group theory, we show under ⟡ that there is a group whose automorphism tower is highly malleable by forcing.

Abstract We prove that there are groups in the constructible universe whose automorphism towers are highly malleable by forcing. This is a consequence of the fact that, under a suitable diamond hypothesis, there are sufficiently many highly rigid non-isomorphic Souslin trees whose isomorphism relation can be precisely controlled by forcing.

Extending results of Schindler, Hamkins and Welch, we establish in the context of infinite time Turing machines that P is properly contained in NP ∩ co-NP. For higher analogues of these classes, we exhibit positive and negative results.

Abstract We summarize the known methods of producing a non-supercompact strongly compact cardinal and describe some new variants. Our Main Theorem shows how to apply these methods to many cardinals simultaneously and exactly control which cardinals are supercompact and which are only strongly compact in a forcing extension. Depending upon the method, the surviving non-supercompact strongly compact cardinals can be strong cardinals, have trivial Mitchell rank or even contain a club disjoint from the set of measurable cardinals. These results improve and unify Theorems 1 and 2 of [5], due to the first author.

Abstract In this paper, following an idea of Christophe Chalons, I propose a new kind of forcing axiom, the Maximality Principle, which asserts that any sentence φ holding in some forcing extension Vℙ and all subsequent extensions Vℙ*ℚ holds already in V. It follows, in fact, that such sentences must also hold in all forcing extensions of V. In modal terms, therefore, the Maximality Principle is expressed by the scheme (◊ □ φ) ⇒ □ φ, and is equivalent to the modal theory S5. In this article, I prove that the Maximality Principle is relatively consistent with ZFC. A boldface version of the Maximality Principle, obtained by allowing real parameters to appear in φ, is equiconsistent with the scheme asserting that Vδ ≺ V for an inaccessible cardinal δ, which in turn is equiconsistent with the scheme asserting that ORD is Mahlo. The strongest principle along these lines is □ , which asserts that holds in V and all forcing extensions. From this, it follows that 0# exists, that x# exists for every set x, that projective truth is invariant by forcing, that Woodin cardinals are consistent and much more. Many open questions remain.

Abstract Can a supercompact cardinal κ be Laver indestructible when there is a level-by-level agreement between strong compactness and supercompactness? In this article, we show that if there is a sufficiently large cardinal above κ, then no, it cannot. Conversely, if one weakens the requirement either by demanding less indestructibility, such as requiring only indestructibility by stratified posets. or less level-by-level agreement, such as requiring it only on measure one sets, then yes. it can.

Abstract Unfoldable cardinals are preserved by fast function forcing and the Laver-like preparations that fast functions support. These iterations show, by set-forcing over any model of ZFC, that any given unfoldable cardinal κ can be made indestructible by the forcing to add any number of Cohen subsets to κ.

Abstract We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Every set. for example, is decidable by such machines, and the semi-decidable sets form a portion of the sets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

Abstract Small forcing always ruins the indestructibility of an indestructible supercompact cardinal. In fact, after small forcing, any cardinal κ becomes superdestructible—any further <κ-closed forcing which adds a subset to κ will destroy the measurability, even the weak compactness, of κ. Nevertheless, after small forcing indestructible cardinals remain resurrectible, but never strongly resurrectible.

Abstract After small forcing, any <κ-closed forcing will destroy the supercompactness and even the strong compactness of κ.

Abstract Applying the seed concept to Prikry tree forcing ℙμ, I investigate how well ℙμ preserves the maximality property of ordinary Prikry forcing and prove that ℙμ, Prikry sequences are maximal exactly when μ admits no non-canonical seeds via a finite iteration. In particular, I conclude that if μ is a strongly normal supercompactness measure, then ℙμ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjecture of W. Hugh Woodin's.

Abstract Laver [L] and others [G-S] have shown how to make the supercompactness or strongness of κ indestructible by a wide class of forcing notions. We show, alternatively, how to make these properties fragile. Specifically, we prove that it is relatively consistent that any forcing which preserves κ<κ and κ+, but not P(κ), destroys the measurability of κ, even if κ is initially supercompact, strong, or if I1(κ) holds. Obtained as an application of some general lifting theorems, this result is an “inner model” type of theorem proved instead by forcing.