Kurt Gödel and the constructive Mathematics of A.A. Markov

doi:10.1017/9781316716939.005

Kurt Gödel and the constructive Mathematics of A.A. Markov

from Part I - Invited Papers

Published online by Cambridge University Press: 23 March 2017

Boris A. Kushner

Edited by

Petr Hájek

Show author details

Boris A. Kushner: Affiliation:
University of pittsburgh
Petr Hájek: Affiliation:
Academy of Sciences of the Czech Republic, Prague

Book contents

Get access

Summary

I would like to dedicate this article to the memory of Dr. Oswald Demuth (12.9.1936 - 15.9.1988). Oswald was an excellent Mathematician and a dear friend of mine. 1miss him so badly.

The Russian School of constructive Mathematics was founded by A.A. Markov, Jr. (1903-1979) in the late 40-ies - early 50-ies. In private conversations Markov used to state that he nurtured a type of constructive convictions for a very long time, long before the Second World War. This is an interesting fact if one considers that this was the time when Markov worked very actively in various areas of classical Mathematics and achieved first-rate results. Perhaps it is worth mentioning that Markov was a scientist with a very wide area of interest. In his freshman years he published works in Chemistry and he graduated from Leningrad University (1924) with a major in Physics. Besides Mathematics, he published works in theoretical Physics, Celestial Mechanics, Theory of Plasticity (cf., e.g., Markov and Nagorny (1988: introduction by Nagorny]; this monograph (originally in Russian, 1984) was completed and published by N.M. Nagorny after Markov's death). It is almost inevitable that a scientist of such universality arrives to philosophical and foundational issues. I believe that the explicitly “constructive” period of Markov's activities began with his work on Thue's Problem which had stood open since 1914. Thue's Problem was solved independently by A.A. Markov (Jr.) and E. Post in 1947. Markov began to develop his concept of so called normal algorithms as a tool to present his results on Thue Problem. Markov's publications on normal algorithms appeared as early as 1951 (Markov [1960; an English translation]). In 1954 Markov published his famous monograph Theory of Algorithms (Markov (1961; an English Translation]). This monograph can be considered as probably the first systematic presentation of the general theory of algorithms together with related semiotical problems. In this monograph, in particular, one can find a mathematical theory of words as special types of sign complexes. As far as I know, such a theory was developed here for the first time.

Type: Chapter
Information: Gödel '96
Logical Foundations of Mathematics, Computer Science and Physics - Kurt Gödel's Legacy
, pp. 50 - 63

DOI: https://doi.org/10.1017/9781316716939.005 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2017

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Beeson, M. J.. Foundations of Constructive Mathematics. Springer, Berlin, 1985.

Bishop, E.. Foundations of Constructive Analysis. MvGraw-Hill, New York, 1967.

Bishop, E.. Mathematics as a numerical language. Intuitionism and Proof Theory (Proc.Conf, Buffalo, N.Y.), North-Holland, Amsterdam, 53–71, 1970.

Bishop, E.. Schizophrenia in Contemporary Mathematics. Erret Bishop: Reflections on Him and His Research (San Diego California, 1983) (Rosenblatt, M., Editor), AMS, Contemp. Math., vol.36, Providence, Rhode Island, 1984, 1–32.

Bishop, E. and Bridges, D.. Constructive Analysis. Springer-Verlag, Berlin-heidelberg-New York-Tokyo, 1985.

Brouwer, L. E. I.. Bezitzt jede reelle Zahl eine Dezimalbruchentwicklung? Nederl. Akad. Wetensch. Vershlagen, 29, 803–812. Also in Math. Ann 83,201–210, 1921, 1921.Google Scholar

Chernov, V. P.. Topologicheskie varianty teoremy o nepreryvnosti otobrazheniy I rodstvennye teoremy. Russian, Zapiski Nauchnykh Seminarov LOMI, 32, 1972a, 129–139.Google Scholar

Chernov, V. P.. O konstruktivnykh operatorakh konechnykh tipov. Russian, Zapiski Nauchnykh Seminarov LOMI, 32, 1972b, 140–147.Google Scholar

Chernov, V. P.. Klassifikaciya prostranstv operatorov konechnykh tipov. Russian, Zapiski Nauchnykh Seminarov LOMI, 32, 1972c, 148–152.Google Scholar

van Dalen, D.. Why Constructive Mathematics? The Foundational Debate. Complexity and Constructivity in Mathematics and Physics, Depauli-Schimanovich, W. et al, Eds. Vienna Circle Yearbook, Kluwer, Dordrecht, 141–158, 1995.

Davis, M.. Why Gödel Didn't Have Church's Thesis. Information and Control, 54, 3–24, 1982.Google Scholar

Demuth, O.. Lebesque integration in constructive analysis Russian, Dokl. Akad. Nauk SSSR (Engl. transl. in Soviet Math. Dokl. 6 (1965), 160, 1965, 1239–1241.Google Scholar

Demuth, O.. Nekotorye voprosy teorii konstruktivnykh funktsiy deystvitel'noy peremennoy. Russian, Acta Universitatis Carolinae, Math, et Phys., 19, No 1, 61–69, 1978.Google Scholar

Demuth, O.. O konstruktivnom integrate Perrona. Russian, Acta Universitatis Carolinae, Math, et Phys., 21, No 1, 3–57, 1980.Google Scholar

Dragalin, A. G.. Mathematical Intuitionism: Introduction to proof theory. AMS (Translation from the Russian; Russian original 1979), Providence, Rhode Island, 1988.

Feferman, S.. Kurt Gödel:Conviction and Caution. Philosophia Naturalis, 21 (2–4), 546–562, 1984.Google Scholar

Feferman, S.. Gödel's Dialectica interpretation and its two-way stretch. Computational Logic and Proof Theory, Proc. of the Third Kurt Gödel Colloquium, Gottlob, G. et al, Eds, Lecture Notes in Computer Science, 713, 1993, 23–40.

Gödel, . The consistency of the Continuum Hypothesis. Princeton University Press, Princeton, New Jersey, 1940.

Gödel, . Über eine bisher noch nicht benütze Erweiterung des finititen Standpunktes. Dialectica, 12, 240–251, 1958.Google Scholar

Heyting, A.. Intuitionism. An Introduction. North-Holland, Amsterdam, 1956.

Heyting, A.. After thirty years. Logic, Methodology and Philosophy of Science, Proceedings of the 1960 International Congress, Nagel, E. et al, Eds, Stanford University Press, Stanford, California, 194–197, 1962.

Hilbert, D. and Bernays, P.. The Grundlagen der Mathematik, 1. Springer-Verlag, Berlin-Heidelberg-New York, 1968.

Kleene, S. C. and Vesley, R. E.. The Foundations of Intuitionistic Mathematics. Especially in Relation to Recursive functions. North-Holland, Amsterdam, 1965.

Kolmogorov, A. N. and Uspensky, V. A.. Kopredeleniyu algoritma. Russian, Uspekhi Mathematicheskikh Nauk, 13, vol. 4(82), 3–28, 1958.Google Scholar

Kushner, B. A.. Some extensions of Markov's constructive continuum and their applications to the theory of constructive functions. The L.E.J. Brouwer Centenary Symposium, Troelstra, A. S. and van Dalen, D., Eds, North-Holland Publishing Company, Amsterdam-New York-Oxford, 1982, 261–273.

Kushner, B. A.. Lectures on Constructive Mathematical Analysis. (Translation from the Russian; Russian original 1973), AMS, Providence, Rhode Island, 1984.

Kushner, B. A.. Printsip bar-induktsii i teoriya kontinuuma u Brauera. Russian, Zakonomemosti razvitiya sovremennoy matematiki, Nauka, Moscow, 1987, 230–250.

Kushner, B. A.. Ob odnom predstavlenii Bar-Induktsii. Russian, Voprosy Matematicheskoy Logiki i Teorii Algoritmov, Vychislitel'ny Tsentr AN SSSR, Moscow, 1988, 11–18.

Kushner, B. A.. Markov's Constructive Mathematical Analysis: the Expectations and Results. Mathematical Logic, Petkov, P., Ed., 53–58, 1990, Plenum Press, New York-London.

Kushner, B. A.. A Version of Bar-Induction. Abstract, 1992, 57, No 1 The Journal of Symbolic Logic. Google Scholar

Kushner, B. A.. Markov i Bishop. Russian, Voprosy Istorii Estestvoznaniya i Tekhniki, 1, 1992, 70–81.Google Scholar

Kushner, B. A.. Markov and Bishop. Golden Years of Moscow Mathematics, Zdravkovska, S., Duren, P., Eds, 179–197, 1993a, AMS-LMS, Providence, Rhode Island.

Kushner, B. A.. Konstruktivnaya matematika A.A. Markova: nekotorye razmyshleniya. Russian, Modern Logic, 3, No 2, 119–144, 1993b.Google Scholar

Manukyan, S. N.. O nekotorykh topologicheskikh osobennostyakh konstruktivnykh prostykh dug. Russian, Issledovaniya po teorii algorifmov i matematicheskoy logike, Kushner, B. A. and Markov, A. A., Eds, Vychislitel'ny Tsentr AN SSSR, Moscow, 1976, 122–129.

Markov, A. A.. O zavisimosti aksiomy B6 ot drugikh aksiom sistemy Bernaysa-Gedelya. Russian, Izvestiya Akademii Nauk SSSR, ser. matem., 12, 1948, 569–570.Google Scholar

Markov, A. A.. The theory of algorithms. Amer. Math. Soc. Transl., (2) 15, 1960, AMS (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951), 176–189), Providence, Rhode Island.Google Scholar

Markov, A. A.. The theory of algorithms. Israel Programm Sci. Transl. (Translation from the Russian, Trudy Instituta im. Steklova 42 (1954)), Jerusalem, 1961.Google Scholar

Markov, A. A.. On constructive mathematics. Amer.Math.Soc. Transl., (2) 98, 1971, AMS (Translation from the Russian, Trudy Instituta im. Steklova, 67, 8–14, (1964)), Providence, Rhode Island.Google Scholar

Markov, A. A.. Comments of the Editor of the Russian translation of Heyting's book Intuitionism. Russian, Geyting, A., Intuitsionizm. Russian, Moskva, Mir, 1965, 161–193.

Markov, A. A.. Essai de construction d'une logique de la mathematique constructive. Revue intern, de Philosophic, 1971, 98, Fasc.4.Google Scholar

Markov, A. A.. Popytka postroeniya logiki konstruktivnoy matematiki. Russian, Issledovaniya po teorii algorifmov i matematicheskoy logike, Kushner, B. A. and Markov, A. A., Eds, Vychislitel'ny Tsentr AN SSSR, Moscow, 1976, 3–31, A Russian version of Markov 1971.

Markov, A. A. and Nagorny, N. M. The Theory of Algorithms. Kluwer Academic Publishers (Translation from the Russian; Russian original 1984), Dordrecht-Boston-London, 1988.

Mendelson, E.. Second thought about Church's thesis and mathematical proofs. The Journal of Philosophy, 87, 225–233, 1990.Google Scholar

Nagorny, N. M.. K voprosu o neprotivorechivosti klassicheskoy formal'noy arifmetiki. Russian, Computing Center RAN, Moscow, 1995.

Rogers, H. Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill Book Company, New York, 1967.

Specker, E.. Nicht konstruktiv beweisbare Sätze der Analysis. The Journal of Symbolic Logic, 14, 145–158, 1949.Google Scholar

Troelstra, A. S.. On the early history of intuitionistic logic. Mathematical Logic, Petkov, P. P., Ed., Plenum Press, New York-London, 1990, 3–17.

Troelstra, A. S.. Choice Sequences. A Chapter of Intuitionistic Mathematics. Clarendon Press, Oxford, 1977.

Troelstra, A. S. and van Dalen, D.. Constructivism in Mathematics. An Introduction. Vol. 1–2, North-Holland, Amsterdam-New York-Oxford-Tokyo, 1988.

Turing, A. M.. On computable numbers, with an application to the Entscheidungsproblem. 1936–37, 42 (2), Proc. London Math. Soc., 230–265.Google Scholar

Turing, A. M.. Correction. 1937, 43 (2), Proc. London Math. Soc., 544–546.

Book contents

Kurt Gödel and the constructive Mathematics of A.A. Markov

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive