9 found
Order:
  1.  21
    Natural Factors of the Medvedev Lattice Capturing IPC.Rutger Kuyper - 2014 - Archive for Mathematical Logic 53 (7-8):865-879.
    Skvortsova showed that there is a factor of the Medvedev lattice which captures intuitionistic propositional logic. However, her factor is unnatural in the sense that it is constructed in an ad hoc manner. We present a more natural example of such a factor. We also show that the theory of every non-trivial factor of the Medvedev lattice is contained in Jankov’s logic, the deductive closure of IPC plus the weak law of the excluded middle ¬p∨¬¬p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2.  7
    Coarse Reducibility and Algorithmic Randomness.Denis R. Hirschfeldt, Carl G. Jockusch, Rutger Kuyper & Paul E. Schupp - 2016 - Journal of Symbolic Logic 81 (3):1028-1046.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  39
    Natural Factors of the Muchnik Lattice Capturing IPC.Rutger Kuyper - 2013 - Annals of Pure and Applied Logic 164 (10):1025-1036.
    We give natural examples of factors of the Muchnik lattice which capture intuitionistic propositional logic , arising from the concepts of lowness, 1-genericity, hyperimmune-freeness and computable traceability. This provides a purely computational semantics for IPC.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  27
    On Weihrauch Reducibility and Intuitionistic Reverse Mathematics.Rutger Kuyper - 2017 - Journal of Symbolic Logic 82 (4):1438-1458.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  27
    Model Theory of Measure Spaces and Probability Logic.Rutger Kuyper & Sebastiaan A. Terwijn - 2013 - Review of Symbolic Logic 6 (3):367-393.
    We study the model-theoretic aspects of a probability logic suited for talking about measure spaces. This nonclassical logic has a model theory rather different from that of classical predicate logic. In general, not every satisfiable set of sentences has a countable model, but we show that one can always build a model on the unit interval. Also, the probability logic under consideration is not compact. However, using ultraproducts we can prove a compactness theorem for a certain class of weak models.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  11
    Computational Aspects of Satisfiability in Probability Logic.Rutger Kuyper - 2014 - Mathematical Logic Quarterly 60 (6):444-470.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  26
    First-Order Logic in the Medvedev Lattice.Rutger Kuyper - 2015 - Studia Logica 103 (6):1185-1224.
    Kolmogorov introduced an informal calculus of problems in an attempt to provide a classical semantics for intuitionistic logic. This was later formalised by Medvedev and Muchnik as what has come to be called the Medvedev and Muchnik lattices. However, they only formalised this for propositional logic, while Kolmogorov also discussed the universal quantifier. We extend the work of Medvedev to first-order logic, using the notion of a first-order hyperdoctrine from categorical logic, to a structure which we will call the hyperdoctrine (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  8.  7
    Levels of Uniformity.Rutger Kuyper - 2019 - Notre Dame Journal of Formal Logic 60 (1):119-138.
    We introduce a hierarchy of degree structures between the Medvedev and Muchnik lattices which allow varying amounts of nonuniformity. We use these structures to introduce the notion of the uniformity of a Muchnik reduction, which expresses how uniform a reduction is. We study this notion for several well-known reductions from algorithmic randomness. Furthermore, since our new structures are Brouwer algebras, we study their propositional theories. Finally, we study if our new structures are elementarily equivalent to each other.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  9.  12
    Nullifying Randomness and Genericity Using Symmetric Difference.Rutger Kuyper & Joseph S. Miller - 2017 - Annals of Pure and Applied Logic 168 (9):1692-1699.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark