Self-embeddings of computable trees

MaRDI QIDQ1049747zbMATH OpenFDO

Authors Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, James H. Schmerl, Reed Solomon

Publication date 13 January 2010

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2286

zbMATH Keywords

computable treeself-embedding

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

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^{″}$ 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 $P{i}_1^0$ antichain. This result is optimal and has connections to the program of reverse mathematics.

Review text

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.

Recommendations

• On self-embeddings of computable linear orderings
• On computable self-embeddings of computable linear orderings
• The computable dimension of trees of infinite height
• Tree self-embeddings
• Self-embeddings of trees

Cited in

(13)

• Chains and antichains in partial orderings
• Embedding trees in recursive circulants
• Self-embeddings of trees
• On self-embeddings of computable linear orderings
• On Ramsey-minimal infinite graphs
• scientific article; zbMATH DE number 1696443 (Why is no real title available?)
• Tree self-embeddings
• The computable dimension of trees of infinite height
• On a question of Slaman and Groszek
• On computable self-embeddings of computable linear orderings
• The Computable Dimension of I-Trees of Infinite Height
• Computable trees of Scott rank ω₁^CK, and computable approximation
• The reverse mathematics of \textsf{CAC for trees}

This page was built for publication: Self-embeddings of computable trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1049747)