6 found
Order:
  1.  45
    Reverse Mathematics, Computability, and Partitions of Trees.Jennifer Chubb, Jeffry L. Hirst & Timothy H. McNicholl - 2009 - Journal of Symbolic Logic 74 (1):201-215.
    We examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n-tuples of a binary tree are colored.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  2.  39
    Degree Spectra of the Successor Relation of Computable Linear Orderings.Jennifer Chubb, Andrey Frolov & Valentina Harizanov - 2009 - Archive for Mathematical Logic 48 (1):7-13.
    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.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  24
    $\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations.John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl & Sarah Pingrey - 2007 - Journal of Symbolic Logic 72 (3):1003 - 1018.
    We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable $\Pi _{1}^{0}$ subsets of 2ω and Kolmogorov complexity play a major role in the proof.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  3
    Detecting properties from descriptions of groups.Iva Bilanovic, Jennifer Chubb & Sam Roven - 2020 - Archive for Mathematical Logic 59 (3-4):293-312.
    We consider whether given a simple, finite description of a group in the form of an algorithm, it is possible to algorithmically determine if the corresponding group has some specified property or not. When there is such an algorithm, we say the property is recursively recognizable within some class of descriptions. When there is not, we ask how difficult it is to detect the property in an algorithmic sense. We consider descriptions of two sorts: first, recursive presentations in terms of (...)
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  5.  2
    Model Completeness and Relative Decidability.Jennifer Chubb, Russell Miller & Reed Solomon - forthcoming - Archive for Mathematical Logic:1-15.
    We study the implications of model completeness of a theory for the effectiveness of presentations of models of that theory. It is immediate that for a computable model \ of a computably enumerable, model complete theory, the entire elementary diagram \\) must be decidable. We prove that indeed a c.e. theory T is model complete if and only if there is a uniform procedure that succeeds in deciding \\) from the atomic diagram \\) for all countable models \ of T. (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  15
    Partial Automorphism Semigroups.Jennifer Chubb, Valentina S. Harizanov, Andrei S. Morozov, Sarah Pingrey & Eric Ufferman - 2008 - Annals of Pure and Applied Logic 156 (2):245-258.
    We study the relationship between algebraic structures and their inverse semigroups of partial automorphisms. We consider a variety of classes of natural structures including equivalence structures, orderings, Boolean algebras, and relatively complemented distributive lattices. For certain subsemigroups of these inverse semigroups, isomorphism of the subsemigroups yields isomorphism of the underlying structures. We also prove that for some classes of computable structures, we can reconstruct a computable structure, up to computable isomorphism, from the isomorphism type of its inverse semigroup of computable (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark