FOM: priority arguments in reverse mathematics

[Stephen G Simpson]

This posting is part of the ongoing discussion of the so-called
``Simpson's Thesis'' concerning priority arguments in applied
recursion theory.

Robert Soare (FOM, 2 Aug 1999 12:54:07) made many false claims
concerning alleged priority arguments in reverse mathematics.  And
even after they have been refuted, he still persists in defending at
least two of his sets of false claims (FOM, 5 Aug 1999 10:37:59).  I
will now try once again to set the record straight on at least those
two.

1. BROWN/SIMPSON/MYTILINAIOS/SLAMAN

First, there are Soare's false claims (FOM, 2 Aug 1999 12:54:07,
repeated 5 Aug 1999 10:37:59) about a published result of Michael
Mytilinaios and Ted Slaman, which answered a published question of
Brown and Simpson.

[ I am referring to Douglas K. Brown and Steve Simpson of Penn State
University, not Nicole Brown and O. J. Simpson of Brentwood. ]

The publications are:
  
  Brown/Simpson, ``The Baire category theorem in weak subsystems of
  second order arithmetic'', Journal of Symbolic Logic, vol. 58, 1993,
  pp. 557-578.
  
  Mytilinaios/Slaman, ``On a question of Brown and Simpson'', London
  Math Society Lecture Notes, no. 224, 1996, pp. 205-218.

The question raised by Brown and Simpson and answered by Mytilinaios
and Slaman was whether BCT-II is provable in a system weaker than
RCA_0^+.  The answer is that that there exists an omega-model of
BCT-II which does not satisfy RCA_0^+.  Technically, the proof which
Mytilinaios and Slaman present cites another theorem (Proposition 3.5)
whose proof uses a priority argument.  However, there is also the
following much more direct proof, of which Mytilinaios and Slaman were
obviously aware:

  Theorem (Mytilinaios/Slaman).  There exists an omega-model of BCT-II
  which does not satisfy RCA_0^+.

  Proof.  By an easy forcing argument, let X be a subset of omega
  which is at or below level 15 of the arithmetical hierarchy, and is
  10-generic, i.e., Cohen-generic for arithmetical formulas at levels
  10 and below of the arithmetical hierarchy.  Let M be the
  omega-model consisting of all sets that are recursive in (X)_0 join
  (X)_1 join ... join (X)_n for some n.  Then M satisfies RCA_0 plus
  ``for all Y there exists Z such that Z is 5-generic relative to Y''.
  Hence by Brown/Simpson, M satisfies BCT-II.  But since M also
  satisfies ``there is no 20-generic set'', it follows by
  Brown/Simpson that M does not satisfy RCA_0^+.  Q.E.D.

Note that this proof contains no trace of a priority argument.  

In the above proof, the numbers 5, 10, 15, 20 are far from optimal.
In order to obtain an optimal result in this direction, priority
arguments are an appropriate technique, and this is the point of the
Mytilinaios/Slaman propositions 3.5 and 4.2.

Summary: Contrary to Soare's false claim, the Mytilinaios/Slaman
answer to the question of Brown and Simpson does not involve a
priority argument.

It's interesting that, when confronted with this refutation of his
false claim, Soare (FOM, 5 Aug 1999 01:05:59) deferred to Slaman and
said

 > Beyond that let's let Slaman and Simpson haggle over the details.
 > I do not know them since I was not a co-author.

In other words, Soare doesn't know the details and doesn't care to
learn them.  He is operating completely second-hand, via Slaman.

[ Incidentally, I have to admit that I too erred, in 4 Aug 1999
19:18:00, by thinking that Mytilinaios/Slaman model for proposition
4.2 was obtained by means of the low basis theorem.  By Brown/Simpson,
this cannot be the case, because the model satisfies BCT-II.  However,
it is true that the model consists of low sets.  I thank Ted Slaman
for setting me straight here. ]

2. HARRINGTON/STEEL/FRIEDMAN

Second, there are Soare's false claims (FOM, 2 Aug 1999 12:54:07)
about an unpublished result of Harrington on Sigma11 choice.

To begin with, I myself (FOM, 3 Aug 1999 20:56:31, ``Soare on Sigma11
choice'') soundly refuted Soare's claims.  Then John Steel (FOM, 4 Aug
1999 16:08:36, ``Sigma_1^1-AC error'') confirmed my account of the
matter and graciously (perhaps too graciously) took upon himself all
the blame for Soare's error.  Then Soare himself (FOM, 5 Aug 1999
01:56:17, ``Harrington-Steel theorem withdrawn'') partially
acknowledged his own error and partially withdrew his false claims.
So I thought we were making progress.

But then, a few hours later (FOM, 5 Aug 1999 10:37:59), Soare resumed
defending his false claims, citing a web page on his web site which he
attributes to Steel!

There is really nothing more to say about the underlying mathematical
facts here, which are anyway well documented in the literature, e.g.,
the thorough exposition in sections VIII.5 and VIII.6 of my book
``Subsystems of Second Order Arithmetic''
<http://www.math.psu.edu/simpson/sosoa/>.  (I will comment more later
on the history of these and related results.)

About this particular set of false claims by Soare, the only thing
left to say is that, once again, Soare is obviously operating
completely second-hand, this time via Harrington and Steel.  Soare
himself has no first-hand knowledge of the underlying mathematics and
does not seem interested in learning it.  His only interest here is to
refute the so-called ``Simpson's Thesis''.

-- Steve