L'école constructive de Markov

Margenstern, Maurice

Revue d'histoire des mathématiques, Tome 1 (1995) no. 2, pp. 271-305.

Cet article donne les principales caractéristiques de l'école constructive d'Andrej Andreevich Markov (1903-1979). Après un bref rappel de la situation des mathématiques et de la logique au début du xxe siècle, on évoque rapidement la naissance de l'intuitionnisme et de la théorie des fonctions récursives. On décrit ensuite les objets et les méthodes du constructivisme de Markov. A titre d'exemples on expose les principaux résultats relatifs à l'analyse réelle selon le point de vue de Markov. On termine en soulignant l'intérêt de ces résultats pour les mathématiques d'aujourd'hui.

This paper sets out the main features of the constructivist school, as promoted by Andrej Andreevich Markov (1903-1979). After a short survey of the situation pertaining in mathematics and logic, at the beginning of the 20th century, the emergence of intuitionism, and of recursive function theory, is sketched in. The paper then outlines the aims and methods of Markov's constructivism - reviewing, by way of illustration, the major results obtained through Markov's approach, in the field of real-number analysis. Finally, emphasis is laid on the current relevance of such results for present-day mathematics.

[1] Bernays (P.), Hilbert (D.) [1934] Grundlagen der Mathematik, vol. 1, Berlin : Springer, 1934 ; 2e éd., 1968. | MR | Zbl

[2] Bishop (E.) [1967] Foundations of constructive analysis, New York : McGraw-Hill, 1967. | MR | Zbl

[3] Bridges (D.), Demuth (O.) [1991] On the Lebesgue measurability of continuous functions in constructive analysis, Bulletin of the American Mathematical Society, 24 (1991), p. 259-276. | MR | Zbl

[4] Cejtin (G.S.) [1962a] Algorifmicheskie operatory v konstruktivnykh metricheskikh prostranstvakh, Trudy matematicheskogo Instituta Steklova, 67 (1962), p. 295-361. Trad. angl., Algorithmic operators in constructive metric spaces, American Mathematical Society Translations, (2) 64 (1967), p. 1-80.

[5] Cejtin (G.S.) [1962b] Teoremy o srednem znachenii v konstructivnom analize, Trudy mat. Inst. Steklova, 67 (1962), p. 362-384. Trad. angl., Mean value theorems in constructive analysis, Amer. Math. Soc. Transl., (2) 98 (1971), p. 11-40.

[6] Cejtin (G.S.) [1964] Tri teoremy o konstructivnykh funkcijakh, Trudy mat. Inst. Steklova, 72 (1964), p. 537-543. Trad. angl., Three theorems on constructive functions, Amer. Math. Soc. Transl., (2) 100 (1972), p. 11-40. | MR

[7] Cejtin (G.S.), Zaslavskij (I.D.) [1962] O singuljarnykh i svjazannykh s nimi svojstvakh konstruktivnykh funkcij, Trudy mat. Inst. Steklova, 67 (1962), p. 458-502. Trad. angl., On singular coverings and related properties of constructive functions, Amer. Math. Soc. Transl., (2) 98 (1971), p. 41-89. | MR | Zbl

[8] Demuth (O.) [1968] Integral Lebega i ponjatie izmerimosti funkcij v konstruktivnom analize, Zapiski nauchrykh seminarov Leningradskogo otdelenija matematicheskogo Instituta Steklova, 8 (1968), p. 21-28. Trad. angl., The Lebesgue integral and the concept of function measurability in constructive analysis, Seminars in Mathematics Steklov Institute, 8 (1970), p. 7-10. | MR | Zbl

[9] Detlovs (V.K.) [1958] Ekvivalentnost' normal'nykh algorifmov i rekursivnykh funkcij, Trudy mat. Inst. Steklova, 52 (1958), p. 75-139. Trad. angl., The equivalence of normal algorithms and recursive functions, Amer. Math. Soc. Transl., (2) 23 (1963), p. 15-81. | MR | Zbl

