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

self-embeddingcomputable tree

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)

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

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)