Category Archives: Publications

Tall cardinals

Posted on by
Reply

[bibtex key=Hamkins2009:TallCardinals]

A cardinal $\kappa$ is tall if for every ordinal $\theta$ there is an embedding $j:V\to M$ with critical point $\kappa$ such that $j(\kappa)\gt\theta$ and $M^\kappa\subset 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 $\kappa$ can be made indestructible by a variety of forcing notions, including forcing that pumps up the value of $2^\kappa$ as high as desired.

The proper and semi-proper forcing axioms for forcing notions that preserve $\aleph_2$ or $\aleph_3$

Posted on by
Reply

[bibtex key=HamkinsJohnstone2009:PFA(aleph_2-preserving)]

We prove that the PFA lottery preparation of a strongly unfoldable cardinal $\kappa$ under $\neg 0^\sharp$ forces $\text{PFA}(\aleph_2\text{-preserving})$, $\text{PFA}(\aleph_3\text{-preserving})$ and $\text{PFA}_{\aleph_2}$, with $2^\omega=\kappa=\aleph_2$.  The method adapts to semi-proper forcing, giving $\text{SPFA}(\aleph_2\text{-preserving})$, $\text{SPFA}(\aleph_3\text{-preserving})$ and $\text{SPFA}_{\aleph_2}$ from the same hypothesis. It follows by a result of Miyamoto that the existence of a strongly unfoldable cardinal is equiconsistent with the conjunction $\text{SPFA}(\aleph_2\text{-preserving})+\text{SPFA}(\aleph_3\text{-preserving})+\text{SPFA}_{\aleph_2}+2^\omega=\aleph_2$.  Since unfoldable cardinals are relatively weak as large cardinal notions, our summary conclusion is that in order to extract significant strength from PFA or SPFA, one must collapse $\aleph_3$ to $\aleph_1$.

Infinite time computable model theory

Posted on by
1

[bibtex key=HamkinsMillerSeaboldWarner2007:InfiniteTimeComputableModelTheory]

We introduce infinite time computable model theory, the computable model theory arising with infinite time Turing machines,  which provide infinitary notions of computability for structures built on the reals  $\mathbb{R}$. Much of the finite time theory generalizes to the infinite time context, but several fundamental questions, including the infinite time  computable analogue of the Completeness Theorem, turn out to be  independent of ZFC.

Changing the heights of automorphism towers by forcing with Souslin trees over $L$

Posted on by
Reply

[bibtex key=FuchsHamkins2008:ChangingHeightsOverL]

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.

In an earlier paper with Simon Thomas, “Changing the heights of automorphism towers,” we had added such malleable groups by forcing, and the current paper addresses the question as to whether there are such groups already in L.

The ground axiom is consistent with $V\ne{\rm HOD}$

Posted on by
Reply

[bibtex key=HamkinsReitzWoodin2008:TheGroundAxiomAndVequalsHOD]

Abstract. The Ground Axiom asserts that the universe is not a nontrivial set-forcing extension of any inner model. Despite the apparent second-order nature of this assertion, it is first-order expressible in set theory. The previously known models of the Ground Axiom all satisfy strong forms of $V=\text{HOD}$. In this article, we show that the Ground Axiom is relatively consistent with $V\neq\text{HOD}$. In fact, every model of ZFC has a class-forcing extension that is a model of $\text{ZFC}+\text{GA}+V\neq\text{HOD}$. The method accommodates large cardinals: every model of ZFC with a supercompact cardinal, for example, has a class-forcing extension with $\text{ZFC}+\text{GA}+V\neq\text{HOD}$ in which this supercompact cardinal is preserved.

The modal logic of forcing

Posted on by
3

[bibtex key=HamkinsLoewe2008:TheModalLogicOfForcing]

What are the most general principles in set theory relating forceability and truth? As with Solovay’s celebrated analysis of provability, both this question and its answer are naturally formulated with modal logic. We aim to do for forceability what Solovay did for provability. A set theoretical assertion $\psi$ is forceable or possible, if $\psi$ holds in some forcing extension, and necessary, if $\psi$ holds in all forcing extensions. In this forcing interpretation of modal logic, we establish that if ZFC is consistent, then the ZFC-provable principles of forcing are exactly those in the modal theory known as S4.2.

Follow-up article:  Structural connections between a forcing class and its modal logic

Large cardinals with few measures

Posted on by
Reply

[bibtex key=ApterCummingsHamkins2006:LargeCardinalsWithFewMeasures]

