4 found
Order:
  1.  36
    Mass Problems and Hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
    A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if for all Y ∈ Q there exists X ∈ P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. Let [Formula: see text] be the lattice of weak degrees of mass problems associated with nonempty [Formula: see text] subsets of the Cantor (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  2.  10
    The ∀∃-Theory of the Effectively Closed Medvedev Degrees is Decidable.Joshua A. Cole & Takayuki Kihara - 2010 - Archive for Mathematical Logic 49 (1):1-16.
    We show that there is a computable procedure which, given an ∀∃-sentence ${\varphi}$ in the language of the partially ordered sets with a top element 1 and a bottom element 0, computes whether ${\varphi}$ is true in the Medvedev degrees of ${\Pi^0_1}$ classes in Cantor space, sometimes denoted by ${\mathcal{P}_s}$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  30
    Embedding FD(Ω) Into {Mathcal{P}_s} Densely.Joshua A. Cole - 2008 - Archive for Mathematical Logic 46 (7-8):649-664.
    Let ${\mathcal{P}_s}$ be the lattice of degrees of non-empty ${\Pi_1^0}$ subsets of 2 ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in ${\mathcal{P}_s}$ . Cenzer and Hinman proved that ${\mathcal{P}_s}$ is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by Cenzer (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4. Embedding FD) Into InlineEquation ID=" IEq1"> ImageObject FileRef=" 153200762ArticleIEq1. Gif" Format=" GIF" Color=" BlackWhite" Type=" Linedraw" Rendition=" HTML"/> EquationSource Format=" TEX"> Densely. [REVIEW]Joshua A. Cole - 2007 - Archive for Mathematical Logic 46 (7):649-664.
    Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}_s}$$\end{document} be the lattice of degrees of non-empty \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi_1^0}$$\end{document} subsets of 2ω under Medvedev reducibility. Binns and Simpson proved that FD, the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}_s}$$\end{document}. Cenzer and Hinman proved that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{P}_s}$$\end{document} is (...)
    Direct download  
     
    Export citation  
     
    Bookmark