IN MEMORIAM: GERALD E. SACKS, 1933–2019

Gerald E. Sacks, age 86, Professor Emeritus of Mathematics at Harvard and M.I.T., passed away at his home in Falmouth, Maine, after a long illness. Sacks was born in Brooklyn and graduated from Brooklyn Technical High School. He initially was an engineering major, but interrupted his college studies at Cornell University to serve in the U.S. Army from 1953 to 1956. After returning to Cornell, he developed an interest in Mathematical Logic and continued his studies in that area, receiving his Ph.D. in 1961 as a student of J. Barclay Rosser. He began his academic career at Cornell University, but moved to M.I.T. in 1966, and later accepted a joint appointment at M.I.T. and Harvard. During his career, he held visiting positions at The Institute for Advanced Study and several prestigious universities.

Sacks had a brilliant mind for Mathematics and an abiding curiosity about it. In addition, he had a magnetic personality, and was always a center of attention. He was a captivating speaker, and a witty and deep thinker. His knowledge and interests were broad, covering not only his field of expertise but also the major developments in mathematics as a whole and in the world at large. His interests were varied; he enjoyed reading and had an extensive library, wrote poetry, and was a movie buff with a fantastic recall of highlights of movies. He gave willingly of his time and encouragement to his students, colleagues, and friends, and that encouragement frequently bore fruit. One cannot overestimate the effect he had on his main area of interest, Computability Theory, not only through his innovative work, but also through the work of his more than 30 students and more than 750 mathematical descendents.

Sacks began his work in Classical Computability Theory when the field was in its infancy. Kleene and Post had begun the study of degrees of unsolvability, or Turing degrees, and Post the study of the computably enumerable Turing degrees. The results of Friedberg and independently Muchnik (incomparable computably enumerable Turing degrees) and Spector (minimal degrees) stimulated interest in the area. But it was the pioneering work of Sacks in his monograph, Degrees of Unsolvability [1] that generated an exhaustive study of those degrees. Sacks’ work in that monograph covered many aspects of degree theory, and his innovative techniques produced several theorems that bear his name. Moreover, the importance of the results was equalled by the importance of the techniques he introduced.

The degrees of unsolvability form an algebraic structure that provides a measure of the complexity of information inherent in an oracle attached to a computer. One asks if the information coded into a set A (the oracle) is sufficient for a computer program with access to that information to compute a different set B. The computably enumerable degrees are a subset of these degrees containing the sets that are outputs of computer programs which do not have access to an oracle. Friedberg and Muchnik introduced a novel technique, the priority method, to show that there were incomparable computably enumerable Turing degrees, and thereby answered a question raised by Post that had become a central open question in the area. The priority method at the time was understood as a tool, but the true nature of priority arguments was not understood until later; the priority arguments introduced by Friedberg and Muchnik were later classified as $\Sigma _{1}^{0}$ , but at the time, the method was known as the finite injury method. In his monograph, Sacks extended this method to $\Delta _{2}^{0}$ through his Sacks-preservation strategy; he showed that a noncomputable, computably enumerable set can be split into two sets of lesser information content, which together can compute the original set. This theorem is now known as the Sacks Splitting Theorem. He [2] and Shoenfield independently introduced the $\Pi _{2}^{0}$ method. Sacks used this technique to prove the Sacks Jump Theorem, which characterizes the greatest degree that can be computable enumerable using a fixed computably enumerable set as an oracle, as those degrees that are computably enumerable over $0^{\prime }$ , the greatest degree of a computably enumerable set.

Sacks’ monograph dealt with aspects of degree theory other than computable enumerability. He generalized Spector’s construction of a minimal degree (the degree of a non-computable set A whose information content can only compute sets that are of the same degree as A or which are themselves computable) by showing that there is a minimal degree below $0^{\prime }$ . This proof combined the techniques of Spector with the priority method. He pioneered the use of category and measure to characterize the sparseness of classes of degrees, such as the class of all sets minimal degree which has cardinality of the continuum, but has measure $0$ .

The theorems proved in the monograph also set the foundation for the study of the global structure of the degrees. His characterization of the partially ordered sets that can be embedded into the computably enumerable degree led to a complete characterization of the existential theory of the computably enumerable degrees, and the study he began of initial segments of the degrees was later extended by others and became the basis of showing that the $\Pi _{2}^{0}$ -theory of the Turing degrees is decidable, while the $\Sigma ^{0} _{3}$ -theory is not, and that the full theory is effectively isomorphic to second-order arithmetic. The study of initial segments introduced the technique now known as Sacks forcing, a technique that has been useful in Set Theory as well as Computability Theory.

