by Richard Lockhart
I was David Blackwell’s Ph.D. student from mid-1977 to early 1979, having asked him to supervise after hearing the clearest lectures I had, and have, ever heard. I was Ph.D. student number sixty-two of sixty-five, according to the Mathematics Genealogy Project, where it will be seen that David had four students finish in 1978, two in 1979, and two more in 1981. I remember the chair outside his office where I would wait for my weekly half hour. I remember that he suggested a problem to me by giving me a paper and saying he didn’t think he had done everything there that he could have. A few months later I gave up and asked to work on something he was doing currently — programmable sets.
David gave a talk at Stanford in the Berkeley–Stanford colloquium series in which he described these objects. I emerged from the talk amazed by how clear and easy it all was. Trying to tell others about it, I saw quickly that the lecture was a very clear presentation of something not so easy at all and that David had the capacity to organize arguments far, far better than I. The idea is simple as he described it. Imagine a computer represented as a countably infinite sequence of lights. A computer program is a function \( f \) that turns off some lights. Which lights are extinguished is a function of the current pattern of on and off lights. You start with some initial pattern of lights, \( x_0 \) say, and let the program run by computing \( x_1 = f(x_0) \), \( x_2 = f(x_1) \), and so on inductively, generating the sequence \( x_n; n = 0, 1, 2, \dots \). The sequence \( x_n \) decreases so it has a limit, which we call \( x_{\omega} \). But for a general function \( f \) the program might not be finished — \( x_{\omega} \) need not be a fixed point of \( f \). So continue applying \( f \) inductively, once for each countable ordinal \( \alpha \) arriving at \( x_{\omega_1} \), the limit at \( \omega_1 \), the first uncountable ordinal. The limit must actually be reached at some countable ordinal, which may depend on \( x_0 \).
The iterates \( x_{\alpha} \) are, of course, iterates of the function \( f \) applied to \( x_0 \), so that we may think of the functions \( f_{\alpha} \) converging (pointwise) to the limit function \( f_{\omega_1} \), and we may wonder what sorts of functions \( g \) have the form of such limits if the basic function \( f \) is Borel? David looked at the output program \( f_{\omega_1} \) as a step in defining general functions \( g \) between two polish spaces \( U \) and \( V \), which were defined by mapping \( U \) into the computer’s state space by a Borel function, running the program, and then mapping the result into \( V \) in a Borel way. Any function admitting such a factorization is Borel programmable (BP), and sets are BP if their indicator functions are. David’s 1978 paper, establishing the basic properties of the sets and functions and showing that they had potential as useful objects in probability theory, is typical of his work — very clear, very concise, questions not answered set forth, and not quite four pages long.
In my thesis I solved one or two minor problems connected with these ideas. I was trying to clarify the relation between BP-sets, R-sets studied by Kolmogorov and others, and C-sets. I wanted to know, for instance, if letting the program, encoding, and decoding functions be BP, rather than just Borel, gave you a larger class of sets than the BP class. (John Burgess did the problem properly in Fundamenta Mathematica in 1981 using results from logic concerning monotone operators, the lightface and boldface set hierarchies and game quantifiers.) I cannot remember how I came to realize that I needed to think not about sigma fields but about collections of sets like the analytic sets which had fewer closure properties. I now think, though, that David planted the seed of this idea in my head one day — just by emphasizing the importance of closure properties to me; I rather suspect that my thesis would not have taken him more than a few weeks to put together and that the result would have been much shorter and far clearer.
I wish I could say I knew him well, but my weekly meetings were all I knew — and they were all mathematics. I was young and shy and David was friendly but formal, I think. I wish we could all learn mathematics from people who see it as clearly as David did.
