THE n-r.e. DEGREES: UNDECIDABILITY AND Σ1 SUBSTRUCTURES

被引：3

作者：

Cai, Mingzhong ^{[1
]}

Shore, Richard A. ^{[2
]}

Slaman, Theodore A. ^{[3
]}

机构：

[1] Univ Wisconsin, Dept Math, Madison, WI 53706 USA

[2] Cornell Univ, Dept Math, Ithaca, NY 14853 USA

[3] Univ Calif Berkeley, Dept Math, Berkeley, CA 94720 USA

来源：

JOURNAL OF MATHEMATICAL LOGIC | 2012年 / 12卷 / 01期

基金：

美国国家科学基金会;

关键词：

Turing degree; n-recursively enumerable; undecidability; Sigma(1)-substructure; DRE DEGREES;

D O I：

10.1142/S0219061312500055

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study the global properties of D-n, the Turing degrees of the n-r.e. sets. In Theorem 1.5, we show that the first order of D-n is not decidable. In Theorem 1.6, we show that for any two n and m with n < m, D-n is not a Sigma(1)-substructure of D-m.

引用

页数：30

共 50 条

[31] INITIAL SEGMENTS OF THE R.E. TT-DEGREES
HAUGHT, C
SHORE, R
JOURNAL OF SYMBOLIC LOGIC, 1988, 53 (03) : 1000 - 1001
[32] Medvedev Degrees of Generalized R.E. separating Classes
Cenzer, Douglas
Hinman, Peter G.
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2007, 167 : 203 - 223
[33] E-r-pH and E-r-m(KOH) diagrams for nickel at 25 degrees C
Balej, J
Divisek, J
COLLECTION OF CZECHOSLOVAK CHEMICAL COMMUNICATIONS, 1997, 62 (05) : 696 - 708
[34] The weak density of properly d-r.e. branching degree in the d-r.e. degrees
Hong Lu
Decheng Ding
Science in China Series A: Mathematics, 1999, 42 : 691 - 698
[35] The weak density of properly d-r.e. branching degree in the d-r.e. degrees
Lu, H
Ding, DC
SCIENCE IN CHINA SERIES A-MATHEMATICS PHYSICS ASTRONOMY, 1999, 42 (07): : 691 - 698
[36] Weak density of properly d-r.e. branching degree in the d-r.e. degrees
Sci China Ser A, 7 (691-698):
[37] (1R,2R,E,E)-N,N′-Bis(4-chlorobenzylidene)cyclohexane-1,2-diamine
Arvinnezhad, Hamid
Jadidi, Khosrow
Notash, Behrouz
ACTA CRYSTALLOGRAPHICA SECTION E-STRUCTURE REPORTS ONLINE, 2012, 68 : O407 - U686
[38] ENERGETICS OF THE KUROSHIO EXTENSION AT 35-DEGREES-N, 152-DEGREES-E
HALL, MM
JOURNAL OF PHYSICAL OCEANOGRAPHY, 1991, 21 (07) : 958 - 975
[39] IS (N/R)/NR LESS THAN (N+1/R)/(N+1)R
FOX, EW
NG, BY
COLLEGE MATHEMATICS JOURNAL, 1984, 15 (02): : 168 - 168
[40] The weak density of properly d-r. e. branching degree in the d-r.e. degrees
陆宏
丁德成
Science China Mathematics, 1999, (07) : 691 - 698

← 1 2 3 4 5 →