کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662646 1633551 2006 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bounding computably enumerable degrees in the Ershov hierarchy
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Bounding computably enumerable degrees in the Ershov hierarchy
چکیده انگلیسی

Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: (1) there is a low c.e. degree isolating a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 (2002) 259–266]; (2) there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 (2006) 31–51].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 141, Issues 1–2, August 2006, Pages 79-88