61 found
Order:
  1.  15
    Subsystems of Second-Order Arithmetic.Stephen G. Simpson - 1999 - 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 ...
    Direct download  
     
    Export citation  
     
    Bookmark   60 citations  
  2. Subsystems of Second-Order Arithmetic.Stephen G. Simpson - 2004 - Studia Logica 77 (1):129-129.
     
    Export citation  
     
    Bookmark   52 citations  
  3. 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 (11 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  4.  20
    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   16 citations  
  5.  21
    Countable Algebra and Set Existence axioms11Research Partially Supported by NSF Grants MCS-79-23743, MCS-78-02558, and MCS 8107867. Simpson's Research Was Also Supported by an Alfred P. Sloan Research Fellowship. [REVIEW]Harvey M. Friedman, Stephen G. Simpson & Rick L. Smith - 1983 - Annals of Pure and Applied Logic 25 (2):141-181.
  6. Partial Realizations of Hilbert's Program.Stephen G. Simpson - 1988 - Journal of Symbolic Logic 53 (2):349-363.
  7.  26
    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 (6 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  8.  12
    Propagation of Partial Randomness.Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson & Keita Yokoyama - 2014 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  9.  31
    Mass Problems and Hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  10.  18
    Which Set Existence Axioms Are Needed to Prove the Separable Hahn-Banach Theorem?Douglas K. Brown & Stephen G. Simpson - 1986 - Annals of Pure and Applied Logic 31 (2):123-144.
  11.  25
    Which Set Existence Axioms Are Needed to Prove the Cauchy/Peano Theorem for Ordinary Differential Equations?Stephen G. Simpson - 1984 - 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 (7 more)  
     
    Export citation  
     
    Bookmark   25 citations  
  12.  18
    Reverse Mathematics and Peano Categoricity.Stephen G. Simpson & Keita Yokoyama - 2013 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  13.  14
    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   19 citations  
  14.  9
    Factorization of Polynomials and Σ10 Induction.Stephen G. Simpson & Rick L. Smith - 1986 - Annals of Pure and Applied Logic 31 (2):289-306.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  15.  4
    Reverse Mathematics, Young Diagrams, and the Ascending Chain Condition.Kostas Hatzikiriakou & Stephen G. Simpson - 2017 - Journal of Symbolic Logic 82 (2):576-589.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  15
    Located Sets and Reverse Mathematics.Mariagnese Giusto & Stephen G. Simpson - 2000 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  17.  28
    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   4 citations  
  18.  15
    Vitali's Theorem and WWKL.Douglas K. Brown, Mariagnese Giusto & Stephen G. Simpson - 2002 - Archive for Mathematical Logic 41 (2):191-206.
  19.  6
    A Nonstandard Counterpart of WWKL.Stephen G. Simpson & Keita Yokoyama - 2011 - 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)  
     
    Export citation  
     
    Bookmark   3 citations  
  20.  20
    Ordinal Numbers and the Hilbert Basis Theorem.Stephen G. Simpson - 1988 - Journal of Symbolic Logic 53 (3):961-974.
  21. Reverse Mathematics and Π21 Comprehension.Carl Mummert & Stephen G. Simpson - 2005 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  22.  14
    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 (9 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  23.  19
    Some Conservation Results on Weak König's Lemma.Stephen G. Simpson, Kazuyuki Tanaka & Takeshi Yamazaki - 2002 - 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 (5 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  24.  6
    A Degree-Theoretic Definition of the Ramified Analytical Hierarchy.Carl G. Jockusch & Stephen G. Simpson - 1976 - Annals of Mathematical Logic 10 (1):1-32.
  25.  12
    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 (8 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  26.  5
    Nonprovability of Certain Combinatorial Properties of Finite Trees.Stephen G. Simpson - 1990 - Journal of Symbolic Logic 55 (2):868-869.
  27.  19
    Mass Problems and Measure-Theoretic Regularity.Stephen G. Simpson - 2009 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  28.  16
    On the Strength of König's Duality Theorem for Countable Bipartite Graphs.Stephen G. Simpson - 1994 - 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 (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  29.  30
    The Baire Category Theorem in Weak Subsystems of Second-Order Arithmetic.Douglas K. Brown & Stephen G. Simpson - 1993 - 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 (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  30.  8
    Baire Categoricity and $\Sigma^{0}_{1}$ -Induction.Stephen G. Simpson - 2014 - Notre Dame Journal of Formal Logic 55 (1):75-78.
  31.  14
    Friedman's Research on Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1990 - Journal of Symbolic Logic 55 (2):870-874.
    Direct download  
     
    Export citation  
     
    Bookmark   5 citations  
  32.  20
    Periodic Points and Subsystems of Second-Order Arithmetic.Harvey Friedman, Stephen G. Simpson & Xiaokang Yu - 1993 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  33.  24
    Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen.Kurt Schütte & Stephen G. Simpson - 1985 - Archive for Mathematical Logic 25 (1):75-89.
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   4 citations  
  34. N? Sets and Models of Wkl0.Stephen G. Simpson - 2005 - In Stephen Simpson (ed.), Reverse Mathematics 2001. pp. 21--352.
     
    Export citation  
     
    Bookmark   2 citations  
  35.  33
    Sets Which Do Not Have Subsets of Every Higher Degree.Stephen G. Simpson - 1978 - Journal of Symbolic Logic 43 (1):135-138.
  36. The Gödel Hierarchy and Reverse Mathematics.Stephen G. Simpson - 2010 - In Kurt Gödel, Solomon Feferman, Charles Parsons & Stephen G. Simpson (eds.), Kurt Gödel: Essays for His Centennial. Association for Symbolic Logic.
     
    Export citation  
     
    Bookmark   1 citation  
  37.  9
    Addendum to “Countable Algebra and Set Existence Axioms”.Harvey M. Friedman, Stephen G. Simpson & Rick L. Smith - 1984 - Annals of Pure and Applied Logic 28 (3):319-320.
  38.  15
    On the Role of Ramsey Quantifiers in First Order Arithmetic.James H. Schmerl & Stephen G. Simpson - 1982 - Journal of Symbolic Logic 47 (2):423-435.
  39.  31
    An Incompleteness Theorem for [Image].Carl Mummert & Stephen G. Simpson - 2004 - 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  40.  9
    Special Section: Computability Theory and the Foundation of Mathematics.Chi Tat Chong & Stephen G. Simpson - 2017 - Annals of the Japan Association for Philosophy of Science 25:23-24.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  41.  17
    Factorization of Polynomials and< I> Σ_< Sub> 1< Sup> 0 Induction.Stephen G. Simpson & Rick L. Smith - 1986 - Annals of Pure and Applied Logic 31:289-306.
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  42.  21
    Implicit Definability in Arithmetic.Stephen G. Simpson - 2016 - Notre Dame Journal of Formal Logic 57 (3):329-339.
    We consider implicit definability over the natural number system $\mathbb{N},+,\times,=$. We present a new proof of two theorems of Leo Harrington. The first theorem says that there exist implicitly definable subsets of $\mathbb{N}$ which are not explicitly definable from each other. The second theorem says that there exists a subset of $\mathbb{N}$ which is not implicitly definable but belongs to a countable, explicitly definable set of subsets of $\mathbb{N}$. Previous proofs of these theorems have used finite- or infinite-injury priority constructions. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  43.  15
    Separation and Weak König's Lemma.A. James Humphreys & Stephen G. Simpson - 1999 - 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 (11 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  44.  22
    An Incompleteness Theorem for Βn-Models.Carl Mummert & Stephen G. Simpson - 2004 - 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)  
     
    Export citation  
     
    Bookmark  
  45.  9
    Countable Valued Fields in Weak Subsystems of Second-Order Arithmetic.Kostas Hatzikiriakou & Stephen G. Simpson - 1989 - Annals of Pure and Applied Logic 41 (1):27-32.
  46.  11
    Proof Theory.Proof Theory: Some Personal Recollections.Contributions of the Schutte School in Munich to Proof Theory.Subsystems of Z 2 and Reverse Mathematics.Proof Theory: A Personal Report. [REVIEW]Dag Prawitz, Gaisi Takeuti, Georg Kreisel, Wolfram Pohlers, Stephen G. Simpson & Solomon Feferman - 1991 - Journal of Symbolic Logic 56 (3):1094.
  47.  22
    High and Low Kleene Degrees of Coanalytic Sets.Stephen G. Simpson & Galen Weitkamp - 1983 - Journal of Symbolic Logic 48 (2):356-368.
  48.  10
    Cone Avoidance and Randomness Preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
  49.  8
    On the Existence of Two Analytic Non-Borel Sets Which Are Not Isomorphic.A. Maitra, C. Ryll-Nardzewski, R. Daniel Mauldin, Karel Hrbacek & Stephen G. Simpson - 1984 - Journal of Symbolic Logic 49 (2):665-668.
  50.  13
    Spring Meeting of the Association for Symbolic Logic.Stephen G. Simpson - 1993 - Journal of Symbolic Logic 58 (3):1093-1095.
1 — 50 / 61