Alvir, Rachael; Knight, Julia F.; McCoy CSC, Charles Complexity of Scott sentences. (English) Zbl 1485.03103 Fundam. Math. 251, No. 2, 109-129 (2020). 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. Cited in 1 ReviewCited in 5 Documents MSC: 03C57 Computable structure theory, computable model theory 03C75 Other infinitary logic 03D45 Theory of numerations, effectively presented structures Keywords:infinitary logic; Scott sentence; Borel hierarchy; finitely generated groups; computable structure theory Citations:Zbl 1386.03053; Zbl 0487.03013; Zbl 0409.03030 PDFBibTeX XMLCite \textit{R. Alvir} et al., Fundam. Math. 251, No. 2, 109--129 (2020; Zbl 1485.03103) 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.