On optimal Scott sentences of finitely generated algebraic structures

Harrison-Trainor, Matthew; Ho, Meng-Che

doi:10.1090/proc/14063

On optimal Scott sentences of finitely generated algebraic structures
HTML articles powered by AMS MathViewer

by Matthew Harrison-Trainor and Meng-Che Ho PDF

Proc. Amer. Math. Soc. 146 (2018), 4473-4485 Request permission

Abstract:

Scott showed that for every countable structure $\mathcal {A}$, there is a sentence of the infinitary logic $\mathcal {L}_{\omega _1\omega }$, called a Scott sentence for $\mathcal {A}$, whose countable models are exactly the isomorphic copies of $\mathcal {A}$. Thus, the least quantifier complexity of a Scott sentence of a structure is an invariant that measures the complexity “describing” the structure. Knight et al. have studied the Scott sentences of many structures. In particular, Knight and Saraph showed that a finitely generated structure always has a $\Sigma ^0_3$ Scott sentence. We give a characterization of the finitely generated structures for which the $\Sigma ^0_3$ Scott sentence is optimal. One application of this result is to give a construction of a finitely generated group where the $\Sigma ^0_3$ Scott sentence is optimal.

References

R. Alvir, J. F. Knight, and C. F. D. McCoy, Complexity of scott sentences, Preprint.
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
V. Kalvert, V. S. Kharizanova, D. F. Naĭt, and S. Miller, Index sets of computable models, Algebra Logika 45 (2006), no. 5, 538–574, 631–632 (Russian, with Russian summary); English transl., Algebra Logic 45 (2006), no. 5, 306–325. MR 2307694, DOI 10.1007/s10469-006-0029-0
J. Carson, V. Harizanov, J. Knight, K. Lange, C. McCoy, A. Morozov, S. Quinn, C. Safranski, and J. Wallbaum, Describing free groups, Trans. Amer. Math. Soc. 364 (2012), no. 11, 5715–5728. MR 2946928, DOI 10.1090/S0002-9947-2012-05456-0
Meng-Che Ho, Describing groups, Proc. Amer. Math. Soc. 145 (2017), no. 5, 2223–2239. MR 3611333, DOI 10.1090/proc/13458
J. F. Knight and C. McCoy, Index sets and Scott sentences, Arch. Math. Logic 53 (2014), no. 5-6, 519–524. MR 3237865, DOI 10.1007/s00153-014-0377-8
Julia F. Knight and Vikram Saraph, Scott sentences for certain groups, Archive for Mathematical Logic (2017).
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
Douglas E. Miller, The invariant $\Pi ^{0}_{\alpha }$ separation principle, Trans. Amer. Math. Soc. 242 (1978), 185–204. MR 496802, DOI 10.1090/S0002-9947-1978-0496802-9
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