Tag Archives: equivalence relations

Burak Kaya, Ph.D. March 2016

Posted on by
4

Burak Kaya successfully defended his dissertation, “Cantor minimal systems from a descriptive perspective,” on March 24, 2016, earning his Ph.D. degree at Rutgers University under the supervision of Simon Thomas. The dissertation committee consisted of Simon Thomas, Gregory Cherlin, Grigor Sargsyan and myself, as the outside member.

Burak Kaya defense

The defense was very nice, with an extremely clear account of the main results, and the question session included a philosophical discussion on various matters connected with the dissertation, including the principle attributed to Gao that any collection of mathematical structures that has a natural Borel representation has a unique such representation up to Borel isomorphism, a principle that was presented as a Borel-equivalence-relation-theory analogue of the Church-Turing thesis.

Burak Kaya

Burak Kaya | MathOverflow profile | ar$\chi$iv profile

Abstract.  In recent years, the study of the Borel complexity of naturally occurring classification problems has been a major focus in descriptive set theory. This thesis is a contribution to the project of analyzing the Borel complexity of the topological conjugacy relation on various Cantor minimal systems.

 

We prove that the topological conjugacy relation on pointed Cantor minimal systems is Borel bireducible with the Borel equivalence relation $\newcommand\d{\Delta^+_{\mathbb{R}}}\d$. As a byproduct of our analysis, we also show that $\d$ is a lower bound for the topological conjugacy relation on Cantor minimal systems.

 

The other main result of this thesis concerns the topological conjugacy relation on Toeplitz subshifts. We prove that the topological conjugacy relation on Toeplitz subshifts with separated holes is a hyperfinite Borel equivalence relation. This result provides a partial affirmative answer to a question asked by Sabok and Tsankov.

 

As pointed Cantor minimal systems are represented by properly ordered Bratteli diagrams, we also establish that the Borel complexity of equivalence of properly ordered Bratteli diagrams is $\d$.

 

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, Cambridge, March 2012

Posted on by
Reply

This is a talk I shall give at the workshop on Logical Approaches to Barriers in Complexity II, March 26-30, 2012, a part of the program Semantics and Syntax: A Legacy of Alan Turing at the Isaac Newton Institute for Mathematical Sciences in Cambridge, where I am currently a Visiting Fellow.

Many of the naturally arising equivalence relations in mathematics, such as isomorphism relations on various types of countable structures, turn out to be equivalence relations on a standard Borel space, and these relations form an intensely studied hierarchy under Borel reducibility.  The topic of this talk is to introduce and explore the computable analogue of this robust theory, by studying the corresponding hierarchy of equivalence relations on the natural numbers under computable reducibility.  Specifically, one relation $E$ is computably reducible to another $F$ , if there is a unary computable function $f$ such that $x\mathrel{E}y$ if and only if $f(x)\mathrel{F}f(y)$.  This gives rise to a very different hierarchy than the Turing degrees on such relations, since it is connected with the difficulty of the corresponding classification problems, rather than with the difficulty of computing the relations themselves.  The theory is 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.  An abundance of open questions remain, and the subject is an attractive mix of methods from mathematical logic, computability, set theory, particularly descriptive set theory, and the rest of mathematics, subjects in which many of the equivalence relations arise.  This is joint work with Sam Coskey and Russell Miller.

Slides | Slides (longer version, from a similar talk) | Article | Conference abstract | Video

The hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility, New York March 2012

Posted on by
Reply

I gave a talk at the CUNY MAMLS conference March 9-10, 2012 at the City University of New York.

This talk will be about a generalization of the concept of Turing degrees to the hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility.  The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on $\mathbb{R}$ under Borel reducibility, a theory which has led to deep insights on the complexity hierarchy of classification problems arising throughout mathematics. In the computable analogue, we consider the corresponding reduction notion in the context of Turing computability for relations on $\mathbb{N}$.  Specifically, one relation $E$ is computably reducible to another, $F$, if there is a computable function $f$ such that $x\mathrel{E} y$ if and only if $f(x)\mathrel{F} f(y)$.  This is a very different concept from mere Turing reducibility of $E$ to $F$, for it sheds light on the comparative difficulty of the classification problems corresponding to $E$ and $F$, rather than on the difficulty of computing the relations themselves.  In particular, 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.  This is joint work with Sam Coskey and Russell Miller.

article | slides | abstract on conference web page | related talk Florida MAMLS 2012 | Sam’s post on this topic

The hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility, Florida, 2012

Posted on by
1

This is a talk at the Alan Turing centenary conference at Florida Atlantic University, January 13-15, 2012, sponsored by MAMLS, and part of the 2012 Alan Turing Year of events in celebration of the one hundredth year of the birth of Alan Turing.

This talk will be about a recent generalization of the concept of Turing degrees to the hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility.  The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on $\mathbb{R}$ under Borel reducibility, a theory which has led to deep insights on the complexity hierarchy of classification problems arising throughout mathematics. In our computable analogue, we consider the corresponding reduction notion in the context of Turing computability for relations on $\mathbb{N}$.  Specifically, one relation $E$ is computably reducible to another, $F$, if there is a computable function $f$ such that $x\mathrel{E} y$ if and only if $f(x)\mathrel{F} f(y)$.  This is a very different concept from mere Turing reducibility of $E$ to $F$, for it sheds light on the comparative difficulty of the classification problems corresponding to $E$ and $F$, rather than on the difficulty of computing the relations themselves.  In particular, 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.  This is joint work with Sam Coskey and Russell Miller.

Article | Sam’s post on this topic | Slides

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

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.