We prove a number of structural theorems about the honest polynomial m-degrees contingent on the assumption P = NP . In particular, we show that if P = NP , then the topped finite initial segments of Hm are exactly the topped finite distributive lattices, the topped initial segments of Hm are exactly the direct limits of ascending sequences of finite distributive lattices, and all recursively presentable distributive lattices are initial segments of Hm ∩ RE. Additionally, assuming ¦∑¦ = 1, (...) we show that the theory of the hpm-degrees is undecidable. We also show that index sets cannot be minimal. Lastly, we examine an alternative definition of honest m-reduction under which recursive minimal sets can be constructed. (shrink)

We answer a question of Jockusch by constructing a hyperimmune-free minimal degree below a 1-generic one. To do this we introduce a new forcing notion called arithmetical Sacks forcing. Some other applications are presented.

This paper presents a refinement of a result by Conidis, who proved that there is a real $X$ of effective packing dimension $0\lt \alpha\lt 1$ which cannot compute any real of effective packing dimension $1$. The original construction was carried out below $\emptyset''$, and this paper’s result is an improvement in the effectiveness of the argument, constructing such an $X$ by a limit-computable approximation to get $X\leq_{T}\emptyset'$.

Let b and c be r.e. Turing degrees such that b>c. We show that there is an r.e. degree a such that b>a>c and all lattices containing a critical triple, including the lattice M5, cannot be embedded into the interval [c, a].

A set A is symmetric enumeration (se-) reducible to a set B (A ≤\sb se B) if A is enumeration reducible to B and \barA is enumeration reducible to \barB. This reducibility gives rise to a degree structure (D\sb se) whose least element is the class of computable sets. We give a classification of ≤\sb se in terms of other standard reducibilities and we show that the natural embedding of the Turing degrees (D\sb T) into the enumeration degrees (D\sb e) (...) translates to an embedding (ι\sb se) into D\sb se that preserves least element, suprema, and infima. We define a weak and a strong jump and we observe that ι\sb se preserves the jump operator relative to the latter definition. We prove various (global) results concerning branching, exact pairs, minimal covers, and diamond embeddings in D\sb se. We show that certain classes of se-degrees are first-order definable, in particular, the classes of semirecursive, Σ\sb n ⋃ Π\sb n, Δ\sb n (for any n \in ω), and embedded Turing degrees. This last result allows us to conclude that the theory of D\sb se has the same 1-degree as the theory of Second-Order Arithmetic. (shrink)

The occasion of a retiring presidential address seems like a time to look back, take stock and perhaps look ahead.Institutionally, it was an honor to serve as President of the Association and I want to thank my teachers and predecessors for guidance and advice and my fellow officers and our publisher for their work and support. To all of the members who answered my calls to chair or serve on this or that committee, I offer my thanks as well. Your (...) work was both needed and appreciated.A major component of the efforts of the Association is devoted to our publications. My first important task as President was to deal with the need to reorganize the reviews section of the JSL and eventually to move it to the BSL. Appropriately enough, my first administrative job for the Association, some thirty years ago, was to serve on a committee to plan a reorganization of the reviews. I thank all those who helped with this transition and who took over the task of running the new reviews section. I hope that it will be another thirty years before further major changes are needed in this area and that someone else will be making them. (shrink)