12 found
Order:
  1.  24
    The complexity of Scott sentences of scattered linear orders.Rachael Alvir & Dino Rossegger - 2020 - Journal of Symbolic Logic 85 (3):1079-1101.
    We calculate the complexity of Scott sentences of scattered linear orders. Given a countable scattered linear order L of Hausdorff rank $\alpha $ we show that it has a ${d\text {-}\Sigma _{2\alpha +1}}$ Scott sentence. It follows from results of Ash [2] that for every countable $\alpha $ there is a linear order whose optimal Scott sentence has this complexity. Therefore, our bounds are tight. We furthermore show that every Hausdorff rank 1 linear order has an optimal ${\Pi ^{\mathrm {c}}_{3}}$ (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2.  34
    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  
  3.  20
    Bi‐embeddability spectra and bases of spectra.Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Mathematical Logic Quarterly 65 (2):228-236.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  5
    Degrees of bi-embeddable categoricity.Luca San Mauro, Nikolay Bazhenov, Ekaterina Fokina & Dino Rossegger - 2021 - Computability 1 (10):1-16.
    We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure A as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of A; the degree of bi-embeddable categoricity of A is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  8
    A Lopez-Escobar Theorem for Continuous Domains.Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger, Alexandra Soskova & Stefan Vatev - forthcoming - Journal of Symbolic Logic:1-18.
    We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega $ in vocabulary $\tau $ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is $\Pi ^0_\alpha $ in the Borel hierarchy of this topology if and only if it is definable by a $\Pi ^p_\alpha $ -formula, a positive $\Pi ^0_\alpha $ formula in the infinitary logic $L_{\omega _1\omega }$. As (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6. 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  
  7.  7
    The Structural Complexity of Models of Arithmetic.Antonio Montalbán & Dino Rossegger - forthcoming - Journal of Symbolic Logic:1-17.
    We calculate the possible Scott ranks of countable models of Peano arithmetic. We show that no non-standard model can have Scott rank less than $\omega $ and that non-standard models of true arithmetic must have Scott rank greater than $\omega $. Other than that there are no restrictions. By giving a reduction via $\Delta ^{\mathrm {in}}_{1}$ bi-interpretability from the class of linear orderings to the canonical structural $\omega $ -jump of models of an arbitrary completion T of $\mathrm {PA}$ we (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  12
    On bi-embeddable categoricity of algebraic structures.Nikolay Bazhenov, Dino Rossegger & Maxim Zubkov - 2022 - Annals of Pure and Applied Logic 173 (3):103060.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  6
    Degrees of categoricity and treeable degrees.Barbara F. Csima & Dino Rossegger - forthcoming - Journal of Mathematical Logic.
    In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to [Formula: see text]. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute [Formula: see text]. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree [Formula: see text] with [Formula: see text] for [Formula: see text] a computable ordinal greater than [Formula: see (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  10. Bi-embeddability spectra and basis of spectra.Luca San Mauro, Ekaterina Fokina & Dino Rossegger - 2019 - Mathematical Logic Quarterly 2 (65):228-236.
    We study degree spectra of structures with respect to the bi-embeddability relation. The bi-embeddability spectrum of a structure is the family of Turing degrees of its bi-embeddable copies. To facilitate our study we introduce the notions of bi-embeddable triviality and basis of a spectrum. Using bi-embeddable triviality we show that several known families of degrees are bi-embeddability spectra of structures. We then characterize the bi-embeddability spectra of linear orderings and study bases of bi-embeddability spectra of strongly locally finite graphs.
     
    Export citation  
     
    Bookmark  
  11.  3
    Measuring the complexity of reductions between equivalence relations.Luca San Mauro, Ekaterina Fokina & Dino Rossegger - 2019 - Computability 3 (8):265-280.
    Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibility. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  12.  9
    Degree Spectra of Analytic Complete Equivalence Relations.Dino Rossegger - 2022 - Journal of Symbolic Logic 87 (4):1663-1676.
    We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by these relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a $\boldsymbol {\Sigma }^1_1$ complete equivalence relation. We then investigate the algorithmic properties of this reduction. We obtain that elementary bi-embeddability on the class of computable graphs is $\Sigma ^1_1$ complete with respect (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark