Computing maximal chains (Q453200)

This paper examines computability properties of chains of maximal order type (maximal chains, for short) contained in computable well partial orders (wpo's). The centerpiece is the theorem that, given any computable wpo \(P\) and any hyperarithmetically generic set \(G\), then \(P\) contains some maximal chain that is Turing-reducible to \(G\). On the other hand, the authors show that for any computable ordinal \(\alpha\), there exists a computable wpo containing no maximal chain reducible to \(0^{(\alpha)}\).