Home / Science / Research Еxcellence 2008-2013 / Definability in the Local Structure of the Enumeration Degrees

   

Name of Excellence: Definability in the Local Structure of the Enumeration Degrees

Authors: Assoc. Prof. Hristo Ganchev, Department of Mathematical Logic and Its Applications
  Assoc. Prof. Mariya I. Soskova, Department of Mathematical Logic and Its Applications

Research domain: Mathematical Logic - Computability Theory

Hr.Ganchev
 

Hristo Ganchev received his education at the Faculty of Mathematics and Informatics of Sofia University “St. Kliment Ohridski”.

In 2002 he received a Bachelor and in 2004 - a Master degree in Mathematics. In 2009 he received a Doctoral degree in Mathematical Logic. In 2008 he was employed as an Assistant Professor and since 2012 he has been an Associate Professor at the Department of Mathematical Logic and Its Applications, Faculty of Mathematics and Informatics.

His scientific interests are in the area of mathematical logic and in particu­lar in Computability theory.

Assoc. Prof. Hristo Ganchev
M.Soskova
 

Mariya Soskova received her Bachelor degree in Computer Science and Master degree in Mathematics from the Faculty of Mathematics and Informatics, Sofia University “St. Kliment Ohridski” in 2004 and 2005 respectively.

In 2008 she received a PhD degree at the University of Leeds.

She was employed as a mathematician in 2008 and since 2012 she has been an Associate Professor at the Department of Mathematical Logic and Its Applications, Faculty of Mathematics and Informatics. In the period 2012 - 2014 she was a visiting scholar at the University of California, Berkeley.

Assoc. Prof. Mariya I. Soskova    

Computability theory originates from the work of Turing and Post in the 1930’s and 1940’s. One of the central themes in this area is degree theory.

The subject of the present research is the structure of the enumeration degrees. The structure arises from the notion of enumeration reducibility, which essentially formalizes the ability to extract positive information about a given real number from the positive information content of a different real number.

The central research questions refer to the complexity of the structure and its expressive power. In particular, the presented work provides a complete answer to the question set by S. B. Cooper in 1990 about the complexity of the local theory of the structure of the enumeration degrees and a partial answer to the question set by Rogers in 1967 about the fi rst order defi nability of a natural copy of the structure of the Turing degrees in the structure of the enumeration degrees. The two central results are as follows:

  1. The local theory of the enumeration degrees is computably isomorphic to first order arith­metic.
  2. The Turing degrees that are comparable with the first jump of the least enumeration de­gree are first order definable in the structure of the enumeration degrees.
Номерационни-степени

 

The two results, as well as many other acquired results about definability in the local structureof the enumeration degrees are a con­sequence of the theory of Kalimullin pairs, which is developed in a series of four articles.

All of the described results are di­rectly correlated with the chracterization of the automorphism group of the Turing and enumeration degrees, which remains a central open question in Degree Theory.

The presented work has been support­ed by Grants DОО2-258/18.12.2008, DMU07-3/12.12.2011 of the Bulgarian Science Fund at the Ministry of Education and Science and FP7-MC-IOF-2298471 of the European Commission.