Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Limitwise monotonic sequences and degree spectra of structures


Authors: Iskander Kalimullin, Bakhadyr Khoussainov and Alexander Melnikov
Journal: Proc. Amer. Math. Soc. 141 (2013), 3275-3289
MSC (2010): Primary 03C57, 03D75, 03D80
DOI: https://doi.org/10.1090/S0002-9939-2013-11586-8
Published electronically: May 31, 2013
MathSciNet review: 3068980
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we study effective monotonic approximations of sets and sequences of sets. We show that there is a sequence of sets which has no uniform computable monotonic approximation but has an $ \mathbf {x}$-computable monotonic approximation for every hyperimmune degree $ \mathbf {x}$. We also construct a $ \Sigma ^0_2$ set which is not limitwise monotonic but is $ \mathbf {x}$-limitwise monotonic relative to every non-zero $ \Delta ^0_2$ degree $ \mathbf {x}$. We show that if a sequence of sets is uniformly limitwise monotonic in $ \mathbf {x}$ for all except countably many degrees $ \mathbf {x}$, then it has to be uniformly limitwise monotonic. Finally, we apply these results to investigate degree spectra of abelian groups, equivalence relations, and $ \aleph _1$-categorical structures.


References [Enhancements On Off] (What's this?)

  • 1. Baldwin, J.T. and Lachlan, A.H. On strongly minimal sets. J. Symbolic Logic, 36, 1971, pp. 79-96. MR 0286642 (44:3851)
  • 2. Calvert, W., Cenzer, D., Harizanov, V., and Morozov, A. Effective categoricity of equivalence structures. Annals of Pure and Applied Logic, 141, 2006, pp. 61-78. MR 2229930 (2007j:03048)
  • 3. Csima, B., Hirschfeldt, D., Knight, J., and Soare, R. Bounding prime models. J. Symbolic Logic, 69, Issue 4, 2004, pp. 1117-1142. MR 2135658 (2005m:03065)
  • 4. Csima, B. and Kalimullin, I. Degree spectra and immunity properties. Math. Log. Q., 56(1), 2010, pp. 67-77. MR 2598838 (2011i:03038)
  • 5. Cenzer, D., Harizanov, V., and Remmel, J. $ \Sigma ^0_1$ and $ \Pi ^0_1$ equivalence structures. Mathematical Theory and Computational Practice, K. Ambos-Spies, B. Loewe, and W. Merkle, eds., Lect. Notes in Comput. Sci., 5635, Springer, 2009, pp. 99-108. MR 2545884 (2011h:03054)
  • 6. Downey, R., Kach, A., and Turetsky, D. Limitwise monotonic functions and their applications. Proceedings of the Eleventh Annual Asian Logic Conference, World Sci. Publ., Hackensack, NJ, 2012, pp. 59-85. MR 2868506 (2012m:03084)
  • 7. Ershov, Yu. and Goncharov, S. (editors). Logic Notebook. Open questions in logic. Novosibirsk University Press, 1989.
  • 8. Ershov, Yu. and Goncharov, S. Constructive models. Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622 (2002a:03069)
  • 9. Frolov, A., Harizanov, V., Miller, R., Kalimullin, I., and Kudinov, O. Degree spectra of high$ _n$ and nonlow$ _n$ degrees. Journal of Logic and Computation, 22, 2012, pp. 755-777, doi:10.1093 $ \mbox {/logcom}$/exq041
  • 10. Goncharov, S., Harizanov, V., Knight, J., McCoy, C., Miller, R., and Solomon, R. Enumerations in computable structure theory. Annals of Pure and Applied Logic, 136, 2005, pp. 219-246. MR 2169684 (2006f:03071)
  • 11. Harris, K. $ \eta $-representation of sets and degrees. J. Symbolic Logic, 73(4), 2008, pp. 1097-1121. MR 2467206 (2009k:03066)
  • 12. Hirschfeldt, D. Prime models of theories of computable linear orderings. Proceedings of the American Mathematical Society, Vol. 129, No. 10, 2001, pp. 3079-3083. MR 1840114 (2002d:03062)
  • 13. Hirschfeldt, D., Miller, R., and Podzorov, S. Order-computable sets. Notre Dame J. Formal Logic, Volume 48, Number 3, 2007, pp. 317-347. MR 2336351 (2008g:03075)
  • 14. Hirschfeldt, D., Khoussainov, B., and Semukhin P. An uncountably categorical theory whose only computably presentable model is saturated. Notre Dame J. Formal Logic, 47, 2006, No. 1, pp. 63-71. MR 2211182 (2007b:03047)
  • 15. Hirschfeldt, D., Khoussainov, B., Shore, R., and Slinko, A. Degree spectra and computable dimensions in algebraic structures. Annals of Pure and Applied Logic, 115, 2002, pp. 71-113. MR 1897023 (2003d:03060)
  • 16. Kach, A. Computable shuffle sums of ordinals. Archive for Mathematical Logic, 47(3), 2008, pp. 211-219. MR 2415492 (2009e:03078)
  • 17. Kach, A. and Turetsky, D. Limitwise monotonic functions, sets, and degrees on computable domains. J. Symbolic Logic, 75:1, 2010, 131-154. MR 2605885 (2011k:03093)
  • 18. Khisamiev, N. Constructive abelian groups. In: Handbook of Recursive Mathematics, Vol. 2, volume 139 of Stud. Logic Found. Math., North-Holland, Amsterdam, 1998, pp. 1177-1231. MR 1673602 (2000d:03093)
  • 19. Khoussainov, B., Nies, A., and Shore, R. Computable models of theories with few models. Notre Dame J. Formal Logic, 38(2), 1997, pp. 165-178. MR 1489408 (99c:03049)
  • 20. Miller, R. The $ \Delta ^0_2$-spectrum of a linear order. J. Symbolic Logic, 66, Issue 2, 2001, pp. 470-486. MR 1833459 (2002e:03065)
  • 21. Melnikov, A. Enumerations and completely decomposable torsion-free abelian groups. Theory Comput. Syst., 45(4), 2009, pp. 897-916. MR 2529752 (2010m:03069)
  • 22. Slaman, T. Relative to any nonrecursive set. Proc. Amer. Math. Soc., 126, 1998, pp. 2117-2122. MR 1443408 (98h:03047)
  • 23. Coles, R., Downey, R., and Khoussainov, B. On initial segments of computable linear orders. Order, 14, no. 2, 1997/98, pp. 107-124. MR 1631684 (99m:03088)
  • 24. Fuchs, L. Infinite abelian groups. Vol. II. Academic Press, 1973. MR 0349869 (50:2362)
  • 25. Wallbaum, J. Computability of algebraic structures. PhD thesis, University of Notre Dame, 2010. MR 2827319
  • 26. Wehner, St. Enumerations, countable structures and Turing degrees. Proc. Amer. Math. Soc., 126, 1998, pp. 2131-2139. MR 1443415 (98h:03059)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03C57, 03D75, 03D80

Retrieve articles in all journals with MSC (2010): 03C57, 03D75, 03D80


Additional Information

Iskander Kalimullin
Affiliation: Department of Mathematics, Kazan Federal University, Kazan Tatarstan, Russia 420008
Email: Iskander.Kalimullin@ksu.ru

Bakhadyr Khoussainov
Affiliation: Department of Computer Science, Private Bag 92019, University of Auckland, Auckland, New Zealand
Email: bmk@cs.auckland.ac.nz

Alexander Melnikov
Affiliation: Department of Computer Science, Private Bag 92019, University of Auckland, Auckland, New Zealand
Email: a.melnikov@cs.auckland.ac.nz

DOI: https://doi.org/10.1090/S0002-9939-2013-11586-8
Received by editor(s): September 14, 2010
Received by editor(s) in revised form: February 21, 2011, November 7, 2011, and November 30, 2011
Published electronically: May 31, 2013
Additional Notes: The first author was partially supported by RFBR grants 09-01-97010, 10-01-00399 and by the Russian President Grant MK-1784.2010.1
All authors acknowledge support of the Marsden Fund of the Royal Society of New Zealand
Communicated by: Julia Knight
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society