Tag Archives: descriptive set theory

The hierarchy of equivalence relations on the natural numbers under computable reducibility, Chicheley Hall, June 2012

Posted on by
Reply

 

This will be a talk at The Incomputable, a workshop held June 12-15, 2012 at the Kavli Royal Society International Centre at Chicheley Hall as a part of the program Semantics and Syntax: A Legacy of Alan Turing organized by the Isaac Newton Institute of Mathematical Sciences in Cambridge, UK.

Abstract.  I will speak on the computable analogue of the theory of equivalence relations on the reals under Borel reducibility.  The Borel theory has been enormously successful in clarifying the hierarchy of classification problems arising throughout mathematics.  The computable analogue, meanwhile, appears to be particularly well-suited for an analysis of the c.e. instances of those problems, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups.  In particular, every equivalence relation on countable structures has its natural restriction to the c.e. instances, which may be viewed as an equivalence relation on the indices of those c.e. sets.  Specifically, one equivalence relation E on the natural numbers is computably reducible to another F, if there is a computable function f such that n E m if and only if f(n) F f(m).   This reduction notion has beenMathematical discussions with Philip Welch introduced and studied independently by several different researchers and research groups.  In this talk, I will describe recent joint work with Sam Coskey and Russell Miller that fills out parts of the hierarchy.  An abundance of questions remain open.

Article | Slides | Workshop abstract 

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

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.

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.

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.