No subject

[George Odifreddi]

Dear Steve,

let me make some brief comments on the significance of priority arguments
in mathematics, hoping I'm not repeating what other people have already
said. While writing Volume II of my book, which is coming out in September,
I tried quite hard to find references to their use in other branches of
mathematics: I must admit, with scarce success. 

The oldest example I could come up with was suggested by Kreisel, and it is
Ackermann's modification of Hilbert's $\varepsilon$©substitution method,
that required the setting of an order of priority determined by the rank of
an $\varepsilon$©term, whose value could change finitely often during the
process (the result and the proof are reported in Volume II of 
Hilbert©Bernays). This even predates the uses in Recursion Theory itself.

Another interesting example is of course Martin's original proof of Borel
Determinacy: although there are now different proofs, one could argue that
Martin could come up with his original one because he had a training in
Recursion Theory, and could use the tool when he needed it. This is also
probably the case with Chandra's application of priority to problems in
Computer Science, of which I have just read (with pleasure) in your fom
list.

I think this is the kind of examples that one should look for in a
discussion on the significance of the priority method. I'm not at all
impressed by the fact that there are applications of the method to parts of
RECURSIVE Mathematics or Computer Science, in particular to the study of
collapsing degrees in Complexity Theory. This is certainly not to despise
this work: after all, I dedicate half of my Volume II to a treatment of the
latter. But it is obvious that such applications are bound to occur, if one
is taking a recursive point of view, and do not prove anything about a
wider significance of the method.  

I think that a look back at the history of the priority method could be
useful. The original motivations of Post for introducing in 1944 the method
in its simplest form (without injuries, the form often used today in
Complexity Theory) was to construct a hypersimple set: a step, he hoped,
towards the solution of a problem motivated by the study of undecidability
proofs of formal systems. 

The finite injury priority method was introduced by Friedberg and Muchnik
in 1956 to solve Post's Problem, which Godel thought at the time could
provide a hint for the solution of nothing less than Cantor's Continuum
Hypothesis, on the parallel: recursive vs. diagonally non©recursive (the
Halting Problem) on the one hand, and countable vs. diagonally uncountable
(the continuum) on the other hand.

The infinite injury priority method was introduced by Shoenfield in 1959 to
solve a problem not about r.e. degrees, but rather about formal systems and
undecidability proofs again.

Admittedly, these days are gone. And the priority method has been used
mostly to prove results in a field that, as John Myhill once said, was

I hope that the debate you started will produce, for good or worse, a
rethinking of our attitudes towards our own subject. My impression is that
we understand the tools of Recursion Theory much better than its goals, and
that we very much need a philosophical perspective, which can certainly
come from people outside the field, for example some of those in fom. I'm
thinking here, for example, of the effect that Kreisel's 1969 paper ``Some
reasons for generalizing Recursion Theory'' had on the field (and, I
believe, on your personal work in it, too). Perhaps, after the initial
pyrotechnic, we could stop debating whether the priority method is
``never'' or ``always'' used, and start exchanging opinions about what we
can do for Recursion Theory, and what Recursion Theory can do for
mathematics.