63 found
Order:
  1. 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   19 citations  
  2.  21
    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.
  3.  48
    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   14 citations  
  4.  16
    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   9 citations  
  5.  16
    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   12 citations  
  6.  16
    Embedding Brouwer Algebras in the Medvedev Lattice.Andrea Sorbi - 1991 - Notre Dame Journal of Formal Logic 32 (2):266-275.
  7.  13
    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   3 citations  
  8.  39
    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 (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  9.  24
    Some Quotient Lattices of the Medvedev Lattice.Andrea Sorbi - 1991 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (9-12):167-182.
  10.  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   9 citations  
  11. 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  
  12.  15
    Some Quotient Lattices of the Medvedev Lattice.Andrea Sorbi - 1991 - Mathematical Logic Quarterly 37 (9‐12):167-182.
  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.  6
    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  
  15.  19
    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   1 citation  
  16.  27
    Universal Recursion Theoretic Properties of R.E. Preordered Structures.Franco Montagna & Andrea Sorbi - 1985 - Journal of Symbolic Logic 50 (2):397-406.
  17.  39
    Trial and Error Mathematics I: Dialectical and Quasidialectical Systems.Jacopo Amidei, Duccio Pianigiani, Luca San Mauro, Giulia Simi & Andrea Sorbi - 2016 - Review of Symbolic Logic 9 (2):299-324.
  18.  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   4 citations  
  19.  10
    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  
     
    Export citation  
     
    Bookmark   5 citations  
  20.  17
    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   2 citations  
  21.  27
    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   1 citation  
  22.  24
    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   2 citations  
  23.  38
    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  
  24.  28
    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 (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  25.  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   4 citations  
  26. 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  
  27.  21
    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  
  28. 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   1 citation  
  29.  31
    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  
  30.  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  
  31.  51
    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  
  32.  27
    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  
     
    Export citation  
     
    Bookmark   1 citation  
  33.  7
    A Note on Initial Segments of the Enumeration Degrees.Theodore A. Slaman & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (2):633-643.
  34.  17
    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.
  35.  16
    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  
  36.  72
    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  
  37.  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  
  38.  15
    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  
  39.  40
    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. Branching in the InlineEquation ID=" IEq1"> ImageObject FileRef=" 153200881ArticleIEq1. Gif" Format=" GIF" Color=" BlackWhit" Type=" Linedraw" Rendition=" HTML"/> EquationSource Format=" TEX">-Enumeration. [REVIEW]Maria L. Affatato, Thomas F. Kent & Andrea Sorbi - 2008 - Archive for Mathematical Logic 47 (3):221-232.
    We give an alternative and more informative proof that every incomplete \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{0}_{2}}$$\end{document} -enumeration degree is the meet of two incomparable \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{0}_{2}}$$\end{document} -degrees, which allows us to show the stronger result that for every incomplete \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{0}_{2}}$$\end{document} -enumeration degree a, there exist enumeration degrees x1 and x2 such that a, x1, x2 are incomparable, and for (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  41. Initial Segments of the Degrees of Ceers.Uri Andrews & Andrea Sorbi - forthcoming - Journal of Symbolic Logic:1-23.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42.  21
    Computability in Context: Computation and Logic in the Real World.S. B. Cooper & Andrea Sorbi (eds.) - 2011 - 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  
     
    Export citation  
     
    Bookmark  
  43.  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   2 citations  
  44.  27
    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.
    Direct download  
     
    Export citation  
     
    Bookmark  
  45.  31
    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.
  46.  43
    ? 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  
  47.  8
    Classifying equivalence relations in the Ershov hierarchy.Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi & Mars Yamaleev - 2020 - Archive for Mathematical Logic 59 (7-8):835-864.
    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  
  48.  11
    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  
  49.  5
    Word Problems and Ceers.Valentino Delle Rose, Luca San Mauro & Andrea Sorbi - 2020 - Mathematical Logic Quarterly 66 (3):341-354.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  50.  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  
     
    Export citation  
     
    Bookmark  
1 — 50 / 63