Category Archives: Publications

The hierarchy of equivalence relations on the natural numbers under computable reducibility

Posted on by
4

[bibtex key=CoskeyHamkinsMiller2012:HierarchyOfEquivalenceRelationsOnN]

We define and elaborate upon the notion of computable reducibility between equivalence relations on the natural numbers, providing a natural computable analogue of Borel reducibility, and investigate the hierarchy to which it gives rise. The theory appears well suited for an analysis of equivalence relations on classes of c.e. structures, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In this regard, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remain.

See Sam’s post on this article

Set-theoretic geology

Posted on by
7

[bibtex key=FuchsHamkinsReitz2015:Set-theoreticGeology]

A ground of the universe V is a transitive proper class W subset V, such that W is a model of ZFC and V is obtained by set forcing over W, so that V = W[G] for some W-generic filter G subset P in W . The model V satisfies the ground axiom GA if there are no such W properly contained in V . The model W is a bedrock of V if W is a ground of V and satisfies the ground axiom. The mantle of V is the intersection of all grounds of V . The generic mantle of V is the intersection of all grounds of all set-forcing extensions of V . The generic HOD, written gHOD, is the intersection of all HODs of all set-forcing extensions. The generic HOD is always a model of ZFC, and the generic mantle is always a model of ZF. Every model of ZFC is the mantle and generic mantle of another model of ZFC. We prove this theorem while also controlling the HOD of the final model, as well as the generic HOD. Iteratively taking the mantle penetrates down through the inner mantles to what we call the outer core, what remains when all outer layers of forcing have been stripped away. Many fundamental questions remain open.

The rigid relation principle, a new weak choice principle

Posted on by
Reply

[bibtex key=HamkinsPalumbo2012:TheRigidRelationPrincipleANewWeakACPrinciple]

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 (among other general instances) is provable without the axiom of choice.

This paper arose out of my related mathoverflow question:  Does every set admit a rigid binary relation (and how is this related to the axiom of choice)?

Generalizations of the Kunen inconsistency

Posted on by
6

[bibtex key=HamkinsKirmayerPerlmutter2012:GeneralizationsOfKunenInconsistency]

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 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 from any definable class to V, among many other possibilities we consider, including generic embeddings, definable embeddings and results not requiring the axiom of choice. We have aimed in this article for a unified presentation that weaves together some previously known unpublished or folklore results, several due to Woodin and others, along with our new contributions.

Pointwise definable models of set theory

Posted on by
12

[bibtex key=HamkinsLinetskyReitz2013:PointwiseDefinableModelsOfSetTheory]

One occasionally hears the argument—let us call it the math-tea argument, for perhaps it is heard at a good math tea—that there must be real numbers that we cannot describe or define, because there are are only countably many definitions, but uncountably many reals.  Does it withstand scrutiny?

This article provides an answer.  The article has a dual nature, with the first part aimed at a more general audience, and the second part providing a proof of the main theorem:  every countable model of set theory has an extension in which every set and class is definable without parameters.  The existence of these models therefore exhibit the difficulties in formalizing the math tea argument, and show that robust violations of the math tea argument can occur in virtually any set-theoretic context.

A pointwise definable model is one in which every object is definable without parameters. In a model of set theory, this property strengthens V=HOD, but is not first-order expressible. Nevertheless, if ZFC is consistent, then there are continuum many pointwise definable models of ZFC. If there is a transitive model of ZFC, then there are continuum many pointwise definable transitive models of ZFC. What is more, every countable model of ZFC has a class forcing extension that is pointwise definable. Indeed, for the main contribution of this article, every countable model of Godel-Bernays set theory has a pointwise definable extension, in which every set and class is first-order definable without parameters.

Effective Mathemematics of the Uncountable

Posted on by
5

EMU book jacket[bibtex key=EMU]

Classical computable model theory is most naturally concerned with countable domains. There are, however, several methods – some old, some new – that have extended its basic concepts to uncountable structures. Unlike in the classical case, however, no single dominant approach has emerged, and different methods reveal different aspects of the computable content of uncountable mathematics. This book contains introductions to eight major approaches to computable uncountable mathematics: descriptive set theory; infinite time Turing machines; Blum-Shub-Smale computability; Sigma-definability; computability theory on admissible ordinals; E-recursion theory; local computability; and uncountable reverse mathematics. This book provides an authoritative and multifaceted introduction to this exciting new area of research that is still in its early stages. It is ideal as both an introductory text for graduate and advanced undergraduate students, and a source of interesting new approaches for researchers in computability theory and related areas.

Many of the authors whose work appears in this volume were also involved in the Effective Mathematics of the Uncountable conferences EMU 2008 and EMU 2009, held at the CUNY Graduate Center.

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

Posted on by
Reply

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

The set-theoretical multiverse

Posted on by
17

[bibtex key=Hamkins2012:TheSet-TheoreticalMultiverse]

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 diversity of set-theoretic possibilities, a phenomenon that challenges the universe view. In particular, I argue that the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for.

Multiversive at n-Category Cafe | Multiverse on Mathoverflow

Infinite time decidable equivalence relation theory

Posted on by
Reply

[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 by
Reply

[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 by
Reply

[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 by
Reply

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

Some second order set theory

Posted on by
1

[bibtex key=Hamkins2009:SomeSecondOrderSetTheory]

This article surveys two recent developments in set theory sharing an essential second-order nature, namely, the modal logic of forcing, oriented upward from the universe of set theory to its forcing extensions; and set-theoretic geology, oriented downward from the universe to the inner models over which it arises by forcing. The research is a mixture of ideas from several parts of logic, including, of course, set theory and forcing, but also modal logic, finite combinatorics and the philosophy of mathematics, for it invites a mathematical engagement with various philosophical views on the nature of mathematical existence.

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

Posted on by
Reply

[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 by
Reply

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