Switch to: Citations

Add references

You must login to add references.
  1. Introduction to Metamathematics.Ann Singleterry Ferebee - 1968 - Journal of Symbolic Logic 33 (2):290-291.
    Direct download  
     
    Export citation  
     
    Bookmark   170 citations  
  • Embeddings Into the Medvedev and Muchnik Lattices of Π0 1 Classes.Stephen Binns & Stephen G. Simpson - 2004 - Archive for Mathematical Logic 43 (3):399-414.
    Let w and M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π1 0 subsets of 2ω, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of w . We show that many countable distributive lattices are lattice-embeddable below any non-zero element of M.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  • Vitali's Theorem and WWKL.Douglas K. Brown, Mariagnese Giusto & Stephen G. Simpson - 2002 - Archive for Mathematical Logic 41 (2):191-206.
  • Mass Problems and Intuitionism.Stephen G. Simpson - 2008 - Notre Dame Journal of Formal Logic 49 (2):127-136.
    Let $\mathcal{P}_w$ be the lattice of Muchnik degrees of nonempty $\Pi^0_1$ subsets of $2^\omega$. The lattice $\mathcal{P}$ has been studied extensively in previous publications. In this note we prove that the lattice $\mathcal{P}$ is not Brouwerian.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
  • Mass Problems and Almost Everywhere Domination.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):483-492.
    We examine the concept of almost everywhere domination from the viewpoint of mass problems. Let AED and MLR be the sets of reals which are almost everywhere dominating and Martin-Löf random, respectively. Let b1, b2, and b3 be the degrees of unsolvability of the mass problems associated with AED, MLR × AED, and MLR ∩ AED, respectively. Let [MATHEMATICAL SCRIPT CAPITAL P]w be the lattice of degrees of unsolvability of mass problems associated with nonempty Π01 subsets of 2ω. Let 1 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • Mass Problems and Randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
    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 every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   27 citations  
  • Mathematical Logic.Donald Monk - 1975 - Journal of Symbolic Logic 40 (2):234-236.
    Direct download  
     
    Export citation  
     
    Bookmark   97 citations  
  • Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
  • Computable Structures and the Hyperarithmetical Hierarchy.Valentina Harizanov - 2001 - Bulletin of Symbolic Logic 7 (3):383-385.
    Direct download  
     
    Export citation  
     
    Bookmark   39 citations  
  • 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   15 citations  
  • Almost Everywhere Domination and Superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
    Let ω be the set of natural numbers. For functions f, g: ω → ω, we say f is dominated by g if f < g for all but finitely many n ∈ ω. We consider the standard “fair coin” probability measure on the space 2ω of in-finite sequences of 0's and 1's. A Turing oracle B is said to be almost everywhere dominating if, for measure 1 many X ∈ 2ω, each function which is Turing computable from X is (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   23 citations  
  • Uniform Almost Everywhere Domination.Peter Cholak, Noam Greenberg & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (3):1057 - 1072.
    We explore the interaction between Lebesgue measure and dominating functions. We show, via both a priority construction and a forcing construction, that there is a function of incomplete degree that dominates almost all degrees. This answers a question of Dobrinen and Simpson, who showed that such functions are related to the proof-theoretic strength of the regularity of Lebesgue measure for Gδ sets. Our constructions essentially settle the reverse mathematical classification of this principle.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Almost Everywhere Domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
    A Turing degree a is said to be almost everywhere dominating if, for almost all $X \in 2^{\omega}$ with respect to the "fair coin" probability measure on $2^{\omega}$ , and for all g: $\omega \rightarrow \omega$ Turing reducible to X, there exists f: $\omega \rightarrow \omega$ of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this problem to some questions in (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • A Splitting Theorem for the Medvedev and Muchnik Lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
    This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  • On a Conjecture of Dobrinen and Simpson Concerning Almost Everywhere Domination.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman & Reed Solomon - 2006 - Journal of Symbolic Logic 71 (1):119 - 136.
  • A Study of Singular Points and Supports of Measures in Reverse Mathematics.Xiaokang Yu - 1996 - Annals of Pure and Applied Logic 79 (2):211-219.
    Arithmetical comprehension is proved to be equivalent to the enumerability of singular points of any measure on the Cantor space. It is provable in ACA0 that any perfect closed subset of [0, 1] is the support of some continuous positive linear functional on C[0, 1].
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Riesz Representation Theorem, Borel Measures and Subsystems of Second-Order Arithmetic.Xiaokang Yu - 1993 - Annals of Pure and Applied Logic 59 (1):65-78.
    Yu, X., Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Annals of Pure and Applied Logic 59 65-78. Formalized concept of finite Borel measures is developed in the language of second-order arithmetic. Formalization of the Riesz representation theorem is proved to be equivalent to arithmetical comprehension. Codes of Borel sets of complete separable metric spaces are defined and proved to be meaningful in the subsystem ATR0. Arithmetical transfinite recursion is enough to prove the measurability of Borel sets for (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • Lebesgue Convergence Theorems and Reverse Mathematics.Xiaokang Yu - 1994 - Mathematical Logic Quarterly 40 (1):1-13.
    Concepts of L1 space, integrable functions and integrals are formalized in weak subsystems of second order arithmetic. They are discussed especially in relation with the combinatorial principle WWKL (weak-weak König's lemma and arithmetical comprehension. Lebesgue dominated convergence theorem is proved to be equivalent to arithmetical comprehension. A weak version of Lebesgue monotone convergence theorem is proved to be equivalent to weak-weak König's lemma.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  • Measure Theory and Weak König's Lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.
    We develop measure theory in the context of subsystems of second order arithmetic with restricted induction. We introduce a combinatorial principleWWKL (weak-weak König's lemma) and prove that it is strictly weaker thanWKL (weak König's lemma). We show thatWWKL is equivalent to a formal version of the statement that Lebesgue measure is countably additive on open sets. We also show thatWWKL is equivalent to a formal version of the statement that any Borel measure on a compact metric space is countably additive (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   31 citations  
  • Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
    Direct download  
     
    Export citation  
     
    Bookmark   529 citations  
  • Kurt Gödel. Essays for His Centennial.Solomon Feferman, Charles Parsons & Stephen G. Simpson - 2011 - Bulletin of Symbolic Logic 17 (1):125-126.
     
    Export citation  
     
    Bookmark   3 citations