Switch to: References

Add citations

You must login to add citations.
  1. Ordinal analysis of partial combinatory algebras.Paul Shafer & Sebastiaan A. Terwijn - 2021 - Journal of Symbolic Logic 86 (3):1154-1188.
    For every partial combinatory algebra, we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pca’s, i.e., the smallest ordinals where these relations become equal. We show that the closure ordinal of Kleene’s first model is ${\omega _1^{\textit {CK}}}$ and that the closure ordinal of Kleene’s second model is $\omega _1$. We calculate the exact complexities of the extensionality relations in Kleene’s first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Degrees of categoricity of trees and the isomorphism problem.Mohammad Assem Mahmoud - 2019 - Mathematical Logic Quarterly 65 (3):293-304.
    In this paper, we show that for any computable ordinal α, there exists a computable tree of rank with strong degree of categoricity if α is finite, and with strong degree of categoricity if α is infinite. In fact, these are the greatest possible degrees of categoricity for such trees. For a computable limit ordinal α, we show that there is a computable tree of rank α with strong degree of categoricity (which equals ). It follows from our proofs that, (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • $\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 (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Relative to any non-hyperarithmetic set.Noam Greenberg, Antonio Montalbán & Theodore A. Slaman - 2013 - Journal of Mathematical Logic 13 (1):1250007.
    We prove that there is a structure, indeed a linear ordering, whose degree spectrum is the set of all non-hyperarithmetic degrees. We also show that degree spectra can distinguish measure from category.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Degrees of Categoricity and the Hyperarithmetic Hierarchy.Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore - 2013 - Notre Dame Journal of Formal Logic 54 (2):215-231.
    We study arithmetic and hyperarithmetic degrees of categoricity. We extend a result of E. Fokina, I. Kalimullin, and R. Miller to show that for every computable ordinal $\alpha$, $\mathbf{0}^{}$ is the degree of categoricity of some computable structure $\mathcal{A}$. We show additionally that for $\alpha$ a computable successor ordinal, every degree $2$-c.e. in and above $\mathbf{0}^{}$ is a degree of categoricity. We further prove that every degree of categoricity is hyperarithmetic and show that the index set of structures with degrees (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  • The property “arithmetic-is-recursive” on a cone.Uri Andrews, Matthew Harrison-Trainor & Noah Schweber - 2021 - Journal of Mathematical Logic 21 (3).
    We say that a theory T satisfies arithmetic-is-recursive if any X′-computable model of T has an X-computable copy; that is, the models of T satisfy a sort of jump inversion. We give an example of a...
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • The property “arithmetic-is-recursive” on a cone.Uri Andrews, Matthew Harrison-Trainor & Noah Schweber - 2021 - Journal of Mathematical Logic 21 (3):2150021.
    We say that a theory [Formula: see text] satisfies arithmetic-is-recursive if any [Formula: see text]-computable model of [Formula: see text] has an [Formula: see text]-computable copy; that is, the models of [Formula: see text] satisfy a sort of jump inversion. We give an example of a theory satisfying arithmetic-is-recursive non-trivially and prove that the theories satisfying arithmetic-is-recursive on a cone are exactly those theories with countably many [Formula: see text]-back-and-forth types.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Scott complexity of countable structures.Rachael Alvir, Noam Greenberg, Matthew Harrison-Trainor & Dan Turetsky - 2021 - Journal of Symbolic Logic 86 (4):1706-1720.
    We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$, $\Pi _{\alpha }$, or $\mathrm {d-}\Sigma _{\alpha }$. We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Tree-automatic well-founded trees.Alexander Kartzow, Jiamou Liu & Markus Lohrey - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 363--373.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•