To the editors:

I was enormously pleased to read Allyn Jackson’s essay recounting some of the main events in the life and career of Emil Post. Jackson’s work here will be valuable to anyone interested in this singular man. She paints a picture of a person equipped with boundless creativity, capable of extraordinary productivity even under circumstances—anti-Semitism within the American academy, physical disability, mental illness—that would have snuffed out a lesser light. Even some of Post’s occasional wry humor and humility comes across, principally in the description of Post’s notes on his discussions with Kurt Gödel, although anyone who wishes to become better acquainted with this dimension of Post’s personality may have to look at the footnotes and marginalia of his work for a fuller picture.

My reply consists of a few things that I would like to append to Jackson’s essay. I will close with some remarks on Post’s relevance to contemporary philosophy of mathematics.

First, let me elaborate on Post’s argument that a complete symbolic logic is impossible. Post’s proof here is so delightful, and so simple, that I think it is worth reproducing, at least in its essential elements, for the interested reader. We need one key concept: systems in normal form. Recall that these are nothing but the sets of strings generated from a given string by finitely many rules that remove a certain prefix and append a certain suffix. For example, we might define the rule A: “Remove 1 and add 0,” and the rule B: “Remove 00 and add 111,” and begin with the string 11. We would thereby produce

11 : A→ 10 : A→ 00 : B→ 111 : A→ 110 : A→ 100 : A→ 000 : B→ 0111.

At this point the rules A and B cannot be applied and we are left with the set

{11, 10, 00, 111, 110, 100, 000, 0111}.

Systems in normal form might seem like little more than interesting combinatorial objects if it were not for Post’s normal form theorem: the theorem that, as Jackson mentions, Marvin Minsky called “one of the most beautiful theorems in mathematics.” Post’s normal form theorem establishes that a remarkably broad class of systems—including systems in canonical form C, and by implication, even systems like the set of theorems of Principia Mathematica—can be reduced to normal form systems, in the sense that one can find a procedure for rewriting strings, with each string rewritten to a unique new string, so that all and only the members of a reduced set X are rewritten to be members of some normal form set X'. This is an example from 1921 of what mathematicians would much later come to call a 1:1-reduction.¹ A 1:1-reduction of X to X' lets us answer the question of whether a given string is a member of X, so long as we can tell when something is a member of X'. All that is needed is to rewrite our given string and ask whether the rewritten string is a member of X'.

Hence, Post’s theorem seems to show that if we can always answer membership questions about systems in normal form, then we can always answer membership questions concerning sets of deep intrinsic mathematical interest—the set of theorems of Principia Mathematica. A lesser thinker might have stopped with that optimistic picture. Post, however, pushed forward with a double insight. First, Post’s thesis: ANY set that can be mechanically produced can be generated by taking some system in normal form, and perhaps throwing away all the words containing some auxiliary symbols. Second, he established that there is at least one set that can be described, but cannot be thusly generated.

Here is the simple and beautiful proof: It is easy to see that the systems in normal form can be enumerated, one by one, in a row; each one can be completely described in a finite number of words, so that we could alphabetize these descriptions, for example. Similarly, the strings that they may or may not produce can be enumerated. Hence, we can consider whether the nth string is part of the nth system. We can then consider a set D containing the nth string if and only if that string is not part of the nth system. D, then, is not the nth system for any n—if the nth system contains the nth string, D excludes it, and if the nth system excludes the nth string, D includes it.

From this, which is an analogue of Alan Turing’s proof of the unsolvability of the halting problem, Post went on to establish that there exist normal form systems more and more closely approximating, but never completely exhausting, the information carried by the set D. And, a decade before Gödel’s incompleteness theorems, Post drew the conclusion that no purely mechanical mathematical procedure can ever completely and correctly describe the contents of D. Mathematical truth is laid out in an open-ended progression, each point of which might perhaps someday be within our reach, but whose totality must necessarily elude us.

Let me briefly mention two other of Post’s innovations, one well-known, and the other only occasionally mentioned, since it remained unpublished during Post’s lifetime. Jackson mentions that Post was deeply influenced by C. I. Lewis, and in particular by his conception of mathematics as a purely syntactic activity. In addition to establishing the completeness of the propositional fragment of the Principia, relative to truth-table semantics, Post—in his doctoral thesis—also established that this propositional logic was complete in a purely syntactical sense.² He showed that the addition of any axiom to this fragment would result in the system proving every sentence, rendering it useless. Hence, the propositional axioms of the Principia are, even without reference to their intended meaning, finished: nothing can be added to them. First-order logic, and in general, undecidable logics, cannot be Post-complete, since the Post-completeness of a formal system entails its decidability.³

Jackson also mentions that, from the time of his 1921 insights and through to the end of his career, Post was deeply interested in whether there might exist an absolutely undecidable proposition. This would be not a family of propositions, like the various truths concerning the contents of D, which cannot be encompassed by a single mechanical procedure, but a single proposition which we can never mathematically establish and can never mathematically refute. This is still a profoundly interesting question, one that will require both philosophical insight—what does it mean, precisely, to mathematically establish a theorem?—and mathematical ingenuity to answer satisfactorily. However, Post’s proposed route to answering the question was independently interesting. Having established that there were absolutely unsolvable problems—e.g., the problem “given n, determine whether the nth string is in D”—Post felt that the intermediate step required to adequately address the problem of absolute undecidability was to find an absolute notion of definability, one that encompassed every set of things definable by mathematical means.

In pursuit of this goal, between September 9, 1952, and February 4, 1953, Post filled a Sterling notebook, the kind with a cardboard cover marbled black-and-white. He filled it with reflections on the notion of definability. Among these reflections can be found an original definition of the hereditarily ordinal definable sets, as well as the basic results concerning these sets. Post was unaware that Gödel, in 1947, during the Princeton bicentennial lectures, had advanced the same concept as an analysis of absolute definability. This notebook resides in the Philadelphia archives of the American Philosophical Society, along with Post’s other papers and correspondence, easily available to interested scholars.

This brings me to my final topic: Post’s relevance to contemporary philosophy of mathematics. In many ways, Post was eclipsed, during his lifetime and beyond, by others, notably Gödel and Turing, both of whom have become about as famous as it is possible for a mathematician to be and both of whose eponymous phenomena—Gödelian incompleteness and Turing computability—were encountered, at least in some inchoate form, by Post in 1921.

I will not speculate about why Post is still a mathematician’s mathematician, so little appreciated relative to similar figures. I will, however, make the following suggestion. We can learn a great deal about mathematics—not just its contents, but its nature—by entering into the intellectual worlds of its pioneers, those thinkers who cleared new spaces for inquiry. Many philosophers have taken this lesson to heart. Accordingly, they have spent a great deal of time parsing and analyzing the works of thinkers such as Gödel, Turing, Gottlob Frege, Ernst Zermelo, David Hilbert, and the rest, from their most famous publications to their most incidental ephemera. Post was a great pioneer. But his work has gone comparatively unexamined, at least among philosophers of mathematics. With the centenary of Post’s 1921 miracle year rapidly approaching, I would venture that it is time for this to change.

Graham Leach-Krouse

Allyn Jackson replies:

It is gratifying to have such thoughtful and edifying reactions. Many thanks to Graham Leach-Krouse and Liesbeth de Mol for sharing their knowledge and insights.