5 papers
Scott Analysis below the Vaught Ordinal
David Gonzalez, Dino Rossegger, Dan Turetsky
We develop new tools for determining the existence of models of specific Scott ranks under countability conditions. Using these, we improve a result of Sacks by showing that any co…
Structural vs. computational complexity
Johanna N. Y. Franklin, Dino Rossegger, Dan Turetsky
We consider highness in the context of computable structure theory and, particularly, the Scott rank of a structure. We define highness for Scott rank and highness for computably d…
Classifying the complexity of models of arithmetic
David Gonzalez, Mateusz ÅeÅyk, Dino Rossegger +1
We classify the possible Scott complexities for models of Peano arithmetic. We construct models of particular complexities by first giving a complete Scott analysis of colored line…
The Borel complexity of the class of models of first-order theories
Uri Andrews, David Gonzalez, Steffen Lempp +2
We investigate the descriptive complexity of the set of models of first-order theories. Using classical results of Knight and Solovay, we give a sharp condition for complete theori…
Hausdorff dimension and countable Borel equivalence relations
Andrew Marks, Dino Rossegger, Theodore Slaman
We show that if is a countable Borel equivalence relation on , then there is a closed subset of Hausdorff dimension so that $E \restrictio…