On the ranked points of a Π1 0 set

Journal of Symbolic Logic 54 (3):975-991 (1989)


This paper continues joint work of the authors with P. Clote, R. Soare and S. Wainer (Annals of Pure and Applied Logic, vol. 31 (1986), pp. 145--163). An element x of the Cantor space 2 ω is said have rank α in the closed set P if x is in $D^\alpha(P)\backslash D^{\alpha + 1}(P)$ , where D α is the iterated Cantor-Bendixson derivative. The rank of x is defined to be the least α such that x has rank α in some Π 0 1 set. The main result of the five-author paper is that for any recursive ordinal λ + n (where λ is a limit and n is finite), there is a point with rank λ + n which is Turing equivalent to O (λ + 2n) . All ranked points constructed in that paper are Π 0 2 singletons. We now construct a ranked point which is not a Π 0 2 singleton. In the previous paper the points of high rank were also of high hyperarithmetic degree. We now construct ▵ 0 2 points with arbitrarily high rank. We also show that every nonrecursive RE point is Turing equivalent to an RE point of rank one and that every nonrecursive ▵ 0 2 point is Turing equivalent to a hyperimmune point of rank one. We relate Clote's notion of the height of a Π 0 1 singleton in the Baire space with the notion of rank. Finally, we show that every hyperimmune point x is Turing equivalent to a point which is not ranked

Download options


    Upload a copy of this work     Papers currently archived: 72,766

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

20 (#563,435)

6 months
1 (#386,499)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Countable Algebra and Set Existence Axioms.Harvey M. Friedman - 1983 - Annals of Pure and Applied Logic 25 (2):141.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 14 (7-12):159-166.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7‐12):159-166.

View all 8 references / Add more references

Citations of this work

Countable Thin Π01 Classes.Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 59 (2):79-139.
Choice Classes.Ahmet Çevik - 2016 - Mathematical Logic Quarterly 62 (6):563-574.

Add more citations

Similar books and articles

A Theory of Hierarchical Consequence and Conditionals.Dov M. Gabbay & Karl Schlechta - 2010 - Journal of Logic, Language and Information 19 (1):3-32.
On $\pi^0_1$ Classes and Their Ranked Points.Rod Downey - 1991 - Notre Dame Journal of Formal Logic 32 (4):499-512.
Ranked Partial Structures.Timothy J. Carlson - 2003 - Journal of Symbolic Logic 68 (4):1109-1144.
The Effect of Dual Candidacy on Voting Decisions.Yoichi Hizen - 2006 - Japanese Journal of Political Science 7 (3):289-306.
Species as Ranked Taxa.David A. Baum - 2009 - Systematic Biology 58 (1):74-86.
Inferring a Linear Ordering Over a Power Set.Ran Spiegler - 2001 - Theory and Decision 51 (1):31-49.