45 found
Sort by:
  1. Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson & Keita Yokoyama (2014). Propagation of Partial Randomness. Annals of Pure and Applied Logic 165 (2):742-758.
    Let f be a computable function from finite sequences of 0ʼs and 1ʼs to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a (...)
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. Stephen G. Simpson (2014). Baire Categoricity and $\Sigma^{0}_{1}$ -Induction. Notre Dame Journal of Formal Logic 55 (1):75-78.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  3. Stephen G. Simpson & Keita Yokoyama (2013). Reverse Mathematics and Peano Categoricity. Annals of Pure and Applied Logic 164 (3):284-293.
    We investigate the reverse-mathematical status of several theorems to the effect that the natural number system is second-order categorical. One of our results is as follows. Define a system to be a triple A,i,f such that A is a set and i∈A and f:A→A. A subset X⊆A is said to be inductive if i∈X and ∀a ∈X). The system A,i,f is said to be inductive if the only inductive subset of A is A itself. Define a Peano system to be (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Kurt Gödel, Solomon Feferman, Charles Parsons & Stephen G. Simpson (eds.) (2010). Kurt Gödel: Essays for His Centennial. Association for Symbolic Logic.
    Machine generated contents note: Part I. General: 1. The Gödel editorial project: a synopsis Solomon Feferman; 2. Future tasks for Gödel scholars John W. Dawson, Jr., and Cheryl A. Dawson; Part II. Proof Theory: 3. Kurt Gödel and the metamathematical tradition Jeremy Avigad; 4. Only two letters: the correspondence between Herbrand and Gödel Wilfried Sieg; 5. Gödel's reformulation of Gentzen's first consistency proof for arithmetic: the no-counter-example interpretation W. W. Tait; 6. Gödel on intuition and on Hilbert's finitism W. W. (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  5. Stephen G. Simpson (2010). The Gödel Hierarchy and Reverse Mathematics. In Kurt Gödel, Solomon Feferman, Charles Parsons & Stephen G. Simpson (eds.), Kurt Gödel: Essays for His Centennial. Association for Symbolic Logic.
     
    My bibliography  
     
    Export citation  
  6. Stephen G. Simpson & Keita Yokoyama (2010). A Nonstandard Counterpart of WWKL. Notre Dame Journal of Formal Logic 52 (3):229-243.
    In this paper, we introduce a system of nonstandard second-order arithmetic $\mathsf{ns}$-$\mathsf{WWKL_0}$ which consists of $\mathsf{ns}$-$\mathsf{BASIC}$ plus Loeb measure property. Then we show that $\mathsf{ns}$-$\mathsf{WWKL_0}$ is a conservative extension of $\mathsf{WWKL_0}$ and we do Reverse Mathematics for this system.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  7. Stephen G. Simpson (2009). Mass Problems and Measure-Theoretic Regularity. Bulletin of Symbolic Logic 15 (4):385-409.
    A well known fact is that every Lebesgue measurable set is regular, i.e., it includes an F$_{\sigma}$ set of the same measure. We analyze this fact from a metamathematical or foundational standpoint. We study a family of Muchnik degrees corresponding to measure-theoretic regularity at all levels of the effective Borel hierarchy. We prove some new results concerning Nies's notion of LR-reducibility. We build some $\omega$-models of RCA$_0$which are relevant for the reverse mathematics of measure-theoretic regularity.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  8. Stephen G. Simpson (2008). Mass Problems and Intuitionism. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  9. Joshua A. Cole & Stephen G. Simpson (2007). Mass Problems and Hyperarithmeticity. Journal of Mathematical Logic 7 (02):125-143.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  10. Stephen G. Simpson (2007). Almost Everywhere Domination and Superhighness. 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 (...)
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  11. Stephen G. Simpson (2007). Mass Problems and Almost Everywhere Domination. 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 (...)
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  12. Carl Mummert & Stephen G. Simpson (2005). Reverse Mathematics and Π21 Comprehension. Bulletin of Symbolic Logic 11 (4):526-533.
    We initiate the reverse mathematics of general topology. We show that a certain metrization theorem is equivalent to Π2 1 comprehension. An MF space is defined to be a topological space of the form MF(P) with the topology generated by $\lbrace N_p \mid p \in P \rbrace$ . Here P is a poset, MF(P) is the set of maximal filters on P, and $N_p = \lbrace F \in MF(P) \mid p \in F \rbrace$ . If the poset P is countable, (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  13. Stephen G. Simpson (2005). Mass Problems and Randomness. 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 (9 more)  
     
    My bibliography  
     
    Export citation  
  14. Stephen G. Simpson (2005). N? Sets and Models of Wkl0. In Stephen Simpson (ed.), Reverse Mathematics 2001. 21--352.
    No categories
     
    My bibliography  
     
    Export citation  
  15. Stephen Binns & Stephen G. Simpson (2004). Embeddings Into the Medvedev and Muchnik Lattices of Π0 1 Classes. 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.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  16. Natasha L. Dobrinen & Stephen G. Simpson (2004). Almost Everywhere Domination. 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 (7 more)  
     
    My bibliography  
     
    Export citation  
  17. Carl Mummert & Stephen G. Simpson (2004). An Incompleteness Theorem for [Image]. Journal of Symbolic Logic 69 (2):612 - 616.
    Let n be a positive integer. By a $\beta_{n}-model$ we mean an $\omega-model$ which is elementary with respect to $\sigma_{n}^{1}$ formulas. We prove the following $\beta_{n}-model$ version of $G\ddot{o}del's$ Second Incompleteness Theorem. For any recursively axiomatized theory S in the language of second order arithmetic, if there exists a $\beta_{n}-model$ of S, then there exists a $\beta_{n}-model$ of S + "there is no countable $\beta_{n}-model$ of S". We also prove a $\beta_{n}-model$ version of $L\ddot{o}b's$ Theorem. As a corollary, we obtain (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  18. Carl Mummert & Stephen G. Simpson (2004). An Incompleteness Theorem for Βn-Models. Journal of Symbolic Logic 69 (2):612-616.
    Let n be a positive integer. By a βn-model we mean an ω-model which is elementary with respect to Σ1n formulas. We prove the following βn-model version of Gödel’s Second Incompleteness Theorem. For any recursively axiomatized theory S in the language of second order arithmetic, if there exists a βn-model of S, then there exists a βn-model of S + “there is no countable βn-model of S”. We also prove a βn-model version of Löb’s Theorem. As a corollary, we obtain (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  19. Douglas K. Brown, Mariagnese Giusto & Stephen G. Simpson (2002). Vitali's Theorem and WWKL. Archive for Mathematical Logic 41 (2):191-206.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  20. Stephen G. Simpson, Kazuyuki Tanaka & Takeshi Yamazaki (2002). Some Conservation Results on Weak König's Lemma. Annals of Pure and Applied Logic 118 (1-2):87-114.
    By , we denote the system of second-order arithmetic based on recursive comprehension axioms and Σ10 induction. is defined to be plus weak König's lemma: every infinite tree of sequences of 0's and 1's has an infinite path. In this paper, we first show that for any countable model M of , there exists a countable model M′ of whose first-order part is the same as that of M, and whose second-order part consists of the M-recursive sets and sets not (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  21. Stephen G. Simpson & Jeffrey Ketland (2001). Reviews-Subsystems of Second-Order Arithmetic. British Journal for the Philosophy of Science 52 (1):191-196.
    No categories
     
    My bibliography  
     
    Export citation  
  22. Mariagnese Giusto & Stephen G. Simpson (2000). Located Sets and Reverse Mathematics. Journal of Symbolic Logic 65 (3):1451-1480.
    Let X be a compact metric space. A closed set K $\subseteq$ X is located if the distance function d(x, K) exists as a continuous real-valued function on X; weakly located if the predicate d(x, K) $>$ r is Σ 0 1 allowing parameters. The purpose of this paper is to explore the concepts of located and weakly located subsets of a compact separable metric space in the context of subsystems of second order arithmetic such as RCA 0 , WKL (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  23. A. James Humphreys & Stephen G. Simpson (1999). Separation and Weak König's Lemma. Journal of Symbolic Logic 64 (1):268-278.
    We continue the work of [14, 3, 1, 19, 16, 4, 12, 11, 20] investigating the strength of set existence axioms needed for separable Banach space theory. We show that the separation theorem for open convex sets is equivalent to WKL 0 over RCA 0 . We show that the separation theorem for separably closed convex sets is equivalent to ACA 0 over RCA 0 . Our strategy for proving these geometrical Hahn-Banach theorems is to reduce to the finite-dimensional case (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  24. Stephen G. Simpson (1999). Subsystems of Second-Order Arithmetic. Springer-Verlag.
    Stephen George Simpson. with definition 1.2.3 and the discussion following it. For example, taking 90(n) to be the formula n §E Y, we have an instance of comprehension, VYEIXVn(n€X<—>n¢Y), asserting that for any given set Y there exists a ...
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  25. Stephen G. Simpson (1994). On the Strength of König's Duality Theorem for Countable Bipartite Graphs. Journal of Symbolic Logic 59 (1):113-123.
    Let CKDT be the assertion that for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M. (This is a theorem of Podewski and Steffens [12].) Let ATR0 be the subsystem of second-order arithmetic with arithmetical transfinite recursion and restricted induction. Let RCA0 be the subsystem of second-order arithmetic with recursive comprehension and restricted induction. We show that (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  26. Douglas K. Brown & Stephen G. Simpson (1993). The Baire Category Theorem in Weak Subsystems of Second-Order Arithmetic. Journal of Symbolic Logic 58 (2):557-578.
    Working within weak subsystems of second-order arithmetic Z2 we consider two versions of the Baire Category theorem which are not equivalent over the base system RCA0. We show that one version (B.C.T.I) is provable in RCA0 while the second version (B.C.T.II) requires a stronger system. We introduce two new subsystems of Z2, which we call RCA+ 0 and WKL+ 0, and show that RCA+ 0 suffices to prove B.C.T.II. Some model theory of WKL+ 0 and its importance in view of (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  27. Harvey Friedman, Stephen G. Simpson & Xiaokang Yu (1993). Periodic Points and Subsystems of Second-Order Arithmetic. Annals of Pure and Applied Logic 62 (1):51-64.
    We study the formalization within sybsystems of second-order arithmetic of theorems concerning periodic points in dynamical systems on the real line. We show that Sharkovsky's theorem is provable in WKL0. We show that, with an additional assumption, Sharkovsky's theorem is provable in RCA0. We show that the existence for all n of n-fold iterates of continuous mappings of the closed unit interval into itself is equivalent to the disjunction of Σ02 induction and weak König's lemma.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  28. Stephen G. Simpson (1993). Spring Meeting of the Association for Symbolic Logic. Journal of Symbolic Logic 58 (3):1093-1095.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  29. Xiaokang Yu & Stephen G. Simpson (1990). Measure Theory and Weak König's Lemma. 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 (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  30. Kostas Hatzikiriakou & Stephen G. Simpson (1989). Countable Valued Fields in Weak Subsystems of Second-Order Arithmetic. Annals of Pure and Applied Logic 41 (1):27-32.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  31. Stephen G. Simpson (1988). Ordinal Numbers and the Hilbert Basis Theorem. Journal of Symbolic Logic 53 (3):961-974.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  32. Stephen G. Simpson (1988). Partial Realizations of Hilbert's Program. Journal of Symbolic Logic 53 (2):349-363.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  33. Stephen G. Simpson, American Mathematical Society, Institute of Mathematical Statistics & Society for Industrial and Applied Mathematics (1987). Logic and Combinatorics Proceedings of the Ams-Ims-Siam Joint Summer Research Conference Held August 4-10, 1985. Monograph Collection (Matt - Pseudo).
    No categories
     
    My bibliography  
     
    Export citation  
  34. Douglas K. Brown & Stephen G. Simpson (1986). Which Set Existence Axioms Are Needed to Prove the Separable Hahn-Banach Theorem? Annals of Pure and Applied Logic 31 (2):123-144.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  35. Stephen G. Simpson & Rick L. Smith (1986). Factorization of Polynomials and Σ10 Induction. Annals of Pure and Applied Logic 31 (2):289-306.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  36. Stephen G. Simpson & Rick L. Smith (1986). Factorization of Polynomials and< I> Σ_< Sub> 1< Sup> 0 Induction. Annals of Pure and Applied Logic 31:289-306.
    Direct download  
     
    My bibliography  
     
    Export citation  
  37. Harvey M. Friedman, Stephen G. Simpson & Rick L. Smith (1985). Addendum to “Countable Algebra and Set Existence Axioms”. Annals of Pure and Applied Logic 28 (3):319-320.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  38. Kurt Schütte & Stephen G. Simpson (1985). Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen. Archive for Mathematical Logic 25 (1):75-89.
    No categories
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  39. Stephen G. Simpson (1984). Which Set Existence Axioms Are Needed to Prove the Cauchy/Peano Theorem for Ordinary Differential Equations? Journal of Symbolic Logic 49 (3):783-802.
    We investigate the provability or nonprovability of certain ordinary mathematical theorems within certain weak subsystems of second order arithmetic. Specifically, we consider the Cauchy/Peano existence theorem for solutions of ordinary differential equations, in the context of the formal system RCA 0 whose principal axioms are ▵ 0 1 comprehension and Σ 0 1 induction. Our main result is that, over RCA 0 , the Cauchy/Peano Theorem is provably equivalent to weak Konig's lemma, i.e. the statement that every infinite {0, 1}-tree (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  40. Harvey M. Friedman, Stephen G. Simpson & Rick L. Smith (1983). Countable Algebra and Set Existence Axioms. Annals of Pure and Applied Logic 25 (2):141-181.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  41. Stephen G. Simpson (1983). Review: L. A. S. Kirby, J. B. Paris, A. Lachlan, M. Srebrny, A. Zarach, Initial Segments of Models of Peano's Axioms; J. B. Paris, Some Independence Results for Peano Arithmetic. [REVIEW] Journal of Symbolic Logic 48 (2):482-483.
    Direct download  
     
    My bibliography  
     
    Export citation  
  42. Stephen G. Simpson & Galen Weitkamp (1983). High and Low Kleene Degrees of Coanalytic Sets. Journal of Symbolic Logic 48 (2):356-368.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  43. James H. Schmerl & Stephen G. Simpson (1982). On the Role of Ramsey Quantifiers in First Order Arithmetic. Journal of Symbolic Logic 47 (2):423-435.
  44. Stephen G. Simpson (1978). Sets Which Do Not Have Subsets of Every Higher Degree. Journal of Symbolic Logic 43 (1):135-138.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  45. Carl G. Jockusch & Stephen G. Simpson (1976). A Degree-Theoretic Definition of the Ramified Analytical Hierarchy. Annals of Mathematical Logic 10 (1):1-32.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation