Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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
Published electronically: May 31, 2013
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?)


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: http://dx.doi.org/10.1090/S0002-9939-2013-11586-8
PII: S 0002-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.