12 found
Order:
Disambiguations
Mariya I. Soskova [11]Mariya Ivanova Soskova [1]
  1.  17
    Density of the cototal enumeration degrees.Joseph S. Miller & Mariya I. Soskova - 2018 - Annals of Pure and Applied Logic 169 (5):450-462.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  2.  13
    A structural dichotomy in the enumeration degrees.Hristo A. Ganchev, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2022 - Journal of Symbolic Logic 87 (2):527-544.
    We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half of a nontrivial relativized $\mathcal {K}$ -pair. This leads to a structural dichotomy in the enumeration degrees.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  33
    How Enumeration Reducibility Yields Extended Harrington Non-Splitting.Mariya I. Soskova & S. Barry Cooper - 2008 - Journal of Symbolic Logic 73 (2):634 - 655.
  4.  8
    A structural dichotomy in the enumeration degrees.Hristo A. Ganchev, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2020 - Journal of Symbolic Logic:1-18.
    We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half a nontrivial relativized K-pair. This leads to a structural dichotomy in the enumeration degrees.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  11
    A non-splitting theorem in the enumeration degrees.Mariya Ivanova Soskova - 2009 - Annals of Pure and Applied Logic 160 (3):400-418.
    We complete a study of the splitting/non-splitting properties of the enumeration degrees below by proving an analog of Harrington’s non-splitting theorem for the enumeration degrees. We show how non-splitting techniques known from the study of the c.e. Turing degrees can be adapted to the enumeration degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  6.  13
    Cupping and definability in the local structure of the enumeration degrees.Hristo Ganchev & Mariya I. Soskova - 2012 - Journal of Symbolic Logic 77 (1):133-158.
    We show that every splitting of ${0}_{\mathrm{e}}^{\prime }$ in the local structure of the enumeration degrees, $$\mathcal{G}_{e} , contains at least one low-cuppable member. We apply this new structural property to show that the classes of all $\mathcal{K}$ -pairs in $\mathcal{G}_{e}$ , all downwards properly ${\mathrm{\Sigma }}_{2}^{0}$ enumeration degrees and all upwards properly ${\mathrm{\Sigma }}_{2}^{0}$ enumeration degrees are first order definable in $\mathcal{G}_{e}$.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  29
    The limitations of cupping in the local structure of the enumeration degrees.Mariya I. Soskova - 2010 - Archive for Mathematical Logic 49 (2):169-193.
    We prove that a sequence of sets containing representatives of cupping partners for every nonzero ${\Delta^0_2}$ enumeration degree cannot have a ${\Delta^0_2}$ enumeration. We also prove that no subclass of the ${\Sigma^0_2}$ enumeration degrees containing the nonzero 3-c.e. enumeration degrees can be cupped to ${\mathbf{0}_e'}$ by a single incomplete ${\Sigma^0_2}$ enumeration degree.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  8.  10
    The automorphism group of the enumeration degrees.Mariya I. Soskova - 2016 - Annals of Pure and Applied Logic 167 (10):982-999.
  9.  23
    Pa Relative to an Enumeration Oracle.G. O. H. Jun Le, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (4):1497-1525.
    Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  19
    Maximal Towers and Ultrafilter Bases in Computability Theory.Steffen Lempp, Joseph S. Miller, André Nies & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (3):1170-1190.
    The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory.We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  12
    Expanding the Reals by Continuous Functions Adds No Computational Power.Uri Andrews, Julia F. Knight, Rutger Kuyper, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (3):1083-1102.
    We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  13
    Enumeration 1-Genericity in the Local Enumeration Degrees. [REVIEW]Liliana Badillo, Charles M. Harris & Mariya I. Soskova - 2018 - Notre Dame Journal of Formal Logic 59 (4):461-489.
    We discuss a notion of forcing that characterizes enumeration 1-genericity, and we investigate the immunity, lowness, and quasiminimality properties of enumeration 1-generic sets and their degrees. We construct an enumeration operator Δ such that, for any A, the set ΔA is enumeration 1-generic and has the same jump complexity as A. We deduce from this and other recent results from the literature that not only does every degree a bound an enumeration 1-generic degree b such that a'=b', but also that, (...))
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation