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

Izv. Vyssh. Uchebn. Zaved. Mat., 2010 Number 4, Pages 3–9 (Mi ivm6720)

This article is cited in 3 papers

Isolated 2-computably enumerable $Q$-degrees

I. I. Batyrshin

Chair of Algebra and Mathematical Logic, Kazan State University, Kazan, Russia

Abstract: We demonstrate that for every pair of computably enumerable degrees $\mathbf a<_\mathbf Q\mathbf b$ there exists a properly 2-computably enumerable degree $\mathbf d$, $\mathbf a<_\mathbf Q\mathbf d<_\mathbf Q\mathbf b$, such that $\mathbf a$ isolates $\mathbf d$ from below and $\mathbf b$ isolates $\mathbf d$ from above. As a corollary we prove that there exists a 2-computably enumerable degree which is $Q$-incomparable with any nontrivial (i.e., different from $\boldsymbol0$ and $\boldsymbol0'$) computably enumerable degree, and that every nontrivial computably enumerable degree isolates some 2-computably enumerable degree from below and some 2-computably enumerable degree from above.

Keywords: computably enumerable sets, quasi-reducibility, 2-computably enumerable sets, isolated degrees.

UDC: 510.532

Received: 03.03.2008


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:4, 1–6

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024