•  13
    Enumerations in computable structure theory
    with Sergey Goncharov, Julia Knight, Charles McCoy, Russell Miller, and Reed Solomon
    Annals of Pure and Applied Logic 136 (3): 219-246. 2005.
    We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a com…Read more
  •  12
    Degree spectra of the successor relation of computable linear orderings
    with Jennifer Chubb and Andrey Frolov
    Archive for Mathematical Logic 48 (1): 7-13. 2009.
    We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees
  •  10
    Uncountable degree spectra
    Annals of Pure and Applied Logic 54 (3): 255-263. 1991.
    We consider a recursive model and an additional recursive relation R on its domain, such that there are uncountably many different images of R under isomorphisms from to some recursive model isomorphic to . We study properties of the set of Turing degrees of all these isomorphic images of R on the domain of
  •  9
    Dependence relations in computably rigid computable vector spaces
    with Rumen D. Dimitrov and Andrei S. Morozov
    Annals of Pure and Applied Logic 132 (1): 97-108. 2005.
    We construct a computable vector space with the trivial computable automorphism group, but with the dependence relations as complicated as possible, measured by their Turing degrees. As a corollary, we answer a question asked by A.S. Morozov in [Rigid constructive modules, Algebra and Logic, 28 570–583 ; 379–387 ]
  •  7
    with Douglas Cenzer, David Marker, and Carol Wood
    Archive for Mathematical Logic 48 (1): 1-6. 2009.
  •  18
    Spectra of Structures and Relations
    with Russel G. Miller
    Journal of Symbolic Logic 72 (1). 2007.
    We consider embeddings of structures which preserve spectra: if g: M → S with S computable, then M should have the same Turing degree spectrum (as a structure) that g(M) has (as a relation on S). We show that the computable dense linear order L is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph G. Such structures are said to be spectrally universal. We use our results to answer a question of Goncharov, an…Read more
  •  20
    Turing degrees of certain isomorphic images of computable relations
    Annals of Pure and Applied Logic 93 (1-3): 103-113. 1998.
    A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary for to contain every Turing degree. These conditions imply that if every Turing degre…Read more
  •  201
    Frequency computations and the cardinality theorem
    with Martin Kummer and Jim Owings
    Journal of Symbolic Logic 57 (2): 682-687. 1992.
  •  5
    Π₁¹ Relations and Paths through ᵊ
    with Sergey S. Goncharov, Julia F. Knight, and Richard A. Shore
    Journal of Symbolic Logic 69 (2). 2004.