41 found
Sort by:
  1. Serikzhan A. Badaev, Mustafa Manat & Andrea Sorbi (forthcoming). Friedberg Numberings in the Ershov Hierarchy. Archive for Mathematical Logic.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. Serikzhan A. Badaev, Mustafa Manat & Andrea Sorbi (2012). Rogers Semilattices of Families of Two Embedded Sets in the Ershov Hierarchy. Mathematical Logic Quarterly 58 (4‐5):366-376.
    No categories
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  3. Thomas F. Kent, Andrew Em Lewis & Andrea Sorbi (2012). Empty Intervals in the Enumeration Degrees. Annals of Pure and Applied Logic 163 (5):567-574.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Daniele Marsibilio & Andrea Sorbi (2012). Bounded Enumeration Reducibility and its Degree Structure. 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 (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Irakli O. Chitaia, Roland Sh Omanadze & Andrea Sorbi (2011). Immunity Properties and Strong Positive Reducibilities. 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. (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  6. S. B. Cooper & Andrea Sorbi (eds.) (2011). Computability in Context: Computation and Logic in the Real World. World Scientific.
    Recent new paradigms of computation, based on biological and physical models, address in a radically new way questions of efficiency and challenge assumptions ...
    Direct download  
     
    My bibliography  
     
    Export citation  
  7. Andrew Em Lewis, Richard A. Shore & Andrea Sorbi (2011). Topological Aspects of the Medvedev Lattice. 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 (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  8. Samuel R. Buss, S. Barry Cooper, Benedikt Löwe & Andrea Sorbi (2009). Preface. Annals of Pure and Applied Logic 160 (3):229-230.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  9. Maria L. Affatato, Thomas F. Kent & Andrea Sorbi (2008). Branching in the {Sigma^0_2} -Enumeration Degrees: A New Perspective. [REVIEW] 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 ).
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Maria L. Affatato, Thomas F. Kent & Andrea Sorbi (2008). Branching in the InlineEquation ID=" IEq1"> ImageObject FileRef=" 153200881ArticleIEq1. Gif" Format=" GIF" Color=" BlackWhit" Type=" Linedraw" Rendition=" HTML"/> EquationSource Format=" TEX">-Enumeration. [REVIEW] Archive for Mathematical Logic 47 (3):221-232.
    No categories
     
    My bibliography  
     
    Export citation  
  11. Roland Sh Omanadze & Andrea Sorbi (2008). A Characterization of the Δ⁰₂ Hyperhyperimmune Sets. 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)  
     
    My bibliography  
     
    Export citation  
  12. Andrea Sorbi & Sebastiaan A. Terwijn (2008). Intermediate Logics and Factors of the Medvedev Lattice. Annals of Pure and Applied Logic 155 (2):69-85.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  13. S. B. Cooper, Benedikt Löwe & Andrea Sorbi (eds.) (2007). New Computational Paradigms: Changing Conceptions of What is Computable. Springer.
    Logicians and theoretical physicists will also benefit from this book.
    Direct download  
     
    My bibliography  
     
    Export citation  
  14. Thomas F. Kent & Andrea Sorbi (2007). Bounding Nonsplitting Enumeration Degrees. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  15. Matthew Giorgi, Andrea Sorbi & Yue Yang (2006). Properly [Image] Enumeration Degrees and the High/Low Hierarchy. Journal of Symbolic Logic 71 (4):1125 - 1144.
    We show that there exist downwards properly $\Sigma _{2}^{0}$ (in fact noncuppable) e-degrees that are not high. We also show that every high e-degree bounds a noncuppable e-degree.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  16. Roland Sh Omanadze & Andrea Sorbi (2006). Strong Enumeration Reducibilities. 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, (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  17. S. Barry Cooper, Angsheng Li, Andrea Sorbi & Yue Yang (2005). Bounding and Nonbounding Minimal Pairs in the Enumeration Degrees. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  18. Steffen Lempp, Theodore A. Slaman & Andrea Sorbi (2005). On Extensions of Embeddings Into the Enumeration Degrees of the -Sets. Journal of Mathematical Logic 5 (02):247-298.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  19. Steffen Lempp & Andrea Sorbi (2002). Embedding Finite Lattices Into the Σ02 Enumeration Degrees. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  20. Steffen Lempp & Andrea Sorbi (2002). Embedding Finite Lattices Into the {$\Sigma\Sp 0\Sb 2$} Enumeration Degrees. Journal of Symbolic Logic 67 (1):69-90.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  21. Marat M. Arslanov, Iskander Sh Kalimullin & Andrea Sorbi (2001). Density Results in the Δ20 E-Degrees. 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.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  22. Stanislaw Bereznyuk, Richard Coles & Andrea Sorbi (2000). The Distribution of Properly $Sigma^0_2$ E-Degrees. 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 (2 more)  
     
    My bibliography  
     
    Export citation  
  23. Stanislaw Bereznyuk, Richard Coles & Andrea Sorbi (2000). The Distribution of Properly Σ02 E-Degrees. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  24. André Nies & Andrea Sorbi (2000). Structural Properties and Σ02 Enumeration Degrees. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  25. Andrea Sorbi (1998). Sets of Generators and Automorphism Bases for the Enumeration Degrees. Annals of Pure and Applied Logic 94 (1-3):263-272.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  26. Caterina Bianchini & Andrea Sorbi (1996). A Note on Closed Degrees of Difficulty of the Medvedev Lattice. Mathematical Logic Quarterly 42 (1):127-133.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  27. S. Barry Cooper & Andrea Sorbi (1996). Noncappable Enumeration Degrees Below 0'e. [REVIEW] Journal of Symbolic Logic 61 (4):1347 - 1363.
    We prove that there exists a noncappable enumeration degree strictly below 0' e.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  28. S. Barry Cooper, Andrea Sorbi & Xiaoding Yi (1996). Cupping and Noncupping in the Enumeration Degrees of ∑20 Sets. Annals of Pure and Applied Logic 82 (3):317-342.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  29. S. Barry Cooper, Andrea Sorbi & Xiaoding Yi (1996). Cupping and Noncupping in the Enumeration Degrees of∑< Sub> 2< Sup> 0 Sets. Annals of Pure and Applied Logic 82 (3):317-342.
    Direct download  
     
    My bibliography  
     
    Export citation  
  30. Franco Montagna, Giulia Simi & Andrea Sorbi (1996). Logic and Probabilistic Systems. 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 (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  31. Andrea Sorbi (1996). The Medvedev Lattice of Degrees of Difficulty. In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. 224--289.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  32. Sandra Fontani, Franco Montagna & Andrea Sorbi (1994). A Note on Relative Efficiency of Axiom Systems. Mathematical Logic Quarterly 40 (2):261-272.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  33. Caterina Bianchini & Andrea Sorbi (1992). Reducibility in Some Categories of Partial Recursive Operators. Mathematical Logic Quarterly 38 (1):349-359.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  34. Andrea Sorbi (1991). Embedding Brouwer Algebras in the Medvedev Lattice. Notre Dame Journal of Formal Logic 32 (2):266-275.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  35. Andrea Sorbi (1991). Some Quotient Lattices of the Medvedev Lattice. Mathematical Logic Quarterly 37 (9‐12):167-182.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  36. Andrea Sorbi (1990). On Some Filters and Ideals of the Medvedev Lattice. 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 (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  37. Andrea Sorbi (1990). Some Remarks on the Algebraic Structure of the Medvedev Lattice. 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 (7 more)  
     
    My bibliography  
     
    Export citation  
  38. Franco Montagna & Andrea Sorbi (1989). Creativeness and Completeness in Recursion Categories of Partial Recursive Operators. Journal of Symbolic Logic 54 (3):1023-1041.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  39. Franco Montagna & Andrea Sorbi (1985). Universal Recursion Theoretic Properties of R.E. Preordered Structures. Journal of Symbolic Logic 50 (2):397-406.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  40. Claudio Bernardi & Andrea Sorbi (1983). Classifying Positive Equivalence Relations. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  41. Andrea Sorbi (1982). ∑0n-Equivalence Relations. 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)  
     
    My bibliography  
     
    Export citation