Self-embeddings of computable trees (Q1049747): Difference between revisions

The authors study the problem of how complex it is to find a non-trivial self-embedding of an infinite computable tree. They represent trees as partial orderings, and define self-embeddings to be non-trivial if they are not onto. The answer is that \(0^{\prime\prime}\) is sufficient and necessary to compute non-trivial self-embedding. They also consider some sub-classes of trees where \(0^{\prime}\) is sufficient and necessary. When proving the necessity of these oracles, they ask the interesting question of whether one can build a single tree where every non-trivial self-embedding of any computable copy of the tree computes \(0^{\prime\prime}\) (or \(0'\) in the restricted class), rather than just every non-trivial self-embedding of a single presentation. They obtain partial results in this regard. In the last section they prove that every infinite computable tree has either an infinite computable chain, or an infinite \(\Pi^0_1\) antichain, and that these bounds are optimal. This contrasts with a previous result of Herrmann which says that every infinite computable partial ordering has either an infinite \(\Delta^0_2\) chain, or an infinite \(\Pi^0_2\) antichain.