Low basis theorem

The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree

, it is possible to find an infinite path through the tree with particular computability properties.

The low basis theorem, in particular, shows that there must be a path which is low; that is, the Turing jump of the path is Turing equivalent to the halting problem

The low basis theorem states that every nonempty

(see arithmetical hierarchy) contains a set of low degree (Soare 1987:109).

This is equivalent, by definition, to the statement that each infinite computable subtree of the binary tree

Hájek and Kučera (1989) showed that the low basis is provable in the formal system of arithmetic known as

For a set X⊆ω, let f(X) = Σ{i}(X)↓2−i, where {i}(X)↓ means that Turing machine i halts on X (with the sum being over all such i).

S⊆2ω, the (unique) X∈S minimizing f(X) has a low Turing degree.

In other words, whether a machine halts on X is forced by a finite condition, which allows for X′ =

One application of the low basis theorem is to construct completions of effective theories so that the completions have low Turing degree.

For example, the low basis theorem implies the existence of PA degrees strictly below