Abstract We investigate the question “To what extent can random reals be used as a tool to establish number theoretic facts?” Let 2-RANbe the principle that for every realXthere is a realRwhich is 2-random relative toX. In Section 2, we observe that the arguments of Csima and Mileti [3] can be implemented in the base theoryRCA0and soRCA0+ 2-RANimplies the Rainbow Ramsey Theorem. In Section 3, we show that the Rainbow Ramsey Theorem is not conservative overRCA0for arithmetic sentences. Thus, from the Csima–Mileti fact that the existence of random reals has infinitary-combinatorial consequences we can conclude that 2-RANhas non-trivial arithmetic consequences. In Section 4, we show that 2-RANis conservative overRCA0+BΣ2for -sentences. Thus, the set of first-order consequences of 2-RANis strictly stronger thanP−+IΣ1and no stronger thanP−+BΣ2.

Abstract Recently, the Dimension Problem for effective Hausdorff dimension was solved by J. Miller in [14], where the author constructs a Turing degree of non-integral Hausdorff dimension. In this article we settle the Dimension Problem for effective packing dimension by constructing a real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one (on the other hand, it is known via [10. 3. 7] that every real of strictly positive effective Hausdorff dimension computes reals whose effective packing dimensions are arbitrarily close to, but not necessarily equal to, one).

Abstract In 2004 Csima, Hirschfeldt, Knight, and Soare [1] showed that a set A ≤T 0′ is nonlow2 if and only if A is prime bounding, i.e., for every complete atomic decidable theory T, there is a prime model computable in A. The authors presented nine seemingly unrelated predicates of a set A, and showed that they are equivalent for sets. Some of these predicates, such as prime bounding, and others involving equivalence structures and abelian p-groups come from model theory, while others involving meeting dense sets in trees and escaping a given function come from pure computability theory. As predicates of A, the original nine properties are equivalent for sets; however, they are not equivalent in general. This article examines the (degree-theoretic) relationship between the nine properties. We show that the nine properties fall into three classes, each of which consists of several equivalent properties. We also investigate the relationship between the three classes, by determining whether or not any of the predicates in one class implies a predicate in another class.