B An interview with Gerald E. Sacks

Chi Tat Chong and Yue Yang3

Gerald E. Sacks is Emeritus Professor of Mathematical Logic at Harvard University. He received his PhD degree in 1961 from Cornell University and taught at Cornell until 1967 when he took up an appointment at MIT. He was on the faculty of Harvard and MIT from 1972 and retired from MIT in 2006 and from Harvard in 2012. Professor Sacks’s work in recursion theory has had a profound influence on the development of the subject over the past 50 years. This interview was conducted in June 2009 at the Graduate Center of the City University of New York.

Question: Thanks for granting this interview. We thought it would be a good idea to spend some time talking and hearing from you about your work and views on recursion theory and logic in general. They will be an inspiration to students of logic and an important source of information to professional logicians as well as historians of the subject. We think people would be interested to get a sense of the development of major topics and ideas in recursion theory from your perspective. Such an account would be very illuminating.

Sacks: I find that hard to believe but I am willing to try. (laughter)

Q: I think it is good for us, for the purpose of this interview, to start at the beginning. I understand that you come from Brooklyn.

S: Brooklyn, New York. Yes.

Q: You went to a place called Brooklyn Technical High School. Did you already decide then that you wanted to be a mathematician?

S: No. No. I was interested in math when I was around 10 or 11. But my interest faded when I became 12 or 13. I think what I noticed was that girls were not interested in math, or boys who talked about math all the time. But they were interested in literature and art. So my interest shifted. (laughter) I became less interested in math and more interested in literature, poetry and arts, that sort of thing.

Q: But when you went to college, did you then …

S: When I went to college, I thought I was going to be an engineer. I have no idea why. That would have been a terrible mistake. But fortunately before I finished engineering I went to the army. In the army, where I was for three years, I became interested in math again. Someone gave me a copy of Introduction to Metamathematics by S. C. Kleene …

Q: A mathematician, I presume, who gave it to you?

S: Yes, yes and I started reading it and I thought it was very interesting.

This was before I graduated. I was sort of half way through the engineering program. I interrupted it to go into the army. I was amazed by, for example, his use of the principle of mathematical induction. Back in the days when I was so interested in math I learned about mathematical induction. But here Kleene used it to prove something about formulas. So I found that amazing. I thought you have to do induction, you know, on integers. But here, he was proving the deduction theorem and related theorems by induction. I think just for the propositional calculus. To me that was amazing.

Q: Before that, you had not taken any courses in logic? So this was your first introduction to the subject?

S: The math courses at Brooklyn Tech were just routine. You know, the old fashioned curriculum. No calculus, just algebra, plane geometry and solid geometry – you know, all that stuff. I mean there were four years of math there but kind of elementary, compared to what’s now available at school.

Q: So did you go to Brooklyn College for your engineering?

S: No. I was at Cornell University.

I returned to Cornell and I decided the simplest thing was to finish up the engineering course. But I took every possible elective course in the math department. I was now interested in math. But I still wasn’t certain about giving up engineering. By the time I finished the engineering course, I was now committed to math and one of the reasons was Cornell had a famous logician, Barkley Rosser, who had agreed to be my advisor. I was now committed to math and in particular to logic.

Q: But you never took a logic course from him before that.

S: No. But I had read most of Kleene’s book. So I knew a little bit about logic. I fought my way through the Incompleteness Theorem, and he had me in my first year explain to him the proof in great detail – that was his method of teaching. I had to stand in front of a blackboard telling him the proof of Gödel’s Incompleteness Theorem in detail. He wanted it in detail which I got some pleasure out of at that time, but I never forced it upon any of my students.

Q: Were you the only logic student at that time in Cornell?

S: Yeah, I was his only student. Roughly speaking the logic seminar consisted of him and me. He also spoke. He explained various things to me. But he had me explain – let me see – the Incompleteness Theorem, Gödel’s proof of the Generalized Continuum Hypothesis in L. So we just kept going.

Q: Which year was that?

S: That would be the academic year of 1958–59. There’s that orange book (The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory).

Q: One of the earliest volumes in the Princeton Annals of Mathematical Studies series.

S: Rosser was of course familiar with it. But you are right though, there was very little available. For example, Rosser knew about Tarski’s decision procedure for the reals, and the real closed fields and so on, but all he had was a mimeographed manuscript. There was no book in which it was discussed. There were very few books on logic. I mean, though Gödel’s Continuum monograph was out, I would not really call that a book. It is just a form of argument. There is not a single intuitive remark in it.

Q: It’s a monograph, certainly not something that …

S: So I worked my way through it. I don’t claim I really understood what was really going on, but I certainly understood it line by line. I was not yet familiar with the downward Skolem–Löwenheim Theorem4 and no one had heard of fine structure or anything like that. I mean none of that existed. But I was able to give myself intuitive explanations as well as checking all the formal things. Gödel’s monograph tells you every detail, you just have to check it and the argument sort of made sense. I guess sort of. But the real understanding of it came later. Thanks to a number of people, one of whom was Dana Scott.

Q: You met Scott in the late fifties?

S: No. I met him, I guess, in ’61. I got my PhD in ’61 and I think I met him somewhere around Princeton, maybe the fall of ’60. Somewhere in the academic year ’61 to ’63, he must have been passing through. Let me see. I went to Princeton on a postdoctoral fellowship ’61 to ’62 and I used it at the Institute for Advanced Study. Of course a lot of people came there and gave talks. He must have been one of them. Kreisel, for example, came through a couple of times. Church was on leave for a semester or two. So he was replaced by Abraham Robinson, whom I met at that time.

Q: Robinson was visiting …

S: Robinson was a visiting professor, I guess, for the academic year beginning 1961. I met him then and he was very encouraging. He seemed eager to speak with me. He certainly gave me a big lift.

Q: Maybe I can bring things back a little, to a few years before that. So you were in the army and you got this book by Kleene. But when you decided to do mathematics – switch to mathematics – how did you decide logic was the way to go, rather than algebra, geometry or whatever?

S: I am not sure. Certainly the idea of a recursive (computable) function was very appealing. But it’s hard to explain. Certainly I was very impressed by Gödel’s Continuum monograph, the ideas involved and that it is possible to prove something like that – its relative consistency – that seems interesting and unusual. It’s quite different from, say, real analysis or complex analysis, algebraic topology. I mean, math was interesting, but these ideas somehow seemed more interesting.

Q: Did you see the methods and ideas Gödel introduced in his monograph as an illustration of an infinite Turing machine at work?

S: Oh, no, no. I was just amazed that you could take a question like “Is the Axiom of Choice consistent with ZF” and give an answer yes. I couldn’t conceive how anyone could come up with that.

Q: Did you at that time think of the possibility of some independence results?

S: No. Not really. The first year I didn’t know what I was going to do. Rosser tried to push me toward set theory, but I resisted, because his interests in set theory were different. He was still concerned with some open problems with respect to new foundations …

Q: Quine’s New Foundations?

S: Yes. I looked into that. He cleaned it up. His version of new foundations was much simpler than Quine’s and equivalent to his. Rosser was also interested in more conventional set-theoretic properties. He was very interested in the question: “Do there exist inaccessible cardinals?” So for example he toyed with the idea trying to prove as a theorem of set theory there were none.

But I couldn’t see how to even begin something like that. Clearly you would assume there is an inaccessible and try to get a contradiction, try to do some combinatorial thing and he had some grand schemes for doing that. But I shied away from that …

Q: But he knew that it wasn’t provable under ZF – he knew about that?

S: He knew you couldn’t prove the existence of an inaccessible. Oh yeah, he knew that. But he was trying to prove there are no inaccessibles. So that was not proven. I mean, nothing to this day, as far as I know, rules that out, unless you assume something stronger. Meanwhile there were papers coming out, more and more papers coming out, in recursive function theory. The first year all we had available was the Kleene–Post paper. I thought that was a good paper. He made me explain the whole paper to him. There was a theorem at the end of that paper that I liked very much, which was, that there exists essentially a minimal pair over the degrees of arithmetical sets: There exist degrees a and b such that a degree is recursive in both of them if and only if it is arithmetical.

Q: Yes, that’s a very nice result?

S: The construction there intrigued me and then the second year Rosser was away. He was replaced for that year by Anil Nerode and Simon Kochen.

Q: They had just joined Cornell.

S: So Kochen taught me a little bit of Model Theory which of course was still in a very primitive state. But Nerode was very eager to discuss recursion theory. Now we had available several more papers: there were two papers by Spector, one on degrees, another on hyperdegrees of -sets.

Also Shoenfield had a paper on degrees and I think that really convinced me. In Shoenfield’s paper there was also an open problem at the end that convinced me to try to write a thesis on recursion theory. I wanted to try those questions. And we also had Friedberg’s solution of Post Problem. But Shoenfield’s paper made me think that Friedberg’s method – really the Friedberg–Muchnik method – could be developed a lot further. Certainly the solution to Post Problem really fascinated me. I couldn’t get over it. That seemed quite different from what I’d ever seen or thought about. I mean it’s trivial now, of course, but at that time, there was nothing like that.

Q: When did you first hear of the Friedberg solution?

S: In the fall of the second year, Nerode taught a course in recursion theory. This would be the academic year ’59–’60 and he did the solution. He explained it.

Q: I see. Rosser didn’t make you do a seminar and talk about …

S: I guess if he had been there that year, he would have made me do it.

But we kept busy that first year. He knew about Friedberg, when he got to it. We touched on a lot different things. Then Nerode made me aware of these other papers by Shoenfield, Spector and the like. I was also intrigued, Spector gave a measure theoretic argument then, that there exists incomparable hyper-degrees. So again that is intriguing. Again that was an unexpected argument: What made him think like that? At the end of the second year, the beginning of the summer I started my thesis. Of course, I have memories of that time, some of them maybe false, who knows? We always rewrite the past. But Shoenfield had a theorem in his paper: Here is 0′, there exist degrees a and b both less than 0′, and their union is 0′. He splits 0′ into two smaller degrees a and b. So I wondered why can’t a and b be degrees of r.e. sets? I thought about that during the summer. I finally saw, if I took an r.e. set which is nonrecursive … Oh, first I took one of degree 0′, I finally saw I could split it into two incomparables. Then I realized for any nonrecursive r.e., the argument would still work. So I had a theorem5 and I was rolling …

That was the summer of, I guess, 1960. That’s the end of my second year. Oh yes, I forgot, it was Friedberg’s Splitting Theorem. I think Nerode brought that to my attention. Friedberg had split a nonrecursive r.e. set into two nonrecursive r.e. sets – that was in my head. So the question was to get them of lower degrees. So that was an influence. The proof of the Splitting Theorem used a finite injury argument, but there was a further twist.

Q: Yes, we now call it the Sacks preservation strategy. The method is by now classic in recursion theory.

S: I can’t explain how my thinking was. I just fooled around with the problem day by day. But it finally worked out. Now Shoenfield had another open problem at the end of that paper, a minimal degree less than 0′. So I thought about that and didn’t get anywhere. At the end of the summer, although I was still a student, I went down to Princeton to become a visiting student at Princeton for my third and final year of graduate study, because Rosser was down there. When he left at the end of the first year, he decided he was going to stay two years in Princeton. So I was reunited with him. I kept thinking about the Shoenfield problem, minimal degree below 0′, because this minimal degree construction was yet another one that intrigued me immensely. I read that over and over. I guess a year earlier Nerode had me explain the proof to him. It seems a common teaching method. (laughter) I guess, both sides benefit.

Q: So was it before or after you met Spector when you started thinking about the problem?

S: I had not met Spector. I met him after I got my degree. I stayed on in Princeton a second year but now as an NSF PostDoc fellow in the institute. He was just finishing such a year. He was about to leave but he was there over the summer. Unfortunately during that summer he died. He was only 31.

Q: It was a tragic loss …

S: I thought about the minimal degree below 0′ problem. I looked at his argument. He used Cantor sets, I decided fairly early on, I could use somewhat arbitrary trees, but I wasn’t sure just what to do with them. Meanwhile I also thought about a bunch of other problems, such as embedding partial orderings in the degrees. So I played around a lot with that. Finally I guess – I can’t remember exactly – maybe February 1961, while I was waiting in line in the supermarket near Princeton, I saw how I could do the minimal degree below 0′.

Q: Waiting in line at the supermarket helps!

S: The idea is simple enough. In other words, look at the Spector argument and use trees of a suitable type and each tree was essentially coded by an r.e. set of numbers. So I realized you could change your mind. If you change your mind finitely often then things would settle down. I realized that could do it. In other words, 0′ suffices to be the oracle. I don’t need a 0″ oracle. I could do all this if I knew the story of 0′.

Q: I guess you wouldn’t advise a graduate student to spend time at the supermarket when stuck with a math problem?

S: I don’t know. I had an experience a few years later of a similar nature with the Density Theorem.

Q: It was getting to be a habit …

S: I worked on that one for quite a long time, maybe for close to two years, off and on.

I graduated in June 1961 at the Institute. I was still trying to do recursion theory. So again in the Shoenfield paper, there was a theorem that says if you take a degree between 0′ and 0″, which is r.e. in 0′, then it is a jump of a degree below 0′. So I said to myself, could that degree be r.e.? That would be a much prettier theorem for obvious reasons. I started working on it and – he is not here to defend himself – but Shoenfield was one of the people I met during that year in the Institute when he too passed through, and we chatted and I told him I was trying to improve his result in this way. He said he didn’t believe that was possible.

I tried to find out why he felt that way; why was he so sure? This is a reconstruction. His argument was a finite injury argument and he felt he had used the strongest method available in recursion theory. Since there is no stronger method, that would be no stronger result, something like that. Yeah, that was the beginning of a very pleasant relationship with him. He was always in a kind of gruff way very encouraging. I met him very often after that. Over the years he always said “What are you doing now?” and I would say “Well, I was doing this and I have done that” or “I was trying to do such and such”. He would tell me that’s the wrong thing to do; you should be doing this one. But he was the one that pushed for the Density Theorem. He thought it was true. Until it was done, he would bump into me: “Have you done the Density Theorem? What’s holding it up?” (laughter) I didn’t realize for a long time that he was fond of me. I thought he was always being so critical, but in later years I realized that … So he didn’t have the personal warmth that someone like Abraham Robinson had. He had the same good feelings.

Q: About the Density Theorem: One has to have a strong belief in the order of the r.e. degrees to work on the problem. There were very few clues on the structure available then.

S: I took an awful chance putting all that time and energy. Well, with the Splitting Theorem, you have a little bit of evidence. Alright, what else? I succeeded with the Jump Theorem6 that was an improvement of Shoenfield’s result. In order to do that, I made use of infinite injury argument.

Q: Was this the first time when infinite injury …

S: Well, that was for me, but I found out several years later that Shoenfield had done an infinite injury argument and published a paper.

