9 found
Order:
  1.  10
    Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
    We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  2.  7
    Some Structural Properties of Quasi-Degrees.Roland Sh Omanadze - 2018 - Logic Journal of the IGPL 26 (1):191-201.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  11
    A Characterization of the Δ⁰₂ Hyperhyperimmune Sets.Roland Sh Omanadze & Andrea Sorbi - 2008 - Journal of Symbolic Logic 73 (4):1407-1415.
    Let A be an infinite Δ₂⁰ set and let K be creative: we show that K≤Q A if and only if K≤Q₁ A. (Here ≤Q denotes Q-reducibility, and ≤Q₁ is the subreducibility of ≤Q obtained by requesting that Q-reducibility be provided by a computable function f such that Wf(x)∩ Wf(y)=∅, if x \not= y.) Using this result we prove that A is hyperhyperimmune if and only if no Δ⁰₂ subset B of A is s-complete, i.e., there is no Δ⁰₂ subset (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  15
    Immunity Properties and Strong Positive Reducibilities.Irakli O. Chitaia, Roland Sh Omanadze & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):341-352.
    We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has ${\overline{K}\not\le_{\rm ss} B}$ (respectively, ${\overline{K}\not\le_{\overline{\rm s}} B}$ ): here ${\le_{\overline{\rm s}}}$ is the finite-branch version of s-reducibility, ≤ss is the computably bounded version of ${\le_{\overline{\rm s}}}$ , and ${\overline{K}}$ is the complement of the halting set. (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5. R ‐Maximal Sets and Q1,N‐Reducibility.Roland Sh Omanadze & Irakli O. Chitaia - forthcoming - Mathematical Logic Quarterly.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  6. $$sQ_1$$-Degrees of Computably Enumerable Sets.Roland Sh Omanadze - forthcoming - Archive for Mathematical Logic.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  1
    $$sQ_1$$ s Q 1 -degrees of computably enumerable sets.Roland Sh Omanadze - forthcoming - Archive for Mathematical Logic:1-17.
    We show that the sQ-degree of a hypersimple set includes an infinite collection of \-degrees linearly ordered under \ with order type of the integers and each c.e. set in these sQ-degrees is a hypersimple set. Also, we prove that there exist two c.e. sets having no least upper bound on the \-reducibility ordering. We show that the c.e. \-degrees are not dense and if a is a c.e. \-degree such that \, then there exist infinitely many pairwise sQ-incomputable c.e. (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  9
    On the Bounded Quasi‐Degrees of C.E. Sets.Roland Sh Omanadze - 2013 - Mathematical Logic Quarterly 59 (3):238-246.
  9.  15
    A Characterization of the $\delta _{2}^{0}$ Hyperhyperimmune Sets.Roland Sh Omanadze & Andrea Sorbi - 2008 - Journal of Symbolic Logic 73 (4):1407 - 1415.
    Let A be an infinite $\Delta _{2}^{0}$ set and let K be creative: we show that K ≤Q A if and only if K ≤Q1 A. (Here ≤Q denotes Q-reducibility, and ≤Q1 is the subreducibility of ≤Q obtained by requesting that Q-reducibility be provided by a computable function f such that Wf(x) ∩ Wf(y) = ∅, if x ≠ y.) Using this result we prove that A is hyperhyperimmune if and only if no $\Delta _{2}^{0}$ subset B of A is (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations