MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Sometime around 1975, Leo Harrington wrote a set of notes, apparently 13 pages long, entitled Kolmogorov's $R$-operator and the first nonprojectible ordinal. I do not know how widely they were circulated (or if they were ever available from the UCB library or anywhere).

From what I understand, these notes relate recursion on the first stable ordinal in the first nonprojectible to recursion in a certain explicitly defined type-3 functional. A more precise statement is given in Thomas John's paper “Recursion in Kolmogorov's $R$-operator and the ordinal $\sigma_3$” (J. Symbol. Logic 51 (1986) 1–11), but the proof is not reproduced there. A related but slightly different result of Harrington's, with a different type-3 operator, is quoted (as example 4.10) by Stephen Simpson's “Short course on Admissible Recursion Theory” (355–390 in: Fenstad &al. eds., Generalized Recursion Theory II (Oslo 1977), North-Holland 1978).

I'd very much like to see a copy of these notes, or a proof of any closely related result (e.g., the one quoted by Simpson's paper mentioned above).

The author has been kind enough to see if he can find them, but he isn't too optimistic. I've also written to a number of people who worked in the subject around that time (Sacks, Shore, Simpson and Soare), but without success. So I now turn to MO in the hope that someone has heard of these notes or knows where a copy might be found.

[Xref: link to meta thread]

PS: While I'm aware that offering prizes other than reputation points is frowned upon on MO, if someone should go through the (real-world!) trouble of copying, scanning or mailing these notes for me, I think it would be appropriate that I should respond with a small (real-world!) token of thanks, like an Amazon gift card or something. :-)

share|cite|improve this question
As I told you, I did speak with Prof. Harrington last week. I also called him yesterday during his office hour, no luck. An assistant on a different floor of Evans confirmed that he is pretty good about his office hours. Meanwhile, I sent him another email, repeating the names of the four other people you asked. At some point there should be a firm response about whether he has a copy himself. – Will Jagy Feb 28 '13 at 21:58
Prof. Harrington says he emailed you. – Will Jagy Mar 7 '13 at 1:11
up vote 23 down vote accepted

I asked Alekos Kechris. He had a copy and made a scan of it. Here is a link to it.

Regards, Ted

share|cite|improve this answer
I emailed the pdf to Prof. Harrington. I do not think he looks at MO. I included your name and A. Kechris. Meanwhile, these are his office hours, but he's not picking up his phone. – Will Jagy Mar 27 '13 at 21:43
I see, you are at Evans also. Just no direct phone number listed. – Will Jagy Mar 27 '13 at 21:49
Just saw this. Thanks a lot to you and others who helped in finding these notes! – Gro-Tsen Apr 2 '13 at 21:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.