Self-Embeddings of Computable Trees
Binns, Stephen ; Kjos-Hanssen, Bjørn ; Lerman, Manuel ; Schmerl, James H. ; Solomon, Reed
Notre Dame J. Formal Logic, Tome 49 (2008) no. 1, p. 1-37 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 2008-01-15
Classification:  quantifiers,  decidability,  hereditarily finite sets,  03B25,  03E30,  03C62 
@article{1199649898,
     author = {Binns, Stephen and Kjos-Hanssen, Bj\o rn and Lerman, Manuel and Schmerl, James H. and Solomon, Reed},
     title = {Self-Embeddings of Computable Trees},
     journal = {Notre Dame J. Formal Logic},
     volume = {49},
     number = {1},
     year = {2008},
     pages = { 1-37},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1199649898}
}

Binns, Stephen; Kjos-Hanssen, Bjørn; Lerman, Manuel; Schmerl, James H.; Solomon, Reed. Self-Embeddings of Computable Trees. Notre Dame J. Formal Logic, Tome 49 (2008) no. 1, pp.  1-37. http://gdmltest.u-ga.fr/item/1199649898/