This article is cited in 1 paper

Brief communications

Definable relations in structures of Turing degrees

M. M. Arslanov

Chair of Algebra and Mathematical Logic, Kazan (Volga Region) Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia

Abstract: In this paper we investigate questions about the definability of classes of $n$-computably enumerable (c.e.) sets and degrees in the Ershov difference hierarchy. It is proved that the class of all c.e. sets it is definable under the set inclusion $\subseteq$ in all finite levels of the difference hierarchy. It is also proved the definability of all $m$-c.e. degrees in each higher level of the hierarchy. Besides, for each level $n$, $n\ge2$, of the hierarchy a definable non-trivial subset of $n$-c.e. degrees is established.

Keywords: computably enumerable sets, Turing degrees of unsolvability, definable relations, high degrees, major subsets.

UDC: 510.54

Received: 14.08.2013

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2014, 58:2, 64–67

Bibliographic databases:

•