The influence of Sacks’ monograph should be measured not only by the results it contained, as the lists of open question in the two editions were every bit as influential in the development of the field. Several of these questions were answered fairly quickly by Lachlan and Yates while Sacks himself proved the density of the computably enumerable degrees. This last result is well known as the Sacks Density Theorem and it required a further strengthening of the priority method to the $\Delta _{3}^{0}$ -level. Over the following decades most of the questions were solved but some remain open to this day.

One of the remarkable things about Sacks’ work was its innovation, not only in the methods of proof he introduced, but also in the groundbreaking work he began in other areas. After making an indelible imprint through his work in degree theory, Sacks, partially under the influence of Kreisel, was led to study a much broader question. He tried to understand the general nature of computability in structures other than arithmetic, and this led to an analysis of computability in terms of definability. He founded the study of degree theory in $\alpha $ -Recursion Theory, or Computability Theory on Admissible Ordinals, and set his students to try to prove counterparts of the important theorems of Classical Computability Theory. The first challenge, of course, was the Friedberg–Muchnik Theorem. Several of his students, and others, worked on this problem and were able to get the counterpart for special cases, but a proof for all admissible ordinals remained elusive. Finally, Sacks, together with his student Stephen Simpson [9], was able to obtain a solution combining the priority method with a method derived from model theory, Skolem hulls. While the use of Skolem hulls was later replaced with combinatorial methods, the insight and innovation of Sacks and Simpson led to a deeper understanding of computation in terms of definability properties, and in particular, definability properties of admissible ordinals, that had not come to light beforehand. But once work in the field took hold, Sacks jumped to the study of computation and definability on other structures, first $\beta $ -Recursion Theory (Computability Theory on Limit Ordinals) and then to higher types and beyond.

Sacks finally did find what he had been seeking among the generalizations of recursion theory. He wrote 14 papers and the final third of his book, Higher Recursion Theory [6] about Kleene’s theory of recursive functionals of finite type and its extension by Normann and Moschovakis to recursive operations on arbitrary sets (E-recursion). The first of these papers, The 1-section of type n object [4], appeared in 1974 and the last, On the non-enumerability of L [8], appeared in 2016, a span of more than 40 years. We will give a brief summary here, with a few examples. Sacks’ 2013 survey paper, E-Recursive Intuitions [7], is a revealing account of why he found the topic so illuminating and appealing.

In Normann’s formulation, a partial function from sets to sets is E-recursive relative to a predicate R when it can be defined inductively by application of one of seven schemes. Such functions are indexed using the instances of the schemes used to define them as $\{e\}^{R}$ . When $\{e\}^{R}=y$ , there is a well-founded tree, the computation of $\{e\}^{R}$ on input x, which verifies the equality. The function taking x to this tree is also E-recursive relative to R. When $\{e\}^{R}$ is partial at x, the computation tree is not well-founded but still E-recursively enumerable.

E-recursion theory captures a sizable fragment of the subject of effective definability. A partial function from natural numbers to natural numbers is E-recursive exactly when its graph is recursively enumerable. It is E-recursive relative to the set parameter $\omega $ exactly when its graph is $\Pi _{1}^{1}$ , which is equivalent to being $\Sigma _{1}$ -definable in $L_{\omega _{1}^{CK}}$ . Say that a transitive set is E-closed if it is closed under applications of the partial E-recursive functions. In these last two cases, the E-recursively enumerable predicates are exactly those which are $\Sigma _{1}$ -definable over the E-closures of their arguments.

This coincidence is not always the case and Sacks was fascinated by the distinction between E-recursively enumerability and existential definability over the collection of sets generated by the E-recursive functions. Sacks’ 2016 paper provides an interesting example. Membership in Gödel’s L has a natural existential definition since $x\in L$ exactly when there is a set w that satisfies $V=L$ and $x\in w$ . The main result in that paper is that membership in L is E-recursively enumerable relative to some set parameter p if and only if $V=L$ . The argument is subtle when p is uncountable.

