-
40The 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
-
29Resurrection 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.
-
22Indestructible Weakly Compact Cardinals and the Necessity of Supercompactness for Certain Proof SchemataMathematical Logic Quarterly 47 (4): 563-572. 2001.We show that if the weak compactness of a cardinal is made indestructible by means of any preparatory forcing of a certain general type, including any forcing naively resembling the Laver preparation, then the cardinal was originally supercompact. We then apply this theorem to show that the hypothesis of supercompactness is necessary for certain proof schemata
-
62Generalizations of the Kunen inconsistencyAnnals of Pure and Applied Logic 163 (12): 1872-1890. 2012.We present several generalizations of the well-known Kunen inconsistency that there is no nontrivial elementary embedding from the set-theoretic universe V to itself. For example, there is no elementary embedding from the universe V to a set-forcing extension V[G], or conversely from V[G] to V, or more generally from one set-forcing ground model of the universe to another, or between any two models that are eventually stationary correct, or from V to HOD, or conversely from HOD to V, or indeed f…Read more
-
85Canonical seeds and Prikry treesJournal of Symbolic Logic 62 (2): 373-396. 1997.Applying the seed concept to Prikry tree forcing P μ , I investigate how well P μ preserves the maximality property of ordinary Prikry forcing and prove that P μ 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 P μ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjecture of W. Hugh Woodin's
-
76Unfoldable cardinals and the GCHJournal of Symbolic Logic 66 (3): 1186-1198. 2001.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 κ
-
69Degrees of rigidity for Souslin treesJournal of Symbolic Logic 74 (2): 423-454. 2009.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
-
7Small Forcing Makes any Cardinal SuperdestructibleJournal of Symbolic Logic 63 (1): 51-58. 1998.Small forcing always ruins the indestructibility of an indestructible supercompact cardinal. In fact, after small forcing, any cardinal $\kappa$ becomes superdestructible--any further
-
101Indestructibility and the level-by-level agreement between strong compactness and supercompactnessJournal of Symbolic Logic 67 (2): 820-840. 2002.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
-
31P^f NP^f for almost all fMathematical Logic Quarterly 49 (5): 536. 2003.We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines Pf = NPf can be true for any function f from the reals into ω1. We show that “almost everywhere” the answer is negative
-
134Infinite time Turing machinesJournal of Symbolic Logic 65 (2): 567-604. 2000.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.
-
159Utilitarianism in Infinite WorldsUtilitas 12 (1): 91. 2000.Recently in the philosophical literature there has been some effort made to understand the proper application of the theory of utilitarianism to worlds in which there are infinitely many bearers of utility. Here, we point out that one of the best, most inclusive principles proposed to date contradicts fundamental utilitarian ideas, such as the idea that adding more utility makes a better world
-
71Every countable model of set theory embeds into its own constructible universeJournal of Mathematical Logic 13 (2): 1350006. 2013.The main theorem of this article is that every countable model of set theory 〈M, ∈M〉, including every well-founded model, is isomorphic to a submodel of its own constructible universe 〈LM, ∈M〉 by means of an embedding j : M → LM. It follows from the proof that the countable models of set theory are linearly pre-ordered by embeddability: if 〈M, ∈M〉 and 〈N, ∈N〉 are countable models of set theory, then either M is isomorphic to a submodel of N or conversely. Indeed, these models are pre-well-ordere…Read more
-
45Algebraicity 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
-
64The rigid relation principle, a new weak choice principleMathematical Logic Quarterly 58 (6): 394-398. 2012.The rigid relation principle, introduced in this article, asserts that every set admits a rigid binary relation. This follows from the axiom of choice, because well-orders are rigid, but we prove that it is neither equivalent to the axiom of choice nor provable in Zermelo-Fraenkel set theory without the axiom of choice. Thus, it is a new weak choice principle. Nevertheless, the restriction of the principle to sets of reals is provable without the axiom of choice
-
50Infinite 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
-
27Review: Yiannis N. Moschovakis, Notes on Set Theory (review)Journal of Symbolic Logic 62 (4): 1493-1494. 1997.
-
17Lectures in Logic and Set Theory, volumes 1 and 2 (review)Bulletin of Symbolic Logic 11 (2): 241-243. 2005.
-
92Indestructible Strong UnfoldabilityNotre Dame Journal of Formal Logic 51 (3): 291-321. 2010.Using the lottery preparation, we prove that any strongly unfoldable cardinal $\kappa$ can be made indestructible by all
-
6Canonical Seeds and Prikry TreesJournal of Symbolic Logic 62 (2): 373-396. 1997.Applying the seed concept to Prikry tree forcing $\mathbb{P}_\mu$, I investigate how well $\mathbb{P}_\mu$ preserves the maximality property of ordinary Prikry forcing and prove that $\mathbb{P}_\mu$ Prikry sequences are maximal exactly when $\mu$ admits no non-canonical seeds via a finite iteration. In particular, I conclude that if $\mu$ is a strongly normal supercompactness measure, then $\mathbb{P}_\mu$ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjectur…Read more
-
4Unfoldable Cardinals and the GCHJournal of Symbolic Logic 66 (3): 1186-1198. 2001.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 $\kappa$ can be made indestructible by the forcing to add any number of Cohen subsets to $\kappa$.
-
42Tall 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
-
43Superstrong 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
-
48Post'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
-
27Infinite 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.
-
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
-
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^{
-
97A simple maximality principleJournal of Symbolic Logic 68 (2): 527-550. 2003.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 varphi holding in some forcing extension $V^P$ and all subsequent extensions $V^{P\ast Q}$ 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 $(\lozenge \square \varphi) \Rightarrow \square \varphi$ , and is equ…Read more
-
307The set-theoretic multiverseReview of Symbolic Logic 5 (3): 416-449. 2012.The multiverse view in set theory, introduced and argued for in this article, is the view that there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe. The universe view, in contrast, asserts that there is an absolute background set concept, with a corresponding absolute set-theoretic universe in which every set-theoretic question has a definite answer. The multiverse position, I argue, explains our experience with the enormous range of set-theoretic …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 |