11 found
Order:
  1.  80
    Effective Choice and Boundedness Principles in Computable Analysis.Vasco Brattka & Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (1):73-117.
    In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified certain choice (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  2.  10
    Completion of Choice.Vasco Brattka & Guido Gherardi - 2021 - Annals of Pure and Applied Logic 172 (3):102914.
    We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of total (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  13
    The Bolzano–Weierstrass Theorem is the Jump of Weak Kőnig’s Lemma.Vasco Brattka, Guido Gherardi & Alberto Marcone - 2012 - Annals of Pure and Applied Logic 163 (6):623-655.
  4.  14
    Weihrauch Degrees, Omniscience Principles and Weak Computability.Vasco Brattka & Guido Gherardi - 2011 - Journal of Symbolic Logic 76 (1):143 - 176.
    In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  5.  14
    How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
    We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between WKL0 and the class (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  6.  4
    Weihrauch Goes Brouwerian.Vasco Brattka & Guido Gherardi - 2020 - Journal of Symbolic Logic 85 (4):1614-1653.
    We prove that the Weihrauch lattice can be transformed into a Brouwer algebra by the consecutive application of two closure operators in the appropriate order: first completion and then parallelization. The closure operator of completion is a new closure operator that we introduce. It transforms any problem into a total problem on the completion of the respective types, where we allow any value outside of the original domain of the problem. This closure operator is of interest by itself, as it (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  47
    Alan Turing and the Foundations of Computable Analysis.Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (3):394-430.
    We investigate Turing's contributions to computability theory for real numbers and real functions presented in [22, 24, 26]. In particular, it is shown how two fundamental approaches to computable analysis, the so-called ‘Type-2 Theory of Effectivity' (TTE) and the ‘realRAM machine' model, have their foundations in Turing's work, in spite of the two incompatible notions of computability they involve. It is also shown, by contrast, how the modern conceptual tools provided by these two paradigms allow a systematic interpretation of Turing's (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  8.  14
    Super-Strict Implications.Guido Gherardi & Eugenio Orlandelli - 2021 - Bulletin of the Section of Logic 50 (1):1-34.
    This paper introduces the logics of super-strict implications, where a super-strict implication is a strengthening of C.I. Lewis' strict implication that avoids not only the paradoxes of material implication but also those of strict implication. The semantics of super-strict implications is obtained by strengthening the relational semantics for strict implication. We consider all logics of super-strict implications that are based on relational frames for modal logics in the modal cube. it is shown that all logics of super-strict implications are connexive (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  15
    Interpolation in Extensions of First-Order Logic.Guido Gherardi, Paolo Maffezioli & Eugenio Orlandelli - 2020 - Studia Logica 108 (3):619-648.
    We prove a generalization of Maehara’s lemma to show that the extensions of classical and intuitionistic first-order logic with a special type of geometric axioms, called singular geometric axioms, have Craig’s interpolation property. As a corollary, we obtain a direct proof of interpolation for first-order logic with identity, as well as interpolation for several mathematical theories, including the theory of equivalence relations, partial and linear orders, and various intuitionistic order theories such as apartness and positive partial and linear orders.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  13
    Addendum To: “The Bolzano–Weierstrass Theorem is the Jump of Weak Kőnig's Lemma” [Ann. Pure Appl. Logic 163 623–655]. [REVIEW]Vasco Brattka, Andrea Cettolo, Guido Gherardi, Alberto Marcone & Matthias Schröder - 2017 - Annals of Pure and Applied Logic 168 (8):1605-1608.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  11.  15
    Effective Borel Degrees of Some Topological Functions.Guido Gherardi - 2006 - Mathematical Logic Quarterly 52 (6):625-642.
    The focus of this paper is the incomputability of some topological functions using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ℝn, like closure, border, intersection, and derivative, and we prove for such functions results of Σ02-completeness and Σ03-completeness in the effective Borel hierarchy. Then, following [13], we re-consider two well-known topological results: the lemmas of Urysohn and Urysohn-Tietze for generic metric spaces (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation