9 papers
Characterizing relative decidability in terms of model completeness
Matthew Harrison-Trainor, Liam Tan
A theory is said to be relatively decidable if for every model of , one can compute the elementary diagram of that model from its atomic diagram together with . We verify…
Scott spectral gaps for trees are bounded
Matthew Harrison-Trainor, J. Thomas Kim
Given a Borel class of trees, we show that there is a tree in that class whose Scott sentence is not too much more complicated than the definition of the class. In particular, if t…
Dichotomy results for classes of countable graphs
Vittorio Cipriani, Ekaterina Fokina, Matthew Harrison-Trainor +2
We study classes of countable graphs where every member does not contain a given finite graph as an induced subgraph -- denoted by for a given finite g…
Optimal Syntactic Definitions of Back-and-Forth Types
Ruiyuan Chen, David Gonzalez, Matthew Harrison-Trainor
The back-and-forth relations are central to computable structure theory and countable model theory. It is well-known that the relation is (ligh…
Measuring the complexity of characterizing , , and up to homeomorphism
Matthew Harrison-Trainor, Eissa Haydar
In analogy to the study of Scott rank/complexity of countable structures, we initiate the study of the Wadge degrees of the set of homeomorphic copies of topological spaces. One ca…
Relative to any non-arithmetic set
Matthew Harrison-Trainor
Given a countable structure , the degree spectrum of is the set of all Turing degrees which can compute an isomorphic copy of . One of the m…