×

Complexity of Scott sentences. (English) Zbl 1485.03103

Summary: We give effective versions of some results on Scott sentences. Effectivizing a result of A. Montalbán [Proc. Am. Math. Soc. 143, No. 12, 5427–5436 (2015; Zbl 1386.03053)], we show that if \(\mathcal{A}\) has a computable \(\Pi_\alpha\) Scott sentence, then the automorphism orbits of all tuples are defined by formulas that are computable \(\Sigma_\beta\) for some \(\beta < \alpha \). Effectivizing a result of A. W. Miller [Notre Dame J. Formal Logic 24, 22–34 (1983; Zbl 0487.03013)], we show that if a countable structure \(\mathcal{A}\) has a computable \(\Sigma_{\alpha }\) Scott sentence and one that is computable \(\Pi_{\alpha }\), then it has one that is computable \(d-\Sigma_{ < \alpha }\). We also give an effective version of a result of D. E. Miller [Trans. Am. Math. Soc. 242, 185–204 (1978; Zbl 0409.03030)] on which the result of A. Miller [loc. cit.] was based. Using the non-effective results of Montalbán [loc. cit.] and A. Miller [loc. cit.], we show that a finitely generated group has a \(d-\Sigma_2\) Scott sentence if{f} the orbit of some (or every) generating tuple is defined by a \(\Pi_1\) formula. Using our effective results, we show that a computable finitely generated group has a computable \(d-\Sigma_2\) Scott sentence if{f} the orbit of some (or every) generating tuple is defined by a computable \(\Pi_1\) formula.

MSC:

03C57 Computable structure theory, computable model theory
03C75 Other infinitary logic
03D45 Theory of numerations, effectively presented structures
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] C. J. Ash and J. F. Knight,Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, 2000. · Zbl 0960.03001
[2] S. Badaev,Computable enumerations of families of general recursive functions, Algebra and Logic 16 (1977), 83-98. · Zbl 0399.03028
[3] J. Carson, V. Harizanov, J. Knight, K. Lange, C. Maher, C. McCoy, A. Morozov, S. Quinn, and J. Wallbaum,Describing free groups, Trans. Amer. Math. Soc. 364 (2012), 5715-5728. · Zbl 1302.03045
[4] M. Harrison-Trainor and M.-C. Ho,On optimal Scott sentences of finitely generated algebraic structures, Proc. Amer. Math. Soc. 146 (2018), 4473-4485. · Zbl 1522.03126
[5] M.-C. Ho,Describing groups, Proc. Amer. Math. Soc. 145 (2017), 2223-2239. Complexity of Scott sentences129 · Zbl 1423.03150
[6] H. J. Keisler,Model Theory for Infinitary Logic, North-Holland, 1971. · Zbl 0222.02064
[7] J. F. Knight and H. J. Keisler,Barwise: infinitary logic and admissible sets, Bull. Symbolic Logic 10 (2004), 4-36. · Zbl 1080.03026
[8] J. F. Knight and V. Saraph,Scott sentences for certain groups, Arch. Math. Logic 57 (2018), 453-472. · Zbl 1522.03173
[9] D. Marker,Lectures on Infinitary Model Theory, Lecture Notes in Logic 56, Cambridge Univ. Press, 2016. · Zbl 1356.03004
[10] A. Miller,The Borel classification of the isomorphism class of a countable model, Notre Dame J. Formal Logic 24 (1983), 22-34. · Zbl 0487.03013
[11] D. E. Miller,The invariantΠ0αseparation principle, Trans. Amer. Math. Soc. 242 (1978), 185-204. · Zbl 0409.03030
[12] A. Montalbán,A robuster Scott rank, Proc. Amer. Math. Soc. 143 (2015), 5427-5436. · Zbl 1386.03053
[13] A. Raz,Index sets of some computable groups, honors thesis, Wellesley College, 2014; https://repository.wellesley.edu/islandora/object/ir
[14] D. Scott,Logic with denumerably long formulas and finite strings of quantifiers, in: The Theory of Models, J. Addition et al. (eds.), North-Holland, Amsterdam, 1965, 329-341. · Zbl 0166.26003
[15] M. Vanden Boom,The effective Borel hierarchy, Fund. Math. 195 (2007), 269-289. · Zbl 1125.03035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.