Emil Leon Post

from Wikipedia, the free encyclopedia
Emil Leon Post

Emil Leon Post (born February 11, 1897 in Augustów , Congress Poland ; † April 21, 1954 in New York , USA ) was a Polish - American mathematician and logician .

life and work

Post comes from a Polish-Jewish family who emigrated from what was then part of Russia to the USA in 1904 when he was still a child. He studied at City College of New York (bachelor's degree in 1917) and at Columbia University (master's degree in 1918) up to his doctorate, which he took in 1920 with Cassius Keyser . Even before obtaining his intermediate diploma, he wrote an original work on differential operators with non-integer degrees, which was not published until 1930.

In his dissertation Introduction to a general theory of elementary propositions he proved the completeness and consistency of the propositional logic calculus of the Principia Mathematica by introducing truth tables. He was able to generalize these also for multi-valued logics. In addition, he established the view of logic as a method of generating words with a finite number of derivation rules in a finite alphabet. After earning his doctorate in Princeton , he was a Proctor Fellow and then went to Columbia University.

Already in 1921 he came very close to the discovery of the incompleteness theorems later proved by Kurt Gödel , but did not publish anything about it, as his own work on this topic did not seem mature enough to him.

In 1924 he moved to Cornell University. During this time his mental illness began to hamper his further mathematical career. From 1927 he was a high school math teacher. In 1932 he went to the City College of New York and became a university professor again. However, due to a mental illness, he had to give up his job and did not return to the university until 1936, where he stayed until his death.

In the same year he developed an automaton model in the computability theory , which is just as powerful as the Turing machine developed at the same time . In 1947 he showed that the word problem is recursively unsolvable in semigroups ( Post's correspondence problem ). In doing so he was the first to prove (like Andrei Andrejewitsch Markow junior ) that a problem in classical mathematics could not be decided. He is one of the founders of the theory of recursive functions .

Like Kurt Gödel, Post suffered from manic-depressive attacks, which first occurred during his time at Princeton. He was therefore several times in mental hospitals, where he was treated with electroconvulsive therapy , as was customary at the time . Shortly after such treatment, he died of a heart attack.

He had been married to Gertrude Singer since 1929 and had a daughter Phyllis with her.

Martin Davis is one of his students .

Multi-valued propositional logic work

Emil Leon Post already considered systems of multi-valued propositional logic in his dissertation and afterwards independently of Jan Łukasiewicz and at about the same time. Post developed these systems in the context of investigating classical propositional logic , in particular its functional completeness. Post introduces arbitrary finite-value systems and discusses the case that besides the value 1, further quasi-truth values can be distinguished. He uses the so-called post-negation as a negation and the Łukasiewicz-Tarski alternative as an alternative . In Post there is an implication that is a coupling of the Łukasiewicz-Tarski implication and the Gödel implication and is called post-implication .

Fonts

  • The generalized Gamma Functions , Annals of Mathematics, Volume 20, 1919, pp. 202-217
  • Introduction to a General Theory of Elementary Propositions In: American Journal of Mathematics. Volume 43, 1921, pp. 163-185. pdf
  • On a simple case of deductive systems , Bulletin American Mathematical Society, Volume 27, 1921, pp. 396-397
  • Generalized Differentiation, Transactions of the American Mathematical Society, Volume 32, 1930, pp. 723-781
  • Finite Combinatory Processes - Formulation 1 , Journal of Symbolic Logic, Volume 1, 1936, pp. 103-105 (reprinted in Davis, The undecidable, Raven Press 1965 288-291)
  • Polyadic groups , Transactions of the American Mathematical Society, Volume 48, 1940, pp. 208-350.
  • Formal Reductions of the General Combinatorial Decision Problem , American Journal of Mathematics, Volume 65, 1943, pp. 197-215.
  • Recursively enumerable sets of positive integers and their decision problems , Bulletin of the American Mathematical Society, Volume 50, 1944, pp. 284-316, Online (reprinted in Davis, The undecidable 1965, 304-337)
  • The Two-Valued Iterative Systems Of Mathematical Logic , Princeton University Press, Annals of Mathematical Studies, 1941; ISBN 0-691-09570-1
  • Absolutely unsolvable problems and relatively undecidable propositions. Account of an anticipation , 1941, unpublished, reprinted in Martin Davis, The undecidable, 1965, pp. 338-433
  • Formal reductions of the general combinatorial decision problem , American Journal of Mathematics, Volume 65, 1943, pp. 197-215
  • A variant of a recursively unsolvable problem , Bull. Amer. Math. Soc., Vol. 52, 1946, pp. 264-268, online
  • Note on a Conjecture of Skolem, in Journal of Symbolic Logic, Volume 11, 1946, pp. 73-74
  • Recursive unsolvability and a problem of Thue , Journal of Symbolic Logic, Volume 12, 1947, 1-11 (reprinted in Davis, The undecidable 1965, 292-303)
  • with Stephen C. Kleene : The Upper Semi-Lattice of Degrees of Recursive Unsolvability, Annals of Mathematics, 2nd ser., Volume 59, 1954, pp. 379-407

literature

  • Martin Davis (Ed.): The Undecidable ; Pp. 288-406. Dover. ISBN 0-486-43228-9 . (Reprints of some of Post's works)
  • Martin Davis (Ed.); Solvability, Provability, Definability: The Collected Works of Emil L. Post ; Birkhäuser 1994 (with biography of Davis)
  • Jean van Heijenoort ; From Frege to Gödel- Sourcebook of Mathematical Logic , 1967 (contains Post's dissertation, published 1921, Introduction to the general theory of elementary propositions )
  • Ivor Grattan-Guinness : The manuscripts of Emil L Post, Hist. Philos. Logic, Vol. 11, No. 1, 1990, pp. 77-83.
  • Hubert C. Kennedy : Post, Emil Leon . In: Charles Coulston Gillispie (Ed.): Dictionary of Scientific Biography . tape 11 : A. Pitcairn - B. Rush . Charles Scribner's Sons, New York 1975, p. 106-108 .

Web links

Individual evidence

  1. ↑ References to this can be found in his mathematical diary, which he kept from 1916. An essay submitted by him in 1941, which, according to its editor Martin Davis, was to show that he anticipated the later ideas of Church, Turing and Gödel in the 1920s and 1930s or worked on similar developments, was rejected and not until 1965 by Martin Davis released. However, he recognized Gödel's priority and achievement without reservation.
  2. ^ Post, Finite Combinatory Processes - Formulation 1, Journal of Symbolic Logic, Volume 1, 1936, pp. 103-105
  3. ↑ Post, Recursive unsolvability and a problem of Thue , Journal of Symbolic Logic, Volume 12, 1947, 1-11
  4. ↑ Post, Recursively enumerable sets of positive integers and Their decision problems , Bulletin of the American Mathematical Society, Volume 50, 1944, pp 284-316
  5. ^ Submitted for publication by Post 1941 to a mathematical journal, but rejected
personal data
SURNAME Post, Emil Leon
BRIEF DESCRIPTION Polish-American mathematician and logician
DATE OF BIRTH February 11, 1897
PLACE OF BIRTH Augustów , Congress Poland , Russian Empire
DATE OF DEATH April 21, 1954
Place of death New York City , USA