Emil Leon Post

Emil Leon Post

Emil L. Post (född skrevs den februari 11, 1897 i Augustów , kongressen Polen ; † skrevs den april 21, 1954 i New York , USA ) var en polsk - amerikansk matematiker och logiker .

liv och arbete

Post kommer från en polsk-judisk familj som emigrerade från det som då var en del av Ryssland till USA 1904 när han fortfarande var barn. Han studerade vid City College i New York (kandidatexamen 1917) och vid Columbia University (magisterexamen 1918) fram till sin doktorsexamen, som han tog 1920 med Cassius Keyser . Redan innan han fick sitt mellanliggande examen skrev han ett originalverk om differentiella operatörer med icke-heltal grader, som inte publicerades förrän 1930.

I sin avhandling Introduktion till en allmän teori om elementära propositioner bevisade han fullständigheten och konsistensen av den propositionella logiska kalkylen i Principia Mathematica genom att införa sanningstabeller. Han kunde också generalisera dessa för flervärdeslogik. Dessutom etablerade han synen på logik som en metod för att generera ord med ett begränsat antal avledningsregler i ett ändligt alfabet. Efter att ha tagit sin doktorsexamen i Princeton var han Proctor Fellow och gick sedan till Columbia University.

Redan 1921 kom han mycket nära upptäckten av de ofullständiga satser som senare bevisades av Kurt Gödel , men publicerade ingenting om dem, eftersom hans eget arbete om detta ämne inte tycktes vara mogen för honom.

År 1924 flyttade han till Cornell University. Under denna tid började hans psykiska sjukdom hämma hans ytterligare matematiska karriär. Från 1927 var han matematiklärare på gymnasiet. År 1932 gick han till City College i New York och var därmed återigen universitetsprofessor. Men han var tvungen att ge upp sitt jobb på grund av en psykisk sjukdom och återvände inte till universitetet förrän 1936, där han stannade fram till sin död.

Samma år utvecklade han en automatmodell i beräkbarhetsteorin , som är lika kraftfull som Turing-maskinen utvecklades samtidigt . 1947 visade han att ordet problem i semigrupper är rekursivt olösligt ( Posts korrespondensproblem ). Genom att göra detta var han den första som bevisade (som Andrei Andrejewitsch Markow junior ) obeslutbarheten av ett problem inom klassisk matematik. Han är en av grundarna av teorin om rekursiva funktioner .

Liksom Kurt Gödel led Post av manisk-depressiva attacker, som först inträffade under hans tid i Princeton. Han var därför flera gånger på mentalsjukhus, där han behandlades med elektrokonvulsiv terapi , vilket var vanligt vid den tiden . Strax efter en sådan behandling dog han av en hjärtinfarkt.

Han hade varit gift med Gertrude Singer sedan 1929 och hade en dotter, Phyllis, med sig.

Martin Davis är en av hans elever .

Flervärdet förslagslogikarbete

Emil Leon Post betraktade redan system av mångsidigt propositionell logik i sin avhandling och därefter oberoende av Jan Łukasiewicz och ungefär samtidigt. Post utvecklade dessa system i samband med att undersöka klassisk propositionellogik , särskilt dess funktionella fullständighet. Post introducerar godtyckliga ändvärderade system och diskuterar fallet att, förutom värdet 1, kan ytterligare kvasi-sanningsvärden särskiljas. Han använder den så kallade post-negationen som en negation och alternativet Łukasiewicz-Tarski som ett alternativ . Det finns en implikation i Post som är en koppling av Łukasiewicz-Tarski-implikationen och Gödel-implikationen och kallas postimplikation .

Typsnitt

• De generaliserade gammafunktionerna. I: Matematikens annaler . Serie 2, Vol. 20, nr 3, 1919, s. 202-217, JSTOR 1967871 .
• Introduktion till en allmän teori om elementära propositioner. I: American Journal of Mathematics . Vol. 43, nr 3, 1921, s. 163-185, JSTOR 2370324 .
• På en enkel klass av deduktiva system. I: Bulletin of the American Mathematical Society . Volym 27, nr 9/10, 1921, s. 396-397, doi : 10.1090 / S0002-9904-1921-03453-7 .
• Generaliserad differentiering. I: Transaktioner från American Mathematical Society . Volym 32, nr 4, 1930, sid 723-781, JSTOR 1989348 .
• Slutliga kombinationsprocesser - formulering 1. I: Journal of Symbolic Logic . Volym 1, nr 3, 1936, s. 103-105, JSTOR 2269031 , (omtryckt i Davis: The Undecidable. 1965, s. 288-291).
• Polyadiska grupper. I: Transaktioner från American Mathematical Society. Volym 48, nr 2, 1940, s. 208-350, JSTOR 1990085 .
• Helt olösliga problem och relativt obeslutbara förslag. Redogörelse för en förväntan. 1941, (opublicerat, omtryckt i Davis: The Undecidable. 1965, s. 338-433).
• De tvåvärderade iterativa systemen för matematisk logik (= Annaler för matematikstudier. 5, ISSN  0066-2313 ). Princeton University Press, Princeton, NJ 1941.
• Formella minskningar av det allmänna kombinationsbeslutsproblemet. I: American Journal of Mathematics. Vol. 65, nr 2, 1943, sid. 197-215, JSTOR 2371809 .
• Rekursivt uppräkbara uppsättningar av positiva heltal och deras beslutsproblem. I: Bulletin of the American Mathematical Society. Volym 50, nr 5, 1944, s. 284-316, doi : 10.1090 / S0002-9904-1944-08111-1 , (omtryckt i Davis: The Undecidable. 1965, s. 304-337).
• En variant av ett rekursivt olösligt problem. I: Bulletin of the American Mathematical Society. Volym 52, nr 4, 1946, s. 264-268, doi : 10.1090 / S0002-9904-1946-08555-9 .
• Anmärkning om en gissning av Skolem. I: Journal of Symbolic Logic. Volym 11, nr 3, 1946, s 73-74, JSTOR 2266735 .
• Rekursiv olösbarhet och ett problem med Thue. I: Journal of Symbolic Logic. Vol. 12, nr 1, 1947, s. 1-11, JSTOR 2267170 , (omtryckt i Davis: The Undecidable. 1965, s. 292-303).
• med Stephen C. Kleene : The Upper Semi-Lattice of Degrees of Recursive Unsolvability. I: Matematikens annaler. Serie 2, Vol. 59, nr 3, 1954, s. 379-407, JSTOR 1969708 .

litteratur

• Martin Davis (red.): The Undecidable. Grundläggande dokument om obeslutbara förslag, olösliga problem och beräkningsbara funktioner. Raven Press, Hewlett NY 1965, s. 288-406, (återtryck av en del av Posts arbete).
• Martin Davis (red.): Löslighet, tillgänglighet, definierbarhet. Emil L. Posts samlade verk. Birkhäuser, Boston MA et al. 1994, ISBN 0-8176-3579-3 (med en biografi om Davis).
• Ivor Grattan-Guinness : Emil L. Posts manuskript. I: Historia och logikfilosofi. Volym 11, nr 1, 1990, sid 77-83, doi : 10.1080 / 01445349008837159 .
• Jean van Heijenoort : Från Frege till Gödel. En källbok om matematisk logik, 1879-1931. Harvard Univ. Press, Cambridge MA et al. 1967, (innehåller Posts avhandling, publicerad 1921, Introduction to the general theory of elementary propositions. ).
• Hubert C. Kennedy : Post, Emil Leon . I: Charles Coulston Gillispie (red.): Dictionary of Scientific Biography . tejp 11 : A. Pitcairn - B. Rush . Charles Scribner's Sons, New York 1975, s. 106-108 . 

webb-länkar

• John J. O'Connor, Edmund F. Robertson :  Emil Leon Post. I: MacTutor History of Mathematics arkiv .

Individuella bevis

1. ↑ Hänvisningar till detta finns i hans matematiska dagbok, som han förde från 1916. En uppsats som skickades in av honom 1941, som enligt dess redaktör Martin Davis skulle visa att han förutsåg de senare idéerna från Church, Turing och Gödel på 1920- och 1930-talet eller arbetade med liknande utveckling, avvisades och först 1965 av Martin Davis släpptes. Men han erkände Gödels prioritet och prestation utan förbehåll.
2. ^ Inlägg: Finita kombinationsprocesser - formulering 1. I: Journal of Symbolic Logic. Volym 1, nr 3, 1936, s 103-105.
3. ↑ Inlägg: Rekursiv olösbarhet och ett problem med Thue. I: Journal of Symbolic Logic. Vol. 12, nr 1, 1947, s. 1-11.
4. ↑ Inlägg: Rekursivt oräkneliga uppsättningar av positiva heltal och deras beslutsproblem. I: Bulletin of the American Mathematical Society. Volym 50, nr 5, 1944, s. 284-316.
5. ↑ Inlämnad för publicering av Post 1941 till en matematisk tidskrift men avvisad.