Timeline for Proofs that use Infinite/Finite Priority Injury Method
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18, 2011 at 8:10 | vote | accept | user15756 | ||
| Jun 17, 2011 at 0:41 | answer | added | Dave Marker | timeline score: 4 | |
| Jun 16, 2011 at 13:49 | comment | added | Andreas Blass | As far as I remember, this is the first time I've seen Kleene-Post arguments given the name "priority" (except jokingly --- "zero injury priority" --- which I might have said myself). The point of "priority" is that the relative order of the requirements is used in an essential way, to determine what actions can be taken to satisfy a requirement (i.e., you're not allowed to injure requirements of higher priority). That's not the case in Kleene-Post arguments. | |
| Jun 16, 2011 at 13:38 | answer | added | Carl Mummert | timeline score: 5 | |
| Jun 16, 2011 at 12:36 | comment | added | user15756 | @Carl - correct for both counts. | |
| Jun 16, 2011 at 11:34 | comment | added | Carl Mummert | @Ali Enayat: you're right that Kleene and Post didn't invent arguments with injury, but so-called "Kleene-Post" or "finite extension" arguments are sometimes thought of as priority arguments that happen to have no injury. For example, they had a proof that there are noncomputable degrees that don't compute $0'$, but they couldn't get the degrees to be r.e. with their injury-free method. | |
| Jun 16, 2011 at 11:31 | comment | added | Carl Mummert | @MC: if I understand the question you just want people to list proofs that use a priority argument outside of computability? | |
| Jun 16, 2011 at 10:12 | answer | added | Quinn Culver | timeline score: 4 | |
| Jun 16, 2011 at 9:06 | history | edited | user15756 | CC BY-SA 3.0 |
added 170 characters in body
|
| Jun 16, 2011 at 7:13 | comment | added | user15756 | François - the other notes are also very informative! But do you know of any other places where finite priority injury methods are used? | |
| Jun 16, 2011 at 6:43 | comment | added | user15756 | ...contd. in FM-theorem, we say that r.e. sets $A$ and $B$ exist s.t. $A \mid_T B$. I want to use this technique to solve some other problems, but wanted to gain some 'field experience' by researching what other problems have this as aprt of their solution. François Many thanks for the links! Some of these I had seen before (Lerman's papers on iterated trees of priority frameworks esp.). But some of the others should prove most useful. And yes, I had been informed of another book by Soare. Apologies for causing people problems... I had only hoped for informative results... | |
| Jun 16, 2011 at 6:35 | comment | added | user15756 | I have read Soare's book - I was wondering where else this technique has been used. I've also read Soare's papers on the subject, amongst Googling for examples (relatively unsuccessfully) and asking people as I meet them. I would like to think that this is asked with some research done... A normal - that is non-injured - priority argument is used in the construction of non-r.e. degrees (in fact, it's in Soare's book, p. 93). Two separate sets of requirements $R_e$ and $S_e$, are satisfied to resolve that there are incomparable degrees.... | |
| Jun 16, 2011 at 5:14 | comment | added | François G. Dorais | 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 | |
| Jun 16, 2011 at 5:13 | comment | added | François G. Dorais | 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 | |
| Jun 16, 2011 at 2:32 | comment | added | Gerhard Paseman | 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 | |
| Jun 16, 2011 at 1:24 | comment | added | Ali Enayat | (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. | |
| Jun 15, 2011 at 23:58 | comment | added | Gerhard Paseman | 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 | |
| Jun 15, 2011 at 23:50 | history | asked | user15756 | CC BY-SA 3.0 |