Switch to: References

Add citations

You must login to add citations.
  1. Degrees of bi-embeddable categoricity of equivalence structures.Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Archive for Mathematical Logic 58 (5-6):543-563.
    We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, \ bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of \ bi-embeddable categoricity and relative \ bi-embeddable categoricity coincide for equivalence structures for \. We also prove that computable equivalence structures have degree of bi-embeddable categoricity \, or \. We furthermore obtain results (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Necessary use of [image] induction in a reversal.Itay Neeman - 2011 - Journal of Symbolic Logic 76 (2):561 - 574.
    Jullien's indecomposability theorem (INDEC) states that if a scattered countable linear order is indecomposable, then it is either indecomposable to the left, or indecomposable to the right. The theorem was shown by Montalbán to be a theorem of hyperarithmetic analysis, and then, in the base system RCA₀ plus ${\mathrm{\Sigma }}_{1}^{1}\text{\hspace{0.17em}}$ induction, it was shown by Neeman to have strength strictly between weak ${\mathrm{\Sigma }}_{1}^{1}$ choice and ${\mathrm{\Delta }}_{1}^{1}$ comprehension. We prove in this paper that ${\mathrm{\Sigma }}_{1}^{1}$ induction is needed for (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Fraïssé’s conjecture in [math]-comprehension.Antonio Montalbán - 2017 - Journal of Mathematical Logic 17 (2):1750006.
    We prove Fraïssé’s conjecture within the system of Π11-comprehension. Furthermore, we prove that Fraïssé’s conjecture follows from the Δ20-bqo-ness of 3 over the system of Arithmetic Transfinite Recursion, and that the Δ20-bqo-ness of 3 is a Π21-statement strictly weaker than Π11-comprehension.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Classes of structures with no intermediate isomorphism problems.Antonio Montalbán - 2016 - Journal of Symbolic Logic 81 (1):127-150.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • On Fraïssé’s conjecture for linear orders of finite Hausdorff rank.Alberto Marcone & Antonio Montalbán - 2009 - Annals of Pure and Applied Logic 160 (3):355-367.
    We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ2, the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in +“φ2 is well-ordered” and, over , implies +“φ2 is well-ordered”.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • Equimorphy: the case of chains.C. Laflamme, M. Pouzet & R. Woodrow - 2017 - Archive for Mathematical Logic 56 (7-8):811-829.
    Two structures are said to be equimorphic if each embeds in the other. Such structures cannot be expected to be isomorphic, and in this paper we investigate the special case of linear orders, here also called chains. In particular we provide structure results for chains having less than continuum many isomorphism classes of equimorphic chains. We deduce as a corollary that any chain has either a single isomorphism class of equimorphic chains or infinitely many.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • On Σ1 1 equivalence relations over the natural numbers.Ekaterina B. Fokina & Sy-David Friedman - 2012 - Mathematical Logic Quarterly 58 (1-2):113-124.
    We study the structure of Σ11 equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h-reducibility and FF-reducibility, respectively. We show that the structure is rich even when one fixes the number of properly equation imagei.e., Σ11 but not equation image equivalence classes. We also show the existence of incomparable Σ11 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ11 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • Isomorphism relations on computable structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
    We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  • Computable bi-embeddable categoricity.Luca San Mauro, Nikolay Bazhenov, Ekaterina Fokina & Dino Rossegger - 2018 - Algebra and Logic 5 (57):392-396.
    We study the algorithmic complexity of isomorphic embeddings between computable structures.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•