I thought I had a method that seemed to deal with some of the difficulties that came up with the Density Theorem, not all of them. There was one, for example, I fooled around with sort of to warm up: If I had r.e. sets A <T B, and I assumed that A′ <T B′, then I could do it. I could get an r.e. set C strictly between A and B. So that was a warm up but it avoided the real problem. The problem itself took a while. But I was waiting in line at the supermarket. So this was back in the spring of 1962. I had an appointment with the person I just had lunch with.

Q: You were in Princeton at that time?

S: No. I came to visit him in New York City. I was supposed to meet him in front of his apartment building at a certain time and he was late. So I was sort of thinking about this problem one more time. How could one define an r.e. set C to outwit any computation using A as an oracle that tries to compute C? And I suddenly saw how it could be done.

I tried in the paper to say something intuitive about the idea behind the construction, but I failed. I said, well, we have a scheme here for sort of pretending to embed B into C, but then erasing it if necessary. Erasing it is intuitively reasonable here, if you look at it, but I don’t think it helps very much in the exposition.

Q: But your early papers were pretty formal.

S: But that was… Whom can I blame that on? (laughter) I complained to Spector that his paper was terribly formal. His excuse was that Kleene was his thesis advisor and Kleene was also the referee of that paper. So the referee forced him to write in that language.

Q: To be 100% accurate, I suppose.

S: Yes, I thought I was a bit less formal than that, but not much.

Q: I think in your orange book Degrees of Unsolvability there are pages and paragraphs in which you did try to motivate the reader.

S: Yes, but it’s still terrible. I guess Rosser also encouraged that approach. He didn’t seem to need intuitive remarks. (laughter) I mean he could just read this stuff and run through it. He was actually a very strong mathematician. He was quicker than I was. I could present him the mass of equations. He could just run right through.

Q: Who was his teacher?

S: Church. He was a student of Church. That’s interesting. He and Kleene were students of Church at the same time. Rosser was thought to be the quicker one. Again Kleene is not here to defend himself. But I noticed that Kleene was more persistent. That did pay off. Rosser was less persistent. He knew lots more mathematics. He was quicker. But …

Q: His interest seemed to be pretty wide, not just in mathematics, also in all sort of things.

S: Rocket ballistics, analytic number theory: he went from one thing to another.

Q: Kleene was probably more focused.

S: Yes, very focused, focused to a degree that you cannot imagine. I once asked him about my favorite theorem of his, which is simply this: The one section of 2E consists of exactly the hyperarithmetic sets.7 I was very intrigued by that. But it’s not a put-up job. Both of the things were defined by him – years apart! (laughter)One day he realized they were equal. So I think that’s the theorem in question. He didn’t do that in one day. No, no, I think the thing he was most persistent about was: If a set of integers is , then it is HYP – it’s hyperarithmetic. So I learned that one because when I was an assistant professor at Cornell, Nerode asked me to explain that. (laughter)That was a challenge. That paper was totally formal. There is not a single intuitive remark. I read it over and over and over and over. He used the Fixed Point Theorem to do effective transfinite recursion, but the phrase effective transfinite recursion does not occur! He just does it.

Q: The line of thought was there.

S: I didn’t know that was what he was doing. He just made very, to me, surprising use of the Fixed Point Theorem. So I was able to present it formally, but I didn’t really understand it intuitively. I mean I was able to verify everything. So I once asked him about how he got that theorem. He also had no knowledge of classical descriptive set theory. If he had, that would help, because he could sort of use that as a guide. But he knew nothing. He just did it from nothing. It took a while, but he said he was very conscious about the fact that you can’t work on a problem forever. You have to draw some limit, otherwise you just destroy yourself. So he had chosen a limit, a time limit on this problem, a certain day, 5 o’clock, and he would no longer work on that problem. So the months passed and the day approached. Around 4:30 that day, he figured it out!

I’m not making this up. He told me this story. So I think I learned from him. This is quite a digression you are asking me why my papers were formal, those early papers. I think, it’s partly his influence. He was too formal even for me. I had no love with formalism and he loved it. But I guess some pressure from him and Rosser made me write that way. I finally made Rosser admit that he had various intuitive pictures in his mind, though some of the things he did I don’t see how that was possible. You see, he did something in combinatoric logic and in λ-calculus, where I don’t see how there are any possible intuitive pictures. It’s truly formal and you are stuck with that. But he can do that. Maybe these men were more able than you or I to perceive formally (laughter) to a degree that I find impossible even to contemplate. It’s when I was working in classical recursion theory, I was constantly making pictures with dots, crosses, lines on pieces of paper or on the blackboard, none of which made it to the write-up. (laughter)

Q: You were already using Church’s thesis very freely, at least internally?

S: Of course, of course. The write-ups had nothing to do with the way that I thought about those things which, looking back now, was senseless. I would advise people to try to write things up the way they actually did it, in so far as it is possible.

Q: That’s right. So it seems very soon after you did those two or three major results – the Splitting Theorem, the Jump Inversion Theorem, the Density Theorem – you…

S: I was also very proud of the minimal degree below 0′ …

Q: Yes, I forgot to mention that one.

