Celebratio Mathematica

I was Dav­id Black­well’s Ph.D. stu­dent from mid-1977 to early 1979, hav­ing asked him to su­per­vise after hear­ing the clearest lec­tures I had, and have, ever heard. I was Ph.D. stu­dent num­ber sixty-two of sixty-five, ac­cord­ing to the Math­em­at­ics Gene­a­logy Pro­ject, where it will be seen that Dav­id had four stu­dents fin­ish in 1978, two in 1979, and two more in 1981. I re­mem­ber the chair out­side his of­fice where I would wait for my weekly half hour. I re­mem­ber that he sug­ges­ted a prob­lem to me by giv­ing me a pa­per and say­ing 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 do­ing cur­rently — pro­gram­mable sets.

Dav­id gave a talk at Stan­ford in the Berke­ley–Stan­ford col­loqui­um series in which he de­scribed these ob­jects. I emerged from the talk amazed by how clear and easy it all was. Try­ing to tell oth­ers about it, I saw quickly that the lec­ture was a very clear present­a­tion of something not so easy at all and that Dav­id had the ca­pa­city to or­gan­ize ar­gu­ments far, far bet­ter than I. The idea is simple as he de­scribed it. Ima­gine a com­puter rep­res­en­ted as a count­ably in­fin­ite se­quence of lights. A com­puter pro­gram is a func­tion $f$ that turns off some lights. Which lights are ex­tin­guished is a func­tion of the cur­rent pat­tern of on and off lights. You start with some ini­tial pat­tern of lights, $x_0$ say, and let the pro­gram run by com­put­ing $x_1=f(x_0)$, $x_2=f(x_1)$, and so on in­duct­ively, gen­er­at­ing the se­quence $x_n;n=0,1,2,\dots$. The se­quence $x_n$ de­creases so it has a lim­it, which we call $x_{\omega }$. But for a gen­er­al func­tion $f$ the pro­gram might not be fin­ished — $x_{\omega }$ need not be a fixed point of $f$. So con­tin­ue ap­ply­ing $f$ in­duct­ively, once for each count­able or­din­al $\alpha$ ar­riv­ing at $x_{{\omega }_1}$, the lim­it at ${\omega }_1$, the first un­count­able or­din­al. The lim­it must ac­tu­ally be reached at some count­able or­din­al, which may de­pend on $x_0$.

The it­er­ates $x_{\alpha }$ are, of course, it­er­ates of the func­tion $f$ ap­plied to $x_0$, so that we may think of the func­tions $f_{\alpha }$ con­ver­ging (point­wise) to the lim­it func­tion $f_{{\omega }_1}$, and we may won­der what sorts of func­tions $g$ have the form of such lim­its if the ba­sic func­tion $f$ is Borel? Dav­id looked at the out­put pro­gram $f_{{\omega }_1}$ as a step in de­fin­ing gen­er­al func­tions $g$ between two pol­ish spaces $U$ and $V$, which were defined by map­ping $U$ in­to the com­puter’s state space by a Borel func­tion, run­ning the pro­gram, and then map­ping the res­ult in­to $V$ in a Borel way. Any func­tion ad­mit­ting such a fac­tor­iz­a­tion is Borel pro­gram­mable (BP), and sets are BP if their in­dic­at­or func­tions are. Dav­id’s 1978 pa­per, es­tab­lish­ing the ba­sic prop­er­ties of the sets and func­tions and show­ing that they had po­ten­tial as use­ful ob­jects in prob­ab­il­ity the­ory, is typ­ic­al of his work — very clear, very con­cise, ques­tions not answered set forth, and not quite four pages long.

In my thes­is I solved one or two minor prob­lems con­nec­ted with these ideas. I was try­ing to cla­ri­fy the re­la­tion between BP-sets, R-sets stud­ied by Kolmogorov and oth­ers, and C-sets. I wanted to know, for in­stance, if let­ting the pro­gram, en­cod­ing, and de­cod­ing func­tions be BP, rather than just Borel, gave you a lar­ger class of sets than the BP class. (John Bur­gess did the prob­lem prop­erly in Fun­da­menta Math­em­at­ica in 1981 us­ing res­ults from lo­gic con­cern­ing mono­tone op­er­at­ors, the light­face and bold­face set hier­arch­ies and game quan­ti­fi­ers.) I can­not re­mem­ber how I came to real­ize that I needed to think not about sigma fields but about col­lec­tions of sets like the ana­lyt­ic sets which had few­er clos­ure prop­er­ties. I now think, though, that Dav­id planted the seed of this idea in my head one day — just by em­phas­iz­ing the im­port­ance of clos­ure prop­er­ties to me; I rather sus­pect that my thes­is would not have taken him more than a few weeks to put to­geth­er and that the res­ult would have been much short­er and far clear­er.

I wish I could say I knew him well, but my weekly meet­ings were all I knew — and they were all math­em­at­ics. I was young and shy and Dav­id was friendly but form­al, I think. I wish we could all learn math­em­at­ics from people who see it as clearly as Dav­id did.