-
56The lottery preparationAnnals of Pure and Applied Logic 101 (2-3): 103-146. 2000.The lottery preparation, a new general kind of Laver preparation, works uniformly with supercompact cardinals, strongly compact cardinals, strong cardinals, measurable cardinals, or what have you. And like the Laver preparation, the lottery preparation makes these cardinals indestructible by various kinds of further forcing. A supercompact cardinal κ, for example, becomes fully indestructible by
-
51Large cardinals need not be large in HODAnnals of Pure and Applied Logic 166 (11): 1186-1198. 2015.
-
49Infinite Time Decidable Equivalence Relation TheoryNotre Dame Journal of Formal Logic 52 (2): 203-228. 2011.We introduce an analogue of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time ge…Read more
-
48Fragile measurabilityJournal of Symbolic Logic 59 (1): 262-282. 1994.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 $\kappa^{
-
47Post's problem for supertasks has both positive and negative solutionsArchive for Mathematical Logic 41 (6): 507-523. 2002.The infinite time Turing machine analogue of Post's problem, the question whether there are semi-decidable supertask degrees between 0 and the supertask jump 0∇, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between 0 and 0∇, but in the context of sets of reals, there are; indeed, there are incomparable semi-decidable supertask degrees. Both arguments employ a kind of transfinite-injury construction which generalizes canonically to …Read more
-
47Set-theoretic mereologyLogic and Logical Philosophy 25 (3): 285-308. 2016.We consider a set-theoretic version of mereology based on the inclusion relation ⊆ and analyze how well it might serve as a foundation of mathematics. After establishing the non-definability of ∈ from ⊆, we identify the natural axioms for ⊆-based mereology, which constitute a finitely axiomatizable, complete, decidable theory. Ultimately, for these reasons, we conclude that this form of set-theoretic mereology cannot by itself serve as a foundation of mathematics. Meanwhile, augmented forms of s…Read more
-
46The Halting Problem Is Decidable on a Set of Asymptotic Probability OneNotre Dame Journal of Formal Logic 47 (4): 515-524. 2006.The halting problem for Turing machines is decidable on a set of asymptotic probability one. The proof is sensitive to the particular computational models
-
44Algebraicity and Implicit Definability in Set TheoryNotre Dame Journal of Formal Logic 57 (3): 431-439. 2016.We analyze the effect of replacing several natural uses of definability in set theory by the weaker model-theoretic notion of algebraicity. We find, for example, that the class of hereditarily ordinal algebraic sets is the same as the class of hereditarily ordinal definable sets; that is, $\mathrm{HOA}=\mathrm{HOD}$. Moreover, we show that every algebraic model of $\mathrm{ZF}$ is actually pointwise definable. Finally, we consider the implicitly constructible universe Imp—an algebraic analogue o…Read more
-
41Superstrong and other large cardinals are never Laver indestructibleArchive for Mathematical Logic 55 (1-2): 19-35. 2016.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, Σn-reflecting cardinals, Σn-correct cardinals and Σn-extendible cardinals are never Laver indestructible. In fact, all these large cardinal properties are superdest…Read more
-
39Tall cardinalsMathematical Logic Quarterly 55 (1): 68-86. 2009.A cardinal κ is tall if for every ordinal θ there is an embedding j: V → M with critical point κ such that j > θ and Mκ ⊆ M. Every strong cardinal is tall and every strongly compact cardinal is tall, but measurable cardinals are not necessarily tall. It is relatively consistent, however, that the least measurable cardinal is tall. Nevertheless, the existence of a tall cardinal is equiconsistent with the existence of a strong cardinal. Any tall cardinal κ can be made indestructible by a variety o…Read more
-
39Changing the heights of automorphism towersAnnals of Pure and Applied Logic 102 (1-2): 139-157. 2000.If G is a centreless group, then τ denotes the height of the automorphism tower of G. We prove that it is consistent that for every cardinal λ and every ordinal α
-
38Infinite Time Turing Machines With Only One TapeMathematical Logic Quarterly 47 (2): 271-287. 2001.Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions f : ℝ → ℕ, the same class of computable functions. Nevertheless, there are infinite time computable functions f : ℝ → ℝ that are not one-tape computable, and so the two models of infinitary computation are not equivalent. Surprisingl…Read more
-
38The least weakly compact cardinal can be unfoldable, weakly measurable and nearly $${\theta}$$ θ -supercompactArchive for Mathematical Logic 54 (5-6): 491-510. 2015.We prove from suitable large cardinal hypotheses that the least weakly compact cardinal can be unfoldable, weakly measurable and even nearly θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta}$$\end{document}-supercompact, for any desired θ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} …Read more
-
36Choiceless large cardinals and set‐theoretic potentialismMathematical Logic Quarterly 68 (4): 409-415. 2022.We define a potentialist system of ‐structures, i.e., a collection of possible worlds in the language of connected by a binary accessibility relation, achieving a potentialist account of the full background set‐theoretic universe V. The definition involves Berkeley cardinals, the strongest known large cardinal axioms, inconsistent with the Axiom of Choice. In fact, as background theory we assume just. It turns out that the propositional modal assertions which are valid at every world of our syst…Read more
-
36What is the theory without power set?Mathematical Logic Quarterly 62 (4-5): 391-406. 2016.We show that the theory, consisting of the usual axioms of 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 in which ω1 is singular, in which every set of reals is countable, yet ω1 exists, in which there a…Read more
-
35George Tourlakis. Lectures in Logic and Set Theory, volumes 1 and 2. Cambridge studies in advanced mathematics, vol. 83. Cambridge University Press, Cambridge, UK, 2003. xi + 328 and xv + 575 pp (review)Bulletin of Symbolic Logic 11 (2): 241-243. 2005.
-
34Post’s Problem for ordinal register machines: An explicit approachAnnals of Pure and Applied Logic 160 (3): 302-309. 2009.We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals
-
34Changing the Heights of Automorphism Towers by Forcing with Souslin Trees over LJournal of Symbolic Logic 73 (2). 2008.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
-
33The exact strength of the class forcing theoremJournal of Symbolic Logic 85 (3): 869-905. 2020.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}$.…Read more
-
33Ehrenfeucht’s Lemma in Set TheoryNotre Dame Journal of Formal Logic 59 (3): 355-370. 2018.Ehrenfeucht’s lemma asserts that whenever one element of a model of Peano arithmetic is definable from another, 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 fails in the forcing extension of the universe by adding a C…Read more
-
32Lectures in Logic and Set Theory, volumes 1 and 2 (review)Bulletin of Symbolic Logic 11 (2): 241-243. 2005.
-
31Yiannis N. Moschovakis. Notes on set theory. Undergraduate texts in mathematics. Springer-Verlag, New York, Berlin, Heidelberg, etc., 1994, xiv + 272 pp (review)Journal of Symbolic Logic 62 (4): 1493-1494. 1997.
-
30The Set-theoretic Multiverse : A Natural Context for Set TheoryAnnals of the Japan Association for Philosophy of Science 19 37-55. 2011.
-
28Set-theoretic blockchainsArchive for Mathematical Logic 58 (7-8): 965-997. 2019.Given a countable model of set theory, we study the structure of its generic multiverse, the collection of its forcing extensions and ground models, ordered by inclusion. Mostowski showed that any finite poset embeds into the generic multiverse while preserving the nonexistence of upper bounds. We obtain several improvements of his result, using what we call the blockchain construction to build generic objects with varying degrees of mutual genericity. The method accommodates certain infinite po…Read more
-
28Bi-interpretation in weak set theoriesJournal of Symbolic Logic 86 (2): 609-634. 2021.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-foun…Read more
-
28Resurrection axioms and uplifting cardinalsArchive for Mathematical Logic 53 (3-4): 463-485. 2014.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 an uplifting cardinal.
-
27Review: Yiannis N. Moschovakis, Notes on Set Theory (review)Journal of Symbolic Logic 62 (4): 1493-1494. 1997.
-
26Infinite Time Turing MachinesMinds and Machines 12 (4): 521-539. 2002.Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.
-
25The σ1-definable universal finite sequenceJournal of Symbolic Logic 87 (2): 783-801. 2022.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, the sequence is $\Sigma _1$ -definable and provably finite; the sequence is empty in transitive models; and 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. O…Read more
-
University of OxfordFaculty of Philosophy, University CollegeProfessor of Logic, Sir Peter Strawson Fellow
-
Oxford, England, United Kingdom of Great Britain and Northern Ireland
Areas of Specialization
3 more
Mathematical Logic |
The Infinite |
Logic and Philosophy of Logic |
Set Theory |
Philosophy of Mathematics |
Hypercomputation |
Theory of Computation |
Modal Logic |
Areas of Interest
3 more
Logic and Philosophy of Logic |
Mathematical Logic |
The Infinite |
Set Theory |
Modal Logic |
Game Theory |
Theory of Computation |
Hypercomputation |