Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-16T15:20:16.378Z Has data issue: false hasContentIssue false
  • English
  • Français

Limitwise monotonic functions, sets, and degrees on computable domains

Published online by Cambridge University Press:  12 March 2014

Asher M. Kach  and
Daniel Turetsky
Asher M. Kach
Affiliation:
University of Connecticut, Department of Mathematics, Storrs, CT 06269, USA, E-mail: [email protected]
Daniel Turetsky
Affiliation:
University of Wisconsin, Department of Mathematics, Madison, WI 53706, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing (support strictly increasing) limitwise monotonic on various computable domains. As applications, we provide a characterization of the sets S with computable increasing η-representations using support increasing limitwise monotonic sets on ℚ and note relationships between the class of order-computable sets and the class of support increasing (support strictly increasing) limitwise monotonic sets on certain domains.

Keywords

Limitwise monotonic functionη-representation
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 1 , March 2010 , pp. 131 - 154
Copyright
Copyright © Association for Symbolic Logic 2010

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] Coles, Richard J., Downey, Rod, and Khoussainov, Bakhadyr, On initial segments of computable linear orders, Order, vol. 14 (1997/1998), no. 2, pp. 107–124.Google Scholar
[2] Csima, Barbara F., Hirschfeldt, Denis R., Knight, Julia F., and Soare, Robert I., Bounding prime models, this Journal, vol. 69 (2004), no. 4, pp. 1117–1142.Google Scholar
[3] Downey, R. G., Computability theory and linear orderings, Handbook of Recursive Mathematics, Vol. 2, Studies in Logic and the Foundations of Mathematics, vol. 139, North-Holland, Amsterdam, 1998, pp. 823–976.Google Scholar
[4] Frolov, Andrey N. and Zubkov, Maxim V., Increasing η-representable degrees, submitted.Google Scholar
[5] Harris, Kenneth, η-representations of sets and degrees, this Journal, vol. 73 (2008), no. 4, pp. 1097–1121.Google Scholar
[6] Hirschfeldt, Denis, Miller, Russell, and Podzorov, Sergei, Order-computable sets, Notre Dame Journal of Formal Logic, vol. 48 (2007), no. 3, pp. 317–347.Google Scholar
[7] Kach, Asher M., Computable shuffle sums of ordinals, Archive for Mathematical Logic, vol. 47 (2008), no. 3, pp. 211–219.Google Scholar
[8] Khisamiev, N. G., Criterion for constructivizability of a direct sum of cyclic p-groups, Izvestiya Akademii Nauk Kazakhskoi SSR. Seriya Fiziko-Matematicheskaya, vol. 1 (1981), no. 86, pp. 51–55.Google Scholar
[9] Khisamiev, N. G., Constructive abelian groups, Handbook of Recursive Mathematics, Vol. 2, Studies in Logic and the Foundations of Mathematics, vol. 139, North-Holland, Amsterdam, 1998, pp. 1177–1231.Google Scholar
[10] Khoussainov, Bakhadyr, Nies, Andre, and Shore, Richard A., Computable models of theories with few models, Notre Dame Journal of Formal Logic, vol. 38 (1997), no. 2, pp. 165–178.Google Scholar
[11] Lerman, Manuel, On recursive linear orderings, Logic Year 1979-80 (Proceedings of Seminars and Conferences in Mathematical Logic, University of Connecticut, Storrs, Connecticut, 1979/80), Lecture Notes in Mathematics, vol. 859, Springer, Berlin, 1981, pp. 132–142.Google Scholar
[12] Rosenstein, Joseph G., Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press [Harcourt Brace Jovanovich Publishers], New York, 1982.Google Scholar
[13] Zubkov, Maxim, On η-representable sets, Computation and Logic in the Real World, Third Conference on Computability in Europe (CiE), Lecture Notes in Computer Science, vol. 4497, 2007, pp. 364–366.Google Scholar