[10] Duprat (J.), Herreros (Y.), Muller (J.-M.) [1989] Some results about on-line computation of functions, Rapport de Recherche L.I.P., École normale supérieure de Lyon, 89-04, 1989.

[11] Glivenko (V.I.) [1928] Sur la logique de M. Brouwer, Bulletin de l'Académie royale de Belgique. Classe des sciences, (V) 14 (1928), p. 225-228. | JFM

[12] Glivenko (V.I.) [1929] Sur quelques points de la logique de M. Brouwer, Bull. Acad. r. Belg. Cl. sci., (V) 15 (1929), p. 183-188. | JFM

[13] Goodstein (R.L.) [1961] Recursive analysis, Amsterdam : North-Holland, 1961. | MR | Zbl

[14] Grzegorczyk (A.) [1957] On the definitions of computable real continuous functions, Fundamenta mathematicae, 44 (1957), p. 61-71. | MR | Zbl

[15] Heyting (A.) [1956] Intuitionism. An introduction, Amsterdam : North-Holland, 1956 ; 3e éd., 1971. Trad. russe, Moscou : Mir, 1965. | MR | Zbl

[16] Heyting (A.) [1959] (éd.) Constructivity in mathematics. Proceedings of the colloquium held at Amsterdam, 1957, Amsterdam : North-Holland, 1959. | MR | Zbl

[17] Kalmár (L.) [1959] An argument against the plausibility of Church's thesis, dans [Heyting 1959, p. 72-80]. | MR | Zbl

[18] Kleene (S.C.) [1936a] General recursive functions of natural numbers, Matematische Annalen, 112 (1936), p. 727-742. | JFM | MR | Zbl

[19] Kleene (S.C.) [1936b] A note on recursive functions, Bull. Amer. Math. Soc., 42 (1936), p. 544-546. | JFM | MR

[20] Kleene (S.C.) [1987] Reflections on Church's thesis, Notre Dame Journal of Formal Logic, 28 (1987), p. 490-498. | MR | Zbl

[21] Kolmogorov (A.N.) [1925] O principe “tertium non datur », Matematicheskij sbornik, 32 (1925), p. 646-667. Trad. angl., On the principle of exclude middle, dans [van Heijenoort 1967, p. 414-437]. | JFM

[22] Kreisel (G.), Lacombe (D.), Schoenfield (J.R.) [1957] Fonctionnelles récursivement définissables et fonctionnelles récursives, Comptes rendus hebdomadaires des séances de l'Académie des sciences, 245 (1957), p. 399-402. | MR | Zbl

[23] Kreisel (G.), Lacombe (D.), Schoenfield (J.R.) [1959] Partial recursive functionals and effective operations, dans [Heyting 1959, p. 290-297]. | MR | Zbl

[24] Kronecker (L.) [1887] Über den Zahlbegriff, Journal für die reine und angewandte Mathematik, 101 (1887), p. 337-355 ; Werke III${}^1$, Leipzig, 1899, p. 251-274. | JFM

[25] Kushner (B.A.) [1973] Lekcii po konstruktivnomu matematicheskomu analizu, Moskva : Nauka, 1973. Trad. angl., Lectures on constructive mathematical analysis, Providence : American Mathematical Society (Translations of Mathematical Monographs, vol. 60), 1984. | MR | Zbl

[26] Kushner (B.A.) [1993] Markov and Bishop : an essay in memory of A.A. Markov (1903-1979) and E. Bishop (1928-1983), dans Zdravkovska (S.) et Duren (P.L.), éd., Golden years of Moscow mathematics, American Mathematical Society-London Mathematical Society (History of Mathematics, vol. 6), 1993, p. 179-197. | MR

[27] Lacombe (D.) [1957] Quelques propriétés d'analyse récursive, C.R. Acad. sci. Paris, 244 (1957), p. 838-840/996-997. | MR | Zbl

[28] Largeault (J.) [1992] Intuitionisme et théorie de la démonstration. Textes de Bernays, Brouwer, Gentzen, Gödel, Hilbert, Kreisel, Weyl, Paris : Vrin (Mathesis), 1992. | MR | Zbl

