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.

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)