A robuster Scott rank
HTML articles powered by AMS MathViewer
- by Antonio Montalbán
- Proc. Amer. Math. Soc. 143 (2015), 5427-5436
- DOI: https://doi.org/10.1090/proc/12669
- Published electronically: April 14, 2015
- PDF | Request permission
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
- 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
- Chris 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, DOI 10.1016/0168-0072(89)90015-8
- C. J. Ash, Categoricity in hyperarithmetical degrees, Ann. Pure Appl. Logic 34 (1987), no. 1, 1–14. MR 887551, DOI 10.1016/0168-0072(87)90038-8
- Jon Barwise, Admissible sets and structures, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1975. An approach to definability theory. MR 0424560
- 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
- John Chisholm, Effective model theory vs. recursive model theory, J. Symbolic Logic 55 (1990), no. 3, 1168–1191. MR 1071322, DOI 10.2307/2274481
- 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, DOI 10.1007/978-3-642-21875-0_{6}
- R. Douni, D. Khirshvel′d, 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, DOI 10.1023/A:1025971406116
- 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, DOI 10.1016/j.jalgebra.2006.08.040
- 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.
- Su Gao, Complexity ranks of countable models, Notre Dame J. Formal Logic 48 (2007), no. 1, 33–48. MR 2289895, DOI 10.1305/ndjfl/1172787543
- S. S. Gončarov and V. D. Dzgoev, Autostability of models, Algebra i Logika 19 (1980), no. 1, 45–58, 132 (Russian). MR 604657
- S. S. Goncharov, V. S. Kharizanov, Yu. F. Naĭt, 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, DOI 10.1007/s11202-005-0043-9
- Sergey S. Goncharov, Steffen Lempp, and Reed Solomon, The computable dimension of ordered abelian groups, Adv. Math. 175 (2003), no. 1, 102–143. MR 1970243, DOI 10.1016/S0001-8708(02)00042-7
- S. S. Gončarov, Selfstability, and computable families of constructivizations, Algebra i Logika 14 (1975), no. 6, 647–680, 727 (Russian). MR 0437335
- S. S. Gončarov, Autostability of models and abelian groups, Algebra i Logika 19 (1980), no. 1, 23–44, 132 (Russian). MR 604656
- 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, DOI 10.1090/S0002-9947-2011-05331-6
- H. Jerome Keisler, Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers, Studies in Logic and the Foundations of Mathematics, Vol. 62, North-Holland Publishing Co., Amsterdam-London, 1971. MR 0344115
- E. G. K. Lopez-Escobar, An interpolation theorem for denumerably long formulas, Fund. Math. 57 (1965), 253–272. MR 188059, DOI 10.4064/fm-57-3-253-272
- 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, DOI 10.2178/jsl/1107298515
- Peter Edwin La Roche, CONTRIBUTIONS TO RECURSIVE ALGEBRA, ProQuest LLC, Ann Arbor, MI, 1978. Thesis (Ph.D.)–Cornell University. MR 2628051
- A. I. Mal′cev, On recursive Abelian groups, Dokl. Akad. Nauk SSSR 146 (1962), 1009–1012 (Russian). MR 0151378
- Antonio Montalbán, Computability theoretic classifications for classes of structures. To appear in the Proccedings of the ICM 2014.
- Antonio Montalbán, Counting the back-and-forth types, J. Logic Comput. 22 (2012), no. 4, 857–876. MR 2956021, DOI 10.1093/logcom/exq048
- A. T. Nurtazin. Computable classes and algebraic criteria for autostability. PhD thesis, Institute of Mathematics and Mechanics, Alma-Ata, 1974.
- J. B. Remmel, Recursively categorical linear orderings, Proc. Amer. Math. Soc. 83 (1981), no. 2, 387–391. MR 624937, DOI 10.1090/S0002-9939-1981-0624937-1
- Gerald E. Sacks, Bounds on weak scattering, Notre Dame J. Formal Logic 48 (2007), no. 1, 5–31. MR 2289894, DOI 10.1305/ndjfl/1172787542
- 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
- 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, 1981, pp. 302–311. MR 619876
- 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, DOI 10.1007/BF02259845
Bibliographic Information
- Antonio Montalbán
- Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-3840
- Email: antonio@math.berkeley.edu
- 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
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 143 (2015), 5427-5436
- MSC (2010): Primary 03C75; Secondary 03D45
- DOI: https://doi.org/10.1090/proc/12669
- MathSciNet review: 3411157