SOSOA: What's New?

1. By section IV.1 of SOSOA, the following statement is equivalent over RCA0 to WKL0: ``If K is a closed set in a compact metric space, then any covering of K by a sequence of open sets has a finite subcovering.'' In June 1999 Jeffry Hirst showed that the same result holds even if K is assumed to be a closed bounded set of rational numbers.

2. A countable graph G is said to be locally k-colorable if every finite subgraph of G is k-colorable. The following result is due to William Gasarch and Jeffry Hirst, ``Reverse Mathematics and Recursive Graph Theory'', Mathematical Logic Quarterly, 44, 1998, 465-473: For each k greater than or equal to 2 and m greater than or equal to k, the statement ``every countable locally k-colorable graph is m-colorable'' is equivalent over RCA0 to WKL0, provided m is less than or equal to 2k-1. In 1999 James Schmerl showed that the restriction ``m less than or equal to 2k-1'' can be omitted.

3. David Reed Solomon's 1998 Cornell Ph.D. thesis ``Reverse Mathematics and Ordered Groups'' contains many interesting results to the effect that various known theorems about orderings of countable groups are equivalent over RCA0 to WKL0, ACA0, ATR0, Pi11-CA0 respectively. See also remarks III.6.6 and IV.4.6 of SOSOA.

4. In connection with section V.6 of SOSOA, on comparability of countable well orderings, we should note that each of the following statements is equivalent over RCA0 to ATR0:
   • ``If each of two countable well orderings is embeddable in the other, then they are isomorphic.''
   • ``Given two countable well orderings, one is embeddable in the other.''
   • ``Given a countable set of countable well orderings, one is embeddable in another.''
   The first two of these equivalences are due to Friedman/Hirst 1990 and the last is due to Shore 1993. See also theorem X.3.20 of SOSOA.

5. Harvey Friedman is planning a paper entitled ``Reverse Mathematics of Continuous Embeddings'' extending the results of Friedman/Hirst 1991. Various statements about continuous functions on countable sets are seen to be equivalent over RCA0 to ATR0. See also Friedman, FOM, 15 July 1999.

6. In July 1999 Harvey Friedman wrote a new 25-page paper entitled ``Reverse Mathematics of Ulm Theory''. It includes the proof of the result of exercise V.7.6 of SOSOA, and many other results. The conjecture of remark V.7.7 remains open. See also Friedman, FOM, 17 July 1999.

7. In June 1999 Harvey Friedman wrote a new 5-page paper entitled ``Maximal Nonfinitely Generated Subalgebras'' proving that the following statement is equivalent over RCA0 to Pi11-CA0: ``Every countable algebra having a nonfinitely generated subalgebra has a maximal one.'' See also Friedman, FOM, 14 July 1999.

8. Theorems VIII.2.24 and VIII.6.8 of SOSOA may have suggested the following conjecture: ``Suppose M is an omega-model of WKL0 and X belongs to M. Then for all Y not Turing reducible to X, there exists an omega-submodel M1 of M of WKL0 such that X belongs to M1 and Y does not belong to M1.'' However, this conjecture is in general false. For given M and X, the conjecture holds if and only if TJ(X) belongs to M. The ``if'' part is easily obtained from the usual Gandy/Kreisel/Tait construction as in the proof of theorem VIII.2.24. The ``only if'' part is a consequence of the following result of Antonin Kucera, ``On the Role of 0' in Recursion Theory'', Logic Colloquium '86, North-Holland, 1988, 133-141, page 134: For all X there exists an X-recursively inseparable pair of disjoint X-recursively enumerable sets such that, if Z is the symmetric difference of any two separating sets, then either Z is finite or TJ(X) is recursive in Z.

9. In section IX.3 of SOSOA, a model-theoretic argument is used to show that WKL0 is conservative over PRA for Pi02 sentences, and it is argued that this result has some bearing on Hilbert's program of finitistic reductionism. John Burgess, in a draft of a review of SOSOA for Philosophia Mathematica, asked whether it is possible to make this model-theoretic proof truly finitistic and thus formalizable in PRA. Recently Harvey Friedman presented an affirmative answer to this question. He showed how to convert this and several other model-theoretic conservation proofs into finitistic proofs that are formalizable in a system slightly weaker than PRA. See Friedman, FOM, 29 September 1999. Following up on this, Jeremy Avigad wrote a note discussing the relationship between model-theoretic and proof-theoretic proofs of conservation results. See Avigad, FOM, 2 November 1999.

10. In connection with section IX.2 of SOSOA, Kazuyuki Tanaka conjectured in 1995 that WKL0 is conservative over RCA0 for sentences of the form ``for all X there exists a unique Y such that A(X,Y)'' where A(X,Y) is arithmetical. In July 1999 Antonio Marques Fernandes proved the special case of Tanaka's conjecture where A(X,Y) is Sigma03. In November 1999 Simpson, using results of Tanaka and Yamazaki and some additional ideas, proved the full conjecture. This will appear in a Simpson/Tanaka/Yamazaki joint paper (in preparation).

11. In February 2000 Simpson wrote a paper ``Pi01 Sets and Models of WKL0'', available on Simpson's publications page. In this paper, Simpson produces an omega-model of WKL0 plus ``for all X and Y, if X is definable from Y, then X is Turing reducible to Y''. This result may be regarded as a supplement to section VIII.2 of SOSOA. Simpson also presents generalizations to non-omega-models. These generalizations may be regarded as a supplement to section IX.2 of SOSOA.

12. In the year 2000 Simpson is organizing a volume of papers on Reverse Mathematics, by various authors. If you are interested in contributing a paper, please send e-mail to Simpson.

13. In April 2000 Simpson produced a beta-model satisfying ``for all X and Y, if X is definable from Y, then X is hyperarithmetical in Y''. Simpson also presents generalizations involving arbitrary models of ATR0 and Pi1infinity-TI0. These results supplement sections VII.2 and VIII.6 of SOSOA. A preliminary draft of Simpson's paper ``A Symmetric beta-Model'' is available on Simpson's publications page.

14. Two new papers by Downey/Hirschfeldt/Lempp/Solomon on Reverse Mathematics appeared in April 2000. They are ``Computability-Theoretic and Proof-Theoretic Aspects of Partial and Linear Orderings'' and ``Reverse Mathematics of the Nielsen-Schreier Theorem''. Preprints are available at Lempp's web page.

15. The 2001 Annual Meeting of the Association for Symbolic Logic (Philadelphia, March 11-13, 2001) featured a Special Session on Reverse Mathematics.

16. A Midwestern Division meeting of the American Philosophical Association (Minneapolis, May 3-5, 2001) will feature a Symposium on Reverse Mathematics and Computability Theory.

t20@psu.edu / 13 April 2001