REVERSE MATHEMATICS -- a bibliographical update

Stephen G. Simpson

June 30, 2005


Papers by Peter Cholak (updated June 2005)

  See also http://www.nd.edu/~cholak/.

    Peter Cholak, Carl G. Jockusch, and Theodore A. Slaman. On the
    strength of Ramsey's theorem for pairs. J. Symbolic Logic, 66(1):
    1-55, 2001. MR 2002c:03094.

    Peter Cholak, Alberto Marcone, and Reed Solomon. Reverse
    mathematics and the equivalence of definitions for well and better
    quasi-orders.  J. Symbolic Logic, 69(3):683-712, 2004.

    Peter Cholak, Mariagnese Giusto, Jeffry Hirst, and Carl Jockusch.
    Free sets and reverse mathematics. To appear in a refereed volume
    edited by Stephen G. Simpson.

Papers by Harvey Friedman (updated June 2005)

  See also http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html

    1. `Quadratic Axioms', January 3, 2000, 9 pages, draft.

    2. `Finite reverse mathematics', October 19, 2001, 28 pages, draft.

    3. `Metamathematics of Ulm theory', November 25, 2001, 33 pages, draft.

    4. `Strict reverse mathematics', January 31, 2005, 24 pages, draft.

    5. `The inevitability of logical strength', May 31, 2005, 13 pages, draft.

    5 has complete proofs, referring to 2, which also has complete
    proofs, without any dependent papers. 1 is state of the art for
    doing what 5 accomplishes, but staying within the language of
    arithmetic. Not as convincing as 5. 4 concerns the direction I
    would like to take RM now, in a proposal.

    FOM postings:

      74:Reverse arithmetic beginnings 12/22/99 8:33AM
      75:Finite Reverse Mathematics 12/28/99 1:21PM
      78:Qadratic Axioms/Literature Conjectures 1/7/00 11:51AM
      175:Maximal Principle/Hilbert's Program  6/8/03  11:59PM
      177:Strict Reverse Mathematics 1  6/10/03  8:27PM
      181:Strict Reverse Mathematics 2:06/19/03  2:06AM
      210:Coding in Reverse Mathematics 1  2/2/04  12:47AM
      211:Coding in Reverse Mathematics 2  2/4/04  10:52AM

      74 and 75 are programmatic and also states results in 2.
      78 is programmatic and also states results from 1.
      175 discusses results related to 1.
      177 and 181 discuss earlier forms of results in 5.
      210 and 211 are early forms of 4.

Papers by Noam Greenberg (updated June 2005)

   See also http://www.nd.edu/~ngreenbe/Papers/.

   Noam Greenberg and Antonio Montalban.  "Ranked structures and
   arithmetic transfinite recursion". 

      We examine natural statements about classes which admit
      Cantor-Bendixon-like classification such as superatomic Boolean
      algebras and compact metric spaces and show that they are all
      equivalent to arithmetic transfinite recursion. We use
      computable reductions between these classes.

   Noam Greenberg, Peter Cholak and Joe Miller.  "Uniform almost
   everywhere domination". 

      We construct an incomplete, uniformly almost-everywhere
      dominating degree via a priority argument and a forcing
      argument. It follows that the principle of regularity of
      Lebesgue measure for G_\delta classes does not imply and is not
      implied by common systems weaker than arithmetic comprehension.

Papers by Christoph Heinatsch (updated June 2005)

    Christoph Heinatch, Diploma Thesis, University of Muenster.

    Christoph Heinatch and Michael Moellerfeld, The determinacy
    strength of Pi^1_2-comprehension, submitted for publication.

       It is shown that Pi^1_2 comprehension proves the same Pi^1_1
       sentences as ACA_0 plus < omega - Sigma^0_2-determinacy, i.e.,
       determinacy for finite levels of the difference hierarchy over
       boldface Sigma^0_2 sets.

Papers by Bjorn Kjos-Hanssen (updated June 2005)

    See also http://www.math.uconn.edu/~bjorn/

    Klaus Ambos-Spies, Bjorn Kjos-Hanssen, Steffen Lempp and Theodore
    A. Slaman, Comparing DNR and WWKL, J. Symbolic Logic 69 (2004),
    no. 4, 1089--1104.

       Summary: Giusto and Simpson studied the axiom systems DNR
       (asserting existence of diagonally non-recursive functions) and
       WWKL_0 (weak weak König's lemma, asserting existence of paths
       in trees of positive measure). They conjectured that DNR is
       strictly weaker than WWKL_0, and we confirm this by
       constructing an omega-model of DNR where WWKL_0 fails.

    Bjorn Kjos-Hanssen, Stephen Binns, Manuel Lerman and Reed Solomon,
    On a conjecture of Dobrinen and Simpson concerning almost
    everywhere domination, 2005, submitted.

       Summary: We show 0' is K-trivial relative to each almost
       everywhere dominating degree below 0'. In particular each such
       degree is truth-table high. Also, the almost everywhere
       dominating degrees have measure zero and are meager.

    Bjorn Kjos-Hanssen, Almost everywhere domination and K-triviality,
    2005, to appear.

Papers by Jeffry L. Hirst (updated June 2005)

   See also http://www.mathsci.appstate.edu/~jlh/bib/bib.html

   [1] Jeffry L. Hirst, A survey of the reverse mathematics of ordinal
   arithmetic, Reverse Mathematics 2001 (S. Simpson, ed.), Lecture
   Notes in Logic, Association for Symbolic Logic, 2005.

   [2] Jeffry L. Hirst, Reverse mathematics and ordinal suprema,
   Reverse Mathematics 2001 (S. Simpson, ed.), Lecture Notes in Logic,
   Association for Symbolic Logic, 2005.

   [3] Jeffry L. Hirst, A note on compactness of countable sets,
   Reverse Mathematics 2001 (S. Simpson, ed.), Lecture Notes in Logic,
   Association for Symbolic Logic, 2005.

   [4] Peter A. Cholak, Mariagnese Giusto, Jeffry L. Hirst, and Carl
   G. Jockusch, Free sets and reverse mathematics, Reverse Mathematics
   2001 (S. Simpson, ed.), Lecture Notes in Logic, Association for
   Symbolic Logic, 2005.

   [5] Jeffry L. Hirst, Reverse mathematics of separably closed sets,
   Arch. Math. Logic, accepted for publications.

   [6] Jeffry L. Hirst, Hindman's theorem, ultrafilters, and reverse
   mathematics, J. Symbolic Logic 69 (2004), 65-72. MR2039345
   (2005b:03032)

   [7] Jeffry L. Hirst, Minima of initial segments of infinite
   sequences of reals, MLQ Math. Log. Q. 50 (2004), 47-50. MR2029605
   (2005d:03107)

   [8] Jeffry L. Hirst, Reverse mathematics and rank functions for
   directed graphs, Arch. Math. Logic 39 (2000), 569-579. MR1797809
   (2001k:03134)

   [9] Jeffry L. Hirst, Ordinal inequalities, transfinite induction,
   and reverse mathematics, J. Symbolic Logic 64 (1999),
   769-774. MR1777785 (2002g:03138)

   [10] Jeffry L. Hirst, Reverse mathematics of prime factorization of
   ordinals, Arch. Math. Logic 38 (1999), 195-201. MR1684583
   (2000k:03134)

   [11] Jeffry L. Hirst, Reverse mathematics and ordinal
   multiplication, MLQ Math. Log. Q. 44 (1998), 459-464. MR1654285
   (2000d:03151) 1

   [12] William Gasarch and Jeffry L. Hirst, Reverse mathematics and
   recursive graph theory, MLQ Math. Log. Q. 44 (1998),
   465-473. MR1654281 (2000d:03150)

   [13] Peter G. Clote and Jeffry L. Hirst, Reverse mathematics of
   some topics from algorithmic graph theory, Fund. Math. 157 (1998),
   1-13. MR1619288 (99j:03051)

   [14] Jeffry L. Hirst and Steffen Lempp, Infinite versions of some
   problems from finite complexity theory, Notre Dame J. Formal Logic
   37 (1996), 545-553. MR1446228 (98d:03050)

   [15] Jeffry L. Hirst, Reverse mathematics and ordinal
   exponentiation, Ann. Pure Appl. Logic 66 (1994), 1-18. MR1263322
   (95a:03078)

   [16] Jeffry L. Hirst, Derived sequences and reverse mathematics,
   Math. Logic Quart. 39 (1993), 447-453. MR1270391 (95d:03102)

   [17] Jeffry L. Hirst, Embeddings of countable closed sets and
   reverse mathematics, Arch. Math. Logic 32 (1993),
   443-449. MR1245525 (94m:03096)

   [18] Jeffry L. Hirst, Connected components of graphs and reverse
   mathematics, Arch. Math. Logic 31 (1992), 183-192. MR1147740
   (92j:03052)

   [19] Harvey M. Friedman and Jeffry L. Hirst, Reverse mathematics
   and homeomorphic embeddings, Ann. Pure Appl. Logic 54 (1991),
   229-253. MR1133006 (92m:03093)

   [20] Jeffry L. Hirst, Marriage theorems and reverse mathematics,
   Logic and Computation (Pittsburgh, PA, 1987), Contemp. Math.,
   vol. 106, Amer. Math. Soc., Providence, RI, 1990,
   pp. 181-196. MR1057822 (91k:03141)

   [21] Harvey M. Friedman and Jeffry L. Hirst, Weak comparability of
   well orderings and reverse mathematics, Ann. Pure Appl. Logic 47
   (1990), 11-29. MR1050559 (91b:03100)

   [22] Andreas R. Blass, Jeffry L. Hirst, and Stephen G. Simpson,
   Logical analysis of some theorems of combinatorics and topological
   dynamics, Logic and Combinatorics (Arcata, Calif., 1985),
   Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987,
   pp. 125-156. MR891245 (88d:03113)

   [23] Jeffry L. Hirst, Combinatorics in subsystems of second order
   arithmetic, Ph.D. Thesis, The Pennsylvania State University, 1987.

Papers by Steffen Lempp (updated June 2005)

  See also http://www.math.wisc.edu/~lempp/papers/list.html#reverse

    Klaus Ambos-Spies, Bjorn Kjos-Hanssen, Steffen Lempp, and Theodore
    A. Slaman.  Comparing DNR and WWKL.  Published in Journal of
    Symbolic Logic, 2004.  17 pages.

      Abstract: Simpson and X. Yu introduced an axiom system WWKL0 and
      showed it to be strictly intermediate between RCA0 and WKL0 as
      well as equivalent to some statements on Lebesgue and Borel
      measure. WWKL0 was further studied by Giusto and Simpson; and by
      Brown, Giusto and Simpson. Giusto and Simpson found that a
      certain version of the Tietze extension theorem was provable in
      WKL0 and implied the DNR axiom. They pointed out that DNR is
      intermediate between RCA0 and WWKL0, but left open the question
      whether DNR coincides with WWKL0, i. e., has the same theorems
      as WWKL0. Simpson conjectured that DNR is strictly weaker than
      WWKL0.  In the current paper, we confirm Simpson's conjecture.

    Rodney G. Downey, Denis R. Hirschfeldt, Steffen Lempp, and D. Reed
    Solomon. Reverse mathematics of the Nielsen-Schreier Theorem.
    Published in "Proceedings of an International Conference on
    Mathematical Logic Honouring Ershov on his 60th Birthday and
    Mal'tsev on his 90th Birthday", Novosibirsk, 2002.  13 pages.

      Abstract: The Nielsen-Schreier Theorem states that every
      subgroup of a free group is free. To formalize this theorem in
      weak subsystems of second order arithmetic, one has to choose
      between defining a subgroup in terms of a set of group elements
      and defining it in terms of a set of generators. We show that if
      subgroups are defined by sets, then the Nielsen-Schreier Theorem
      is provable in RCA0, while if subgroups are defined by
      generators, the theorem is equivalent to ACA0.

    Rodney G. Downey and Steffen Lempp.  The proof-theoretic strength
    of the Dushnik-Miller Theorem for countable linear orders.
    Published in "Proceedings of the Workshop in Recursion Theory and
    Complexity (Kazan, 14-19 July, 1997)", 1999.  3 pages.

      Abstract: We show that the Dushnik-Miller Theorem for countable
      linear orderings (stating that any countable linear ordering has
      a nontrivial self-embedding) is equivalent (over recursive
      comprehension (RCA0)) to arithmetic comprehension (ACA0).

    Rodney G. Downey, Denis R. Hirschfeldt, Steffen Lempp, and D. Reed
    Solomon.  Computability-theoretic and proof-theoretic aspects of
    partial and linear orderings.  Published in Israel Journal of
    Mathematics, 2003.  15 pages.

      Abstract: Szpilrajn's Theorem states that any partial order P =
      (S, <_P) has a linear extension L = (S, <_L). This is a
      central result in the theory of partial orderings, allowing one
      to define, for instance, the dimension of a partial ordering. It
      is now natural to ask questions like ``Does a well-partial
      ordering always have a well-ordered linear extension?''
      Variations of Szpilrajn's Theorem state, for various (but not
      for all) linear order types tau, that if P does not contain a
      subchain of order type tau, then we can choose L so that L also
      does not contain a subchain of order type tau. In particular, a
      well-partial ordering always has a well-ordered extension.  We
      show that several effective versions of variations of
      Szpilrajn's Theorem fail, and use this to narrow down their
      proof-theoretic strength in the spirit of reverse mathematics.

Papers by Antonio Montalban (updated June 2005)

    Antonio Montalban and Noam Greenberg.  Ranked Structures and
    Arithmetic Transfinite Recursion.  About to be submitted for
    publication.

    Antonio Montalban.  Indecomposable linear orderings and Theories of
    Hyperarithmetic Analysis.  Submitted for publication.

    Antonio Montalban.  Equivalence between Fraisse's conjecture and
    Jullien's theorem.  To appear in the Annals of Pure and Applied
    Logic.

Papers by Carl Mummert (updated June 2005)

    See also http://www.math.psu.edu/mummert/.
    
    Carl Mummert, On the Reverse Mathematics of General Topology,
    Ph.D. Thesis, Pennsylvania State University, June 2005, VI + 102
    pages.

    Carl Mummert and Stephen G. Simpson, Reverse mathematics and Pi12
    comprehension, preprint, 8 pages, accepted 27 June 2005 for
    publication in the Bulletin of Symbolic Logic.

Papers by James H. Schmerl (updated June 2005)

    James H. Schmerl, Graph Coloring and Reverse Mathematics,
    Mathematical Logic Quarterly, Volume 46, 2000, No. 4, pp. 543-548.

    James H. Schmerl, Reverse Mathematics and Graph Coloring:
    Eliminating Diagonalization, 24 pages, in Reverse Mathematics
    2001, S. Simpson, ed., Lecture Notes in Logic, to appear.

    James H. Schmerl, Undecidable Theories and Reverse Mathematics, 6
    pages, in Reverse Mathematics 2001, S. Simpson, ed., Lecture Notes
    in Logic, to appear.

Papers by Richard Shore (updated June 2005)

  See also http://www.math.cornell.edu/~shore/publications.html

    A. Nerode, G. Metakides, and R. A. Shore, Recursive limits on the
    Hahn-Banach theorem, Contemporary Mathematics 39 (1985), 85-91.

      Although not directly on reverse mathematics, this paper can
      certainly be read in that way.

    R. Aharoni, M. Magidor, and R. A. Shore, On the strength of
    K"onig's duality theorem for infinite bipartite graphs, Journal of
    Combinatorial Theory (B) 54 (1992), 257-290

    R. A. Shore, On the strength of Fra"iss'e's conjecture, in Logical
    Methods, J. N. C. Crossley, J. Remmel, R. A. Shore and
    M. Sweedler, eds., Birkh"auser, Boston, 1993, 782-813.

    C.-T. Chong, R. A. Shore and Y. Yang, Intepreting arithmetic in
    the r.e. degrees under $I Sigma_4-induction, in Reverse
    Mathematics 2001, S. Simpson, ed., Lecture Notes in Logic, to
    appear.

    R. A. Shore, Boolean algebras, invariants and ACA_0^+,
    Transactions of the American Mathematical Society, to appear.

    D. Hirschfeldt and R. A. Shore, Combinatorial principles weaker
    than Ramsey's theorem, to appear.

Papers by Ksenija Simic (updated June 2005)

  See also http://math.arizona.edu/~ksimic/.

    Ksenija Simic, Aspects of ergodic theory in subsystems of
    second-order arithmetic, PhD Thesis, Carnegie-Mellon University,
    2004.

    Jeremy Avigad and Ksenija Simic, Fundamental notions of analysis
    in subsystems of second-order arithmetic, to appear in Annals of
    Pure and Applied Logic.

    Ksenija Simic, Properties of L_p spaces in subsystems of
    second-order arithmetic, submitted for publication.

    Ksenija Simic, The pointwise ergodic theorem in subsystems of
    second-order arithmetic, submitted for publication.

Papers by Stephen G. Simpson (updated June 2005)

  Excerpted from my publication list at
  http://www.personal.psu.edu/t20/papers/.

  [9] Stephen G. Simpson, Notes on subsystems of analysis (informally
      distributed lecture notes), typewritten and mimeographed,
      Berkeley, 1973, 38 pages.

  [23] Stephen G. Simpson, Sigma11 and Pi11 transfinite induction, in:
       Logic Colloquium '80, edited by D. van Dalen, D. Lascar and
       J. Smiley, North-Holland, Amsterdam, 1982, pp. 239-253.

  [24] Stephen G. Simpson, Set theoretic aspects of ATR0, in: Logic
       Colloquium '80, edited by D. van Dalen, D. Lascar and J. Smiley,
       North-Holland, Amsterdam, 1982, pp. 255-271.

  [25] Stephen G. Simpson, Which set existence axioms are needed to
       prove the Cauchy/Peano theorem of ordinary differential
       equations?, Journal of Symbolic Logic, 49, 1984, pp. 783-802.

  [27] Harvey Friedman, Stephen G. Simpson, and Rick Smith, Countable
       algebra and set existence axioms, Annals of Pure and Applied
       Logic, 25, 1983, pp. 141-181; Addendum, 28, 1985, pp. 320-321.

  [28] Stephen G. Simpson, Reverse Mathematics, in: Recursion Theory,
       edited by A. Nerode and R. A. Shore, Proceedings of Symposia in
       Pure Mathematics, American Mathematical Society, Volume 42, 1985,
       pp. 461-471.

  [29] Stephen G. Simpson and Rick Smith, Factorization of polynomials
       and Sigma01 induction, Annals of Pure and Applied Logic, 31,
       1986, pp. 289-306.

  [34] Stephen G. Simpson, Friedman's research on subsystems of second
       order arithmetic, in: [42], pp. 137-159.

  [35] Stephen G. Simpson, Subsystems of Z2 and Reverse Mathematics,
       appendix to: Proof Theory, second edition, by G. Takeuti,
       North-Holland, Amsterdam, 1987, pp. 432-446.

  [38] Douglas K. Brown and Stephen G. Simpson, Which set existence
       axioms are needed to prove the separable Hahn-Banach Theorem?,
       Annals of Pure and Applied Logic, 31, 1986, pp. 123-144.

  [39] Stephen G. Simpson, Partial realizations of Hilbert's Program,
       Journal of Symbolic Logic, 53, 1988, pp. 349-363.

  [40] Andreas Blass, Jeffry L. Hirst, and Stephen G. Simpson, Logical
       analysis of some theorems of combinatorics and topological
       dynamics, in [43], pp. 125-156.

  [42] Leo Harrington, Michael Morley, Andre Scedrov and Stephen
       G. Simpson (editors), Harvey Friedman's Research in the
       Foundations of Mathematics, North-Holland, Amsterdam, 1985, XVI +
       408 pages.

  [44] Stephen G. Simpson, Ordinal numbers and the Hilbert Basis
       Theorem, Journal of Symbolic Logic, 53, 1988, pp. 961-974.

  [45] Kostas Hatzikiriakou and Stephen G. Simpson, Countable valued
       fields in weak subsystems of second order arithmetic, Annals of
       Pure and Applied Logic, 41, l989, pp. 27-32.

  [46] Kostas Hatzikiriakou and Stephen G. Simpson, WKL0 and orderings
       of countable Abelian groups, in: Logic and Computation, edited by
       Wilfried Sieg, Contemporary Mathematics, Volume 106, American
       Mathematical Society, 1990, pp. 177-180.

  [47] Xiaokang Yu and Stephen G. Simpson, Measure theory and weak
       K"onig's lemma, Archive for Mathematical Logic, 30, 1990,
       pp. 171-180.

  [48] Harvey Friedman, Stephen G. Simpson, and Xiaokang Yu, Periodic
       points in subsystems of second order arithmetic, Annals of Pure
       and Applied Logic, 62, 1993, pp. 51-64.

  [49] Douglas K. Brown and Stephen G. Simpson, The Baire category
       theorem in weak subsytems of second order arithmetic, Journal of
       Symbolic Logic, 58, 1993, pp. 557-578.

  [50] Stephen G. Simpson, On the strength of K"onig's duality theorem
       for countable bipartite graphs, Journal of Symbolic Logic, 59,
       1994, pp. 113-123.

  [51] Ju Rao and Stephen G. Simpson, Reverse algebra, in: Handbook of
       Recursive Mathematics, edited by Yu. L. Ershov, S. S. Goncharov,
       A. Nerode, and J. B. Remmel, associate editor V. Marek, volume 2,
       Recursive Algebra, Analysis, and Combinatorics, Elsevier, 1998,
       pp. 1355-1372.

  [52] A. James Humphreys and Stephen G. Simpson, Separable Banach space
       theory needs strong set existence axioms, Transactions of the
       American Mathematical Society, 348, 1996, pp. 4231-4255.

  [53] Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson,
       Vitali's theorem and WWKL, Archive for Mathematical Logic, 41,
       2002, pp. 191-206.

  [54] Stephen G. Simpson, Finite and countable additivity, 8 pages,
       preprint, November 1996.

  [55] A. James Humphreys and Stephen G. Simpson, Separation and Weak
       K"onig's Lemma, Journal of Symbolic Logic, 64, 1999, pp. 268-278.

  [56] Mariagnese Giusto and Stephen G. Simpson, Located sets and
       Reverse Mathematics, Journal of Symbolic Logic, 65, 2000,
       pp. 1451-1480.

  [57] Stephen G. Simpson, Subsystems of Second Order Arithmetic,
       Perspectives in Mathematical Logic, Springer-Verlag, 1999, XIV +
       445 pages.

  [59] Harvey Friedman and Stephen G. Simpson, Issues and problems in
       Reverse Mathematics, in: Computability Theory and Its
       Applications: Current Trends and Open Problems, edited by Peter
       A. Cholak, Steffen Lempp, Manuel Lerman and Richard A. Shore,
       Contemporary Mathematics, Volume 257, American Mathematical
       Society, 2000, pp. 127-144.

  [60] Stephen G. Simpson, Predicativity: the outer limits, in
       Reflections on the Foundations of Mathematics: Essays in Honor of
       Solomon Feferman, edited by Wilfried Sieg, Richard Sommer, and
       Carolyn Talcott, Lecture Notes in Logic, Volume 15, Association
       for Symbolic Logic, 2001, pp. 134-140.

  [61] Stephen G. Simpson, Kazuyuki Tanaka, and Takeshi Yamazaki, Some
       conservation results on weak K"onig's lemma, Annals of Pure and
       Applied Logic, 118, 2002, pp. 87-114.

  [62] Stephen G. Simpson, Pi01 sets and models of WKL0, 28 pages,
       preprint, April 2000; accepted February 2001 for publication in
       [64].

  [63] Stephen G. Simpson, A symmetric beta-model, 7 pages, preprint,
       May 2000; submitted for publication.

  [64] Stephen G. Simpson (editor), Reverse Mathematics 2001; 400 pages;
       accepted September 19, 2003 by the Association for Symbolic
       Logic, for publication as Volume 21 of their book series, Lecture
       Notes in Logic; to appear in 2005.

  [68] Carl Mummert and Stephen G. Simpson, An incompleteness theorem
       for beta_n-models, Journal of Symbolic Logic, 69, 2004,
       pp. 612-616.

  [69] Natasha L. Dobrinen and Stephen G. Simpson, Almost everywhere
       domination, Journal of Symbolic Logic, 69, 2004, pp. 914-922.

  [72] Carl Mummert and Stephen G. Simpson, Reverse mathematics and Pi12
       comprehension, preprint, 8 pages, accepted 27 June 2005 for
       publication in the Bulletin of Symbolic Logic.

  [73] Stephen G. Simpson, Subsystems of Second Order Arithmetic, 2nd
       edition, Perspectives in Logic, Association for Symbolic Logic,
       to appear.