0
$\begingroup$

Can anyone point me to any proofs (pref. interesting ones!) that make good (or bad) use of the Finite or Infinite Priority Injury Argument?

Edit: I would suppose that my question could be put this way too. Are priority injury method proofs limited to recursion theory, or have they been used elsewhere?

Motivation: It's a technique that crops up a lot in recursion/computability theory, especially in the Friedberg-Muchnik theorem. As a development of normal Priority Arguments (set up by Kleene and Post), I wish to explore any interesting, or just additional, formulations.

As I said, I'm familiar with 'Movable Marker' proofs, and with 'Priority Method' proofs, and I'm looking for proofs that make use of the injury side of the method.

For those who are unsure; the priority injury method utilises the notion that for a set of requirements that we have to meet, $R_{2e}$ for one side and $R_{2e+1}$ on the other side of our computation, we define the 'use' of each side, and then choose a witness $x$ s.t. $A(x)\neq \Phi^B_i (x)$, where $A$ and $B$ are the sets that we're trying to make incomparable in the Friedberg-Muchnik theorem. The key point is that we allow ourselves to finitely/infinitely injure the requirements that have been satisfied before so that we can satisfy a stronger requirement - it is this technique that I'm interested to see further examples of...

Any proofs considered!

With thanks, M.

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ Do you have access to Robert Soare's Book on R.E. Sets and Degrees? There may be a later and better treatment, but I doubt it. Gerhard "Ask Me About System Design" Paseman, 2011.06.15 $\endgroup$
    – Gerhard Paseman
    Commented Jun 15, 2011 at 23:58
  • $\begingroup$ (1) I am not a specialist in the field, and I am not aware of any writing of Post or Kleene on what you call "normal Priority arguments"; could you please specify a source? (2) there is a LARGE literature on priority arguments, with all sorts of results, part of which are included in the Soare text mentioned by Paseman in his comment above, so your question does not strike me as sufficiently focused. $\endgroup$
    – Ali Enayat
    Commented Jun 16, 2011 at 1:24
  • 2
    $\begingroup$ Ali, my impression is that the question comes with no research done. I suspect ((you will get a cogent answer to your question above) iff (the poster is familiar with Soare's book)). Gerhard "Was Young And Inexperienced Once" Paseman, 2011.06.15 $\endgroup$
    – Gerhard Paseman
    Commented Jun 16, 2011 at 2:32
  • $\begingroup$ As Gerhard mentioned, the classical reference for this is Robert Soare's Recursively Enumerable Sets and Degrees (Perspectives in Mathematical Logic, Springer-Verlag, 1987). Note that Soare will eventually publish a new book to replace this one - people.cs.uchicago.edu/~soare/cta $\endgroup$
    – François G. Dorais
    Commented Jun 16, 2011 at 5:13
  • $\begingroup$ You may also enjoy these notes math.uconn.edu/~lerman/GFposet.pdf by Manny Lerman. However, be aware that Lerman's goal in these notes is to go well beyond infinite injury, so you may find the learning curve very steep. In a similar vein, Steffen Lempp has some notes and other material - math.wisc.edu/~lempp/papers/prio.pdf - math.wisc.edu/~lempp/papers/list.html#prio $\endgroup$
    – François G. Dorais
    Commented Jun 16, 2011 at 5:14

3 Answers 3

Reset to default
5
$\begingroup$

The original proof of Borel determinacy by Donald Martin (1975, Annals of Mathematics) used a priority argument; I haven't read that paper, but Martin cited the complexity of the original proof as a motivation in the paper where he published his second, "purely inductive", proof (1985, Proc. Sympos. Pure Math. 42). The second proof eliminated the priority argument.

Note: the second paper was published in 1985, but was presented in 1982.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I agree with Carl that an important part of Martin's original proof of Borel Determinacy looks like a priority argument, but (if I remember correctly) Martin himself once told me that he didn't think of it that way. $\endgroup$
    – Andreas Blass
    Commented Jun 16, 2011 at 13:44
  • $\begingroup$ Thanks for the info. I was basing my comments on Martin's remarks in the first paragraph of his 1985 paper, where he describes the original argument as a priority argument. But I may be taking that intro paragraph out of larger context, and I'm not familiar with the original argument at all to comment on it. $\endgroup$
    – Carl Mummert
    Commented Jun 16, 2011 at 14:01
4
$\begingroup$

I've heard of priority arguments being used in complexity theory. See this blog post for example.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Many thanks @Quinn.Culver - that post looks interesting! Answers the question as I had hoped. The use of random strings and oracles is unusual - not something I had thought of in the way they write. Additionally, the comments are interesting (and quite philosophical at points). $\endgroup$
    – user15756
    Commented Jun 16, 2011 at 12:44
4
$\begingroup$

One of my favorite applications is Leo Harrington's proof that a computable differential field has a computable differential closure. This is the only proof I know that the differential closure of the constant field of rationals is computable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Dave: could you please provide a reference for Harrington's proof? $\endgroup$
    – Ali Enayat
    Commented Jun 17, 2011 at 2:44
  • $\begingroup$ @Ali, the paper is Harrington, Leo Recursively presentable prime models. J. Symbolic Logic 39 (1974), 305–309. He gives necessary and sufficient conditions for a complete decidable theory to have a decidable prime model. The proof is a finite injury priority argument. $\endgroup$
    – Dave Marker
    Commented Jun 17, 2011 at 13:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .