The algebraic recursive structure of countable languages of classical first-order logic with equality is analysed. all languages of finite undecidable similarity type are shown to be algebraically and recursively equivalent in the following sense: their boolean algebras of formulas are, after trivial factors involving the one element models of the languages have been excepted, recursively isomorphic by a map which preserves the degree of recursiveness of their models.

There is a perfect thin class whose upward closure in the Turing degrees has full measure . Thus, in the Muchnik lattice of classes, the degree of 2-random reals is comparable with the degree of some perfect thin class. This solves a question of Simpson [S. Simpson, Mass problems and randomness, Bulletin of Symbolic Logic 11 1–27].

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)

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)

Cenzer, D., R. Downey, C. Jockusch and R.A. Shore, Countable thin Π01 classes, Annals of Pure and Applied Logic 59 79–139. A Π01 class P {0, 1}ω is thin if every Π01 subclass of P is the intersection of P with some clopen set. Countable thin Π01 classes are constructed having arbitrary recursive Cantor- Bendixson rank. A thin Π01 class P is constructed with a unique nonisolated point A and furthermore A is of degree 0’. It is shown that no (...) set of degree ≥0” can be a member of any thin Π01 class. An r.e. degree d is constructed such that no set of degree d can be a member of any thin Π01 class. It is also shown that between any two distinct comparable r.e. degrees, there is a degree that contains a set which is of rank one in some thin Π01 class. It is shown that no maximal set can have rank one in any Π01 class, while there exist maximal sets of rank 2. The connection between Π01 classes, propositional theories and recursive Boolean algebras is explored, producing several corollaries to the results on Π01 classes. For example, call a recursive Boolean algebra thin if it has no proper nonprincipal recursive ideals. Then no thin recursive Boolean algebra can have a maximal ideal of degree ≥0”. (shrink)