SOSOA: What's New?
I am Stephen
G. Simpson, a mathematics professor at Penn State University.
This web page lists some recent developments related to my book Subsystems of Second Order
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
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.
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.
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:
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.
- ``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
- ``Given a countable set of countable well orderings, one is
embeddable in another.''
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
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
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
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.
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
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 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.
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.
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
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
The 2001 Annual Meeting of the Association for Symbolic Logic
(Philadelphia, March 11-13, 2001) featured a Special Session on Reverse
A Midwestern Division meeting of the American Philosophical
Association (Minneapolis, May 3-5, 2001) will feature a Symposium on Reverse Mathematics and
firstname.lastname@example.org / 13 April 2001