[Date Index] [Thread Index] [FOM Postings] [FOM Home]

*To*: fom@math.psu.edu*From*: George Odifreddi <ogeorge@math.cornell.edu>*Date*: Wed, 28 Jul 1999 20:06:56 -0400*Sender*: owner-fom@math.psu.edu

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.

[Date Prev] [Date Next] [Thread Prev] [Thread Next]

[Date Index] [Thread Index] [FOM Postings] [FOM Home]