The lown and lowm r.e. Degrees are not elementarily equivalent

摘要

［1］Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proc. Lon. Math.Soc. (2), 1936, 42: 230-265.［2］Turing, A. M., Systems of logic based on ordinals, Proc. Lon. Math. Soc. (2), 1939, 45: 161-228.［3］Post, E. L., Finite combinatory processes-formulation, J. Symb. Logic, 1936, 1: 103-105.［4］Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bull. Am. Math. Soc.,1944, 50: 284-316.［5］Friedberg, R. M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Ac.Sci., 1957, 43: 236-238.［6］Muchnik, A. A., On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad.Nauk SSSR, N. S., 1956, 108: 29-32.［7］Shore, R. A., The recursively enumerable degrees, in Handbook of Computaility Theory (ed. Griffor, E. R.),Amsterdam: Elsevier, 1999, 169-198.［8］Nies, A., Shore, R. A., Slaman, T A., Interpretability and definability in the recursively enumerable degrees,Proc. Lon. Math. Soc. (3), 1998, 77: 241-291.［9］Jouckusch, C. G. Jr., Li, A., Yang, Y., A join theorem for the computably enumerable degrees, Trans. Am. Math.Soc., 2004, 356: 2557-2568.［10］Cholak, P., Groszek, M., Slaman, T. A., An almost deep degree, J. Symb. Logic, 2001, 66: 881-901.［11］Shore, R. A., Slaman T. A., Working below a high recursively enumerable degree, J. Symb. Logic, 1993, 58:824-859.［12］Shore, R. A., Slaman T. A., Working below a low2 recursively enumerable degree, Archive for Math. Logic,1990, 29: 201-211.［13］Li, A., Elementary differences among jump hierarchies, preprint.［14］Li, A., Definable relations on the computably enumerable degrees, in Computability and Models (eds. Cooper,S. B., Goncharov, S. S.), New York: Kluwer Academic/Plenum Publishers, 2003, 267-288.［15］Hodges, W., Model Theory, Cambridge: Cambridge University Press, 1993,［16］Sacks, G. E., Recursive enumerability and the jump operator, Trans. Am. Math. Soc., 1963, 108: 223-239.［17］Soare, R. I., Recursively Enumerable Sets and Degrees, Berlin: Springer-Verlag, 1987.［18］Robinson, R. W., Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2), 1971,93: 285-314.