A robuster Scott rank

Montalbán, Antonio

doi:10.1090/proc/12669

A robuster Scott rank
HTML articles powered by AMS MathViewer

by Antonio Montalbán PDF

Proc. Amer. Math. Soc. 143 (2015), 5427-5436 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-New York, 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