Scott sentences for equivalence structures
Tóm tắt
For a computable structure $${\mathcal {A}}$$, if there is a computable infinitary Scott sentence, then the complexity of this sentence gives an upper bound for the complexity of the index set $$I({\mathcal {A}})$$. If we can also show that $$I({\mathcal {A}})$$ is m-complete at that level, then there is a correspondence between the complexity of the index set and the complexity of a Scott sentence for the structure. There are results (Calvert et al. in Algebra Logic 45:306–325, 2006; Carson et al. in Trans Am Math Soc 364:5715–5728, 2012; Knight and Saraph in Scott sentences for certain groups, pre-print; McCoy and Wallbaum in Trans Am Math Soc 364:5729–5734, 2012) that suggest that these complexities will always match. However, it was shown in Knight and McCoy (Arch Math Logic 53:519–524, 2014) that there is a structure (a particular subgroup of $${\mathbb {Q}}$$) for which the index set is m-complete $$d-\varSigma ^0_2$$, though there is no computable $$d-\varSigma _2$$ Scott sentence. In the present paper, we give an example of a particular equivalence structure for which the index set is m-complete $$\varPi _3^0$$ but for which there is no computable $$\varPi _3$$ Scott sentence. There is, however, a computable $$\varPi _3$$ pseudo-Scott sentence for the structure, that is, a sentence that acts as a Scott sentence if we only consider computable structures.
Tài liệu tham khảo
Ash, C.J., Knight, J.F.: Computable Structures and the Hyperarithmetical Hierarchy. Elsevier, Amsterdsm (2000)
Calvert, W.: The isomorphism problem for computable Abelian \(p\)-groups of bounded length. J. Symb. Logic 70, 331–345 (2005)
Calvert, W., Cenzer, D., Harizanov, V., Morozov, A.: Effective categoricity of equivalence structures. Ann. Pure Appl. Logic 141, 61–78 (2006)
Calvert, W., Harizanov, V., Knight, J.F., Miller, S.: Index sets of computable structures. Algebra Logic 45, 306–325 (2006)
Carson, J., Harizanov, V., Knight, J.F., Lange, K., McCoy, C., MOrozov, A., Quinn, S., Safranski, C., Wallbaum, J.: Describing free groups. Trans. Am. Math. Soc. 364, 5715–5728 (2012)
Epstein, R.L., Haas, R., Kramer, R.L.: Hierarchies of sets and degrees below \(0^{\prime }\). In: Lerman, M., Schmerl, J.H., Soare, R.I. (eds.) Proceedings of Logic Year 1979–1980, University of Connecticut, pp. 32–48. Springer, Berlin
Goncharov, S.S., Knight, J.F.: Computable structure and non-structure theorems. Algebra Logic 41, 351–373 (2002)
Karp, C.R.: Lang. Expr. Infinite Length. North-Holland Publishing Company, Amsterdam (1964)
Kechris, A.S.: Classical Descriptive Set Theory. Springer, Berlin (1995)
Keisler, H.J.: Model Theory for Infinitary Logic. North-Holland Publishing Company, Amsterdam (1971)
Khisamiev, N.G.: Criterion for constructivizability of a direct sum of cyclic \(p\)-groups. Izv. Akad. Nauk Kazakh. SSR SerFiz.-Mat. 86, 51–55 (1981)
Khoussainov, B., Nies, A., Shore, R.A.: Computable models of theories with few models. Notre Dame J. Formal Logic 38, 165–178 (1997)
Knight, J.F., McCoy, C.: Index sets and Scott sentences. Arch. Math. Logic 53, 519–524 (2014)
Knight, J.F., Saraph, V.: Scott sentences for certain groups. pre-print
Lopez-Escobar, E.G.K.: An interpolation theorem for denumerably long formulas. Fund. Math. 57, 253–272 (1965)
McCoy, C., Wallbaum, J.: Describing free groups, Part II: \({\varPi }_0^4\) hardness and no \({\varSigma }_0^2\) basis. Trans. Am. Math. Soc. 364, 5729–5734 (2012)
Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)
Scott, D.: Logic with denumerably long formulas and finite strings of quantifiers. In: Addison, J., Henkin, L., Tarski, A. (eds.) The Theory of Models, pp. 329–341. North-Holland Publishing Company, Amsterdam (1965)
Vanden Boom, M.: The effective Borel hierarchy. Fund. Math. 195, 269–289 (2007)
Vaught, R.L.: Invariant sets in topology and logic. Fund. Math. 82, 269–294 (1974)