pith. sign in

arxiv: 1408.2286 · v1 · pith:7OFFXATCnew · submitted 2014-08-11 · 🧮 math.LO

Self-embeddings of computable trees

classification 🧮 math.LO
keywords computableinfinitenontrivialtreescomputesoptimalresultsself-embedding
0
0 comments X
read the original abstract

We divide the class of infinite computable trees into three types. For the first and second types, $0'$ computes a nontrivial self-embedding while for the third type $0''$ 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^0_1$ antichain. This result is optimal and has connections to the program of reverse mathematics.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.