RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2022 Number 11, Pages 124–131 (Mi ivm9832)

This article is cited in 1 paper

Brief communications

Nonuniformity of downwards density in the $n$-computably enumerable Turing degrees

A. I. Talipova, M. M. Yamaleev

Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia

Abstract: In 1993 R. Downey and M. Stob showed that downwards density of computably enumerable (further, c.e.) Turing degrees in the partial order of $2$-c.e. Turing degrees cannot be proved by a uniform construction. In this paper their result is generalized for any $n > 2$ and it is shown that there is no a uniform consruction for the downwards denstiy of $(n-1)$-c.e. degrees in the structure of $n$-c.e. degrees. Moreover, it is shown that there is no a uniform construction for the downwards denstiy in the structure of $n$-c.e. degrees.

Keywords: Turing degree, uniform construction, the Ershov hierarchy, downwards density.

UDC: 510.532

Received: 27.09.2022
Revised: 27.09.2022
Accepted: 28.09.2022

DOI: 10.26907/0021-3446-2022-11-124-131


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2022, 66:11, 110–115


© Steklov Math. Inst. of RAS, 2025