56 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.  32
    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  
  4.  11
    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.
  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.
  6.  5
    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  
  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   9 citations  
  8.  7
    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  
  9.  35
    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  
  10.  6
    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   10 citations  
  11.  21
    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  
  12.  11
    Embedding Brouwer Algebras in the Medvedev Lattice.Andrea Sorbi - 1991 - Notre Dame Journal of Formal Logic 32 (2):266-275.
  13.  23
    Some Quotient Lattices of the Medvedev Lattice.Andrea Sorbi - 1991 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (9-12):167-182.
  14.  8
    Initial Segments of the Enumeration Degrees.Hristo Ganchev & Andrea Sorbi - 2016 - Journal of Symbolic Logic 81 (1):316-325.
  15.  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.
  16.  10
    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  
  17.  14
    Some Quotient Lattices of the Medvedev Lattice.Andrea Sorbi - 1991 - Mathematical Logic Quarterly 37 (9‐12):167-182.
  18.  2
    Effective Inseparability, Lattices, and Pre-Ordering Relations.Uri Andrews & Andrea Sorbi - forthcoming - Review of Symbolic Logic:1-30.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  6
    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  
  20.  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  
  21.  28
    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  
  22.  8
    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  
  23.  8
    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  
  24.  18
    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   2 citations  
  25.  12
    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.  12
    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  
  27.  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  
  28.  12
    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  
  29.  9
    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  
  30.  50
    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  
  31.  11
    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  
  32.  4
    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  
  33.  6
    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  
  34.  20
    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.
  35.  19
    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.
  36.  16
    Universal Recursion Theoretic Properties of R.E. Preordered Structures.Franco Montagna & Andrea Sorbi - 1985 - Journal of Symbolic Logic 50 (2):397-406.
  37.  4
    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.
  38.  24
    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.
  39.  23
    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  
  40.  22
    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  
  41.  37
    ? 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  42.  18
    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  
  43.  7
    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  
  44.  8
    Friedberg Numberings in the Ershov Hierarchy.Serikzhan A. Badaev, Mustafa Manat & Andrea Sorbi - 2015 - Archive for Mathematical Logic 54 (1-2):59-73.
  45.  8
    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  
  46.  5
    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  
  47.  4
    Logic and Probabilistic Systems.Franco Montagna, Giulia Simi & Andrea Sorbi - 2000 - Bulletin of Symbolic Logic 6 (2):223-225.
    Direct download  
     
    Export citation  
     
    Bookmark  
  48.  5
    A Note on Initial Segments of the Enumeration Degrees.Theodore A. Slaman & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (2):633-643.
  49.  7
    The Distribution of Properly $Sigma^0_2$ 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 < 0'_e$ there exists an e-degree c such that $a \leq c < 0'_e$, and all degrees b, with $c \leq b < 0'_e$, are properly $\Sigma^0_2$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  50.  2
    Reducibility in Some Categories of Partial Recursive Operators.Caterina Bianchini & Andrea Sorbi - 1992 - Mathematical Logic Quarterly 38 (1):349-359.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 56