44 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.
    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.
    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.
    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.
    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 (2 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.
    Continuing the investigations of X. Yu and others, we study the role of set existence axioms in classical Lebesgue measure theory. We show that pairwise disjoint countable additivity for open sets of reals is provable in RCA0. We show that several well-known measure-theoretic propositions including the Vitali Covering Theorem are equivalent to WWKL over RCA0.
    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.
    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
    Translate to English
    | 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.
    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 (3 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. 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:123-144.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  34. Stephen G. Simpson & Rick L. Smith (1986). Factorization of Polynomials and Σ10 Induction. Annals of Pure and Applied Logic 31:289-306.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  35. 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  
  36. 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  
  37. 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  
  38. 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  
  39. 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  
  40. 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  
  41. 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  
  42. 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.
  43. 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  
  44. 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