Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-17T09:41:20.408Z Has data issue: false hasContentIssue false
  • English
  • Français

Degree Structures: Local and Global Investigations

Published online by Cambridge University Press:  15 January 2014

Richard A. Shore
Richard A. Shore*
Affiliation:
Department of Mathematics, Cornell University, Ithaca Ny 14853, USAE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

The occasion of a retiring presidential address seems like a time to look back, take stock and perhaps look ahead.

Institutionally, it was an honor to serve as President of the Association and I want to thank my teachers and predecessors for guidance and advice and my fellow officers and our publisher for their work and support. To all of the members who answered my calls to chair or serve on this or that committee, I offer my thanks as well. Your work was both needed and appreciated.

A major component of the efforts of the Association is devoted to our publications. My first important task as President was to deal with the need to reorganize the reviews section of the JSL and eventually to move it to the BSL. Appropriately enough, my first administrative job for the Association, some thirty years ago, was to serve on a committee to plan a reorganization of the reviews. I thank all those who helped with this transition and who took over the task of running the new reviews section. I hope that it will be another thirty years before further major changes are needed in this area and that someone else will be making them.

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 12 , Issue 3 , September 2006 , pp. 369 - 389
Copyright
Copyright © Association for Symbolic Logic 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Abraham, U. and Shore, R. A. [1986], Initial segments of the Turing degrees of size ℵ1 , Israel Journal of Mathematics, vol. 55, pp. 1–51.Google Scholar
Ambos-Spies, K., Jockusch, C. G. Jr., Shore, R. A., and Soare, R. I. [1984], An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Transactions of the American Mathematical Society, vol. 281, pp. 109–128.Google Scholar
Ambos-Spies, K., Lempp, S., and Lerman, M. [1994a], Lattice embeddings into the r.e. degrees preserving 0 and 1, Journal of the London Mathematical Society. Second Series, vol. 49, pp. 1–15.Google Scholar
Ambos-Spies, K., Lempp, S., and Lerman, M. [1994b], Lattice embeddings into the r.e. degrees preserving 1, Logic, methodology and philosophy of science, IX (Uppsala, 1991), Studies in Logic and the Foundations of Mathematics., vol. 134, North-Holland, Amsterdam, pp. 179–198.Google Scholar
Ambos-Spies, K. and Lerman, M. [1986], Lattice embeddings into the recursively enumerable degrees, The Journal of Symbolic Logic, vol. 51, pp. 257–272.Google Scholar
Ambos-Spies, K. and Lerman, M. [1989], Lattice embeddings into the recursively enumerable degrees. II, The Journal of Symbolic Logic, vol. 54, no. 3, pp. 735–760.Google Scholar
Ambos-Spies, K. and Shore, R. A. [1993], Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic, vol. 63, pp. 3–37.Google Scholar
Ambos-Spies, K. and Soare, R. I. [1989], The recursively enumerable degrees have infinitely many one-types, Annals of Pure and Applied Logic, vol. 44, pp. 1–23.Google Scholar
Cooper, S. B. [1973], Minimal degrees and the jump operator, The Journal of Symbolic Logic, vol. 38, pp. 249–271.Google Scholar
Cooper, S. B. [1990], The jump is definable in the structure of the degrees of unsolvability (research announcement), American Mathematical Society. Bulletin. New Series, vol. 23, pp. 151–158.Google Scholar
Cooper, S. B. [1993], On a conjecture of Kleene and Post, University of Leeds, Department of Pure Mathematics Preprint Series, No. 7.Google Scholar
Cooper, S. B. [1997a], Beyond Gödel's theorem: the failure to capture information content, Complexity, logic, and recursion theory (Sorbi, A., editor), Lecture Notes in Pure and Applied Mathematics, vol. 187, Dekker, New York, pp. 93–122.Google Scholar
Cooper, S. B. [1997b], The Turing Universe is not rigid, Technical report, University of Leeds, Department of Pure Mathematics Preprint Series, No. 16.Google Scholar
Cooper, S. B. [2001], On a conjecture of Kleene and Post, Mathematical Logic Quarterly, vol. 47, pp. 3–33.Google Scholar
Downey, R., Jockusch, C., and Stob, M. [1990], Array nonrecursive sets and multiple permitting arguments, Recursion theory week (Ambos-Spies, K., Müller, G. H., and Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1432, Springer, pp. 141–174.Google Scholar
Epstein, R. L. [1979], Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer.Google Scholar
Friedberg, R. M. [1957], Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Science, vol. 43, pp. 236–238.Google Scholar
Gabay, Y. [2004], Double jump inversions and strong minimal covers in the turing degrees, Ph.D. thesis, Cornell University.Google Scholar
Groszek, M. J. and Slaman, T. A. [1983], Independence results on the global structure of the Turing degrees, Transactions of the American Mathematical Society, vol. 277, pp. 579–588.Google Scholar
Harrington, L. and Kechris, A. S. [1975], A basis result for sets of reals with an application to minimal covers, Proceedings of the American Mathematical Society, vol. 53, pp. 445–448.Google Scholar
Harrington, L. and Shelah, S. [1982], The undecidability of the recursively enumerable degrees (research announcement), American Mathematical Society. Bulletin. New Series, vol. 6, pp. 79–80.Google Scholar
Harrington, L. and Shore, R. A. [1981], Definable degrees and automorphisms of D, American Mathematical Society. Bulletin. New Series, vol. 4, pp. 97–100.Google Scholar
Hinman, P. G. and Slaman, T. A. [1991], Jump embeddings in the Turing degrees, The Journal of Symbolic Logic, vol. 56, pp. 563–591.Google Scholar
Ishmukhametov, S. [1999], Weak recursive degrees and a problem of Spector, Recursion theory and complexity, proceedings of the Kazan '97 workshop, Kazan, Russia, July 14–19, 1997 (Arslanov, M. and Lempp, S., editors), de Gruyter Series in Logic and its Applications, vol. 2, Walter de Gruyter, Berlin, pp. 81–88.CrossRefGoogle Scholar
Jockusch, C. G. Jr. [2002], Review of Cooper [2001], Mathematics Review MR1808943 (2002m:03061).Google Scholar
Jockusch, C. G. Jr. and Shore, R. A. [1984], Pseudo-jump operators. II. Transfinite iterations, hierarchies and minimal covers, The Journal of Symbolic Logic, vol. 49, pp. 1205–1236.Google Scholar
Jockusch, C. G. Jr. and Simpson, S. G. [1976], A degree-theoretic definition of the ramified analytical hierarchy, Annals of Pure and Applied Logic, vol. 10, pp. 1–32.Google Scholar
Jockusch, C. G. Jr. and Slaman, T. A. [1993], On the Σ2-theory of the upper semilattice of Turing degrees, The Journal of Symbolic Logic, vol. 58, no. 1, pp. 193–204.Google Scholar
Jockusch, C. G. Jr. and Soare, R. I. [1970], Minimal covers and arithmetical sets, Proceedings of the American Mathematical Society, vol. 25, pp. 856–859.CrossRefGoogle Scholar
Kjos-Hanssen, B. [2002], Lattice initial segments of the Turing degrees, Ph.D. thesis, University of California, Berkeley.Google Scholar
Kjos-Hanssen, B. [2003], Local initial segments of the Turing degrees, this Bulletin, vol. 9, pp. 26–36.Google Scholar
Kleene, S. C. and Post, E. L. [1954], The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics. Second Series, vol. 59, pp. 379–407.Google Scholar
Lachlan, A. H. [1966a], The impossibility of finding relative complements for recursively enumerable degrees, The Journal of Symbolic Logic, vol. 31, pp. 434–454.Google Scholar
Lachlan, A. H. [1966b], Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, vol. 16, pp. 537–569.Google Scholar
Lachlan, A. H. [1968], Distributive initial segments of the degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 14, pp. 457–472.Google Scholar
Lachlan, A. H. [1972], Embedding nondistributive lattices in the recursively enumerable degrees, Conference in mathematical logic, London 1970 (Hodges, W., editor), Springer, pp. 149–177. Lecture Notes in Mathematics, Vol. 255.Google Scholar
Lachlan, A. H. and Soare, R. I. [1980], Not every finite lattice is embeddable in the recursively enumerable degrees, Advances in Mathematics, vol. 37, pp. 74–82.CrossRefGoogle Scholar
Lempp, S. [1998], Decidability and undecidability in the enumerable Turing degrees, Proceedings of the Sixth Asian Logic Conference (Beijing, 1996), World Scientific Publishing, River Edge, NJ, pp. 151–161.Google Scholar
Lempp, S. and Lerman, M. [1992], The existential theory of the poset of r.e. degrees with a predicate for single jump reducibility, The Journal of Symbolic Logic, vol. 57, pp. 1120–1130.Google Scholar
Lempp, S. and Lerman, M. [1995], A general framework for priority arguments, this Bulletin, vol. 1, pp. 189–201.Google Scholar
Lempp, S. and Lerman, M. [1996], The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations, Advances in Mathematics, vol. 120, pp. 1–142.Google Scholar
Lempp, S. and Lerman, M. [1997], A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees, Annals of Pure and Applied Logic, vol. 87, pp. 167–185.Google Scholar
Lempp, S., Lerman, M., and Solomon, R. [2006], Embedding finite lattices into the computably enumerable degrees — a status survey, to appear.Google Scholar
Lempp, S., Nies, A., and Slaman, T. A. [1998], The Π3-theory of the computably enumerable Turing degrees is undecidable, Transactions of the American Mathematical Society, vol. 350, pp. 2719–2736.Google Scholar
Lerman, M. [1971], Initial segments of the degrees of unsolvability, Annals of Mathematics. Second Series, vol. 93, pp. 365–389.Google Scholar
Lerman, M. [1983], Degrees of unsolvability, Springer.Google Scholar
Lerman, M. [2000], A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees, Annals of Pure and Applied Logic, vol. 101, pp. 275–297.Google Scholar
Lerman, M. [2008], The existential theory of the uppersemilattice of Turing degrees with least element and jump is decidable, in preparation.Google Scholar
Lerman, M. and Shore, R. A. [1988], Decidability and invariant classes for degree structures, Transactions of the American Mathematical Society, vol. 310, pp. 669–692.Google Scholar
Lerman, M., Shore, R. A., and Soare, R. I. [1984], The elementary theory of the recursively enumerable degrees is not ℵ0-categorical, Advances in Mathematics, vol. 53, pp. 301–320.Google Scholar
Miller, R. G., Nies, A. O., and Shore, R. A. [2004], The ∀∃-theory of ℛ(≤,⋁,⋀) is undecidable, Transactions of the American Mathematical Society, vol. 356, pp. 3025–3067.Google Scholar
Montalbán, A. [2003], Embedding jump upper semilattices into the Turing degrees, The Journal of Symbolic Logic, vol. 68, pp. 989–1014.Google Scholar
Muchnik, A. A. [1956], On the unsolvability of the problem of reducibility in the theory of algorithms, Rossiiskaya Akademiya Nauk SSSR, vol. 108, pp. 29–32.Google Scholar
Nerode, A. and Shore, R. A. [1980a], Reducibility orderings: theories, definability and automorphisms, Annals of Mathematical Logic, vol. 18, pp. 61–89.Google Scholar
Nerode, A. and Shore, R. A. [1980b], Second order logic and first order theories of reducibility orderings, The kleene symposium (Barwise, J., Keisler, H. J., and Kunen, K., editors), vol. 101, North-Holland, Amsterdam, pp. 181–200.Google Scholar
Nies, A. [2003], Parameter definability in the recursively enumerable degrees, Journal of Mathematical Logic, vol. 3, pp. 37–65.Google Scholar
Nies, A., Shore, R. A., and Slaman, T. A. [1998], Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society. Third Series, vol. 77, pp. 241–291.Google Scholar
Rogers, H. Jr. [1967], Some problems of definability in recursive function theory, Sets, models, and recursion theory, Proceedings of the Summer School in Mathematical Logic and 10th Logic Colloquium, Leicester, August-September 1965 (Crossley, J. N., editor), North-Holland, Amsterdam, pp. 183–201.Google Scholar
Sacks, G. E. [1961], A minimal degree less than 0′, American Mathematical Society. Bulletin. New Series, vol. 67, pp. 416–419.Google Scholar
Sacks, G. E. [1963a], Degrees of unsolvability, Princeton University Press, Princeton, N.J..Google Scholar
Sacks, G. E. [1963b], On the degrees less than 0′, Annals of Mathematics. Second Series, vol. 77, pp. 211–231.Google Scholar
Sacks, G. E. [1963c], Recursive enumerability and the jump operator, Transactions of the American Mathematical Society, vol. 108, pp. 223–239.Google Scholar
Sacks, G. E. [1964], The recursively enumerable degrees are dense, Annals of Mathematics. Second Series, vol. 80, pp. 300–312.Google Scholar
Sacks, G. E. [1966], Degrees of unsolvability, 2nd ed., Annals of Mathematical Studies, vol. 55, Princeton University Press, Princeton N.J..Google Scholar
Shoenfield, J. R. [1961], Undecidable and creative theories, Polska Akademia Nauk. Fundamenta Mathematicae, vol. 49, pp. 171–179.Google Scholar
Shoenfield, J. R. [1965], An application of model theory to degrees of unsolvability, Symposium on the Theory of Models (Addison, J. W., Henkin, L., and Tarski, A., editors), North-Holland, Amsterdam, pp. 359–363.Google Scholar
Shore, R. A. [1978], On the ∀∃-sentences of -recursion theory, Generalized recursion theory, II (Fenstad, J. E., Gandy, R. O., and Sacks, G. E., editors), Studies in Logic and the Foundations of Mathematics, vol. 94, North-Holland, Amsterdam, pp. 331–354.Google Scholar
Shore, R. A. [1979], The homogeneity conjecture, Proceedings of the National Academy of Sciences of the United States of America, vol. 76, pp. 4218–4219.Google Scholar
Shore, R. A. [1981], The theory of the degrees below 0′, The Journal of the London Mathematical Society, vol. 24, pp. 1–14.Google Scholar
Shore, R. A. [1982a], Finitely generated codings and the degrees r.e. in a degree d, Proceedings of the American Mathematical Society, vol. 84, no. 2, pp. 256–263.Google Scholar
Shore, R. A. [1982b], On homogeneity and definability in the first-order theory of the Turing degrees, The Journal of Symbolic Logic, vol. 47, pp. 8–16.Google Scholar
Shore, R. A. [1988], Defining jump classes in the degrees below 0′, Proceedings of the American Mathematical Society, vol. 104, pp. 287–292.Google Scholar
Shore, R. A. [1999], The recursively enumerable degrees, Handbook of computability theory, Studies in Logic and the Foundations of Mathematics, vol. 140, North-Holland, Amsterdam, pp. 169–197.Google Scholar
Shore, R. A. [2000], Natural definability in degree structures, Computability theory and its applications: Current Trends and Open Problems (Cholak, P., Lempp, S., Lerman, M., and Shore, R. A., editors), Contemporary Mathematics, vol. 257, American Mathematical Society, Providence, RI, pp. 255–272.Google Scholar
Shore, R. A. and Slaman, T. A. [1999], Defining the Turing jump, Mathematical Research Letters, vol. 6, pp. 711–722.Google Scholar
Shore, R. A. and Slaman, T. A. [2001], A splitting theorem for n-REA degrees, Proceedings of the American Mathematical Society, vol. 129, no. 12, pp. 3721–3728.Google Scholar
Shore, R. A. and Slaman, T. A. [2006], The ∀∃-theory of D(≤, ⋁,′) is undecidable, Logic colloquium ′03 (Stoltenberg-Hansen, V. and Väänänen, J., editors), Lecture Notes in Logic, Association for symbolic logic, to appear.Google Scholar
Simpson, S. G. [1977], First-order theory of the degrees of recursive unsolvability, Annals of Mathematics. Second Series, vol. 105, no. 1, pp. 121–139.Google Scholar
Slaman, T. A. [1991], Degree structures, Proceedings of the International Congress of Mathematicians, vol. I, II (Kyoto, 1990), Springer, pp. 303–316.Google Scholar
Slaman, T. A. and Soare, R. I. [1995], Algebraic aspects of the computably enumerable degrees, Proceedings of the National Academy of Sciences of the United States of America, vol. 92, pp. 617–621.Google Scholar
Slaman, T. A. and Soare, R. I. [2001], Extension of embeddings in the computably enumerable degrees, Annals of Mathematics. Second Series, vol. 154, pp. 1–43.Google Scholar
Slaman, T. A. and Woodin, W. H. [1986], Definability in the Turing degrees, Illinois Journal of Mathematics, vol. 30, pp. 320–334.Google Scholar
Slaman, T. A. and Woodin, W. H. [2006], Definability in degree structures, to appear.Google Scholar
Soare, R. I. [1987], Recursively enumerable sets and degrees, Springer.Google Scholar
Spector, C. [1956], On degrees of recursive unsolvability, Annals of Mathematics. Second Series, vol. 64, pp. 581–592.CrossRefGoogle Scholar
Yates, C. E. M. [1966], A minimal pair of recursively enumerable degrees, The Journal of Symbolic Logic, vol. 31, pp. 159–168.CrossRefGoogle Scholar