S: … because that was a finite priority argument on trees. In other words, the whole tree changes its mind to what its definition was finitely often.

Q: So by the year 1963 or even some time before that,you started thinking about higher recursion theory, I mean, going beyond the natural numbers?

S: Yes, I guess, I owe that initially to Nerode. In the fall of ’62, my first year as an assistant professor at Cornell, he asked me to give a seminar for as long as it would take. He had a bunch of logic students. Now Cornell had, it must have been, four or five logic students, which was an amazing change. Rosser had like one logic student every seven years or something. (laughter) But the times had changed. So Nerode thought people should learn HYP theory, if they were interested in logic. That started my interests in things higher up.

Q: So you did a seminar on that, a year long seminar?

S: That set me up to try to understand what Kreisel was talking about. Kreisel was talking in an incomprehensible way about generalizations of recursion theory. He had worked out something that, of course, was unnecessarily complex and his way of explaining it was very hard to penetrate or comprehend. But finally it began to make sense to me. His initial formulations were based on HYP theory and that became what he and I called metarecursion theory. This was recursion theory on recursive ordinals.

Q: That was ’65 or ’66, when it appeared?

S: But we started talking about it in summer ’63. So in the spring of ’63, I finished the proof of the Density Theorem, and during the summer of ’63, I wrote it up (in a very unappealing way) and I started speaking with him about recursion theory on the recursive ordinals, metarecursion theory. So it’s the summer of ’63. In the fall of ’63 we had the basic results.

Q: How did the collaboration happen?

S: I usually went to visit him. He went to Princeton a lot, I went down there a few times. Of course there was no email or anything. I tried to visit him as much as I could. And he wanted me to do Post’s Problem on recursive ordinals in his formulation. So I did. He suggested some other problems and so we wrote up a paper. We presented it, I think, in the spring of ’64. There was an AMS meeting when Kleene was the Chairman. Kreisel said I should give the talk and he would sit in the front row and maybe answer questions. So I gave the talk. Of course, it’s an extension of HYP theory. Kleene was very interested and when the clock ran out, I stopped. So he said: Oh, you can talk longer if you’d like; there’s plenty of time. (laughter) He was very very cordial.

Q: From then on you never returned to classical recursion theory. You just kept moving on …

S: Yeah, I got completely caught up in Kreisel’s program and he had a student Platek, whom he put to work on what became known as admissible ordinals. Gaisi Takeuti first noted that constructible cardinals were admissible. The formal notion of an admissible ordinal, and sets in general, were introduced by Richard Platek and Saul Kripke. Jensen’s fine structure theory of L has been fruitfully exploited by Sacks and others to study problems in α-recursion theory. I met him and I spoke with him and I kept talking to Kreisel, who didn’t want to write any more joint papers. He said he would supply me with questions, but just I should write the papers. I said alright. He didn’t want to be coauthor anymore. He was very generous I thought, in this respect. This is the side of him he’d shown to very few people. (laughter)His generous side, it was there. He wanted Post’s Problem for every admissible ordinal. I worked on that. So I did the initial result, kind of trivial, that there is always an intermediate degree – α-degree – for every admissible α. But I didn’t get two incomparables, sort of left out for the moment.

Q: That would be around ’65 or ’66?

S: This was around ‘65 and ‘66, because I got interested in forcing. I wanted to think about forcing, and forcing with perfect sets and some arguments with measure, getting Cohen’s result just with a simple measure-theoretic argument. But then I came back to α-recursion theory and in fact, I owe that to Shore, Richard Shore. I was also getting interested in model theory and I wanted to think about that a bit. But Richard Shore was a student at the time at MIT and I came back after I was on leave for a year. So in the fall of 1970, he said how about Post Problem for every admissible ordinal α?Why hasn’t that been done? I said well I thought a student of Rogers had done it. Let’s call them back. Rogers had a student who claimed to have done it in his thesis. So Shore said he had looked at that, but that was wrong. You know the thesis had been accepted sometime earlier, I said really? He said it’s completely wrong. There was nothing. So I was willing to believe him, I mean, I knew him. His first year as a graduate student I had been around and I’d spoken to him and if he said it was wrong, it was wrong. I started talking about it and as I talked I went to the board and said: Well, suppose we look at this case and I said that doesn’t seem too bad. So I said I think this probably can be done. But I decided to share it with Steve Simpson. I got together with him and we did it as a joint result. He was a more advanced student.

Q: You didn’t give this problem to Simpson to work on? He did write his thesis on α-recursion.

S: No, he was in his final year and yes, he was thinking about α-recursion theory. But I decided to push him a little harder, because he just began his, what has to be his, final year. I said I divided this thing up to cases, and I showed him the case I’d already done. I said only this case remains, and I had a vague idea how it should go. He finished that and he wrote the paper. He wrote it very nicely I thought.

Q: So that’s the Sacks–Simpson paper.

S: Actually we had several proofs of that. But I decided the way he did it in the paper was a nice way to write it up. I developed a proof which uses much more fine structure than necessary. So he got rid of some of it and Manny Lerman got rid of all of it. (laughter)

Q: Lerman didn’t like fine structure?

