Randomness below complete theories of arithmetic

Abstract. An extensive picture of the relationship between complete extensions of Peano Arithmetic and algorithmic randomness, in the Turing degrees will be presented. This is largely based on our result that the degrees containing a complete extensions of arithmetic have the random join property: they are the supremum of any random real they compute, with another random real. The same is true for the truth-table and weak truth-table reducibilities. We will conclude with an open question regarding approximability of complete extensions of Peano Arithmetic by incomplete random reals.

Extended abstract

The incompleteness phenomenon in arithmetic, discovered by , implies that there is no computable binary predicate consistently evaluating the truth of each arithmetical sentence. Formal arithmetic is known as Peano arithmetic as it is generated by Peano’s axioms. Theories of arithmetic can be identified with the infinite binary sequences, reals, under a standard fixed coding of formulas into positive integers. Let \mathsf{PA} denote the set of reals that encode complete extensions of arithmetic; the set \mathsf{PA} forms an effectively closed set, a \Pi^0_1 class. The computational power of members of \mathsf{PA}, in terms of their Turing degrees, has been investigated since , and its systematic study started by . pointed out that the relationships between \mathsf{PA} and algorithmically random reals, in the sense of , are essential for understanding the limitations of obtaining solutions to arithmetical problems by probabilistic methods. These relationships have been under investigation since the work of .

We show that the \mathsf{PA} degrees (Turing degrees of reals in \mathsf{PA}) have the join property with respect to random degrees (Turing degrees of random reals). In general, a degree \mathbf{a} is said to have the join property if, for every non-zero \mathbf{b}<\mathbf{a}, there exists \mathbf{c}<\mathbf{a} with \mathbf{b}\vee \mathbf{c}=\mathbf{a}.

The \mathsf{PA} degrees do not, in general, satisfy the join property . In contrast, we show that for every \mathsf{PA} degree \mathbf{a}, random \mathbf{b}<\mathbf{a} there exists random \mathbf{c}<\mathbf{a} with \mathbf{b}\vee \mathbf{c}=\mathbf{a}.

Theorem 1 (Our theorem). If z is \mathsf{PA} and x<_T z is random, there exists random y<_T z such that x\oplus y \equiv_T z. The same is true for truth-table and weak truth-table reducibility.

The universality of \mathsf{PA} reals implies that they compute some random real. Hence our theorem generalizes an older result by , which says that for each \mathsf{PA} real z there exist random x,y such that z\equiv_T x\oplus y. The latter was used by to derive an interesting fact about logical depth, invented by in order to quantify the hardness of obtaining useful information via probabilistic algorithms.

Intuitively, a real is deep if it cannot be produced by a randomized algorithm with non-trivial probability. The halting problem, for example, is deep. Reals that are not deep are called shallow, and include the computable and the random reals. Depth is not invariant with respect to Turing equivalence, but it is invariant with respect to computations with computable time-bound; equivalently, deep reals are upward closed with respect to truth-table reductions.

showed that there are shallow x,y such that x\oplus y is deep. We obtain the following extension, using our theorem. A real x is \mathbf{0}-dominated (also known as hyperimmune-free) if every x-computable function is dominated by a computable function.

Corollary 1. Let \mathsf{DOM} denote the class of \mathbf{0}-dominated reals.

For each random x\in\mathsf{DOM}, there exists random y\in\mathsf{DOM} such that x\oplus y\in\mathsf{DOM}\cap \mathsf{PA}.
For each random x, there exists random y such that x\oplus y is deep.

We conclude with a short survey of the known facts about the join property with respect to \mathsf{PA} and the random degrees. The join property is one of the central algebraic properties in the study of the structure of the Turing degrees. Recall that a Turing degree \mathbf{a} satisfies the

Does every \mathsf{PA} degree have the join property? That was a question raised by and answered in the negative by . Recall that x is low if x'\equiv_T\emptyset', namely the halting problem relative to x is Turing-equivalent to the unrelativized halting set \emptyset'. The

Our theorem cannot be extended with respect to other standard algebraic properties studied in the Turing degrees, such as bounding a minimal pair, being the supremum of a minimal pair, or even having the meet or complementation property. It is known that:

Toward a strengthening of the join property with randoms shown in our theorem, one would consider the property that reals in \mathsf{PA} bound a minimal pair of randoms (before looking at being the join of a minimal pair of randoms). However even this basic property fails due to (i) and the fact that randoms are \mathsf{DNC}. This failure contrasts with (ii).