Narrow Results

We show that there are Π₅ formulas in the language of the Turing degrees, , with ≤, ∨ and ∧, that define the relations x″ ≤ y″, x″ = y″ and so {x ∈ L₂(y) = x ≥ y|x″ = y″} in any jump ideal containing 0^(ω). There are also Σ₆&Π₆ and Π₈ formulas that define the relations w = x″ and w = x', respectively, in any such ideal . In the language with just ≤ the quantifier complexity of each of these definitions increases by one. For a lower bound on definability, we show that no Π₂ or Σ₂ formula in the language with just ≤ defines L₂ or L₂(y). Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of is fixed on every degree above 0″ and every relation on which is invariant under the double jump or under join with 0″ is definable over if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in .

We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: (i) The degrees of such sets A are precisely the nonlow c.e. degrees. (ii) There is a c.e. set A of density 1 with no computable subset of nonzero density. (iii) There is a c.e. set A of density 1 such that every subset of A of density 1 is of high degree. We also study the extent to which c.e. sets A can be approximated by their computable subsets B in the sense that A\B has small density. There is a very close connection between the computational complexity of a set and the arithmetical complexity of its density and we characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study the notion of "computable at density r" where r is a real in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity, hyperimmunity, and cohesiveness.

We show that there is a strong minimal pair in the computably enumerable (c.e.) Turing degrees, i.e. a pair of nonzero c.e. degrees a and b such that a∩b = 0 and for any nonzero c.e. degree x ≤ a, b ∪ x ≥ a.

Recall that ${{ℰ}}_{\mathrm{\text{w}}}$ is the lattice of Muchnik degrees of nonempty effectively compact sets in Euclidean space. We solve a long-standing open problem by proving that ${{ℰ}}_{\mathrm{\text{w}}}$is dense, i.e. satisfies $\forall x\forall y(x<y\Rightarrow \exists z(x<z<y))$. Our proof combines an oracle construction with hyperarithmetical theory.

In [Countable thin ${\mathrm{\Pi }}_1^0$ classes, Ann. Pure Appl. Logic59 (1993) 79–139], Cenzer, Downey, Jockusch and Shore proved the density of degrees (not necessarily c.e.) containing members of countable thin ${\mathrm{\Pi }}_1^0$ classes. In the same paper, Cenzer et al. also proved the existence of degrees containing no members of thin ${\mathrm{\Pi }}_1^0$ classes. We will prove in this paper that the c.e. degrees containing no members of thin ${\mathrm{\Pi }}_1^0$ classes are dense in the c.e. degrees. We will also prove that the c.e. degrees containing members of thin ${\mathrm{\Pi }}_1^0$ 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 (See [P. Fejer, The density of the nonbranching degrees, Ann. Pure Appl. Logic24 (1983) 113–130] for nonbranching degrees and [T. A. Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic52 (1991) 155–179] for branching degrees).

A strong degree of categoricity is a Turing degree $d$ such that there is a computable structure ${𝒜}$ that is $d$-computably categorical (there is a $d$-computable isomorphism between any two computable copies of ${𝒜}$), and such that there exist two computable copies of ${𝒜}$ between which every isomorphism computes $d$. The question of whether every ${\mathrm{\Delta }}_2^0$ degree is a strong degree of categoricity has been of interest since the first paper on this subject. We answer the question in the affirmative, by constructing an example.

For $A\subseteq \omega$, the coarse similarity class of A, denoted by $[A]$, is the set of all $B\subseteq \omega$ such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric $\delta$ on the space ${𝒮}$ of coarse similarity classes defined by letting $\delta ([A],[B])$ be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form $\{[A]:A\in {𝒰}\}$ where ${𝒰}$ is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of ${𝒰}$.

We then define a distance between Turing degrees based on Hausdorff distance in the metric space $({𝒮},\delta )$. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, $1/2$, and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance $1/2$ from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability.

Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic.

Finally, we study the completeness of $({𝒮},\delta )$ from the perspectives of computability theory and reverse mathematics.

In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to $0^{″}$. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute $0^{″}$. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree $d$ with $0^{(\alpha )}\le d\le 0^{(\alpha +1)}$ for $\alpha$ a computable ordinal greater than 2 is the strong degree of categoricity of a rigid structure. Using quite different techniques we show that every degree $d$ with $0^{\prime }\le d\le 0^{″}$ is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree $d$ with $0^{\prime }<d<0^{″}$ that is not the degree of categoricity of a rigid structure.

We explore the computational strength of the hyperimmune-free Turing degrees. In particular we investigate how the property of being dominated by recursive functions interacts with classical computability notions such as the jump operator, relativization and effectively closed sets.

We construct a pair of c.e. sets A ≡_wtt ∅^′ and B ≡_T ∅^′ whose truth table degrees form a minimal pair.