We show, assuming the consistency of one measurable cardinal, that it is consistent for there to be exactly $\kappa^+$ many normal measures on the least measurable cardinal $\kappa$. This answers a question of Stewart Baldwin. The methods generalize to higher cardinals, showing that the number of $\lambda$-strong compactness or $\lambda$-supercompactness measures on $P_\kappa(\lambda)$ can be exactly $\lambda^+$, if $\lambda>\kappa$ is a regular cardinal. We conclude with a list of open questions. Our proofs use a critical observation due to James Cummings.

A survey of infinite time Turing machines

Posted on by
1

[bibtex key=Hamkins2007:ASurveyOfInfiniteTimeTuringMachines]

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time, thereby providing a natural model of infinitary computability, with robust notions of computability and decidability on the reals, while remaining close to classical concepts of computability. Here, I survey the theory of infinite time Turing machines and recent developments. These include the rise of infinite time complexity theory, the introduction of infinite time computable model theory, the study of the infinite time analogue of Borel equivalence relation theory, and the introduction of new ordinal computational models. The study of infinite time Turing machines increasingly relies on the interaction of methods from set theory, descriptive set theory and computability theory.

The complexity of quickly decidable ORM-decidable sets

Posted on by
Reply

[bibtex key=HamkinsLinetskyMiller2007:ComplexityOfQuicklyDecidableORMSets]

The Ordinal Register Machine (ORM) is one of several different machine models for infinitary computability. We classify, by complexity, the sets that can be decided quickly by ORMs. In particular, we show that the arithmetical sets are exactly those sets that can be decided by ORMs in times uniformly less than $\omega^\omega$. Further, we show that the hyperarithmetical sets are exactly those sets that can be decided by an ORM in time uniformly less than $\omega_1^{CK}$.

Post's Problem for Ordinal Register Machines

Posted on by
Reply

[bibtex key=HamkinsMiller2007:PostsProblemForORMs]

We study Post’s Problem for ordinal register machines, showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors earlier results for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time.

The halting problem is decidable on a set of asymptotic probability one

Posted on by
Reply

[bibtex key=HamkinsMiasnikov2006:HaltingProblemDecidable]

The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (i) B has asymptotic probability one, so that as the number of states n increases, the proportion of all n-state programs that are in B goes to one; (ii) B is polynomial time decidable; and (iii) the halting problem H intersect B is polynomial time decidable. The proof is sensitive to the particular computational model.

Diamond (on the regulars) can fail at any strongly unfoldable cardinal

Posted on by
Reply

[bibtex key=DzamonjaHamkins2006:DiamondCanFail]

If $\kappa$ is any strongly unfoldable cardinal, then this is preserved in a forcing extension in which $\Diamond_\kappa(\text{REG})$ fails. This result continues the progression of the corresponding results for weakly compact cardinals, due to Woodin, and for indescribable cardinals, due to Hauser.

${\rm P}\neq{\rm NP}\cap\textrm{co-}{\rm NP}$ for infinite time Turing machines

Posted on by
Reply

[bibtex key=DeolalikarHamkinsSchindler2005:NPcoNP]

Extending results of Schindler [math.LO/0106087] and also my paper with Philip Welch, we establish in the context of infinite time Turing machines that $P$ is properly contained in $NP$ intersect $coNP$. Furthermore, $NP\cap coNP$ is exactly the class of hyperarithmetic sets. For the more general classes, we establish that $P^+ = (NP^+\cap coNP^+) = (NP \cap  coNP)$, though $P^{++}$ is properly contained in $NP^{++}\cap coNP^{++}$. Within any contiguous block of infinite clockable ordinals, we show that $P_\alpha$ is not equal to $NP_\alpha\cap coNP_\alpha$, but if $\beta$ begins a gap in the clockable ordinals, then $P_\beta = NP_\beta\cap coNP_\beta$. Finally, we establish that $P^f$ is not equal to $NP^f \cap  coNP^f$ for most functions $f$ from the reals to the ordinals, although we provide examples where $P^f = NP^f \cap coNP^f$ and $P^f$ is not equal to $NP^f$.

The necessary maximality principle for c.c.c. forcing is equiconsistent with a weakly compact cardinal

Posted on by
Reply

[bibtex key=HamkinsWoodin2005:NMPccc]

The Necessary Maximality Principle for c.c.c. forcing asserts that any statement about a real in a c.c.c. extension that could become true in a further c.c.c. extension and remain true in all subsequent c.c.c. extensions, is already true in the minimal extension containing the real. We show that this principle is equiconsistent with the existence of a weakly compact cardinal.

See related article on the Maximality Principle

The Ground Axiom

Posted on by
Reply

[bibtex key=Hamkins2005:TheGroundAxiom]

This is an extended abstract for a talk I gave at the 2005 Workshop in Set Theory at the Mathematisches Forschungsinstitut Oberwolfach.

Oberwolfach Research Report 55/2005 | Ground Axiom on Wikipedia