POST, EMIL LEON

(b.Augustów, Poland, 11 February 1897; d northern New York, 21 April 1954)

Mathematics, logic.

Post was the son of Arnold J. and Pearl D. Post. In May 1904 he arrived in America, where his father and his uncle, J. L. Post, were in the fur and clothing business in New York. As a child Post’s first love was astronomy, but the loss of his left arm when he was about twelve ruled that out as a profession. He early showed mathematical ability, however; and his important paper on generalized differentiation, although not published until 1930, was essentially completed by the time he received the B. S. from the College of the City of New York in 1917. Post was a graduate student, and later lecturer, in mathematics at Columbia University from 1917 to 1920, receiving the A. M. in 1918 and the Ph. D. in 1920.

After receiving the doctorate, Post was a Proctor fellow at Princeton University for a year and then returned to Columbia as instructor, but after a year he suffered the first of the recurrent periods of illness that partially curtailed his scientific work. In the spring of 1924 he taught at Cornell University but again became ill. He resumed his teaching in the New York City high schools in 1927. Appointed to City College in 1932, he stayed there only briefly, returning in 1935 to remain for nineteen years. Post’s family was Jewish; while not orthodox in his adult years, he was a religious man and proud of his heritage. He married Gertrude Singer on 25 December 1929 and they had one daughter.

Post was a member of the American Mathematical Society from 1918 and a member of the Association for Symbolic Logic from its founding in 1936. His extra-scientific interests included sketching, poetry, and stargazing.

Post was the first to obtain decisive results in finitistic metamathematics when, in his Ph.D. dissertation of 1920 (published in 1921), he proved the consistency as well as the completeness of the propositional calculus as developed in Whitehead and Russell’s Principia mathematica. This marked the beginning, in important respects, of modern proof theory. In this paper Post systematically applied the truth-table method, which had been introduced into symbolic logic by C. S. Peirce and Ernst Schröder. (Post gave credit for his method to Cassius J. Keyser when he dedicated his Two-Valued Iterative Systems to Keyser, “in one of whose pedagogical devices the author belatedly recognizes the true source of his truth-table method.”) From this paper came general notions of completeness and consistency: A system is said to be complete in Post’s sense if every well-formed formula becomes provable if we add to the axioms any well-formed formula that is not provable. A system is said to be consistent in Post’s sense if no well-formed formula consisting of only a propositional variable is provable. In this paper Post also showed how to set up multivalued systems of propositional logic and introduced multivalued truth tables in analyzing them. Jan Ƚukasiewicz was studying three-valued logic at the same time; but while his interest was philosophical, Post’s was mathematical. Post compared these multivalued systems to geometry, noting that they seem “to have the same relation to ordinary logic that geometry in a space of an arbitrary number of dimensions has to the geometry of Euclid.”

Post began a scientific diary in 1916 and so was able to show, in a paper written in 1941 (but rejected by a mathematics journal and not published until 1965), that he had attained results in the 1920’s similar to those published in the 1930’s by Kurt Gödel, Alonzo Church, and A. M. Turing. In particular, he had planned in 1925 to show through a special analysis that Principia mathematica was inadequate but later decided in favor of working for a more general result, of which the incompleteness of the logic of Principia would be a corollary. This plan, as Post remarked, “did not count on the appearance of a Gödel!”

If Post’s interest in 1920 in multivalued logics was mathematical, he also wrote in his diary about that time: “I study Mathematics as a product of the human mind and not as absolute.” Indeed, he showed an increasing interest in the creative process and noted in 1941 that “perhaps the greatest service the present account could render would stem from its stressing of its final conclusion that mathematical thinking is, and must be, essentially creative.” But this is a creativity with limitations, and he saw symbolic logic as “the indisputable means for revealing and developing these limitations.”

On the occasion of Post’s death in 1954, W. V. Quine wrote:

Modern proof theory, and likewise the modern theory of machine computation, hinge on the concept of a recursive function. This important number-theoretic concept, a precise mathematical substitute for the vague idea of “effectiveness” or “computability,” was discovered independently and in very disparate but equivalent forms by four mathematicians, and one of these was Post. Subsequent work by Post was instrumental to the further progress of the theory of recursive functions.

If other mathematicians failed to recognize the power of this theory, it was forcefully shown to them in 1947, when Post demonstrated the recursive unsolvability of the word problem for semigroups, thus solving a problem proposed by A. Thue in 1914. (An equivalent result had been obtained by A. A. Markov.) When reminded of his earlier statement, Quine in 1972 confirmed his opinion, adding: “The theory of recursive functions, of which Post was a co-founder, is now nearly twice as old as it was when I wrote that letter. What a fertile field it has proved to be!”

BIBLIOGRAPHY

I. Original Works. Except for abstracts of papers read at scientific meetings, the following is believed to be a complete list of Post’s scientific publications: “The Generalized Gamma Functions,” in Annals of Mathematics, 20 (1919), 202–217; “Introduction to a General Theory of Elementary Propositions,” in American Journal of Mathematics, 43 (1921), 163–185, his Ph.D. dissertation, repr. in Jean van Heijenoort, ed., From Frege to Gödel. A Source Book in Mathematical Logic, 1879–1931 (Cambridge, Mass., 1967), 264–283; “Generalized Differentiation,” In Transactions of the American Mathematical Society, 32 (1930), 723–781; “Finite Combinatory Processes. Formulation I,” in Journal of Symbolic Logic, 1 (1936), 103–105, repr. in The Undecidable (see below), 289–291; “Polyadic Groups,” in Transactions of the American Mathematical Society, 48 (1940), 208–350; The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematics Studies no. 5 (Princeton, 1941; “Formal Reductions of the General Combinatorial Decision Problem,” in American Journal of Mathematics, 65 (1943), 197-215; “Recursively Enumerable Sets of Positive Integers and Their Decision Problems,” in Bulletin of the American Mathematical Society, 50 (1944), 284-316, repr. in The Undecidable (see below), 305-337, Spanish trans. by J. R. Fuentes in Revista matemática hispanoamericana, 4th ser., 7 (1947), 187-229; “A Variant of a Recursively Unsolvable Problem,” ibid., 52 (1946), 264-268; “Note on a Conjecture of Skolem,” in Journal of Symbolic Logic, 11 (1946), 73-74; “Recursive Unsolvability of a Problem of Thue,” ibid., 12 (1947), 1 — 11, repr. in The Undecidable (see below), 293-303; “The Upper Semi-Lattice of Degrees of Recursive Unsolvability,” in Annals of Mathematics, 2nd ser., 59 (1954), 379-407, written with S. C. Kleene; and “Absolutely Unsolvable Problems and Relatively Unsolvable Propositions—Account of an Anticipation,” in Martin Davis, ed., The Undecidable (Hewlett, N.Y., 1965), 338-433.

II. Secondary Literature. There is an obituary of E. L. Post in The Campus (City College), 27 April 1954. Part of Post’s work was carried to a conclusion by S. V. Yablonsky and his students. See S. V. Yablonsky, G. P. Gavrilov, V. B. Kudryavtsev, Funktsii algebry logiki i klassy Posta (Moscow, 1966); translated into German as Boolesche Funktionen und Postsche Klassen (Brunswick, 1970).

Hubert C. Kennedy