Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=CoskeyHamkins2013:ITTMandApplicationsToEquivRelations]

We describe the basic theory of infinite time Turing machines and some recent developments, including the infinite time degree theory, infinite time complexity theory, and infinite time computable model theory. We focus particularly on the application of infinite time Turing machines to the analysis of the hierarchy of equivalence relations on the reals, in analogy with the theory arising from Borel reducibility. We define a notion of infinite time reducibility, which lifts much of the Borel theory into the class ${\Delta}^1_2$ in a satisfying way.

Infinite time decidable equivalence relation theory

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=CoskeyHamkins2011:InfiniteTimeComputableEquivalenceRelations]

We introduce an analog 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 generalization of the countable Borel equivalence relations, a key subclass of the Borel equivalence relations, and again show that several key properties carry over to the larger class. Lastly, we collect together several results from the literature regarding Borel reducibility which apply also to absolutely $\Delta^1_2$ reductions, and hence to the infinite time computable reductions.

The set-theoretical multiverse: a natural context for set theory, Japan 2009

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=Hamkins2011:TheMultiverse:ANaturalContext]

This article is based on a talk I gave at the conference in honor of the retirement of Yuzuru Kakuda in Kobe, Japan, March 7, 2009. I would like to express my gratitude to Kakuda-sensei and the rest of the logic group in Kobe for the opportunities provided to me to participate in logic in Japan. In particular, my time as a JSPS Fellow in the logic group at Kobe University in 1998 was a formative experience. I was part of a vibrant research group in Kobe; I enjoyed Japanese life, learned to speak a little Japanese and made many friends. Mathematically, it was a productive time, and after years away how pleasant it is for me to see that ideas planted at that time, small seedlings then, have grown into tall slender trees.

Set theorists often take their subject as constituting a foundation for the rest of mathematics, in the sense that other abstract mathematical objects can be construed fundamentally as sets. In this way, they regard the set-theoretic universe as the universe of all mathematics. And although many set-theorists affirm the Platonic view that there is just one universe of all sets, nevertheless the most powerful set-theoretic tools developed over the past half century are actually methods of constructing alternative universes. With forcing and other methods, we can now produce diverse models of ZFC set theory having precise, exacting features. The fundamental object of study in set theory has thus become the model of set theory, and the subject consequently begins to exhibit a category-theoretic second-order nature. We have a multiverse of set-theoretic worlds, connected by forcing and large cardinal embeddings like constellations in a dark sky. In this article, I will discuss a few emerging developments illustrating this second-order nature. The work engages pleasantly with various philosophical views on the nature of mathematical existence.

Slides

A natural model of the multiverse axioms

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=GitmanHamkins2010:NaturalModelOfMultiverseAxioms]

In this article, we prove that if ZFC is consistent, then the collection of countable computably saturated models of ZFC satisfies all of the Multiverse Axioms that I introduced in my paper, “The set-theoretic multiverse.”

Indestructible strong unfoldability

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=HamkinsJohnstone2010:IndestructibleStrongUnfoldability]

Using the lottery preparation, we prove that any strongly unfoldable cardinal $\kappa$ can be made indestructible by all ${\lt}\kappa$-closed + $\kappa^+$-preserving forcing. This degree of indestructibility, we prove, is the best possible from this hypothesis within the class of ${\lt}\kappa$-closed forcing. From a stronger hypothesis, however, we prove that the strong unfoldability of $\kappa$ can be made indestructible by all ${\lt}\kappa$-closed forcing. Such indestructibility, we prove, does not follow from indestructibility merely by ${\lt}\kappa$-directed closed forcing. Finally, we obtain global and universal forms of indestructibility for strong unfoldability, finding the exact consistency strength of universal indestructibility for strong unfoldability.

Post's problem for ordinal register machines: an explicit approach

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=HamkinsMiller2009:PostsProblemForORMsExplicitApproach]

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.

Degrees of rigidity for Souslin trees

Posted on September 25, 2011 by Joel David Hamkins

[bibtex key=FuchsHamkins2009:DegreesOfRigidity]

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

Tall cardinals

Posted on September 25, 2011 by Joel David Hamkins

[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 September 25, 2011 by Joel David Hamkins

[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 September 25, 2011 by Joel David Hamkins

[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 September 25, 2011 by Joel David Hamkins

[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 September 25, 2011 by Joel David Hamkins

[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.

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share: