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
Arithmetic (SOSOA).

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.

A countable graph G is said to be locally kcolorable if every finite
subgraph of G is kcolorable. The following result is due to William Gasarch and Jeffry Hirst, ``Reverse
Mathematics and Recursive Graph Theory'', Mathematical Logic
Quarterly, 44, 1998, 465473: For each k greater than or equal to 2
and m greater than or equal to k, the statement ``every countable
locally kcolorable graph is mcolorable'' is equivalent over RCA0 to
WKL0, provided m is less than or equal to 2k1. In 1999 James Schmerl showed that the
restriction ``m less than or equal to 2k1'' 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, Pi11CA0 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:
 ``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.

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.

In July 1999 Harvey Friedman
wrote a new 25page 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.

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

Theorems VIII.2.24 and VIII.6.8 of SOSOA may have suggested the
following conjecture: ``Suppose M is an omegamodel of WKL0 and X
belongs to M. Then for all Y not Turing reducible to X, there exists
an omegasubmodel 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, NorthHolland, 1988, 133141, page 134: For all X
there exists an Xrecursively inseparable pair of disjoint
Xrecursively 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 modeltheoretic 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 modeltheoretic 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 modeltheoretic 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 modeltheoretic and
prooftheoretic proofs of conservation results. See Avigad, FOM, 2
November 1999.

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

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 omegamodel 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
nonomegamodels. 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 email to Simpson.

In April 2000 Simpson produced a betamodel 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 Pi1infinityTI0. These results supplement sections VII.2 and
VIII.6 of SOSOA. A preliminary draft of Simpson's paper ``A Symmetric
betaModel'' is available on Simpson's
publications page.

Two new papers by Downey/Hirschfeldt/Lempp/Solomon on Reverse
Mathematics appeared in April 2000. They are
``ComputabilityTheoretic and ProofTheoretic Aspects of Partial and
Linear Orderings'' and ``Reverse Mathematics of the NielsenSchreier
Theorem''. Preprints are available at Lempp's web
page.

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

A Midwestern Division meeting of the American Philosophical
Association (Minneapolis, May 35, 2001) will feature a Symposium on Reverse Mathematics and
Computability Theory.
t20@psu.edu / 13 April 2001