REVERSE MATHEMATICS -- a bibliographical update

Stephen G. Simpson

June 30, 2005

Papers by Peter Cholak (updated June 2005)

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)

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
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)

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

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)

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)

[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)

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)

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)

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)

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.