Limitwise monotonic sequences and degree spectra of structures
HTML articles powered by AMS MathViewer
- by Iskander Kalimullin, Bakhadyr Khoussainov and Alexander Melnikov PDF
- Proc. Amer. Math. Soc. 141 (2013), 3275-3289 Request permission
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
- J. T. Baldwin and A. H. Lachlan, On strongly minimal sets, J. Symbolic Logic 36 (1971), 79–96. MR 286642, DOI 10.2307/2271517
- Wesley Calvert, Douglas Cenzer, Valentina Harizanov, and Andrei Morozov, Effective categoricity of equivalence structures, Ann. Pure Appl. Logic 141 (2006), no. 1-2, 61–78. MR 2229930, DOI 10.1016/j.apal.2005.10.002
- Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight, and Robert I. Soare, Bounding prime models, J. Symbolic Logic 69 (2004), no. 4, 1117–1142. MR 2135658, DOI 10.2178/jsl/1102022214
- Barbara F. Csima and Iskander S. Kalimullin, Degree spectra and immunity properties, MLQ Math. Log. Q. 56 (2010), no. 1, 67–77. MR 2598838, DOI 10.1002/malq.200910001
- Douglas Cenzer, Valentina Harizanov, and Jeffrey B. Remmel, $\Sigma _1^0$ and $\Pi _1^0$ equivalence structures, Mathematical theory and computational practice, Lecture Notes in Comput. Sci., vol. 5635, Springer, Berlin, 2009, pp. 99–108. MR 2545884, DOI 10.1007/978-3-642-03073-4_{1}1
- Rodney G. Downey, Asher M. Kach, and Daniel Turetsky, Limitwise monotonic functions and their applications, Proceedings of the 11th Asian Logic Conference, World Sci. Publ., Hackensack, NJ, 2012, pp. 59–85. MR 2868506, DOI 10.1142/9789814360548_{0}004
- Ershov, Yu. and Goncharov, S. (editors). Logic Notebook. Open questions in logic. Novosibirsk University Press, 1989.
- Yuri L. Ershov and Sergei S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622, DOI 10.1007/978-1-4615-4305-3
- 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
- Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller, and Reed Solomon, Enumerations in computable structure theory, Ann. Pure Appl. Logic 136 (2005), no. 3, 219–246. MR 2169684, DOI 10.1016/j.apal.2005.02.001
- Kenneth Harris, $\eta$-representation of sets and degrees, J. Symbolic Logic 73 (2008), no. 4, 1097–1121. MR 2467206, DOI 10.2178/jsl/1230396908
- Denis R. Hirschfeldt, Prime models of theories of computable linear orderings, Proc. Amer. Math. Soc. 129 (2001), no. 10, 3079–3083. MR 1840114, DOI 10.1090/S0002-9939-01-05923-8
- Denis Hirschfeldt, Russell Miller, and Sergei Podzorov, Order-computable sets, Notre Dame J. Formal Logic 48 (2007), no. 3, 317–347. MR 2336351, DOI 10.1305/ndjfl/1187031407
- Denis R. Hirschfeldt, Bakhadyr Khoussainov, and Pavel Semukhin, An uncountably categorical theory whose only computably presentable model is saturated, Notre Dame J. Formal Logic 47 (2006), no. 1, 63–71. MR 2211182, DOI 10.1305/ndjfl/1143468311
- Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore, and Arkadii M. Slinko, Degree spectra and computable dimensions in algebraic structures, Ann. Pure Appl. Logic 115 (2002), no. 1-3, 71–113. MR 1897023, DOI 10.1016/S0168-0072(01)00087-2
- Asher M. Kach, Computable shuffle sums of ordinals, Arch. Math. Logic 47 (2008), no. 3, 211–219. MR 2415492, DOI 10.1007/s00153-008-0077-3
- Asher M. Kach and Daniel Turetsky, Limitwise monotonic functions, sets, and degrees on computable domains, J. Symbolic Logic 75 (2010), no. 1, 131–154. MR 2605885, DOI 10.2178/jsl/1264433912
- N. G. Khisamiev, Constructive abelian groups, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 1177–1231. MR 1673602, DOI 10.1016/S0049-237X(98)80050-5
- Bakhadyr Khoussainov, Andre Nies, and Richard A. Shore, Computable models of theories with few models, Notre Dame J. Formal Logic 38 (1997), no. 2, 165–178. MR 1489408, DOI 10.1305/ndjfl/1039724885
- Russell Miller, The $\Delta ^0_2$-spectrum of a linear order, J. Symbolic Logic 66 (2001), no. 2, 470–486. MR 1833459, DOI 10.2307/2695025
- Alexander G. Melnikov, Enumerations and completely decomposable torsion-free abelian groups, Theory Comput. Syst. 45 (2009), no. 4, 897–916. MR 2529752, DOI 10.1007/s00224-009-9175-9
- Theodore A. Slaman, Relative to any nonrecursive set, Proc. Amer. Math. Soc. 126 (1998), no. 7, 2117–2122. MR 1443408, DOI 10.1090/S0002-9939-98-04307-X
- Richard J. Coles, Rod Downey, and Bakhadyr Khoussainov, On initial segments of computable linear orders, Order 14 (1997/98), no. 2, 107–124. MR 1631684, DOI 10.1023/A:1006031314563
- László Fuchs, Infinite abelian groups. Vol. II, Pure and Applied Mathematics. Vol. 36-II, Academic Press, New York-London, 1973. MR 0349869
- John D. Wallbaum, Computability of algebraic structures, ProQuest LLC, Ann Arbor, MI, 2010. Thesis (Ph.D.)–University of Notre Dame. MR 2827319
- Stephan Wehner, Enumerations, countable structures and Turing degrees, Proc. Amer. Math. Soc. 126 (1998), no. 7, 2131–2139. MR 1443415, DOI 10.1090/S0002-9939-98-04314-7
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
- MR Author ID: 878230
- ORCID: 0000-0001-8781-7432
- Email: a.melnikov@cs.auckland.ac.nz
- 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
- © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3068980