PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

Complexity of Scott sentences

Volume 251 / 2020

Rachael Alvir, Julia F. Knight, Charles McCoy CSC Fundamenta Mathematicae 251 (2020), 109-129 MSC: Primary 03C75; Secondary 03C57. DOI: 10.4064/fm865-6-2020 Published online: 11 July 2020

Abstract

We give effective versions of some results on Scott sentences. Effectivizing a result of Montalbán (2015), 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 \lt \alpha $. Effectivizing a result of A. Miller (1983), 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 _{ \lt \alpha }$. We also give an effective version of a result of D. Miller (1978) on which the result of A. Miller was based. Using the non-effective results of Montalbán and A. Miller, 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.

Authors

  • Rachael AlvirDepartment of Mathematics
    University of Notre Dame
    255 Hurley
    Notre Dame, IN 46556, U.S.A.
    e-mail
  • Julia F. KnightDepartment of Mathematics
    University of Notre Dame
    255 Hurley
    Notre Dame, IN 46556, U.S.A.
    e-mail
  • Charles McCoy CSCDepartment of Mathematics
    University of Portland
    5000 N. Willamette Blvd.
    Portland, OR 97203, U.S.A.
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image