Degree spectra of relations on a cone. (English) Zbl 1435.03005
Memoirs of the American Mathematical Society 1208. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-4704-2839-6/print; 978-1-4704-4411-2/ebook). vi, 112 p. (2018).
Publisher’s description: 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.
MSC:
| 03-02 | Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations |
| 03D45 | Theory of numerations, effectively presented structures |
| 03C57 | Computable structure theory, computable model theory |
References:
| [1] | Ash, C. J.; Knight, J. F., Possible degrees in recursive copies, Ann. Pure Appl. Logic, 75, 3, 215-221 (1995) · Zbl 0837.03036 · doi:10.1016/0168-0072(94)00043-3 |
| [2] | Ash, Christopher J.; Knight, Julia F., Recursive structures and Ershov’s hierarchy, Math. Logic Quart., 42, 4, 461-468 (1996) · Zbl 0863.03018 · doi:10.1002/malq.19960420138 |
| [3] | Ash, C. J.; Knight, J. F., Possible degrees in recursive copies. II, Ann. Pure Appl. Logic, 87, 2, 151-165 (1997) · Zbl 0877.03022 · doi:10.1016/S0168-0072(96)00026-7 |
| [4] | C. J. Ash and J. F. 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 (2001k:03090)} · Zbl 0960.03001 |
| [5] | Ash, Chris; Knight, Julia; Manasse, Mark; Slaman, Theodore, Generic copies of countable structures, Ann. Pure Appl. Logic, 42, 3, 195-205 (1989) · Zbl 0678.03012 · doi:10.1016/0168-0072(89)90015-8 |
| [6] | Ash, C. J.; Nerode, A., Intrinsically recursive relations. Aspects of effective algebra, Clayton, 1979, 26-41 (1981), Upside Down A Book Co., Yarra Glen, Vic. · Zbl 0467.03041 |
| [7] | Barker, E., Intrinsically \(\Sigma^0_\alpha\) relations, Ann. Pure Appl. Logic, 39, 2, 105-130 (1988) · Zbl 0651.03034 · doi:10.1016/0168-0072(88)90014-0 |
| [8] | Chisholm, John, Effective model theory vs.recursive model theory, J. Symbolic Logic, 55, 3, 1168-1191 (1990) · Zbl 0722.03030 · doi:10.2307/2274481 |
| [9] | R. Downey, B. Khoussianov, J. Miller, and L. Yu, Degree spectra of unary relations on \((,<)\), proceedings of the International Congress in Logic, Methodology and Philosophy of Science, Beijing, 2007 (2009), 36-55. · Zbl 1419.03038 |
| [10] | Epstein, Richard L.; Haas, Richard; Kramer, Richard L., Hierarchies of sets and degrees below \({\bf0}^{\prime} \). Logic Year 1979-80, Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80, Lecture Notes in Math. 859, 32-48 (1981), Springer, Berlin · Zbl 0467.03046 |
| [11] | Er{\v{s}}ov, Ju. L., A certain hierarchy of sets. I, Algebra i Logika, 7, 1, 47-74 (1968) · Zbl 0216.00901 |
| [12] | Er{\v{s}}ov, Ju. L., A certain hierarchy of sets. II, Algebra i Logika, 7, 4, 15-47 (1968) · Zbl 0216.00902 |
| [13] | Er{\v{s}}ov, Ju. L., A certain hierarchy of sets. III, Algebra i Logika, 9, 34-51 (1970) |
| [14] | Goncharov, S. S.; Khusainov, B., On the spectrum of the degrees of decidable relations, Dokl. Akad. Nauk, 352, 3, 301-303 (1997) · Zbl 0961.03032 |
| [15] | Gale, David; Stewart, F. M., Infinite games with perfect information. Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, 245-266 (1953), Princeton University Press, Princeton, N. J. · Zbl 0050.14305 |
| [16] | Harizanov, Valentina S., DEGREE SPECTRUM OF A RECURSIVE RELATION ON A RECURSIVE STRUCTURE, 95 pp. (1987), ProQuest LLC, Ann Arbor, MI |
| [17] | Harizanov, Valentina S., Some effects of Ash-Nerode and other decidability conditions on degree spectra, Ann. Pure Appl. Logic, 55, 1, 51-65 (1991) · Zbl 0756.03022 · doi:10.1016/0168-0072(91)90097-6 |
| [18] | Harizanov, Valentina S., The possible Turing degree of the nonzero member in a two element degree spectrum, Ann. Pure Appl. Logic, 60, 1, 1-30 (1993) · Zbl 0773.03027 · doi:10.1016/0168-0072(93)90190-O |
| [19] | Hirschfeldt, Denis R., Degree spectra of relations on computable structures, Bull. Symbolic Logic, 6, 2, 197-212 (2000) · Zbl 0968.03038 · doi:10.2307/421207 |
| [20] | Jech, Thomas, Set theory, Springer Monographs in Mathematics, xiv+769 pp. (2003), Springer-Verlag, Berlin · Zbl 1007.03002 |
| [21] | Knight, Julia F., Degrees coded in jumps of orderings, J. Symbolic Logic, 51, 4, 1034-1042 (1986) · Zbl 0633.03038 · doi:10.2307/2273915 |
| [22] | Knight, J. F., Coding a family of sets, Ann. Pure Appl. Logic, 94, 1-3, 127-142 (1998) · Zbl 0924.03083 · doi:10.1016/S0168-0072(97)00070-5 |
| [23] | C. Knoll, Degree spectra of unary relations on \[and \], Master’s thesis, University of Waterloo, 2009. |
| [24] | Kruskal, Joseph B., The theory of well-quasi-ordering: A frequently discovered concept, J. Combinatorial Theory Ser. A, 13, 297-305 (1972) · Zbl 0244.06002 |
| [25] | Khoussainov, Bakhadyr; Shore, Richard A., Computable isomorphisms, degree spectra of relations, and Scott families, Ann. Pure Appl. Logic, 93, 1-3, 153-193 (1998) · Zbl 0927.03072 · doi:10.1016/S0168-0072(97)00059-6 |
| [26] | Martin, Donald A., The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc., 74, 687-689 (1968) · Zbl 0165.31605 |
| [27] | Martin, Donald A., Borel determinacy, Ann. of Math. (2), 102, 2, 363-371 (1975) · Zbl 0336.02049 |
| [28] | Mak-ko{\u\i}, Ch. F. D., On \(\Delta^0_3\)-categoricity for linear orders and Boolean algebras, Algebra Logika. Algebra Logic, 41 41, 5, 295-305 (2002) · Zbl 1008.03023 · doi:10.1023/A:1020927703492 |
| [29] | McNicholl, Timothy H., Intrinsic reducibilities, MLQ Math. Log. Q., 46, 3, 393-407 (2000) · Zbl 0973.03060 · doi:10.1002/1521-3870(200008)46:\(3\langle393\)::AID-MALQ |
| [30] | Montalb{\'a}n, Antonio, Notes on the jump of a structure. Mathematical theory and computational practice, Lecture Notes in Comput. Sci. 5635, 372-378 (2009), Springer, Berlin · Zbl 1268.03043 · doi:10.1007/978-3-642-03073-4\_38 |
| [31] | Scott, Dana, Logic with denumerably long formulas and finite strings of quantifiers. Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), 329-341 (1965), North-Holland, Amsterdam · Zbl 0166.26003 |
| [32] | Slaman, Theodore A., Aspects of the Turing jump. Logic Colloquium 2000, Lect. Notes Log. 19, 365-382 (2005), Assoc. Symbol. Logic, Urbana, IL · Zbl 1086.03032 |
| [33] | Slaman, Theodore A.; Steel, John R., Definable functions on degrees. Cabal Seminar 81-85, Lecture Notes in Math. 1333, 37-55 (1988), Springer, Berlin · Zbl 0677.03038 · doi:10.1007/BFb0084969 |
| [34] | Steel, John R., A classification of jump operators, J. Symbolic Logic, 47, 2, 347-358 (1982) · Zbl 0524.03029 · doi:10.2307/2273146 |
| [35] | Wright, Matthew, Computability and structures, 76 pp. (2013), ProQuest LLC, Ann Arbor, MI |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
