|
On the degree spectrum of a class
Author(s):
Thomas
Kent;
Andrew
E. M.
Lewis
Journal:
Trans. Amer. Math. Soc.
362
(2010),
5283-5319.
MSC (2010):
Primary 03D28
Posted:
May 4, 2010
MathSciNet review:
2657680
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
For any , define , the degree spectrum of , to be the set of all Turing degrees such that there exists of degree . We prove a number of basic properties of the structure which is the degree spectra of classes ordered by inclusion and also study in detail some other phenomena relating to the study of classes from a degree theoretic point of view, which are brought to light as a result of this analysis.
References:
-
- [DC]
- D. Cenzer,
classes, in the Handbook of Computability Theory, Studies in logic and the foundations of mathematics, vol 140, Elsevier, 1999. - [CS]
- D. Cenzer and R. Smith, The ranked points of a
set, Journal of Symbolic Logic, 54, pp. 975-991, 1989. MR 1011184 (90j:03090) - [CCS]
- D. Cenzer, P. Clote, R. Smith, R. Soare and S. Wainer, Members of countable
classes, Annals of Pure and Applied Logic, 31, pp. 145-163, 1986. MR 854290 (88e:03064) - [CC]
- P. Cholak, R. Coles, R. Downey and E. Herrmann, Automorphisms of the lattice of
classes; perfect thin classes and ANC degrees, Transactions of the American Mathematical Society, 353 (12), pp. 4899-4924, 2001. MR 1852086 (2002f:03080) - [SC]
- J. Cole and S. Simpson, Mass problems and hyperarithmeticity, Journal of Mathematical Logic, 7, issue 2, pp. 125-143, 2007. MR 2423947 (2009d:03099)
- [BC]
- S.B. Cooper, Computability Theory, Chapman & Hall, CRC Press, Boca Raton, FL, New York, London (2004). MR 2017461 (2005h:03001)
- [OD]
- O. Demuth, Remarks on the structure of tt-degrees based on constructive measure theory, Comment. Math. Carolinae, 29, pp. 233-247, 1988. MR 957390 (89k:03049)
- [RD]
- R. Downey, On
classes and their ranked points, Notre Dame Journal of Formal Logic, 32, pp. 499-512, 1991. MR 1146607 (93a:03046) - [DH]
- R. Downey and D. Hirschfeldt, Algorithmic Randomness and Complexity, monograph in preparation.
- [JM]
- C. Jockusch and T. McLaughlin, Countable retracing functions and
predicates, Pacific J. Math., 30, pp. 67-93, 1969. MR 0269508 (42:4403) - [JS1]
- C. Jockusch and R. Soare,
classes and degrees of theories, Transactions of the American Mathematical Society, 173, pp. 33-56, 1972. MR 0316227 (47:4775) - [JS2]
- C. Jockusch and R. Soare, Degrees of members of
classes, Pacific Journal of Mathematics, 40, pp. 605-616, 1972. MR 0309722 (46:8827) - [SK]
- S. Kleene, Recursive predicates and quantifiers, Transactions of the American Mathematical Society, 53, pp. 41-73, 1943. MR 0007371 (4:126b)
- [KP]
- S. Kripke and M.B Pour-El, Deduction-preserving ``recursive isomorphisms'' between theories, Bulletin of the American Mathematical Society, 73, pp. 145-148, 1967. MR 0215713 (35:6548)
- [AK]
- A. Kucera, Measure,
classes and complete extensions of PA, in Recursion Theory Week (Proceedings Oberwolfach 1984), Lecture Notes in Mathematics, vol 1141, pp. 245-259, 1985. MR 820784 (87e:03102) - [AL]
- A.E.M. Lewis,
classes, strong minimal covers and hyperimmune-free degrees, Bull. Lond. Math. Soc., 39, pp. 892-910, 2007. MR 2392813 (2009b:03113) - [MP]
- D. Martin and M.B. Pour-El, Axiomatixable theories with few axiomatizable extensions, Journal of Symbolic Logic, 35 (2), pp. 205-209, 1970. MR 0280374 (43:6094)
- [AN]
- A. Nies, Computability and Randomness, monograph in preparation.
- [HP]
- M.G. Peretyakin, Finitely Axiomatizable Theories, Scientific Books, ISBN 0-306-11062-8.
- [FS]
- F. Stephan, Martin-Löf random and PA-complete sets. (TR 58) ASL Lecture Notes in Logic, 27, pp. 342-348, 2006. MR 2258714 (2007h:03088)
- [SS]
- S. Simpson, An extension of the recursively enumerable Turing degrees, Journal of the London Mathematical Society, 75, pp. 287-297, 2007. MR 2340228 (2008d:03041)
- [SS2]
- S. Simpson, Mass problems and randomness, Bulletin of Symbolic Logic, 11, pp. 1-27, 2005. MR 2125147 (2005k:03097)
Similar Articles:
Retrieve articles in Transactions of the American Mathematical
Society
with
MSC (2010):
03D28
Retrieve articles in all Journals with
MSC (2010):
03D28
Additional Information:
Thomas
Kent
Affiliation:
Department of Mathematics, Marywood University, Scranton, Pennsylvania 18509
Email:
tfkent@marywood.edu
Andrew
E. M.
Lewis
Affiliation:
Department of Mathematics, University of Leeds, Leeds, England LS2 9JT
Email:
aemlewis@aemlewis.co.uk
DOI:
10.1090/S0002-9947-10-05037-3
PII:
S 0002-9947(10)05037-3
Keywords:
$\Pi ^0_1$ classes
Received by editor(s):
June 13, 2008
Posted:
May 4, 2010
Additional Notes:
The first author was supported by Marie-Curie Fellowship MIFI-CT-2006-021702.
The second author was supported by a Royal Society University Research Fellowship.
Copyright of article:
Copyright
2010,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|