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)

 
 

 

A robuster Scott rank


Author: Antonio Montalbán
Journal: Proc. Amer. Math. Soc. 143 (2015), 5427-5436
MSC (2010): Primary 03C75; Secondary 03D45
DOI: https://doi.org/10.1090/proc/12669
Published electronically: April 14, 2015
MathSciNet review: 3411157
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give a new definition of Scott rank motivated by our main theorem: For every countable structure $ \mathcal {A}$ and ordinal $ \alpha <\omega _1$, we have that: every automorphism orbit is infinitary $ \Sigma _\alpha $-definable without parameters if and only if $ \mathcal {A}$ has an infinitary $ \Pi _{\alpha +1}$ Scott sentence, if and only if $ \mathcal {A}$ is uniformly boldface $ \bf {\Delta }^0_\alpha $-categorical. As a corollary, we show that a structure is computably categorical on a cone if and only if it is the model of a countably categorical infinitary $ \Sigma _3$ sentence.


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

  • [AK00] C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842 (2001k:03090)
  • [AKMS89] C. J. Ash, Julia Knight, Mark Manasse, and Theodore Slaman, Generic copies of countable structures, Ann. Pure Appl. Logic 42 (1989), no. 3, 195-205. MR 998606 (90d:03065), https://doi.org/10.1016/0168-0072(89)90015-8
  • [Ash87] C. J. Ash, Categoricity in hyperarithmetical degrees, Ann. Pure Appl. Logic 34 (1987), no. 1, 1-14. MR 887551 (88e:03053), https://doi.org/10.1016/0168-0072(87)90038-8
  • [Bar75] Jon Barwise, Admissible sets and structures, Springer-Verlag, Berlin-New York, 1975. An approach to definability theory; Perspectives in Mathematical Logic. MR 0424560 (54 #12519)
  • [CCHM06] 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 (2007j:03048), https://doi.org/10.1016/j.apal.2005.10.002
  • [Chi90] John Chisholm, Effective model theory vs. recursive model theory, J. Symbolic Logic 55 (1990), no. 3, 1168-1191. MR 1071322 (91i:03072), https://doi.org/10.2307/2274481
  • [CHR11] Douglas Cenzer, Valentina Harizanov, and Jeffrey B. Remmel, Effective categoricity of injection structures, Models of computation in context, Lecture Notes in Comput. Sci., vol. 6735, Springer, Heidelberg, 2011, pp. 51-60. MR 2843624, https://doi.org/10.1007/978-3-642-21875-0_6
  • [DHK03] R. Douni, D. Khirshveld, and B. Khusainov, Uniformity in the theory of computable structures, Algebra Logika 42 (2003), no. 5, 566-593, 637 (Russian, with Russian summary); English transl., Algebra Logic 42 (2003), no. 5, 318-332. MR 2025716 (2005b:03104), https://doi.org/10.1023/A:1025971406116
  • [DHK$^+$07] Rodney G. Downey, Denis R. Hirschfeldt, Asher M. Kach, Steffen Lempp, Joseph R. Mileti, and Antonio Montalbán, Subspaces of computable vector spaces, J. Algebra 314 (2007), no. 2, 888-894. MR 2344589 (2008m:03024), https://doi.org/10.1016/j.jalgebra.2006.08.040
  • [DKL$^+$] R. Downey, A. Kach, S. Lempp, A.E.M. Lewis-Pye, A. Montalbán, and D. Turetsky,
    The complexity of computable categoricity.
    Submitted for publication.
  • [Gao07] Su Gao, Complexity ranks of countable models, Notre Dame J. Formal Logic 48 (2007), no. 1, 33-48 (electronic). MR 2289895 (2008c:03033), https://doi.org/10.1305/ndjfl/1172787543
  • [GD80] S. S. Goncharov and V. D. Dzgoev, Autostability of models, Algebra i Logika 19 (1980), no. 1, 45-58, 132 (Russian). MR 604657 (82g:03082)
  • [GHK$^+$] S. S. Goncharov, V. S. Harizanov, J. F. Knight, A. S. Morozov, and A. V. Romina, On automorphic tuples of elements in computable models, Sibirsk. Mat. Zh. 46 (2005), no. 3, 523-532 (Russian, with Russian summary); English transl., Siberian Math. J. 46 (2005), no. 3, 405-412. MR 2164557 (2006f:03062), https://doi.org/10.1007/s11202-005-0043-9
  • [GLS03] S. S. Goncharov, Steffen Lempp, and Reed Solomon, The computable dimension of ordered abelian groups, Adv. Math. 175 (2003), no. 1, 102-143. MR 1970243 (2004h:03093), https://doi.org/10.1016/S0001-8708(02)00042-7
  • [Gon75] S. S. Goncharov, Selfstability, and computable families of constructivizations, Algebra i Logika 14 (1975), no. 6, 647-680, 727 (Russian). MR 0437335 (55 #10267)
  • [Gon80] S. S. Goncharov, Autostability of models and abelian groups, Algebra i Logika 19 (1980), no. 1, 23-44, 132 (Russian). MR 604656 (82g:03081)
  • [HM12] Kenneth Harris and Antonio Montalbán, On the $ n$-back-and-forth types of Boolean algebras, Trans. Amer. Math. Soc. 364 (2012), no. 2, 827-866. MR 2846355, https://doi.org/10.1090/S0002-9947-2011-05331-6
  • [Kei71] H. Jerome Keisler, Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers, North-Holland Publishing Co., Amsterdam-London, 1971. Studies in Logic and the Foundations of Mathematics, Vol. 62. MR 0344115 (49 #8855)
  • [LE65] E. G. K. Lopez-Escobar, An interpolation theorem for denumerably long formulas, Fund. Math. 57 (1965), 253-272. MR 0188059 (32 #5500)
  • [LMMS05] Steffen Lempp, Charles McCoy, Russell Miller, and Reed Solomon, Computable categoricity of trees of finite height, J. Symbolic Logic 70 (2005), no. 1, 151-215. MR 2119128 (2005i:03051), https://doi.org/10.2178/jsl/1107298515
  • [LR78] Peter Edwin La Roche, CONTRIBUTIONS TO RECURSIVE ALGEBRA, ProQuest LLC, Ann Arbor, MI, 1978. Thesis (Ph.D.)-Cornell University. MR 2628051
  • [Mal62] A. I. Malcev, On recursive Abelian groups, Dokl. Akad. Nauk SSSR 146 (1962), 1009-1012 (Russian). MR 0151378 (27 #1363)
  • [Mon] Antonio Montalbán,
    Computability theoretic classifications for classes of structures.
    To appear in the Proccedings of the ICM 2014.
  • [Mon12] Antonio Montalbán, Counting the back-and-forth types, J. Logic Comput. 22 (2012), no. 4, 857-876. MR 2956021, https://doi.org/10.1093/logcom/exq048
  • [Nur74] A. T. Nurtazin.
    Computable classes and algebraic criteria for autostability.
    PhD thesis, Institute of Mathematics and Mechanics, Alma-Ata, 1974.
  • [Rem81] J. B. Remmel, Recursively categorical linear orderings, Proc. Amer. Math. Soc. 83 (1981), no. 2, 387-391. MR 624937 (82j:03037), https://doi.org/10.2307/2043534
  • [Sac07] Gerald E. Sacks, Bounds on weak scattering, Notre Dame J. Formal Logic 48 (2007), no. 1, 5-31. MR 2289894 (2008a:03062), https://doi.org/10.1305/ndjfl/1172787542
  • [Sco65] Dana Scott, Logic with denumerably long formulas and finite strings of quantifiers, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 329-341. MR 0200133 (34 #32)
  • [Smi81] Rick L. Smith, Two theorems on autostability in $ p$-groups, Logic Year 1979-80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin-New York, 1981, pp. 302-311. MR 619876 (83h:03064)
  • [Ven92] Yu. G. Ventsov, The effective choice problem for relations and reducibilities in classes of constructive and positive models, Algebra i Logika 31 (1992), no. 2, 101-118, 220 (Russian, with Russian summary); English transl., Algebra and Logic 31 (1992), no. 2, 63-73 (1993). MR 1289026 (95h:03089), https://doi.org/10.1007/BF02259845

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03C75, 03D45

Retrieve articles in all journals with MSC (2010): 03C75, 03D45


Additional Information

Antonio Montalbán
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-3840
Email: antonio@math.berkeley.edu

DOI: https://doi.org/10.1090/proc/12669
Received by editor(s): March 24, 2014
Received by editor(s) in revised form: November 7, 2014
Published electronically: April 14, 2015
Additional Notes: The author was partially supported by the Packard Fellowship.
Communicated by: Mirna Džamonja
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society