[29] Markov (A.A.) [1954a] Teorija algorifmov, Trudy mat. Inst. Steklova, 42 (1954). Trad. angl., The theory of algorithms, The Israel Program for Scientific Translations, 1961. | MR

[30] Markov (A.A.) [1954b] O nepreryvnosti konstruktivnykh funkcij, Uspekhi matematicheskikh nauk, (IX) 3-61 (1954), p. 226-230.

[31] Markov (A.A.) [1956] Ob odnom principe konstruktivnoj matematicheskoj logiki, Trudy tret'ego vsesojuznogo matematicheskogo s« ezda, 2 (1956), p. 146-147.

[32] Markov (A.A.) [1965] Commentaires de l'éditeur, dans [Heyting 1956/1965].

[33] Markov (A.A.), Nagornyj (N.M.) [1984] Teorija algorifmov, Moskva : Nauka, 1984. Trad. angl., The theory of algorithms, Dordrecht : Kluwer, 1988. | MR

[34] Mostowski (A.) [1957] On computable sequences, Fund. math., 44 (1957), p. 37-51. | MR | Zbl

[35] Muller (J.-M.) [1991] Some characterizations of functions in on-line arithmetic, Rapport de Recherche L.I.P., École normale supérieure de Lyon, 91-15, 1991.

[36] Orevkov (V.P.) [1964] O konstruktivnykh otobrazhenijakh kruga v sebja, Trudy mat. Inst. Steklova, 72 (1964), p. 437-461. Trad. angl., On constructive mappings of a disk into itself, Amer. Math. Soc. Transl., (2) 100 (1972), p. 69-100. | MR | Zbl

[37] Shanin (N.A.) [1962] Konstruktivnye veshchestvennye chisla i konstruktivnye funkcional'nye prostranstva, Trudy mat. Inst. Steklova, 67 (1962), p. 15-294. Trad. angl., Constructive real numbers and constructive function spaces, Providence : American Mathematical Society (Transl. Math. Monographs, vol. 21), 1968. | MR

[38] Sinaceur (H.) [1990] Article « Récursivité », dans Encyclopédie philosophique universelle, vol. II, t. 2, Paris : PUF, 1990, p. 2188-2192.

[39] Sinaceur (H.) [1993] Du formalisme à la constructivité : le finitisme, Revue internationale de philosophie, 47-4 (1993), p. 251-284.

[40] Specker (E.) [1949] Nicht konstruktiv beweisbare Sätze der Analysis, The Journal of Symbolic Logic, 14 (1949), p. 145-158. | MR | Zbl

[41] Specker (E.) [1959] Der Satz vom Maximum in der rekursiven Analysis, dans [Heyting 1959, p. 254-265]. | MR | Zbl

[42] Turing (A.M.) [1936] On computable real numbers, with an application to the “Entscheidungsproblem”, Proceedings of the London Mathematical Society, 42 (1936), p. 230-265. Trad. fr. dans La machine de Turing, Paris : Seuil (Sources du savoir), 1995, p. 47-103. | JFM | Zbl

[43] Uspenskij (V.A.) [1960] Lekcii o vychislitmykh funkcijakh, Moscou : Fizmatgiz, 1960. Trad. fr. par A. Chauvin, Leçons sur les fonctions calculables, Paris : Hermann, 1966. | MR

[44] Van Dalen (D.) [1990] The war of the frogs and the mice, or the crisis of the “Mathematische Annalen”, The Mathematical Intelligencer, 12-4 (1990), p. 17-31. | MR | Zbl

[45] Van Heijenoort (J.) (éd.) [1967] From Frege to Gödel. A source book in mathematical logic, 1879-1931, Cambridge (Mass.) : Harvard University Press, 1967. | MR | Zbl

[46] Zaslavskij (I.D.) [1962] Nekotorye svojstva konstruktivnykh veshchestvennykh chisel i konstruktivnykh funkcij, Trudy mat. Inst. Steklova, 67 (1962), p. 385-457. Trad. angl., Some properties of constructive real numbers and of constructive functions, Amer. Math. Soc. Transl., (2) 57 (1966), p. 1-84. | Zbl