Self-embeddings of computable trees

Abstract

We divide the class of infinite computable trees into three types. For the first and second types, $0^{\prime }$ computes a nontrivial self-embedding while for the third type $0^{\prime \prime }$ computes a nontrivial self-embedding. These results are optimal and we obtain partial results concerning the complexity of nontrivial self-embeddings of infinite computable trees considered up to isomorphism. We show that every infinite computable tree must have either an infinite computable chain or an infinite ${\Pi }_1^0$ antichain. This result is optimal and has connections to the program of reverse mathematics.