Journal of Mathematical Logic

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if for all Y ∈ Q there exists X ∈ P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. Let be the lattice of weak degrees of mass problems associated with nonempty subsets of the Cantor space. The lattice has been studied in previous publications. The purpose of this paper is to show that partakes of hyperarithmeticity. We exhibit a family of specific, natural degrees in which are indexed by the ordinal numbers less than and which correspond to the hyperarithmetical hierarchy. Namely, for each , let h_α be the weak degree of 0^(α), the αth Turing jump of 0. If p is the weak degree of any mass problem P, let p* be the weak degree of the mass problem P* = {Y | ∃X (X ∈ P andBLR(X) ⊆ BLR(Y))} where BLR(X) is the set of functions which are boundedly limit recursive in X. Let 1 be the top degree in . We prove that all of the weak degrees , , are distinct and belong to . In addition, we prove that certain index sets associated with are complete.

We characterize the class of c.e. degrees that bound a critical triple (equivalently, a weak critical triple) as those degrees that compute a function that has no ω-c.e. approximation.

Bounded PAC substructures of models of stable theory T are generalizations of bounded PAC fields and bounded PAC beautiful pairs generalize Poizat's beautiful pairs. Both notions were introduced in the authors Ph.D. thesis. In this paper, we prove that under the assumption that the PAC property is first order for T, the theory of any bounded PAC structure is simple. Moreover, if the PAC property is first order for T and T does not have the finite cover property, then the theory of any bounded PAC beautiful pair is simple. We, also, give a characterization of dividing in both cases.

We introduce a new notion of tame geometry for structures admitting an abstract notion of balls. The notion is named b-minimality and is based on definable families of points and balls. We develop a dimension theory and prove a cell decomposition theorem for b-minimal structures. We show that b-minimality applies to the theory of Henselian valued fields of characteristic zero, generalizing work by Denef–Pas [25, 26]. Structures which are o-minimal, v-minimal, or p-minimal and which satisfy some slight extra conditions are also b-minimal, but b-minimality leaves more room for nontrivial expansions. The b-minimal setting is intended to be a natural framework for the construction of Euler characteristics and motivic or p-adic integrals. The b-minimal cell decomposition is a generalization of concepts of Cohen [11], Denef [15], and the link between cell decomposition and integration was first made by Denef [13].

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 .