A Π01 class is an effectively closed set of reals. We study properties of these classes determined by cardinality, measure and category as well as by the complexity of the members of a class P. Given an effective enumeration {Pe:e < ω} of the Π01 classes, the index set I for a certain property is the set of indices e such that Pe has the property. For example, the index set of binary Π01 classes of positive measure is Σ02 complete. (...) Various notions of boundedness are discussed and classified. For example, the index set of the recursively bounded classes is Σ03 complete and the index set of the recursively bounded classes which have infinitely many recursive members is Π04 complete. Consideration of the Cantor-Bendixson derivative leads to index sets in the transfinite levels of the hyperarithmetic hierarchy. (shrink)

In this paper, we prove that there is a Π01 class in 2ω with a unique nonrecursive member, with that member a cohesive set. This solves an open question from Cenzer. The proof uses the Δ03 method in the context of the construction of a Π01 class.

An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a $\Pi _{1}^{0}$ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y ⊆ ω there is an X in P such that X ⩾wtt Y. We show that this is also equivalent to the $\Pi _{1}^{0}$ class's being large (...) in some sense. We give an example of how this result can be used in the study of scattered linear orders. (shrink)

We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable $\Pi _{1}^{0}$ subsets of 2ω and Kolmogorov complexity play a major role in the proof.

We present an overview of the topics in the title and of some of the key results pertaining to them. These have historically been topics of interest in computability theory and continue to be a rich source of problems and ideas. In particular, we draw attention to the links and connections between these topics and explore their significance to modern research in the field.

The main result of this paper is to show that for every recursive ordinal α ≠ 0 and for every nonrecursive r.e. degree d there is a r.e. set of rank α and degree d.

We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a family of generalized Hausdorff measures based on the iterates of the “dissipation” function of a continuous measure and study the effective nullsets given by the corresponding Solovay tests. We introduce two constructions that preserve non-randomness with respect to a given continuous measure. This enables us to prove the existence of NCR reals in a number of Turing (...) degrees. In particular, we show that every \(\Delta ^0_2\) -degree contains an NCR element. (shrink)

We say that a real X is n-generic relative to a perfect tree T if X is a path through T and for all $\Sigma _{n}^{0}(T)$ sets S, there exists a number k such that either X|k ∈ S or for all σ ∈ T extending X|k we have σ ∉ S. A real X is n-generic relative to some perfect tree if there exists such a T. We first show that for every number n all but countably many reals (...) are n-generic relative to some perfect tree. Second, we show that proving this statement requires ZFC− + "∃ infinitely many iterates of the power set of ω". Third, we prove that every finite iterate of the hyperjump. ${\cal O}^{(n)}$ , is not 2-generic relative to any perfect tree and for every ordinal α below the least λ such that supβ<i (βth admissible) = λ, the iterated hyperjump ${\cal O}^{(\alpha)}$ is not 5-generic relative to any perfect tree. Finally, we demonstrate some necessary conditions for reals to be 1-generic relative to some perfect tree. (shrink)

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. (shrink)

If S is a finite set, let |S| be the cardinality of S. We show that if $m \in \omega, A \subseteq \omega, B \subseteq \omega$ , and |{i: 1 ≤ i ≤ 2 m & x i ∈ A}| can be computed by an algorithm which, for all x 1 ,...,x 2 m , makes at most m queries to B, then A is recursive in the halting set K. If m = 1, we show that A is recursive.

In [Countable thin [Formula: see text] classes, Ann. Pure Appl. Logic 59 79–139], Cenzer, Downey, Jockusch and Shore proved the density of degrees containing members of countable thin [Formula: see text] classes. In the same paper, Cenzer et al. also proved the existence of degrees containing no members of thin [Formula: see text] classes. We will prove in this paper that the c.e. degrees containing no members of thin [Formula: see text] classes are dense in the c.e. degrees. We will (...) also prove that the c.e. degrees containing members of thin [Formula: see text] classes are dense in the c.e. degrees, improving the result of Cenzer et al. mentioned above. Thus, we obtain a new natural subclass of c.e. degrees which are both dense and co-dense in the c.e. degrees, while the other such class is the class of branching c.e. degrees 113–130] for nonbranching degrees and [T. A. Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic 52 155–179] for branching degrees). (shrink)