S: I discussed fine structure with him and he knew something about fine structure. But I was certainly interested in the idea of not using any fine structure at all. He nailed it.

Q: I always think incorporating methods and ideas of fine structure theory in recursion theory is a beautiful thing. You see a very nice interplay between recursion theory and set theory, and model theory as well.

S: Certainly. In Shore’s proof of the Density Theorem for all admissible ordinals, there’s some use of fine structure. In fact, he proved a new fact about fine structure which had not come up in the set theory world. So there is some fine structure there, I mean, I can’t prove it, but I would claim it’s absolutely necessary. Once you get deep enough in α-recursion theory, you certainly need fine structure. So you might as well have it from the start. So I got very caught up in α-recursion theory …

Q: Then you decided that admissibility was not really necessary, and you moved to β-recursion theory.

S: I did a little bit on the inadmissible case. Then Sy Friedman dived in, and got some terrific results.

Q: After this you thought, well, maybe E-recursion8 was the way to go?

S: I still wasn’t there yet. Somewhere in there I looked at Kleene’s papers on higher types, recursion in objects of finite type. I guess maybe Shoenfield got me interested in that. He simplified Kleene’s definitions a bit. He looked at recursion in type-two objects; and he wrote a very interesting paper explaining exactly what happened there. Suddenly at least for that case everything was crystal clear, which hadn’t been in Kleene. And Moschovakis9 was working on 3E and he had done something that looked very interesting. I got interested in the problem of sections, 1-sections, k-sections …

Q: I remember in 1970, at the International Congress of Mathematicians, the title of your talk was k-section of a type n object, something along that …

S: Yes, I got interested in that. I had a conjecture about sections. Of course I asked somebody who is an expert in that area, and he told me that couldn’t possibly be true. (laughter) It’s amazing how easy it is to believe firmly that such and such is the case, but it’s not! I think we all made that mistake, but I can tell you I guess I have a whole list of things that I worked on that some recursion theorists told me that couldn’t be true. I succeeded every time (laughter).

Q: Your intuition told you otherwise?

S: Yes, of course. At least that’s the way I wanted it to be. I don’t think my intuition is any better than theirs. The way I wanted was prettier than what they wanted.

Q: Coming back to minimal degrees. One of the major threads of your work seems to revolve around ideas and techniques connected to forcing with perfect sets: From minimal degree below 0′ to minimal hyperdegree, minimal degree of constructibility, and minimal upper bounds for HYP degrees and so forth. Was the intuition to see how far you could push the minimal degree construction?

S: Yes, I wrote this paper with Robin Gandy (“A minimal hyperdegree”). Again, that’s perfect sets and that was around ’65. So now forcing was involved; it was really needed. That was a forcing argument with perfect sets. Of course it made sense in set theory as well.

Q: But into the 1980s you were still looking at problems that were related to or making use of techniques that came from there, for example the problem of minimal upper bounds for a collection of hyperdegrees.

S: Yes yes, I guess I finally said my goodbye (laughter)to perfect set forcing, I don’t know what year it was, but the theorem is on upper bounds for countable sets of hyperdegrees. That’s the name of the paper. That took a while. I’d previously done it for a countable initial segment of L. But that used very heavily the very nice effective well-ordering of L. The admissible set now has no well-ordering yet satisfies Σ1-dependent choice. So there is something in there, an ugly face triple forcing. I didn’t write that one as clearly as I might have. I was certainly more intuitive by that time. That’s kind of funny. The paper was read by several students, all seemed to understand it readily, even though there are gaps in the argument, but they, a number of students, seemed to understand it without any problem. Bob Lubarsky was one of them, Leo Harrington was another – of course he could understand anything – and Fred Abramson.

Q: When did you first meet Jensen? How did the idea of using fine structure of L for α-recursion theory come about?

S: My first meeting with Jensen, I have to think about that for a moment. I guess Carol Karp told me about him. They wrote an important joint paper which goes by the title …

Q: “Primitive recursive set functions”? It appeared in an AMS Summer Institute volume on set theory.

S: I think the phrase “condensation lemma” occurred for the first time there. So they tried to clean up, what was now becoming folklore or common knowledge, in other words, they tried and succeeded in saying in print exactly what had to be said. I thought it was overly formal at that time, but I think I was wrong. Someone had to do that and they did. She got him interested in that, I think, and he carried on with it and of course he developed fine structure. Now he paid a visit to Cambridge (Massachusetts), I think, in 1967 and we talked. I think I met him earlier than this. There was this big Set Theory meeting at UCLA in 1967. He came to that. I don’t remember talking to him much at that time. He was kind of shy. He avoided situations where people might be abrasive to each other. At that time, for instance, a number of people sort of challenged each other. I think they were less civil than they would be now. He didn’t like anything like that. I was game for it, and he didn’t care for it. When he came to Cambridge, I understood him better then so we got along. And I think he was somewhat low at that time. I guess he was working on some hard problems and it was just before his many breakthroughs. This was in the late ’60s. I must have had some inkling about what he was doing with fine structure, before this Sacks–Simpson thing, which was done pretty much in the fall of 1970. Simpson finished in 1971. So we must have done that in the fall of 1970. So fine structure had been around for a while. No?

