Limitwise monotonic sequences and degree spectra of structures

Kalimullin, Iskander; Khoussainov, Bakhadyr; Melnikov, Alexander

doi:10.1090/S0002-9939-2013-11586-8

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