FOM: Better by what criteria?

[Stuart A. Kurtz]

In FOM 13 Aug 1999 15:03:02, Simpson writes:

> > c. Downey-Kurtz proved that there is a computable torsion-free
> > abelian group that is not computably linearly ordered.  This shows
> > that the classical theorem that every torsion-free abelian group
> > can be ordered is nonconstructive. [SAK: quoted from Kurtz FOM
> > 6 Aug 1999 11:08:47.]
> 
> Yes, this was first done with a priority argument.  However, it was
> subsequently done better without one.  Inspired by the recursive
> counterexample of Downey/Kurtz 1986, Hatzikiriakou/Simpson 1990 (see
> page 143 of my book) proved that ``every torsion-free Abelian group
> can be ordered'' is equivalent over RCA0 to WKL0.  This reverse
> mathematics result was proved without a priority argument and
> immediately implies the Downey/Kurtz result.

In this note, I take issue with Simpson's use of the word "better"
in describing the Hatzikiriakou-Simpson proof of the Downey-Kurtz
theorem.  My question to Simpson: "Better by what criteria?"

In my opinion, the original priority proof of Downey-Kurtz was very
good by the criteria that seem most significant mathematically:

  1) Timeliness.  Downey-Kurtz proved the theorem first.  Priority
  (in the sense of scholarly precedence, as well as in the technical
  structure of the argument) is theirs.

  2) Insightfulness.  The Downey-Kurtz proof captured an important
  intuition as to how a computable representation can "change its
  mind" as to the group elements various integers represent, and so
  can introduce a dependence where their had not been one.  This
  makes it clear why any constructive version of Levi's theorem 
  (every torsion-free abelian group can be ordered) requires an
  additional hypothesis (e.g., that the group has a computable
  dependence algorithm), and indicates exactly what kind of obstacle
  any such additional hypothesis must overcome.

  3) Fruitfulness.  Other results, in the form of new computable
  counterexamples and constructivizations of classical theorems,
  flowed out of the Downey-Kurtz proof and its insights.

It may be that the Hatzikiriakou-Simpson proof is superior to the
Downey-Kurtz proof with respect to attributes (2) and (3), although
the burden of proof for such a claim would rest with Simpson, and he
made no such argument.  In any event, the Downey-Kurtz proof is
clearly superior with respect to (1), whatever Simpson might argue.

The brief passage quoted suggests that Simpson has two reasons for
his judgement: first, that Hatzikiriakou-Simpson avoided a priority
argument (which he mentions twice); and second, that Hatzikiriakou-
Simpson exactly classified the proof theoretic strength of Levi's
theorem.  These are valid, and mathematically interesting points. 
However, to claim that the Hatzikiriakou-Simpson proof is "better"
than the Kurtz-Downey proof on these grounds is to beg the principle
question, for it assumes the things that he is trying to prove: that
eliminating priority arguments is good, and that all of
metamathematics is to be judged by reference to Friedman's program
of reverse mathematics.  These are opinions, not facts; they are
opinions I do not share.

But if one does accept that all of metamathematics is to be judged
by reverse mathematics, let me expand the pun from (1) above. 
"Priority" methods are so-called, not because of the structure of
their argument, but rather because they are used to obtain direct
proofs of many interesting theorems prior to those of the reverse
mathematicians.

Respectfully,

Stu
---------------
Stuart A. Kurtz
Professor and Chair
Department of Computer Science
The University of Chicago

web:   http://www.cs.uchicago.edu/~stuart
email: stuart at cs.uchicago.edu
phone: (773)-702-3493
fax:   (773)-702-8487