Sacks and his students developed a detailed account of the generation of $E(x)$ , the E-closure of a set x. This included understanding when an existential quantifier over $E(x)$ is E-recursively enumerable from x. We can summarize the situation as follows. Assume that x is transitive or replace it with its transitive closure. $E(x)$ has the form $L_{\kappa ^{x} }(x)$ , where $\kappa ^{x}$ is the supremum of the ordinals that are E-recursive in x and finitely many of its elements. In the general case, $\kappa ^{x}$ is strictly greater than $\kappa _{0}^{x}$ , which is the supremum of the ordinals that are E-recursive in x alone. Say that $\beta $ is x-reflecting if every $\Sigma _{1}$ statement about x which is true in $L_{\beta }(x)$ is also true in $L_{\kappa _{0}^{x}}(x)$ . Then, let $\kappa _{r}^{x}$ be the supremum of the x-reflecting ordinals. In many cases, such as when x is a set of ordinals or $x={\mathbb {R}}$ , $\kappa _{0}^{x} <\kappa _{r}^{x}<\kappa ^{x}$ and $\kappa _{r}^{x}+1$ is the ordinal at which a complete set of (Moschovakis) witnesses to the divergence of $\{e\}(x)$ is constructed from x, so the failure of reflection takes a canonical form.

[6] and its 1977 sequel, The k-section of a type n object [7], were a tour de force application of this structural view of computation and reflection. Here, type n means an element of the nth iterate of the power set applied to $\omega $ . The k-section of a type n predicate R is the set of type k objects that are E-recursive relative to R using the set of type $n-1$ sets as a parameter. Sacks addressed the fundamental question of whether the type of R was evident is its sections of lower type. He gave a negative solution by showing in [4] that every such 1-section object can be realized as the 1-section of a type 2 object. He completed the analysis in [5] by showing that every k-section of a type n object ( $n>k$ ) is the k-section of a type $(k+1)$ object. One could say that the conclusion is reminiscent of Sacks’ theorem that every countable admissible ordinal is the least admissible relative to some real; however the proof is much more sophisticated. It involves forcing, fine structure, reflection, and a mastery of recursion theoretic thinking.

Sacks further explored the features of reflection and the appropriate notions of forcing, priority arguments, and definability in infinitary languages in several papers. They provide deep insight into the notion of explicit computation and capture both its power and its limitations. Indeed, they elevate recursion theory to high art.

Sacks’ contributions to the Mathematical Logic community were broadly recognized. He spent the academic years of 1961–62 and 1974–75 at the Institute for Advanced Study in Princeton; he was a Guggenheim Fellow in 1966–67; he was invited to speak at the ICM in Nice (1970) and ICLMPS in Bucharest (1971); and he was a Senior Fulbright-Hayes Scholar in 1979. Sacks took pride in his teaching, and the clarity of his exposition extended to colloquium lectures in which he conveyed important advances in all fields of Mathematical Logic to general mathematics audiences. He published two important books in addition to Degrees of Unsolvability; Saturated Model Theory [3] was a popular choice for a first course in Model Theory for several generations of students; and Higher Recursion Theory [6] is the introduction to, and bible for, those studying that topic. His service as an editor of the Journal of Symbolic Logic in the late 1960s was during its transformation from covering Symbolic Logic broadly to a concentration on Mathematical Logic. He was a founding editor of the book series, Perspectives in Mathematical Logic which published many important books for those entering the field, and for use as reference texts by those in the field. He chaired the first Prize Committee for the Association for Symbolic Logic, and co-organized the first Computability Theory meetings in Oberwolfach, meetings that brought together leaders in the field to foster research collaboration, and have continued to this day. He also initiated the Greater Boston Logic Conferences at M.I.T., meetings that took place biennially for many years. He had more than 30 graduate students, and populated some of the major universities with his students. His successful mentoring of outstanding students led to the establishment of the Sacks Prize, a prize awarded annually to the student writing the best Ph.D. thesis in Mathematical Logic, now sponsored by the Association for Symbolic Logic.

Survivors include his wife, Margaret D. Philbrick; his four children, Matthew S. Sacks, Natalie R. Sacks, M.D. (John MacGregor, M.D.), and Paul M. Sacks (Kristen Kaplan) with his former wife Naomi Lavori, and Ella Raposo-Sacks with his former wife Luisa Raposo; three stepchildren, John Philbrick, Katherine Vorenberg, and Louise Philbrick; five grandchildren, Jacob S. MacGregor, Daniel, Kevin, and Harrison Philbrick, and Emma Vorenberg; and his brother, Michael H. Sacks, M.D.