60 found
Order:
  1. Structural Properties and Σ20 Enumeration Degrees.André Nies & Andrea Sorbi - 2000 - Journal of Symbolic Logic 65 (1):285-292.
    We prove that each Σ 0 2 set which is hypersimple relative to $\emptyset$ ' is noncuppable in the structure of the Σ 0 2 enumeration degrees. This gives a connection between properties of Σ 0 2 sets under inclusion and and the Σ 0 2 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to $\emptyset$ '.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  2. The Distribution of Properly Σ20 E-Degrees.Stanislaw Bereznyuk, Richard Coles & Andrea Sorbi - 2000 - Journal of Symbolic Logic 65 (1):19-32.
    We show that for every enumeration degree $a there exists an e-degree c such that $a \leq c , and all degrees b, with $c \leq b , are properly Σ 0 2.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  3.  18
    Universal Computably Enumerable Equivalence Relations.Uri Andrews, Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (1):60-88.
  4.  10
    The Theory of Ceers Computes True Arithmetic.Uri Andrews, Noah Schweber & Andrea Sorbi - 2020 - Annals of Pure and Applied Logic 171 (8):102811.
    We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of L-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of (N, +, \times) .
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5. On Extensions of Embeddings Into the Enumeration Degrees of the -Sets.Steffen Lempp, Theodore A. Slaman & Andrea Sorbi - 2005 - Journal of Mathematical Logic 5 (02):247-298.
    We give an algorithm for deciding whether an embedding of a finite partial order [Formula: see text] into the enumeration degrees of the [Formula: see text]-sets can always be extended to an embedding of a finite partial order [Formula: see text].
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  6.  5
    Effective Inseparability, Lattices, and Preordering Relations.Uri Andrews & Andrea Sorbi - forthcoming - Review of Symbolic Logic:1-28.
    We study effectively inseparable prelattices $\wedge, \vee$ are binary computable operations; ${ \le _L}$ is a computably enumerable preordering relation, with $0{ \le _L}x{ \le _L}1$ for every x; the equivalence relation ${ \equiv _L}$ originated by ${ \le _L}$ is a congruence on L such that the corresponding quotient structure is a nontrivial bounded lattice; the ${ \equiv _L}$ -equivalence classes of 0 and 1 form an effectively inseparable pair of sets). Solving a problem in we show, that if (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7. Classifying Positive Equivalence Relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.
    Given two (positive) equivalence relations ∼ 1 , ∼ 2 on the set ω of natural numbers, we say that ∼ 1 is m-reducible to ∼ 2 if there exists a total recursive function h such that for every x, y ∈ ω, we have $x \sim_1 y \operatorname{iff} hx \sim_2 hy$ . We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a "uniformity property" holds). This (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  8.  11
    Intermediate Logics and Factors of the Medvedev Lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
    We investigate the initial segments of the Medvedev lattice as Brouwer algebras, and study the propositional logics connected to them.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  9.  8
    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   7 citations  
  10.  13
    Cupping and Noncupping in the Enumeration Degrees of ∑20 Sets.S. Barry Cooper, Andrea Sorbi & Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (3):317-342.
    We prove the following three theorems on the enumeration degrees of ∑20 sets. Theorem A: There exists a nonzero noncuppable ∑20 enumeration degree. Theorem B: Every nonzero Δ20enumeration degree is cuppable to 0′e by an incomplete total enumeration degree. Theorem C: There exists a nonzero low Δ20 enumeration degree with the anticupping property.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  11.  44
    Some Remarks on the Algebraic Structure of the Medvedev Lattice.Andrea Sorbi - 1990 - Journal of Symbolic Logic 55 (2):831-853.
    This paper investigates the algebraic structure of the Medvedev lattice M. We prove that M is not a Heyting algebra. We point out some relations between M and the Dyment lattice and the Mucnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  12.  45
    Embedding Finite Lattices Into the Σ20 Enumeration Degrees.Steffen Lempp & Andrea Sorbi - 2002 - Journal of Symbolic Logic 67 (1):69-90.
    We show that every finite lattice is embeddable into the Σ 0 2 enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  13.  3
    The Medvedev Lattice of Degrees of Difficulty.Andrea Sorbi - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. pp. 224--289.
  14.  35
    Topological Aspects of the Medvedev Lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.
    We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  15.  15
    Embedding Brouwer Algebras in the Medvedev Lattice.Andrea Sorbi - 1991 - Notre Dame Journal of Formal Logic 32 (2):266-275.
  16.  24
    Some Quotient Lattices of the Medvedev Lattice.Andrea Sorbi - 1991 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (9-12):167-182.
  17.  6
    Classifying equivalence relations in the Ershov hierarchy.Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi & Mars Yamaleev - forthcoming - Archive for Mathematical Logic:1-30.
    Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by \ on the \ equivalence relations. (...)
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  18.  22
    Generalizations of the Weak Law of the Excluded Middle.Andrea Sorbi & Sebastiaan A. Terwijn - 2015 - Notre Dame Journal of Formal Logic 56 (2):321-331.
    We study a class of formulas generalizing the weak law of the excluded middle and provide a characterization of these formulas in terms of Kripke frames and Brouwer algebras. We use these formulas to separate logics corresponding to factors of the Medvedev lattice.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  19.  15
    Some Quotient Lattices of the Medvedev Lattice.Andrea Sorbi - 1991 - Mathematical Logic Quarterly 37 (9‐12):167-182.
  20.  30
    Density Results in the Δ 2 0 E-Degrees.Marat M. Arslanov, Iskander Sh Kalimullin & Andrea Sorbi - 2001 - Archive for Mathematical Logic 40 (8):597-614.
    We show that the Δ0 2 enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  21.  9
    A Note on Closed Degrees of Difficulty of the Medvedev Lattice.Caterina Bianchini & Andrea Sorbi - 1996 - Mathematical Logic Quarterly 42 (1):127-133.
    We consider some nonprincipal filters of the Medvedev lattice. We prove that the filter generated by the nonzero closed degrees of difficulty is not principal and we compare this filter, with respect to inclusion, with some other filters of the lattice. All the filters considered in this paper are disjoint from the prime ideal generated by the dense degrees of difficulty.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  22.  14
    Bounding Nonsplitting Enumeration Degrees.Thomas F. Kent & Andrea Sorbi - 2007 - Journal of Symbolic Logic 72 (4):1405 - 1417.
    We show that every nonzero $\Sigma _{2}^{0}$ enumeration degree bounds a nonsplitting nonzero enumeration degree.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  23.  30
    Bounding and Nonbounding Minimal Pairs in the Enumeration Degrees.S. Barry Cooper, Angsheng Li, Andrea Sorbi & Yue Yang - 2005 - Journal of Symbolic Logic 70 (3):741 - 766.
    We show that every nonzero $\Delta _{2}^{0}$ e-degree bounds a minimal pair. On the other hand, there exist $\Sigma _{2}^{0}$ e-degrees which bound no minimal pair.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  24.  16
    Bounded Enumeration Reducibility and its Degree Structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
    We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by ≤be, which is a natural extension of s-reducibility ≤s. We show that ≤s, ≤be, and enumeration reducibility do not coincide on the ${\Pi^0_1}$ –sets, and the structure ${\boldsymbol{\mathcal{D}_{\rm be}}}$ of the be-degrees is not elementarily equivalent to the structure of the s-degrees. We show also that the first order theory of ${\boldsymbol{\mathcal{D}_{\rm be}}}$ is computably isomorphic to true second order arithmetic: this answers an open question raised by (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  25.  17
    Noncappable Enumeration Degrees Below 0'e. [REVIEW]S. Barry Cooper & Andrea Sorbi - 1996 - Journal of Symbolic Logic 61 (4):1347 - 1363.
    We prove that there exists a noncappable enumeration degree strictly below 0' e.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  26.  1
    A note on uniform density in weak arithmetical theories.Duccio Pianigiani & Andrea Sorbi - forthcoming - Archive for Mathematical Logic:1-15.
    Answering a question raised by Shavrukov and Visser :569–582, 2014), we show that the lattice of \-sentences ) over any computable enumerable consistent extension T of \ is uniformly dense. We also show that for every \ and \ refer to the known hierarchies of arithmetical formulas introduced by Burr for intuitionistic arithmetic) the lattices of \-sentences over any c.e. consistent extension T of the intuitionistic version of Robinson Arithmetic \ are uniformly dense. As an immediate consequence of the proof, (...)
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  27.  70
    Branching in the $${\Sigma^0_2}$$ -Enumeration Degrees: A New Perspective. [REVIEW]Maria L. Affatato, Thomas F. Kent & Andrea Sorbi - 2008 - Archive for Mathematical Logic 47 (3):221-231.
    We give an alternative and more informative proof that every incomplete ${\Sigma^{0}_{2}}$ -enumeration degree is the meet of two incomparable ${\Sigma^{0}_{2}}$ -degrees, which allows us to show the stronger result that for every incomplete ${\Sigma^{0}_{2}}$ -enumeration degree a, there exist enumeration degrees x 1 and x 2 such that a, x 1, x 2 are incomparable, and for all b ≤ a, b = (b ∨ x 1 ) ∧ (b ∨ x 2 ).
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  28.  22
    New Computational Paradigms: Changing Conceptions of What is Computable.S. B. Cooper, Benedikt Löwe & Andrea Sorbi (eds.) - 2007 - Springer.
    Logicians and theoretical physicists will also benefit from this book.
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  29.  6
    On Some Filters and Ideals of the Medvedev Lattice.Andrea Sorbi - 1990 - Archive for Mathematical Logic 30 (1):29-48.
    Let $\mathfrak{M}$ be the Medvedev lattice: this paper investigates some filters and ideals (most of them already introduced by Dyment, [4]) of $\mathfrak{M}$ . If $\mathfrak{G}$ is any of the filters or ideals considered, the questions concerning $\mathfrak{G}$ which we try to answer are: (1) is $\mathfrak{G}$ prime? What is the cardinality of ${\mathfrak{M} \mathord{\left/ {\vphantom {\mathfrak{M} \mathfrak{G}}} \right. \kern-0em} \mathfrak{G}}$ ? Occasionally, we point out some general facts on theT-degrees or the partial degrees, by which these questions can be (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  30.  15
    Logic and Probabilistic Systems.Franco Montagna, Giulia Simi & Andrea Sorbi - 1996 - Archive for Mathematical Logic 35 (4):225-261.
    Following some ideas of Roberto Magari, we propose trial and error probabilistic functions, i.e. probability measures on the sentences of arithmetic that evolve in time by trial and error. The set ℐ of the sentences that get limit probability 1 is a Π3—theory, in fact ℐ can be a Π3—complete set. We prove incompleteness results for this setting, by showing for instance that for every k > 0 there are true Π3—sentences that get limit probability less than 1/2k. No set (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  31.  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   1 citation  
  32.  25
    Universal Recursion Theoretic Properties of R.E. Preordered Structures.Franco Montagna & Andrea Sorbi - 1985 - Journal of Symbolic Logic 50 (2):397-406.
  33.  2
    Incomparability in local structures of s -degrees and Q -degrees.Irakli Chitaia, Keng Meng Ng, Andrea Sorbi & Yue Yang - forthcoming - Archive for Mathematical Logic:1-15.
    We show that for every intermediate \s-degree there exists an incomparable \s-degree. As a consequence, for every intermediate \Q-degree there exists an incomparable \Q-degree. We also show how these results can be applied to provide proofs or new proofs of upper density results in local structures of s-degrees and Q-degrees.
    No categories
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  34.  9
    Initial Segments of the Enumeration Degrees.Hristo Ganchev & Andrea Sorbi - 2016 - Journal of Symbolic Logic 81 (1):316-325.
    Using properties of${\cal K}$-pairs of sets, we show that every nonzero enumeration degreeabounds a nontrivial initial segment of enumeration degrees whose nonzero elements have all the same jump asa. Some consequences of this fact are derived, that hold in the local structure of the enumeration degrees, including: There is an initial segment of enumeration degrees, whose nonzero elements are all high; there is a nonsplitting high enumeration degree; every noncappable enumeration degree is high; every nonzero low enumeration degree can be (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  35.  18
    Jumps of Computably Enumerable Equivalence Relations.Uri Andrews & Andrea Sorbi - 2018 - Annals of Pure and Applied Logic 169 (3):243-259.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  36.  10
    Comparing the Degrees of Enumerability and the Closed Medvedev Degrees.Paul Shafer & Andrea Sorbi - 2019 - Archive for Mathematical Logic 58 (5-6):527-542.
    We compare the degrees of enumerability and the closed Medvedev degrees and find that many situations occur. There are nonzero closed degrees that do not bound nonzero degrees of enumerability, there are nonzero degrees of enumerability that do not bound nonzero closed degrees, and there are degrees that are nontrivially both degrees of enumerability and closed degrees. We also show that the compact degrees of enumerability exactly correspond to the cototal enumeration degrees.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  37.  35
    Creativeness and Completeness in Recursion Categories of Partial Recursive Operators.Franco Montagna & Andrea Sorbi - 1989 - Journal of Symbolic Logic 54 (3):1023-1041.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  38.  12
    Sets of Generators and Automorphism Bases for the Enumeration Degrees.Andrea Sorbi - 1998 - Annals of Pure and Applied Logic 94 (1-3):263-272.
    We exhibit some automorphism bases for the enumeration degrees, and we derive some consequences relative to the automorphisms of the enumeration degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  39.  13
    Cupping and Noncupping in the Enumeration Degrees of∑< Sub> 2< Sup> 0 Sets.S. Barry Cooper, Andrea Sorbi & Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (3):317-342.
  40.  22
    Reducibility in Some Categories of Partial Recursive Operators.Caterina Bianchini & Andrea Sorbi - 1992 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 38 (1):349-359.
  41.  5
    Noncappable Enumeration Degrees Below $0'_e$.S. Cooper & Andrea Sorbi - 1996 - Journal of Symbolic Logic 61 (3):1347-1363.
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  42.  30
    Empty Intervals in the Enumeration Degrees.Thomas F. Kent, Andrew Em Lewis & Andrea Sorbi - 2012 - Annals of Pure and Applied Logic 163 (5):567-574.
  43.  22
    A Note on the Enumeration Degrees of 1-Generic Sets.Liliana Badillo, Caterina Bianchini, Hristo Ganchev, Thomas F. Kent & Andrea Sorbi - 2016 - Archive for Mathematical Logic 55 (3-4):405-414.
    We show that every nonzero Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^{0}_{2}}$$\end{document} enumeration degree bounds the enumeration degree of a 1-generic set. We also point out that the enumeration degrees of 1-generic sets, below the first jump, are not downwards closed, thus answering a question of Cooper.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  44.  40
    ? 0 N -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
    In this paper we study the reducibility order m (defined in a natural way) over n 0 -equivalence relations. In particular, for every n> 0 we exhibit n 0 -equivalence relations which are complete with respect to m and investigate some consequences of this fact (see Introduction).
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  45.  24
    Rogers Semilattices of Families of Two Embedded Sets in the Ershov Hierarchy.Serikzhan A. Badaev, Mustafa Manat & Andrea Sorbi - 2012 - Mathematical Logic Quarterly 58 (4-5):366-376.
    Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every equation image-computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  46.  21
    A Note on Relative Efficiency of Axiom Systems.Sandra Fontani, Franco Montagna & Andrea Sorbi - 1994 - Mathematical Logic Quarterly 40 (2):261-272.
    We introduce a notion of relative efficiency for axiom systems. Given an axiom system Aβ for a theory T consistent with S12, we show that the problem of deciding whether an axiom system Aα for the same theory is more efficient than Aβ is II2-hard. Several possibilities of speed-up of proofs are examined in relation to pairs of axiom systems Aα, Aβ, with Aα ⊇ Aβ, both in the case of Aα, Aβ having the same language, and in the case (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  47.  10
    Weakly Precomplete Computably Enumerable Equivalence Relations.Serikzhan Badaev & Andrea Sorbi - 2016 - Mathematical Logic Quarterly 62 (1-2):111-127.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  48.  14
    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  
  49.  10
    Friedberg Numberings in the Ershov Hierarchy.Serikzhan A. Badaev, Mustafa Manat & Andrea Sorbi - 2015 - Archive for Mathematical Logic 54 (1-2):59-73.
    We show that for every ordinal notation ξ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\xi}$$\end{document} of a nonzero computable ordinal, there exists a Σξ-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{-1}_\xi}$$\end{document}—computable family which up to equivalence has exactly one Friedberg numbering, which does not induce the least element in the corresponding Rogers semilattice.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  50.  7
    Bounding and Nonbounding Minimal Pairs in the Enumeration Degrees.S. Barry Cooper, Angsheng Li, Andrea Sorbi & Yue Yang - 2005 - Journal of Symbolic Logic 70 (3):741-766.
    We show that every nonzero Δ⁰₂ e-degree bounds a minimal pair. On the other hand, there exist Σ⁰₂ e-degrees which bound no minimal pair.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 60