Q: Jensen’s paper itself only appeared in ’72.

S: What paper is that?

Q: “The fine structure of the constructible universe”. The preprint of the paper was of course already available before that.

S: Well, he must have given talks. In other words, I was certainly not an expert, but I knew a little bit about it. It was easy to get started, having experience with recursive ordinals, I mean, the key there was the projection, right? I certainly knew about the Σ1-projectum. I could see that made sense: For any α, you can define its Σ1-projectum. I certainly knew about the condensation method, I guess, from the Karp– Jensen paper.

Q: But the study of fine structure, at least for the reals, actually started with Hilary Putnam.

S: Oh, yes, yes, right. That’s another source, Boolos and Putnam.

Q: That was before Jensen. Did you take a look at that paper and think about it?

S: Yes. I was aware of that, but of course what I needed was essentially the fact that the two different definitions of say Σn-projectum are the same. I only needed that for Σ1. In the case of , that was sort of trivial. For Σ1 at least, it was very easy to prove by a simple condensation argument. Of course, the Boolos–Putnam thing was a condensation argument.

Q: Also, the notion of a master code and its characterization was already in their paper. It’s embedded somewhere referred to as “arithmetical copy”.

S: Oh, yes. But it’s just that the motivations were so much different. In other words, what I needed was exactly that fact, the two definitions of Σ1-projectum. In other words, that a very small, so to speak, α-r.e. set had to be α-finite. That was the key. But I spent lots of time with higher type objects, I don’t know why. I became quite interested again for a while, in recursion in objects of finite type. I mean that was what Harrington wrote his thesis on, and Ted Slaman wrote his thesis on that. That stayed in my mind for quite a while until, I mean there were various problems I’d thought about, I was just unable to do.

Q: About the minimal α-degree problem,10 first of all, do you think the question has a positive answer?

S: Oh, yes, the minimal α-degree problem for arbitrary admissible α.Yes,I thought about it, but I got nowhere, absolutely nowhere. I mean, of course I find myself thinking about ωω in L. Maybe that’s too tough (laughter).

Q: How about ωω1?

S: Maybe it would be wise to try that. It could be that ωω is the toughest case of all and one should leave that for the next generation or something, or the next century.

Q: That long?

S: No. I’m joking. But, yes, ωω1 maybe a sensible person may try that.

Q: But do you still think the answer is yes?

S: I’m tempted, I mean, I have no good reason. I guess that is the way I wanted it to be.

Q: Consistent with your past intuition about other problems?

S: No no. My intuition on this is worth nothing. It would just be, the argument would have to be interesting, right? If one could do that, it would be interesting al-most even to a set theorist. I mean one might need an insight into fine structure that is new. It’s hard to believe that there is anything left to say about fine structure but maybe there is. I mean, before Jensen came along, I didn’t think there was anything new to say about it, right? So he corrected that. Maybe there is more. I guess, some expert would say no, we know all about fine structure. Well, maybe not. It’s hard to see. Everyone I have ever talked to in detail about fine structure of L seems to have a slightly different intuitive picture. I mean, the way, (Menachem) Magidor say, talks about fine structure, or the way Sy Friedman does, or the way Jensen does, it’s all different. Magidor is much more intuitive and then he brushes off the J-hierarchy. You can be fairly crude, fairly intuitive and it would work if you just push it hard enough. But certainly Jensen’s presentation is very beautiful. His great insight that there are these master codes which are not merely oracles but which are preserved by condensation arguments. Now I never needed that. Maybe that had a role to play in α-recursion theory. I think Sy Friedman used it in the inadmissible case. But I haven’t looked at it in a long time. It doesn’t seem to come up in the admissible case. Maybe I’m wrong.

Q: So, looking ahead, how would you like to see recursion theory develop?

S: Well, I tended over the years to keep predicting the immediate end of recursion theory (laughter). But I have been wrong every time …

Q: By “end” you mean people lose interested in the subject?

S: Yeah. You know they just all stop working on it. But it hasn’t happened yet. This whole randomness phenomena is a big surprise to me. I mean, it has been around – these notions have been around for a long time.

Q: You even mentioned that in your book (Higher Recursion Theory), hidden in pages here and there.

S: Really? I mentioned randomness?

Q: Yes, in some exercises.

S: But that’s very weak use of it. People have gotten very subtle now with the study of randomness. There is an immense amount of activity and piles of papers that go on and on. I also thought forcing would be over by now but there are still people doing very complicated forcing arguments of a highly combinatoric nature. I thought set theory had sort of died out, but there were AD people, led by Hugh Woodin. I think in a way he is becoming more and more isolated. Fewer and fewer people know what he is doing.

Q: Getting harder and harder to understand.

S: And he is going further and further. The amount of material, I don’t see how a student could go to graduate school and hope to write a thesis in that area.

Q: It would also be challenging for a student in the area to have publications upon graduation to land an academic job.

