4 found
  1.  35
    A Functional Interpretation for Nonstandard Arithmetic.Benno van den Berg, Eyvind Briseid & Pavol Safarik - 2012 - Annals of Pure and Applied Logic 163 (12):1962-1994.
    We introduce constructive and classical systems for nonstandard arithmetic and show how variants of the functional interpretations due to Gödel and Shoenfield can be used to rewrite proofs performed in these systems into standard ones. These functional interpretations show in particular that our nonstandard systems are conservative extensions of E-HAω and E-PAω, strengthening earlier results by Moerdijk and Palmgren, and Avigad and Helzner. We will also indicate how our rewriting algorithm can be used for term extraction purposes. To conclude the (...)
    Direct download (6 more)  
    Export citation  
    Bookmark   19 citations  
  2.  14
    On the Computational Content of the Bolzano-Weierstraß Principle.Pavol Safarik & Ulrich Kohlenbach - 2010 - Mathematical Logic Quarterly 56 (5):508-532.
    We will apply the methods developed in the field of ‘proof mining’ to the Bolzano-Weierstraß theorem BW and calibrate the computational contribution of using this theorem in proofs of combinatorial statements. We provide an explicit solution of the Gödel functional interpretation as well as the monotone functional interpretation of BW for the product space Πi ∈ℕ[–ki, ki] . This results in optimal program and bound extraction theorems for proofs based on fixed instances of BW, i.e. for BW applied to fixed (...)
    Direct download (4 more)  
    Export citation  
    Bookmark   6 citations  
  3.  20
    Fluctuations, Effective Learnability and Metastability in Analysis.Ulrich Kohlenbach & Pavol Safarik - 2014 - Annals of Pure and Applied Logic 165 (1):266-304.
    This paper discusses what kind of quantitative information one can extract under which circumstances from proofs of convergence statements in analysis. We show that from proofs using only a limited amount of the law-of-excluded-middle, one can extract functionals , where L is a learning procedure for a rate of convergence which succeeds after at most B-many mind changes. This -learnability provides quantitative information strictly in between a full rate of convergence and a rate of metastability in the sense of Tao (...)
    Direct download (5 more)  
    Export citation  
  4.  19
    The Strength of Countable Saturation.Benno van den Berg, Eyvind Briseid & Pavol Safarik - 2017 - Archive for Mathematical Logic 56 (5-6):699-711.
    In earlier work we introduced two systems for nonstandard analysis, one based on classical and one based on intuitionistic logic; these systems were conservative extensions of first-order Peano and Heyting arithmetic, respectively. In this paper we study how adding the principle of countable saturation to these systems affects their proof-theoretic strength. We will show that adding countable saturation to our intuitionistic system does not increase its proof-theoretic strength, while adding it to the classical system increases the strength from first- to (...)
    Direct download (7 more)  
    Export citation