AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Degree Spectra of Relations on a Cone
About this Title
Matthew Harrison-Trainor, Group in Logic and the Methodology of Science, University of California, Berkeley, California 94720
Publication: Memoirs of the American Mathematical Society
Publication Year:
2018; Volume 253, Number 1208
ISBNs: 978-1-4704-2839-6 (print); 978-1-4704-4411-2 (online)
DOI: https://doi.org/10.1090/memo/1208
Published electronically: March 29, 2018
Keywords: computable structure,
degree spectrum of a relation,
cone of Turing degrees
MSC: Primary 03D45, 03C57
Table of Contents
Chapters
- 1. Introduction
- 2. Preliminaries
- 3. Degree Spectra between the C.E. Degrees and the D.C.E. Degrees
- 4. Degree Spectra of Relations on the Naturals
- 5. A “Fullness” Theorem for 2-CEA\xspace Degrees
- 6. Further Questions
- A. Relativizing Harizanov’s Theorem on C.E. Degrees
Abstract
Let $\mathcal {A}$ be a mathematical structure with an additional relation $R$. We are interested in the degree spectrum of $R$, either among computable copies of $\mathcal {A}$ when $(\mathcal {A},R)$ is a “natural” structure, or (to make this rigorous) among copies of $(\mathcal {A},R)$ computable in a large degree d. We introduce the partial order of degree spectra on a cone and begin the study of these objects. Using a result of Harizanov—that, assuming an effectiveness condition on $\mathcal {A}$ and $R$, if $R$ is not intrinsically computable, then its degree spectrum contains all c.e. degrees—we see that there is a minimal non-trivial degree spectrum on a cone, consisting of the c.e. degrees. We show that this does not generalize to d.c.e. degrees by giving an example of two incomparable degree spectra on a cone. We also give a partial answer to a question of Ash and Knight: they asked whether (subject to some effectiveness conditions) a relation which is not intrinsically $\Delta ^0_\alpha$ must have a degree spectrum which contains all of the $\alpha$-CEA degrees. We give a positive answer to this question for $\alpha = 2$ by showing that any degree spectrum on a cone which strictly contains the $\Delta ^0_2$ degrees must contain all of the 2-CEA degrees. We also investigate the particular case of degree spectra on the structure $(\omega ,<)$. This work represents the beginning of an investigation of the degree spectra of “natural” structures, and we leave many open questions to be answered.- C. J. Ash and J. F. Knight, Possible degrees in recursive copies, Ann. Pure Appl. Logic 75 (1995), no. 3, 215–221. MR 1355133, DOI 10.1016/0168-0072(94)00043-3
- Christopher J. Ash and Julia F. Knight, Recursive structures and Ershov’s hierarchy, Math. Logic Quart. 42 (1996), no. 4, 461–468. MR 1417841, DOI 10.1002/malq.19960420138
- C. J. Ash and J. F. Knight, Possible degrees in recursive copies. II, Ann. Pure Appl. Logic 87 (1997), no. 2, 151–165. Logic Colloquium ’95 Haifa. MR 1490052, DOI 10.1016/S0168-0072(96)00026-7
- C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
- Chris Ash, Julia Knight, Mark Manasse, and Theodore Slaman, Generic copies of countable structures, Ann. Pure Appl. Logic 42 (1989), no. 3, 195–205. MR 998606, DOI 10.1016/0168-0072(89)90015-8
- C. J. Ash and A. Nerode, Intrinsically recursive relations, Aspects of effective algebra (Clayton, 1979) Upside Down A Book Co., Yarra Glen, Vic., 1981, pp. 26–41. MR 629248
- E. Barker, Intrinsically $\Sigma ^0_\alpha$ relations, Ann. Pure Appl. Logic 39 (1988), no. 2, 105–130. MR 955520, DOI 10.1016/0168-0072(88)90014-0
- John Chisholm, Effective model theory vs. recursive model theory, J. Symbolic Logic 55 (1990), no. 3, 1168–1191. MR 1071322, DOI 10.2307/2274481
- R. Downey, B. Khoussianov, J. Miller, and L. Yu, Degree spectra of unary relations on $(\omega ,<)$, proceedings of the International Congress in Logic, Methodology and Philosophy of Science, Beijing, 2007 (2009), 36–55.
- Richard L. Epstein, Richard Haas, and Richard L. Kramer, Hierarchies of sets and degrees below ${\bf 0}^{\prime }$, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin, 1981, pp. 32–48. MR 619859
- Ju. L. Eršov, A certain hierarchy of sets. I, Algebra i Logika 7 (1968), no. 1, 47–74 (Russian). MR 0270911
- Ju. L. Eršov, A certain hierarchy of sets. II, Algebra i Logika 7 (1968), no. 4, 15–47 (Russian). MR 0270912
- Ju. L. Eršov, A certain hierarchy of sets. III, Algebra i Logika 9 (1970), 34–51 (Russian). MR 0299478
- S. S. Goncharov and B. Khusainov, On the spectrum of the degrees of decidable relations, Dokl. Akad. Nauk 352 (1997), no. 3, 301–303 (Russian). MR 1445858
- David Gale and F. M. Stewart, Infinite games with perfect information, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, N. J., 1953, pp. 245–266. MR 0054922
- Valentina S. Harizanov, DEGREE SPECTRUM OF A RECURSIVE RELATION ON A RECURSIVE STRUCTURE, ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)–The University of Wisconsin - Madison. MR 2635809
- Valentina S. Harizanov, Some effects of Ash-Nerode and other decidability conditions on degree spectra, Ann. Pure Appl. Logic 55 (1991), no. 1, 51–65. MR 1134916, DOI 10.1016/0168-0072(91)90097-6
- Valentina S. Harizanov, The possible Turing degree of the nonzero member in a two element degree spectrum, Ann. Pure Appl. Logic 60 (1993), no. 1, 1–30. MR 1212405, DOI 10.1016/0168-0072(93)90190-O
- Denis R. Hirschfeldt, Degree spectra of relations on computable structures, Bull. Symbolic Logic 6 (2000), no. 2, 197–212. MR 1781623, DOI 10.2307/421207
- Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
- Julia F. Knight, Degrees coded in jumps of orderings, J. Symbolic Logic 51 (1986), no. 4, 1034–1042. MR 865929, DOI 10.2307/2273915
- J. F. Knight, Coding a family of sets, Ann. Pure Appl. Logic 94 (1998), no. 1-3, 127–142. Conference on Computability Theory (Oberwolfach, 1996). MR 1640266, DOI 10.1016/S0168-0072(97)00070-5
- C. Knoll, Degree spectra of unary relations on $\omega$ and $\zeta$, Master’s thesis, University of Waterloo, 2009.
- Joseph B. Kruskal, The theory of well-quasi-ordering: A frequently discovered concept, J. Combinatorial Theory Ser. A 13 (1972), 297–305. MR 306057, DOI 10.1016/0097-3165(72)90063-5
- Bakhadyr Khoussainov and Richard A. Shore, Computable isomorphisms, degree spectra of relations, and Scott families, Ann. Pure Appl. Logic 93 (1998), no. 1-3, 153–193. Computability theory. MR 1635605, DOI 10.1016/S0168-0072(97)00059-6
- Donald A. Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968), 687–689. MR 227022, DOI 10.1090/S0002-9904-1968-11995-0
- Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
- Ch. F. D. Mak-koĭ, On $\Delta ^0_3$-categoricity for linear orders and Boolean algebras, Algebra Logika 41 (2002), no. 5, 531–552, 633 (Russian, with Russian summary); English transl., Algebra Logic 41 (2002), no. 5, 295–305. MR 1953178, DOI 10.1023/A:1020927703492
- Timothy H. McNicholl, Intrinsic reducibilities, MLQ Math. Log. Q. 46 (2000), no. 3, 393–407. MR 1774681, DOI 10.1002/1521-3870(200008)46:3<393::AID-MALQ393>3.0.CO;2-H
- Antonio Montalbán, Notes on the jump of a structure, Mathematical theory and computational practice, Lecture Notes in Comput. Sci., vol. 5635, Springer, Berlin, 2009, pp. 372–378. MR 2545911, DOI 10.1007/978-3-642-03073-4_{3}8
- Dana Scott, Logic with denumerably long formulas and finite strings of quantifiers, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 329–341. MR 0200133
- Theodore A. Slaman, Aspects of the Turing jump, Logic Colloquium 2000, Lect. Notes Log., vol. 19, Assoc. Symbol. Logic, Urbana, IL, 2005, pp. 365–382. MR 2143887
- Theodore A. Slaman and John R. Steel, Definable functions on degrees, Cabal Seminar 81–85, Lecture Notes in Math., vol. 1333, Springer, Berlin, 1988, pp. 37–55. MR 960895, DOI 10.1007/BFb0084969
- John R. Steel, A classification of jump operators, J. Symbolic Logic 47 (1982), no. 2, 347–358. MR 654792, DOI 10.2307/2273146
- Matthew Wright, Computability and structures, ProQuest LLC, Ann Arbor, MI, 2013. Thesis (Ph.D.)–The University of Chicago. MR 3167353