Enumerations, countable structures and Turing degrees

Wehner, Stephan

doi:10.1090/S0002-9939-98-04314-7

Enumerations, countable structures and Turing degrees
HTML articles powered by AMS MathViewer

by Stephan Wehner PDF

Proc. Amer. Math. Soc. 126 (1998), 2131-2139 Request permission

Abstract:

It is proven that there is a family of sets of natural numbers which has enumerations in every Turing degree except for the recursive degree. This implies that there is a countable structure which has representations in all but the recursive degree. Moreover, it is shown that there is such a structure which has a recursively represented elementary extension.

References

C. J. Ash, C. G. Jockusch Jr., and J. F. Knight, Jumps of orderings, Trans. Amer. Math. Soc. 319 (1990), no. 2, 573–599. MR 955487, DOI 10.1090/S0002-9947-1990-0955487-0
Julia F. Knight, Degrees coded in jumps of orderings, J. Symbolic Logic 51 (1986), no. 4, 1034–1042. MR 865929, DOI 10.2307/2273915
Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723–731. MR 641486, DOI 10.2307/2273222
Theodore A. Slaman; Relative to any Nonrecursive Set, Proc. Amer. Math. Soc., vol. 126 (1998), 2117–2122.
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
Stephan Wehner, On injective enumerability of recursively enumerable classes of cofinite sets, Arch. Math. Logic 34 (1995), no. 3, 183–196. MR 1337112, DOI 10.1007/s001530050017
C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249–266. MR 241295, DOI 10.1090/S0002-9947-1969-0241295-4