Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-26T17:41:34.175Z Has data issue: false hasContentIssue false
  • English
  • Français

Π01-classes and Rado's selection principle

Published online by Cambridge University Press:  12 March 2014

C. G. Jockusch ,
A. Lewis  and
J. B. Remmel
C. G. Jockusch
Affiliation:
Department of Mathematics, University of Illinois, Urbana, Illinois 61801
A. Lewis
Affiliation:
Department of Mathematics, Cornell University, Ithaca, New York 14853 Department of Mathematical Social Sciences, University of California at Irvine, Irvine, California 92717
J. B. Remmel
Affiliation:
Department of Mathematics, University of California at San Diego, La Jolla, California 92037 Department of Mathematics, University of Florida, Gainesville, Florida 32611
Get access Rights & Permissions [Opens in a new window]

Extract

There are several areas in recursive algebra and combinatorics in which bounded or recursively bounded -classes have arisen. For our purposes we may define a -class to be a set Path(T) of all infinite paths through a recursive tree T. Here a recursive tree T is just a recursive subset of ω<ω, the set of all finite sequences of the natural numbers ω = {0,1,2,…}, which is closed under initial segments. If the tree T is finitely branching, then we say the -class Path(T) is bounded. If T is highly recursive, i.e., if there exists a partial recursive function f: T→ω such that for each node ηЄ T, f(η) equals the number of immediate successors of η, then we say that the -class Path(T) is recursively bounded (r.b.). For example, Manaster and Rosenstein in [6] studied the effective version of the marriage problem and showed that the set of proper marriages for a recursive society S was always a bounded -class and the set of proper marriages for a highly recursive society was always an r.b. -class. Indeed, Manaster and Rosenstein showed that, in the case of the symmetric marriage problem, any r.b. -class could be represented as the set of symmetric marriages of a highly recursive society S in the sense that given any r.b. Π1-class C there is a society Sc such that there is a natural, effective, degree-preserving 1:1 correspondence between the elements of C and the symmetric marriages of Sc. Jockusch conjectured that the set of marriages of a recursive society can represent any bounded -class and the set of marriages of a highly recursive society can represent any r.b. -class. These conjectures remain open. However, Metakides and Nerode [7] showed that any r.b. -class could be represented by the set of total orderings of a recursive real field and vice versa that the set of total orderings of a recursive real field is always an r.b. -class.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 56 , Issue 2 , June 1991 , pp. 684 - 693
Copyright
Copyright © Association for Symbolic Logic 1991

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]Bean, D., Effective coloration, this Journal, vol. 41 (1976), pp. 469–480.Google Scholar
[2]Jockusch, C. G. and McLaughlin, T. G., Countable retracing functions and predicates, Pacific Journal of Mathematics, vol. 30 (1969), pp. 67–93.CrossRefGoogle Scholar
[3]Jockusch, C. G. and Soare, R. I., -classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[4]Jockusch, C. G. and Soare, R. I., Degrees of members of -classes, Pacific Journal of Mathematics, vol. 40 (1972), pp. 605–616.CrossRefGoogle Scholar
[5]Kučera, A., An alternative, priority-free, solution to Post's problem, Mathematical foundations of computer science (twelfth symposium, Bratislava, 1986), edited by Gruska, J.et al., Lecture Notes in Computer Science, vol. 233, Springer-Verlag, Berlin, 1986, pp. 493–500.CrossRefGoogle Scholar
[6]Manaster, A. and Rosenstein, J., Effective matchmaking, Proceedings of the London Mathematical Society, ser. 3 vol. 25 (1972), pp. 615–654.CrossRefGoogle Scholar
[7]Metakides, G. and Nerode, A., Effective content of field theory, Annals of Mathematical Logic, vol. 11 (1979), 147–171.CrossRefGoogle Scholar
[8]Milner, E. C., Selectivity and weakly compact cardinals, Bulletin of the London Mathematical Society, vol. 14 (1982), pp. 329–333.CrossRefGoogle Scholar
[9]Rado, R., Axiomatic treatment of rank in infinite sets, Canadian Journal of Mathematics, vol. 1 (1949), pp. 337–343.CrossRefGoogle Scholar
[10]Rado, R., A selection lemma, Journal of Combinatorial Theory, vol. 10 (1971), pp. 176–177.CrossRefGoogle Scholar
[11]Rado, R., Selective families of sets, Proceedings of the Royal Society of London, Series A, vol. 372 (1980), pp. 307–315.Google Scholar
[12]Rav, Y., Variants of Rado's selection lemma and their applications, Mathematische Nachrichten, vol. 79 (1977), pp. 145–165.CrossRefGoogle Scholar
[13]Remmel, J. B., Graph colorings and recursively bounded -classes, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 185–194.CrossRefGoogle Scholar
[14]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[15]Shoenfield, J. R., Degrees of models, this Journal, vol. 25 (1960), pp. 233–237.Google Scholar
[16]Yates, C. E. M., Arithmetical sets and retracing functions, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 13 (1967), pp. 193–204.CrossRefGoogle Scholar