On Elementary Di®erences Among Jump Classes

Yang Yue

Abstract


We review recent developments in the study of jump classes in com- putably enumerable degrees, with special emphasis on the elementary di®er- ences among the jump classes.

Keywords


Computably enumerable degrees; jump classes

Full Text:

PDF

References


M. Bickford and C. F. Mills. Lowness properties of r.e. degrees. Unpublished preprint, 1982.

Peter Cholak, Marcia Groszek, and Theodore A. Slaman. An almost deep degree. J. Symbolic Logic, 66(2):881{901, 2001.

Peter A. Cholak, Ste®en Lempp, Manuel Lerman, and Richard A. Shore, editors. Computability Theory and Its Applications: Current Trends and Open Problems, volume 257 of Contemporary Mathematics, Providence, RI, 2000. American Mathematical Society.

Peter A. Fejer and Robert I. Soare. The plus-cupping theorem for the recur- sively enumerable degrees. In Logic Year 1979{80: University of Connecticut, pages 49{62, 1981.

R. M. Friedberg. Two recursively enumerable sets of incomparable degrees of unsolvability (solution to post's problem, 1944). Proc. Nat. Acad. Sci. U.S.A., 43:236{238, 1957.

Edward R. Gri®or, editor. Handbook of Computability Theory, volume 140 of Studies in Logic and the Foundations of Mathematics. North-Holland Pub- lishing Co., Amsterdam, 1999.

Leo A. Harrington. Plus-cupping in the recursively enumerable degrees. notes, 1978.

Carl G. Jockusch, Jr., Angsheng Li, and Yue Yang. A join theorem for the computably enumerable degrees. Trans. Amer. Math. Soc., 356:2557{2568, 2004.

Alistair H. Lachlan. A recursively enumerable degree which will not split over all lesser ones. Ann. Math. Logic, 9:307{365, 1975.

Angsheng Li. Elementary di®erences among jump hierarchies. to appear.

A. A. Muchnik. On the unsolvability of the problem of reducibility in the theory of algorithms. Dokl. Akad. Nauk SSSR, N. S. 108:194{197, 1956.

Andre Nies, Richard A. Shore, and Theodore A. Slaman. Interpretability and de¯nability in the recursively enumerable degrees. Proc. London Math. Soc. (3), 77(2):241{291, 1998.

David B. Posner and Robert W. Robinson. Degrees joining to 0. J. Symbolic Logic, 46(4):714-722, 1981.

Emil L. Post. Recursively enumerable sets of positive integers and their deci- sion problems. Bull. Amer. Math. Soc., 50:284-316, 1944.

R. W. Robinson. Interpolation and embedding in the recursively enumerable degrees. Ann. of Math., 93:285{314, 1971.

Richard A. Shore. The Low n and Low m r.e. degrees are not elementarily equivalent. to appear.

Richard A. Shore and Theodore A. Slaman. Working below a low 2 recursively enumerably degree. Arch. Math. Logic, 29(3):201-211, 1990.

Richard A. Shore and Theodore A. Slaman. Working below a high recursively enumerable degree. J. Symbolic Logic, 58(3):824-859, 1993.

Richard A. Shore and Theodore A. Slaman. De¯ning the Turing jump. Math. Res. Lett., 6(5-6):711-722, 1999.

Robert I. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag, Heidelberg, 1987.

Alan M. Turing. On computable numbers with an application to the Entschei- dungsproblem. Proc. London Math. Soc. (3), 42:230{265, 1936. A correction, 43:544{546.




DOI: http://dx.doi.org/10.12962/j1829605X.v1i2.1356

Refbacks

  • There are currently no refbacks.


Jumlah Kunjungan:

Creative Commons License
Limits: Journal Mathematics and its Aplications by Pusat Publikasi Ilmiah LPPM Institut Teknologi Sepuluh Nopember is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://iptek.its.ac.id/index.php/limits.