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.