S: Well, it’s probably not a good reason to produce so many academic mathematicians. I think the world needs more mathematicians, but they don’t have to be all professors. They don’t have to all have academic positions. They can work elsewhere …

We have to try to infiltrate all walks of life around the world with mathematicians. People who routinely think the way mathematicians think. I think there is a shortage of such people. I don’t think the phrase “applied mathematics” is right, but they can simply use mathematical thinking or a mathematical approach in whatever they do in their work. It can be molecular biology or it can be even in the legal field. I think the mathematical approach is very powerful. Gödel certainly thought so. Gödel certainly thought that’s the way to approach almost any problem.

Q: Could you say something about Gödel? When did you first meet him?

S: I met him, I guess in the Fall of ’61. In other words, my visit to the Institute was under his auspices. One has to apply, even though there is money provided by the National Science Foundation, and they have to accept you as a temporary member. Obviously it’s up to him (Gödel).

Q: So he was your host at the Institute?

S: Yes, but of course, I was afraid of him and never sought him out, essentially never spoke with him. But at another year in the Institute – I think it was 1974/75 – when we had a lot of contact, maybe we met once a month.

Q: Was he still interested in mathematics at that time?

S: Oh yes. I remember asking him one day what he thought the outstanding problems were in logic and he gave me a short list right there in person. One of them was the P =? NP problem.

Q: He was aware of that?

S: Yes, he was one of the very first, if not the first to draw attention to that problem. He wrote a letter to John von Neumann when von Neumann was on his deathbed, and he got a reply. Von Neumann said, roughly speaking, this is a very interesting problem, I would like to think about it sometime. (laughter)

This correspondence, I think, was shown to me by Martin Davis. That’s a long time ago. Von Neumann died in the ’50s. Another problem which is not entirely hopeless is consistency of analysis – proof of the consistency of analysis. There are many ways to interpret that. So you could try to find an ordinal which does it. The ordinal bears the same relation to analysis that ε0 bears to formal number theory. What’s the ordinal? And there are people who… well, I have met one person who thought this was do able, Michael Rathjen. But he also seemed to think it might be insane to pursue it, because it is so complicated. In other words, the description of the ordinal would be book length. But it would be possible to give a sort of a clear description of that ordinal and then demonstrate it’s the correct one.

And Gödel had one more problem: Look, what’s now called computable functions – he called them general recursive functions, total functions – there is an intuition that this one is more complicated than that one. Find the corresponding formal concept.

Q: Not in terms of definability?

S: No. Find the true hierarchy of the complexity of computable functions. Of course, no one has managed to do this and I think lots of people think it can be done. It seemed to him people readily said this was more complicated than that one, so there is evidence that the intuitive concept exists. And if that exists, there’s got to be a formal concept that captures that intuitive concept. That’s how his mind worked. It might also be a little complicated. (laughter)

Q: What about set theory? Did he have any comments on set theory?

S: I don’t recall. I mean, I tried to get him interested in AD, but he wouldn’t listen. I understood his objections to AD, but I thought I could say something that he might find of interest. But he would not tolerate.

Q: Not even Projective Determinacy?

S: I tried to work up from, say Borel, since for Borel it’s true. I mean, I had a pep talk prepared. He said AD is obviously false; for it falsifies the Axiom of Choice which is obviously true. He even made a nasty remark which is unusual for him. He said: I suppose sometimes it is interesting in seeing what a man can do with one hand tied behind his back. I mean, that was how the study of AD was to him. I think he was hasty there. I think there is something to talk about even if you believe AD is false, because it might be true in a very restricted setting. It might be true in L(ℝ) or it may be true for the projective sets, or something. I mean, there is something fruitful there, you are not wasting your time even if AD is false, even if AD is dramatically false. There is something going on there.

Q: But he never believed that V = L, right? I guess he only saw L as a tool.

S: Oh, I teased him about that. I teased him because if you go back far enough, he thought V = L might be true; and it might be the completion of ZF – this completed it and in other words, it settled every reasonable problem in set theory and so on. Then some time passed, he seemed to say that Continuum Hypothesis was false. It’s just definitely false. He said so in a paper.

So he tried to settle the matter. He tried to find the right cardinal. He seemed to think it’s ℵ2, because he spent lots of time trying to show that the continuum was ℵ2, and he even developed some false proofs. But what he was calling a proof was not from ZF. He knew ZF couldn’t do it. So he tried to write down some axioms about the real numbers, just true statements about real numbers which he found intuitively appealing, and these kept changing over time. But every once a while he would use that trying to prove the continuum was ℵ2, and he would succeed. Then he would find a mistake. So then more time passed. Now it’s near the end of his life. Now he told me he thought the continuum was ℵ1.

I said – I was teasing him and said – I thought you’ve said it’s equal to ℵ2. So he looked at me and said, I was misled (laughter). Apparently the people who told him all those examples, weird examples that you derive from Continuum Hypothesis misled him. So in the end, he tried to prove it with new axioms that were plausible. So for most of his life he is working on ℵ2.

Q: Thank you very much for spending time here.

S: Oh, I enjoyed the conversation very much. Thanks for your patience.