On self-embeddings of computable linear orderings. (English) Zbl 1105.03036

The authors prove that there exists a computable linear ordering without nontrivial \({\mathbf 0}^\prime\)-computable self-embeddings. It appeared that the previously published proof of this statement in [S. Lempp, A. Morozov, C. McCoy and D. R. Solomon, “On self-embeddings of computable linear orders”, in: S. B. Cooper et al. (eds.), Computability and models. Kluwer Academic/Plenum Publishers, New York, 259–265 (2003; Zbl 1104.03001)] contains an error. The question of how much computability we need to compute such embeddings in the general case and for various kinds of orderings is also studied.


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


Zbl 1104.03001
Full Text: DOI Link


[1] Downey, R., Computability theory and linear orderings, (), 823-977 · Zbl 0941.03045
[2] Downey, R.; LaForte, G.; Shore, R., Decomposition and infima in the c.e. degrees, J. symbolic logic, 68, 551-579, (2003) · Zbl 1059.03035
[3] Downey, R.; Lempp, S., On the proof theoretical strength of the dushnik – miller theorem for countable linear orderings, (), 55-58 · Zbl 0951.03053
[4] Downey, R.; Stob, M., Minimal pairs in initial segments of the recursively enumerable degrees, Israel J. math., 100, 7-27, (1997) · Zbl 0924.03076
[5] Dushnik, B.; Miller, E., Concerning similarity transformations of linearly ordered sets, Bull. amer. math. soc., 46, 322-326, (1940) · JFM 66.0199.02
[6] Jockusch, C.; Soare, R., \(\Pi_1^0\) classes and degrees of theories, Trans. amer. math. soc., 173, 33-56, (1972) · Zbl 0262.02041
[7] Lempp, S.; Morozov, A.; McCoy, C.; Solomon, R., On self-embeddings of computable linear orderings, (), 259-265
[8] Simpson, S., Degrees of unsolvability: a survey of results, (), 631-652
[9] Soare, R., Recursively enumerable sets and degrees, (1987), Springer-Verlag New York · Zbl 0623.03042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.