Died: 21 April 1954 in New York, USA

**Emil Post**'s father was Arnold Post and his mother was Pearl Post. Arnold and Pearl were Polish Jews and their son Emil was born in Russian controlled Poland and spent the first seven years of his life there. The family emigrated to the United States in May 1904 looking for a better life, and set up home in New York.

Emil was an extraordinarily bright child but his life was one of great tragedy. When he was a child he lost an arm in an accident but this handicap was one which he handled well. He had to face mental problems in his adult life which had a devastating effect on him, making the physical problem of having lost an arm seem rather trivial in comparison.

There was free secondary schooling available for specially gifted children in New York. This was at the Townsend Harris High School which was situated on the same site as the College of the City of New York. After graduating from the High School Post remained on the same campus as he continued his studies at the City College.

We now think of Post as a mathematical logician but the first subject which attracted him was astronomy. While studying at the College of the City of New York he studied mathematics but there is little sign that at this stage he was particularly attracted towards logic. While an undergraduate at the College he wrote his first paper which was on generalised differentiation. The question he asked was a fascinating one: what does the differential operator *D*^{n} mean when *n* is not an integer? Although written while he was an undergraduate, Post did not submit the paper to the American Mathematical Society until 1923 and it was not finally published until 1930. It does contain a really important idea, for in the paper Post proves an important result about inverting the Laplace transform. This publication appeared long after Post's graduation with his first degree which was his B.S. awarded by the City College in 1917.

After graduating with his first degree, Post began postgraduate research at Columbia University. The significant event for Post's career had been the publication of Russell and Whitehead's *Principia Mathematica*. The first volume of *Principia Mathematica* was published in 1910, the second in 1912, and the third in 1913. When Post began his graduate studies it was an exciting new development and Post participated in Cassius J Keyser's seminar at Columbia which studied the *Principia Mathematica*. Post was awarded the degree of A.M. in 1918 and of Ph.D. in 1920. His Ph.D. thesis was on mathematical logic, and we shall discuss it further in a moment, but first let us note that Post wrote a second paper as a postgraduate, which was published before his first paper, and this was a short work on the functional equation of the gamma function.

We now turn to Post's Ph.D. thesis, in which he proved the completeness and consistency of the propositional calculus described in the *Principia Mathematica* by introducing the truth table method. He then generalised his truth table method, which was based on the two values "true" and "false", to a method which had an arbitrary finite number of truth values. The final, and perhaps the most remarkable, new idea which Post introduced in his thesis was to give a framework for systems of logic as inference systems based on a finite process of manipulation of symbols. Such a system of logic that Post proposed produces, in today's terminology, a recursively enumerable set of words on a finite alphabet. It would be fair to say that Post's thesis marks the beginning of proof theory.

After receiving his doctorate, Post went to Princeton University for a year as Proctor Fellow. He returned to Columbia University and, shortly after this, he had his first bout of an illness which was to recur throughout his career and limit what he might have achieved. As Davis writes in [4]:-

He suffered all his adult life from crippling manic-depressive disease at a time when no drug therapy was available for this malady.

In 1924 Post went to Cornell but again became ill. He resumed work as a high school teacher in New York in 1927. He married Gertrude Singer in 1929 and they had one child, a daughter Phyllis. Then in 1932 he was appointed to the City College. He left after a short spell, again struggling with his mental illness, but returned three years later and spent the rest of his life there. At the City College his teaching load was 16 contact hours per week which made finding time for research very difficult. Also members of staff has no offices of their own but were all put in a single room with one large table in the middle. Post chose to work at home, but with a young child this put a strain on the family. Post's daughter Phyllis explained later in her life how Gertrude Post had struggled to give her husband the opportunity to devote time to research:-

My father was a genius; my mother was a saint ... Besides typing letters of recommendation, my mother also typed my father's manuscripts and correspondence ... My mother was also the one who handled all financial matters ... she was the buffer in daily life that permitted my father to devote his attention to mathematics(as well as his varied interests in contemporary world affairs). Would he have accomplished so much without her? I for one, don't think so.

Post's early death at the age of 57 was almost certainly a direct consequence of the treatment he received for his mental illness. At that time such manic-depressive illnesses were treated with electric shock treatment. It was an horrific treatment for an horrific illness and one which caused great distress. It was based on nothing better than the fact that after patients received this treatment many had periods of more normal mental states. Post received the electric shock treatment on a number of occasions and it was while he was in a mental institution, shortly after receiving electric shocks, that he suffered a heart attack and died.

