Bjørn Kjos-Hanssen
University of Hawaii
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 Π01 antichain. This result is optimal and has connections to the program of reverse mathematics
Keywords quantifiers   decidability   hereditarily finite sets
Categories (categorize this paper)
DOI 10.1215/00294527-2007-003
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 51,304
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Embeddings of Computable Structures.Asher M. Kach, Oscar Levin & Reed Solomon - 2010 - Notre Dame Journal of Formal Logic 51 (1):55-68.

Add more citations

Similar books and articles


Added to PP index

Total views
20 ( #485,401 of 2,330,104 )

Recent downloads (6 months)
1 ( #583,587 of 2,330,104 )

How can I increase my downloads?


My notes