•  360
    Infinite time Turing machines
    Minds and Machines 12 (4): 567-604. 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.
  •  46
    The Halting Problem Is Decidable on a Set of Asymptotic Probability One
    with Alexei Miasnikov
    Notre 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
  •  61
    Destruction or preservation as you like it
    Annals of Pure and Applied Logic 91 (2-3): 191-229. 1998.
    The Gap Forcing Theorem, a key contribution of this paper, implies essentially that after any reverse Easton iteration of closed forcing, such as the Laver preparation, every supercompactness measure on a supercompact cardinal extends a measure from the ground model. Thus, such forcing can create no new supercompact cardinals, and, if the GCH holds, neither can it increase the degree of supercompactness of any cardinal; in particular, it can create no new measurable cardinals. In a crescendo of …Read more
  •  55
    The lottery preparation
    Annals 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
  •  34
    Changing the Heights of Automorphism Towers by Forcing with Souslin Trees over L
    with Gunter Fuchs
    Journal 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
  •  28
    Resurrection axioms and uplifting cardinals
    with Thomas A. Johnstone
    Archive 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.
  •  37
    The least weakly compact cardinal can be unfoldable, weakly measurable and nearly $${\theta}$$ θ -supercompact
    with Brent Cody, Moti Gitik, and Jason A. Schanker
    Archive 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
  •  21
    Indestructible Weakly Compact Cardinals and the Necessity of Supercompactness for Certain Proof Schemata
    with A. W. Apter
    Mathematical 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
  •  61
    Generalizations of the Kunen inconsistency
    with Greg Kirmayer and Norman Lewis Perlmutter
    Annals 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
  •  73
    Unfoldable cardinals and the GCH
    Journal 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 κ
  •  83
    Canonical seeds and Prikry trees
    Journal 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
  •  7
    Small Forcing Makes any Cardinal Superdestructible
    Journal 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
  •  68
    Degrees of rigidity for Souslin trees
    with Gunter Fuchs
    Journal 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
  •  58
    P^f NP^f for almost all f
    Mathematical 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
  •  95
    Indestructibility and the level-by-level agreement between strong compactness and supercompactness
    with Arthur W. Apter
    Journal 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
  •  130
    Infinite time Turing machines
    with Andy Lewis
    Journal 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.
  •  147
    Utilitarianism in Infinite Worlds
    Utilitas 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
  •  69
    Every countable model of set theory embeds into its own constructible universe
    Journal 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
  •  59
    The rigid relation principle, a new weak choice principle
    with Justin Palumbo
    Mathematical 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
  •  44
    Algebraicity and Implicit Definability in Set Theory
    with Cole Leahy
    Notre 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