|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2014, Number 2, Pages 77–81
(Mi ivm8875)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Received: 14.08.2013
Citation:
M. M. Arslanov, “Definable relations in structures of Turing degrees”, Izv. Vyssh. Uchebn. Zaved. Mat., 2014, no. 2, 77–81; Russian Math. (Iz. VUZ), 58:2 (2014), 64–67
Linking options:
https://www.mathnet.ru/eng/ivm8875 https://www.mathnet.ru/eng/ivm/y2014/i2/p77
|
Statistics & downloads: |
Abstract page: | 254 | Full-text PDF : | 63 | References: | 52 | First page: | 16 |
|