12 found
Order:
  1.  12
    Coding True Arithmetic in the Medvedev and Muchnik Degrees.Paul Shafer - 2011 - Journal of Symbolic Logic 76 (1):267 - 288.
    We prove that the first-order theory of the Medvedev degrees, the first-order theory of the Muchnik degrees, and the third-order theory of true arithmetic are pairwise recursively isomorphic (obtained independently by Lewis, Nies, and Sorbi [7]). We then restrict our attention to the degrees of closed sets and prove that the following theories are pairwise recursively isomorphic: the first-order theory of the closed Medvedev degrees, the first-order theory of the compact Medvedev degrees, the first-order theory of the closed Muchnik degrees, (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  2.  16
    Comparing the Strength of Diagonally Nonrecursive Functions in the Absence of Induction.François G. Dorais, Jeffry L. Hirst & Paul Shafer - 2015 - Journal of Symbolic Logic 80 (4):1211-1235.
    We prove that the statement “there is aksuch that for everyfthere is ak-bounded diagonally nonrecursive function relative tof” does not imply weak König’s lemma over${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that everyk-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of${\rm{I\Sigma }}_2^0$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  17
    Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2011 - Notre Dame Journal of Formal Logic 52 (1):21-38.
    We characterize the join-irreducible Medvedev degrees as the degrees of complements of Turing ideals, thereby solving a problem posed by Sorbi. We use this characterization to prove that there are Medvedev degrees above the second-least degree that do not bound any join-irreducible degrees above this second-least degree. This solves a problem posed by Sorbi and Terwijn. Finally, we prove that the filter generated by the degrees of closed sets is not prime. This solves a problem posed by Bianchini and Sorbi.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  38
    Menger’s Theorem in $${{\Pi^11\Tt{-CA}0}}$$.Paul Shafer - 2012 - Archive for Mathematical Logic 51 (3-4):407-423.
    We prove Menger’s theorem for countable graphs in ${{\Pi^1_1\tt{-CA}_0}}$ . Our proof in fact proves a stronger statement, which we call extended Menger’s theorem, that is equivalent to ${{\Pi^1_1\tt{-CA}_0}}$ over ${{\tt{RCA}_0}}$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  3
    Coding True Arithmetic in the Medvedev Degrees of Classes.Paul Shafer - 2012 - Annals of Pure and Applied Logic 163 (3):321-337.
  6.  6
    Randomness Notions and Reverse Mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.
    We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$-random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C-incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  10
    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  
  8.  18
    Randomness and Semimeasures.Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter & Paul Shafer - 2017 - Notre Dame Journal of Formal Logic 58 (3):301-328.
    A semimeasure is a generalization of a probability measure obtained by relaxing the additivity requirement to superadditivity. We introduce and study several randomness notions for left-c.e. semimeasures, a natural class of effectively approximable semimeasures induced by Turing functionals. Among the randomness notions we consider, the generalization of weak 2-randomness to left-c.e. semimeasures is the most compelling, as it best reflects Martin-Löf randomness with respect to a computable measure. Additionally, we analyze a question of Shen, a positive answer to which would (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  9.  25
    Universality, Optimality, and Randomness Deficiency.Rupert Hölzl & Paul Shafer - 2015 - Annals of Pure and Applied Logic 166 (10):1049-1069.
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark  
  10.  14
    Reverse Mathematics, Well-Quasi-Orders, and Noetherian Spaces.Emanuele Frittaion, Matthew Hendtlass, Alberto Marcone, Paul Shafer & Jeroen Van der Meeren - 2016 - Archive for Mathematical Logic 55 (3-4):431-459.
    A quasi-order Q induces two natural quasi-orders on P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}}$$\end{document}, but if Q is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq, pp. 453–462, 2007) showed that moving from a well-quasi-order Q to the quasi-orders on P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}}$$\end{document} preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  11.  5
    Honest Elementary Degrees and Degrees of Relative Provability Without the Cupping Property.Paul Shafer - 2017 - Annals of Pure and Applied Logic 168 (5):1017-1031.
  12. Menger’s Theorem in \Documentclass[12pt]{Minimal} \Usepackage{Amsmath} \Usepackage{Wasysym} \Usepackage{Amsfonts} \Usepackage{Amssymb} \Usepackage{Amsbsy} \Usepackage{Mathrsfs} \Usepackage{Upgreek} \Setlength{\Oddsidemargin}{-69pt} \Begin{Document}$${{\Pi^11\Tt{-CA}0}}$$\End{Document}.Paul Shafer - 2012 - Archive for Mathematical Logic 51 (3-4):407-423.
    We prove Menger’s theorem for countable graphs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\Pi^1_1\tt{-CA}_0}}$$\end{document}. Our proof in fact proves a stronger statement, which we call extended Menger’s theorem, that is equivalent to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\Pi^1_1\tt{-CA}_0}}$$\end{document} over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\tt{RCA}_0}}$$\end{document}.
    Direct download  
     
    Export citation  
     
    Bookmark