Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T05:31:49.005Z Has data issue: false hasContentIssue false
  • English
  • Français

On computable self-embeddings of computable linear orderings

Published online by Cambridge University Press:  12 March 2014

Rodney G. Downey ,
Bart Kastermans  and
Steffen Lempp
Rodney G. Downey
Affiliation:
School of Mathematics, Statistics and Computer Science, Victoria University, Wellington 6140, New Zealand, E-mail: [email protected]
Bart Kastermans
Affiliation:
Department of Mathematics, University of Colorado, Boulder, Co 80309-0395, USA, E-mail: [email protected]
Steffen Lempp
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, Wi 53706-1388, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We solve a longstanding question of Rosenstein, and make progress toward solving a long-standing open problem in the area of computable linear orderings by showing that every computable η-like linear ordering without an infinite strongly η-like interval has a computable copy without nontrivial computable self-embedding.

The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

Keywords

computable linear orderingself-embedding
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 4 , December 2009 , pp. 1352 - 1366
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ash, Christopher J., Jockusch, Carl G. Jr., and Knight, Julia F., Jumps of orderings, Transactions of the American Mathematical Society, vol. 319 (1990), pp. 573–599.CrossRefGoogle Scholar
[2]Downey, Rodney G., Every recursive Boolean algebra is isomorphic to one with incomplete atoms, Annals of Pure and Applied Logic, vol. 60 (1993), pp. 193–206.CrossRefGoogle Scholar
[3]Downey, Rodney G., Computability theory and linear orderings, Handbook of recursive mathematics, vol. 2, North-Holland, Amsterdam, 1998, pp. 823–976.Google Scholar
[4]Downey, Rodney G., Jockusch, Carl G. Jr., and Miller, Joseph S., On self-embeddings of computable linear orderings. Annals of Pure and Applied Logic, vol. 138 (2006), pp. 52–76.CrossRefGoogle Scholar
[5]Downey, Rodney G. and Lempp, Steffen, The proof–theoretic strength of the Dushnik–Miller Theorem for countable linear orders, Recursion theory and complexity (Kazan, 1997), de Gruyter, Berlin, 1999, pp. 55–57.CrossRefGoogle Scholar
[6]Downey, Rodney G., Lempp, Steffen, and Wu, Guohua, On the complexity of the successivity relation in computable linear orderings, to appear.Google Scholar
[7]Downey, Rodney G. and Moses, Michael F., On choice sets and strongly nontrivial self-embeddings of recursive linear orders, Zeitschrift für Mathematische Logik and Grundlagen der Mathematik, vol. 35 (1989), pp. 237–246.CrossRefGoogle Scholar
[8]Dushnik, Ben and Miller, E. W., Concerning similarity transformations of linearly ordered sets, Bulletin of the American Mathematical Society, vol. 46 (1940), pp. 322–326.CrossRefGoogle Scholar
[9]Feiner, Lawrence, Hierarchies of Boolean algebras, this Journal, vol. 35 (1970), pp. 365–374.Google Scholar
[10]Harrison, Joseph, Recursive pseudo-well-orderings, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.CrossRefGoogle Scholar
[11]Jockusch, Carl G. Jr. and Soare, Robert I., Degrees oforderings not isomorphic to recursive linear orderings, Annals of Pure and Applied Logic, vol. 52 (1991), pp. 39–64, “International Symposium on Mathematical Logic and its Applications” (Nagoya, 1988).CrossRefGoogle Scholar
[12]Lempp, Steffen, Lecture notes on priority arguments, preprint available at http://www.math.wise.edu/~lempp/papers/prio.pdf.Google Scholar
[13]Montalbán, Antonio, Beyond the arithmetic, Ph.D. thesis, Cornell University, 2005.Google Scholar
[14]Montalbán, Antonio, Countably complementable linear orderings, Order, vol. 23 (2006), pp. 321–331.CrossRefGoogle Scholar
[15]Richter, Linda Jean C., Degrees of unsolvability of models, Ph.D. thesis, University of Illinois at Urbana–Champaign, 1977.Google Scholar
[16]Rosenstein, Joseph G., Linear orderings, Academic Press, New York-London, 1982.Google Scholar
[17]Rosenstein, Joseph G., Recursive linear orderings, Orders: description and roles (l'Arbresle, 1982), North-Holland, Amsterdam, 1984, pp. 465–475.Google Scholar
[18]Soare, Robert I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, New York, 1987.CrossRefGoogle Scholar
[19]Watnick, Richard, A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings, this Journal, vol. 49 (1984), pp. 563–569.Google Scholar