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 条

[1] Undecidability of the structure of the Solovay degrees of c.e. reals
Downey, Rod
Hirschfeldt, Denis R.
LaForte, Geoff
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2007, 73 (05) : 769 - 787
[2] Undecidability and 1-types in intervals of the computably enumerable degrees
Ambos-Spies, K
Hirschfeldt, DR
Shore, RA
ANNALS OF PURE AND APPLIED LOGIC, 2000, 106 (1-3) : 1 - 47
[3] UNDECIDABILITY AND 1-TYPES IN THE RECURSIVELY-ENUMERABLE DEGREES
AMBOSSPIES, K
SHORE, RA
ANNALS OF PURE AND APPLIED LOGIC, 1993, 63 (01) : 3 - 37
[4] On the r.e. predecessors of d.r.e. degrees
Ishmukhametov, S
ARCHIVE FOR MATHEMATICAL LOGIC, 1999, 38 (06) : 373 - 386
[5] On the r.e. predecessors of d.r.e. degrees
Shamil Ishmukhametov
Archive for Mathematical Logic, 1999, 38 : 373 - 386
[6] CONTIGUOUS R.E. DEGREES
AMBOSSPIES, K
LECTURE NOTES IN MATHEMATICS, 1984, 1104 : 1 - 37
[7] AN IDENTITY FOR R(N) EMBEDDED INTO E(N+1)
GONZALEZ, G
LOPEZBONILLA, JL
ROSALES, MA
PRAMANA-JOURNAL OF PHYSICS, 1994, 42 (02): : 85 - 88
[8] Racah algebra R(n) from coalgebraic structures and chains of R(3) substructures
Latini, Danilo
Marquette, Ian
Zhang, Yao-Zhong
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2021, 54 (39)
[9] Cupping the recursively enumerable degrees by d.r.e. degrees
Li, AS
Yi, XD
PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 1999, 79 : 1 - 21
[10] DIFFICULTY OF SPLITTING R-E DEGREES
LACHLAN, AH
NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1971, 18 (07): : 1087 - &

← 1 2 3 4 5 →