Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-22T09:16:35.789Z Has data issue: false hasContentIssue false
  • English
  • Français

A General Framework for Priority Arguments

Published online by Cambridge University Press:  15 January 2014

Steffen Lempp  and
Manuel Lerman
Steffen Lempp
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA, E-mail:[email protected]
Manuel Lerman
Affiliation:
Department of Mathematics, University of Connecticut, Storrs, CT 06269-3009, USA, E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure the information content of sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question is equivalent to: Given a computer with access to an oracle which will answer membership questions about a set A, can a program (allowing questions to the oracle) be written which will correctly compute the answers to all membership questions about a set B? If the answer is yes, then we say that B is Turing reducible to A and write B ≤TA. We say that B ≡TA if B ≤TA and A ≤TB. ≡T is an equivalence relation, and ≤T induces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called the degrees of unsolvability, and elements of this poset are called degrees.

Post was particularly interested in computability from sets which are partially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 1 , Issue 2 , June 1995 , pp. 189 - 201
Copyright
Copyright © Association for Symbolic Logic 1995

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

[1] Ash, C. J., Stability of recursive structures in arithmetical degrees, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 113–135.CrossRefGoogle Scholar
[2] Ash, C. J., Labelling systems and r. e. structures, Annals of Pure and Applied Logic, vol. 47 (1990), pp. 99–119.Google Scholar
[3] Cooper, S. B., Rigidity and definability in the noncomputable universe, Proceedings of the international congress for logic, methodology and the philosophy of science (Prawitz, D. and Westerståhl, D., editors), North-Holland, Amsterdam, New York, to appear.Google Scholar
[4] Cooper, S. B., The jump is definable in the structure of the degrees of unsolvability, Bulletin of the American Mathematical Society (New Series), vol. 23 (1990), pp. 151–158.Google Scholar
[5] Friedberg, R. M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Sciences of the USA, vol. 43 (1957), pp. 236–238.Google Scholar
[6] Groszek, M. J. and Slaman, T. A., Foundations of the Priority Method, I: Finite and infinite injury, (manuscript).Google Scholar
[7] Kleene, S. C. and Post, E. L., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, vol. 59 (1954), pp. 379–407.Google Scholar
[8] Knight, J., A metatheorem for constructions by finitely many workers, Journal of Symbolic Logic, vol. 55 (1990), pp. 787–804.CrossRefGoogle Scholar
[9] Kontostathis, K., Topological framework for infinite injury, (to appear).Google Scholar
[10] Kontostathis, K., Topological framework for non-priority, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 37 (1991), pp. 495–500.CrossRefGoogle Scholar
[11] Kontostathis, K., Topological framework for finite injury, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 38 (1992), pp. 189–195.Google Scholar
[12] Lachlan, A. H., On some games which are relevant to the theory of recursively enumerable sets, Annals of Mathematics, vol. 91 (1970), pp. 291–310.Google Scholar
[13] Lachlan, A. H., The priority method for the construction of recursively enumerable sets, Cambridge summer school in mathematical logic (Mathias, A. R. D. and Rogers, H. Jr., editors), Lecture Notes in Mathematics, no. 337, Springer-Verlag, New York, 1973.Google Scholar
[14] Lachlan, A. H., A recursively enumerable degree which will not split over all lesser ones, Annals of Mathematical Logic, vol. 9 (1975), pp. 307–365.Google Scholar
[15] Lempp, S. and Lerman, M., The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations, to appear in Advances in Mathematics.Google Scholar
[16] Lempp, S. and Lerman, M., Iterated trees of strategies and priority arguments, monograph: (to appear).Google Scholar
[17] Lempp, S., Lerman, M., and Weber, F., Minimal pair constructions and iterated trees of strategies, Logical methods, in honor of Anil Nerode's 60th birthday, Birkhäuser, Boston, Basel, Berlin, 1993, pp. 512–554.Google Scholar
[18] Martin, D. A., Borel determinacy, Annals of Mathematics, vol. 102 (1975), pp. 363–371.Google Scholar
[19] Mučnik, A. A., On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR, N.S., vol. 108 (1956), pp. 194–197, (in Russian).Google Scholar
[20] Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.Google Scholar
[21] Sacks, G. E., Degrees of unsolvability, Annals of Mathematical Studies, no. 55, Princeton University Press, Princeton, N.J., 1963.Google Scholar
[22] Shoenfield, J. R., Undecidable and creative theories, Fundamenta Mathematica, vol. 49 (1961), pp. 171–179.Google Scholar
[23] Shoenfield, J. R., Non-bounding constructions, Annals of Pure and Applied Logic, vol. 50 (1990), pp. 191–205.Google Scholar
[24] Shore, R. A., On homogeneity and definability in the first-order theory of the Turing degrees, Journal of Symbolic Logic, vol. 47 (1982), pp. 8–16.CrossRefGoogle Scholar
[25] Slaman, T. A. and Woodin, H., Definability in degree structures, (to appear).Google Scholar
[26] Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.Google Scholar
[27] Solovay, R. M., Degrees of models of true arithmetic, (preliminary version, unpublished).Google Scholar
[28] Yates, C. E. M., On the degrees of index sets, Transactions of the American Mathematical Society, vol. 121 (1966), pp. 309–328.Google Scholar
[29] Yates, C. E. M., Banach-Mazur games, comeagre sets, and degrees of unsolvability, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 79 (1976), pp. 195–220.Google Scholar