We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the class $superhigh^\diamond$ and show that it contains some, but not all, of the noncomputable K-trivial sets.

A well known fact is that every Lebesgue measurable set is regular, i.e., it includes an F$_{\sigma}$ set of the same measure. We analyze this fact from a metamathematical or foundational standpoint. We study a family of Muchnik degrees corresponding to measure-theoretic regularity at all levels of the effective Borel hierarchy. We prove some new results concerning Nies's notion of LR-reducibility. We build some $\omega$-models of RCA$_0$which are relevant for the reverse mathematics of measure-theoretic regularity.

We analyze the pointwise convergence of a sequence of computable elements of L1 in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA0, each is equivalent to the assertion that every Gδ subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Königʼs lemma relativized to the Turing jump of any set. It is also equivalent to the (...) conjunction of the statement asserting the existence of a 2-random relative to any given set and the principle of Σ2 collection. (shrink)

We examine the concept of almost everywhere domination from the viewpoint of mass problems. Let AED and MLR be the sets of reals which are almost everywhere dominating and Martin-Löf random, respectively. Let b1, b2, and b3 be the degrees of unsolvability of the mass problems associated with AED, MLR × AED, and MLR ∩ AED, respectively. Let [MATHEMATICAL SCRIPT CAPITAL P]w be the lattice of degrees of unsolvability of mass problems associated with nonempty Π01 subsets of 2ω. Let 1 (...) and 0 be the top and bottom elements of [MATHEMATICAL SCRIPT CAPITAL P]w. We show that inf, inf, and inf belong to [MATHEMATICAL SCRIPT CAPITAL P]w and 0 < inf < inf < inf < 1. Under the natural embedding of the recursively enumerable Turing degrees into [MATHEMATICAL SCRIPT CAPITAL P]w, we show that inf and inf but not inf are comparable with some recursively enumerable Turing degrees other than 0 and 0′. In order to make this paper more self-contained, we exposit the proofs of some recent theorems due to Hirschfeldt, Miller, Nies, and Stephan. (shrink)

Let ω be the set of natural numbers. For functions f, g: ω → ω, we say f is dominated by g if f < g for all but finitely many n ∈ ω. We consider the standard “fair coin” probability measure on the space 2ω of in-finite sequences of 0's and 1's. A Turing oracle B is said to be almost everywhere dominating if, for measure 1 many X ∈ 2ω, each function which is Turing computable from X is (...) dominated by some function which is Turing computable from B. Dobrinen and Simpson have shown that the almost everywhere domination property and some of its variant properties are closely related to the reverse mathematics of measure theory. In this paper we exposit some recent results of Kjos-Hanssen, Kjos-Hanssen/Miller/Solomon, and others concerning LR-reducibility and almost everywhere domination. We also prove the following new result: If B is almost everywhere dominating, then B is superhigh, i. e., 0″ is truth-table computable from B ′, the Turing jump of B. (shrink)

In this paper we show that there is a pair of superhigh r.e. degree that forms a minimal pair. An analysis of the proof shows that a critical ingredient is the growth rates of certain order functions. This leads us to investigate certain high r.e. degrees, which resemble ∅′ very closely in terms of ∅′-jump traceability. In particular, we will construct an ultrahigh degree which is cappable.

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 [Formula: see text] be the lattice of weak degrees of mass problems associated with nonempty [Formula: see text] subsets of the Cantor (...) space. The lattice [Formula: see text] has been studied in previous publications. The purpose of this paper is to show that [Formula: see text] partakes of hyperarithmeticity. We exhibit a family of specific, natural degrees in [Formula: see text] which are indexed by the ordinal numbers less than [Formula: see text] and which correspond to the hyperarithmetical hierarchy. Namely, for each [Formula: see text], 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 ⊆ BLR )} where BLR is the set of functions which are boundedly limit recursive in X. Let 1 be the top degree in [Formula: see text]. We prove that all of the weak degrees [Formula: see text], [Formula: see text], are distinct and belong to [Formula: see text]. In addition, we prove that certain index sets associated with [Formula: see text] are [Formula: see text] complete. (shrink)

We consider two axioms of second-order arithmetic. These axioms assert, in two different ways, that infinite but narrow binary trees always have infinite paths. We show that both axioms are strictly weaker than Weak König's Lemma, and incomparable in strength to the dual statement (WWKL) that wide binary trees have paths.