Post is best known for his work on polyadic groups, recursively enumerable sets, and degrees of unsolvability, as well as for his contribution to the unsolvability of problems in combinatorial mathematics. He introduced the concepts of completeness and consistency in a paper on truth-table methods which developed from the work of his doctoral thesis. He attributed these methods to his teacher at Columbia, C J Keyser, rather than to Charles Peirce and E Schröder as had been done previously. In the 1920s Post proved results similar to those which Gödel, Church and Turing discovered later, but he did not publish them. He reason he did not publish was because he felt that a 'complete analysis' was necessary to gain acceptance. He wrote:-

The correctness of this result is clearly entirely dependent on the trustworthiness of the analysis leading to the above generalisation... it is fundamentally weak in its reliance on the logic of Principia Mathematica ... for full generality a complete analysis would have to be given of all possible ways in which the human mind could set up finite processes for generating sequences.

He also made a mathematical study of Łukasiewicz's three-valued logic. At around this time he wrote in his diary:-

I study Mathematics as a product of the human mind not as absolute.

When Gödel published his Incompleteness Theorems in 1931, Post realised that he had waited too long to publish what he had proved and that now the whole credit would go to Gödel. In a postcard written to Gödel in 1938, just after they had met for the first time, Post wrote:-

... for fifteen years I carried around the thought of astounding the mathematical world with my unorthodox ideas, and meeting the man chiefly responsible for the vanishing of that dream rather carried me away. Since you seemed interested in my way of arriving at these new developments perhaps Church can show you a long letter I wrote to him about them. As for any claims I might make perhaps the best I can say is that I would have proved Gödel's Theorem in1921- had I been Gödel.

In a follow-up letter written the day after he writes:-

... after all it is not ideas but the execution of ideas that constitute a mark of greatness.

In 1936 he proposed what is now known as a Post machine, a kind of automaton which predates the notion of a program which von Neumann studied in 1946. In 1941 he wrote:-

... mathematical thinking is, and must be, essentially creative...

but he said there are limitations and symbolic logic is:-

... the indisputable means for revealing and developing these limitations.

Post showed that the word problem for semigroups was recursively insoluble in 1947, giving the solution to a problem which had been posed by Thue in 1914.

Quine, in a letter written in 1954 after Post's death, said:-

Modern proof theory, and likewise the modern theory of machine computation, hinge on the concept of the recursive function. This important number theoretic concept ... was discovered independently ... 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.

Quine added in 1972:-

The theory of recursive functions of which Post was cofounder is now nearly twice as old as when I wrote that letter. What a fertile field it has proved to be.

The way that Post conducted his classes at the City College was, to say the least, unusual. Davis attended such classes at the College of the City of New York during the late 1940s, and in [4] he gives us a clear picture:-

Post's classes were tautly organised affairs. Each period would begin with student recitations covering problems and proofs of theorems from the day's assignment. These were handed out apparently at random and had to be put on the blackboard without the aid of textbooks or notes. Woe betide the hapless student who was unprepared. He(or rarely she)would have to face Post's "more in sorrow than anger look". In turn, the students would recite on their work. Afterwards, Post would get out his3by5cards and explain various fine points. The class would be a success if he completed his last card just as the bell rang. Questions from the class were discouraged: there was no time. Surprisingly, these inelastic pedagogic methods were extremely successful, and Post was a very popular teacher.

Paul Chessin recalls being taught by Post in New York in about 1943:-

I recall that he was a short stocky fellow who invariably dressed in a three piece suit, empty sleeve carefully tucked into the side suitcoat pocket. He would stride steadily up and down before the blackboard, speaking clearly, vigorous in his motions. He would frequently, suddenly whirl around to face the board, chalk in hand, to write. This motion always tended to loosen that sleeve from its anchor until finally(to the relief of the class)it flapped loosely about as a cape might. That freedom of motion seemed to us to liberate his thinking as he lectured.

Finally we give this very fine tribute to Post from Davis:-

Post's significance transcends his scientific contributions, important as those were. He remains an inspiration as well, for the manner in which he overcame his potentially crippling mental disability, for his distinctive voice, and for his continued devotion to science and his students.

**Article by:** *J J O'Connor* and *E F Robertson*

**September 2001**

[http://www-history.mcs.st-andrews.ac.uk/Biographies/Post.html]