Low basis theorem

The low basis theorem is one of several basis theorems in computability theory, each of which shows that, given an infinite subtree of the binary tree ${\displaystyle 2^{<\omega }}$, 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 ${\displaystyle \emptyset '}$.

The low basis theorem states that every nonempty ${\displaystyle \Pi _{1}^{0}}$ class in ${\displaystyle 2^{\omega }}$ (see arithmetical hierarchy) contains a set of low degree (Soare 1987:109). This is equivalent, by definition, to the statement that each infinite subtree of the binary tree ${\displaystyle 2^{<\omega }}$ has an infinite path of low degree.

...
Wikipedia