Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-26T07:23:21.471Z Has data issue: false hasContentIssue false
  • English
  • Français

The combinatorics of the splitting theorem

Published online by Cambridge University Press:  12 March 2014

Kyriakos Kontostathis
Kyriakos Kontostathis*
Affiliation:
961 Crimson Lane, Pottstown PA 19464, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

The complexity of priority proofs in recursion theory has been growing since the first priority proofs in [1] and [11]. Refined versions of classic priority proofs can be found in [18]. To this date, this part of recursion theory is at about the same stage of development as real analysis was in the early days, when the notions of topology, continuity, compactness, vector space, inner product space, etc., were not invented. There were no general theorems involving these concepts to prove results about the real numbers and the proofs were repetitive and lengthy.

The priority method contains an unprecedent wealth of combinatorics which is used to answer questions in recursion theory and is bound to have applications in many other fields as well. Unfortunately, very little progress has been made in finding theorems to formulate the combinatorial part of the priority method so as to answer questions without having to reprove the combinatorics in each case.

Lempp and Lerman in [10] provide an overview of the subject. The entire edifice of definitions and theorems which formulate the combinatorics of the priority method has acquired the name Priority Theory. From a different vein, Groszek and Slaman in [2] have initiated a program to classify priority constructions in terms of how much induction or collection is needed to carry them out. This program studies the complexity of priority proofs and can be called Complexity Theory of Priority Proofs or simply Complexity.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 62 , Issue 1 , March 1997 , pp. 197 - 224
Copyright
Copyright © Association for Symbolic Logic 1997

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] Friedberg, R., Two recursively enumerable sets of incomparable degrees of unsohability, Proceedings of the National Academy of Sciences, vol. USA 43 (1957), pp. 236–238.CrossRefGoogle Scholar
[2] Groszek, M. and Slaman, T., Foundations of the priority method I, Finite and infinite injury, preprint, 1987.Google Scholar
[3] Groszek, M. and Slaman, T., On Turing reducibility, preprint, 1989.Google Scholar
[4] Hajék, P. and Kučera, A., On recursion theory in IΣ1, this Journal, vol. 54 (1989), no. 2, pp. 576–589.Google Scholar
[5] Kirby, L. and Paris, J., Σn collection schemas in arithmetic, Logic Colloquium 77, North Holland, Amsterdam, 1978, pp. 199–209.Google Scholar
[6] Kontostathis, K., On the construction of degrees of unsohability, Ph.D. thesis, Duke University, 1988, pp. 1–44.Google Scholar
[7] Kontostathis, K., Topological framework for non-priority, Zeits. für Math. Logik und Grund. der Math., vol. 37 (1991), pp. 495–500.CrossRefGoogle Scholar
[8] Kontostathis, K., Topological framework for finite injury, Zeits. für Math. Logik und Grund. der Math., vol. 38 (1992), pp. 189–195.CrossRefGoogle Scholar
[9] Kontostathis, K., The combinatorics of the Friedberg-Muchnick theorem, Logical methods (Crossley, J. N.et al., editors), Birkhäuser, 1993, book of refereed papers, pp. 467–489.CrossRefGoogle Scholar
[10] Lempp, S. and Lerman, M., Priority arguments using iterated trees of strategies, Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, 1990.Google Scholar
[11] Muchnick, A., On the unsohability of the problem of reducibility in the theory of algorithms, Doklady Akademiya SSR, vol. 108 (1956), pp. 194–197.Google Scholar
[12] Mytilinaios, M., Finite injury and Σ1 induction, this Journal, vol. 54 (1989), pp. 38–49.Google Scholar
[13] Nerode, A., Yakhnis, A., and Yakhnis, V., Concurrent programs as strategies in games, MSI Technical Report, Cornell University, 1990.Google Scholar
[14] Rogers, H., Theory of recursive functions and effective computability, MIT press, 1987.Google Scholar
[15] Shore, R. A., Splitting an α-recursively enumerable set, Transactions of the AMS, vol. 204 (1975), pp. 65–78.Google Scholar
[16] Slaman, T. and Woodin, W., Σ1 collection and the finite injury method, math logic and its applications, Lecture Notes in Mathematics, vol. 1388, Springer-Verlag, 1989.Google Scholar
[17] Soare, R., The Friedberg-Muchnick theorem re-examined, Canadian Journal of Mathematics, vol. XXIV (1972), no. 6, pp. 1070–1078.CrossRefGoogle Scholar
[18] Soare, R., Recursively enumerable sets and degrees, Springer-Verlag, 1987.CrossRefGoogle Scholar