AN INTRODUCTION TO THE SCOTT COMPLEXITY OF COUNTABLE STRUCTURES AND A SURVEY OF RECENT RESULTS

DOI10.1017/bsl.2021.62zbMath1501.03002arXiv2011.03923OpenAlexW3211878077MaRDI QIDQ5067872

Matthew Harrison-Trainor

Publication date: 4 April 2022

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.03923

zbMATH Keywords

computable structure theoryScott rank

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Logic on admissible sets (03C70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Index sets and Scott sentences
• The complexity of computable categoricity
• Strange structures from computable model theory
• The isomorphism problem for classes of computable fields
• Scott rank of Polish metric spaces
• Atomic models higher up
• Bounds on weak scattering
• Complexity ranks of countable models
• Generic copies of countable structures
• Autostability of models
• On the Borel classification of the isomorphism class of a countable model
• Computable structures and the hyperarithmetical hierarchy
• Scott ranks of models of a theory
• Scott sentences for certain groups
• A computability theoretic equivalent to Vaught's conjecture
• Finitely generated groups are universal among finitely generated structures
• The countable admissible ordinal equivalence relation
• Metric Scott analysis
• Bounds on Scott rank for various nonelementary classes
• Three red herrings around Vaught’s conjecture
• Describing free groups
• Describing free groups, Part II: Π⁰₄ hardness and no Σ₂⁰ basis
• Describing groups
• Effectively Existentially-Atomic Structures
• COMPUTABLE STRUCTURES IN GENERIC EXTENSIONS
• COMPUTABLE STRUCTURES OF RANK $\omega_{1}^{{\rm CK}}$
• On optimal Scott sentences of finitely generated algebraic structures
• On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
• Classification from a Computable Viewpoint
• A robuster Scott rank
• Describing Groups
• Index sets of computable structures
• Counting the number of equivalence classes of Borel and coanalytic equivalence relations
• An example concerning Scott heights
• Scott sentences and admissible sets
• The Invariant ∏ 0 α Separation Principle
• An analytic equivalence relation not arising from a Polish group action
• Computably categorical structures and expansions by constants
• Some new computable structures of high rank
• A computably categorical structure whose expansion by a constant has infinite computable dimension
• Model Theory
• Coding in the automorphism group of a computably categorical structure
• Bounds on Scott ranks of some polish metric spaces
• Computable Structure Theory
• SCOTT COMPLEXITY OF COUNTABLE STRUCTURES
• ASSIGNING AN ISOMORPHISM TYPE TO A HYPERDEGREE
• Bounds on continuous Scott rank
• Complexity of Scott sentences
• Scott processes
• The Classification Problem for Compact Computable Metric Spaces
• Index sets for classes of high rank structures
• Computable trees of Scott rank ω₁^CK, and computable approximation
• An interpolation theorem for denumerably long formulas
• Recursive Pseudo-Well-Orderings
• The number of countable models
• Effective model theory vs. recursive model theory