Intuitionism and effective descriptive set theory. (English) Zbl 1437.03172
Summary: Our very eloquent charge from Jan van Mill was to “draw a line to Brouwer from descriptive set theory, but this proved elusive: in fact there are few references to Brouwer, in [N. Lusin, in: Atti Congresso Bologna 1, 295–299 (1929; JFM 55.0657.01); Leçons sur les ensembles analytiques et leurs applications. Paris: Gauthier-Villars (1930; JFM 56.0085.01)]], none of them substantial; and even though Brouwer refers to Borel, Lebesgue and Hadamard in his early papers, it does not appear that he was influenced by their work in any substantive way. We have not found any references by him to more developed work in descriptive set theory, after the critical H. Lebesgue [Journ. de Math. (6) 1, 139–216 (1905; JFM 36.0453.02)]. So instead of looking for historical connections or direct influences (in either direction), we decided to identify and analyze some basic themes, problems and results which are common to these two fields; and, as it turns out, the most significant connections are between intuitionistic analysis and effective descriptive set theory, hence the title.
\(\Rightarrow\) We will outline our approach and (limited) aims in Section 1, marking with an arrow (like this one) those paragraphs which point to specific parts of the article. Suffice it to say here that our main aim is to identify a few, basic results of descriptive set theory which can be formulated and justified using principles that are both intuitionistically and classically acceptable; that we will concentrate on the mathematics of the matter rather than on history or philosophy; and that we will use standard, classical terminology and notation.
This is an elementary, mostly expository paper, broadly aimed at students of logic and set theory who also know the basic facts about recursive functions but need not know a lot about either intuitionism or descriptive set theory. The only (possibly) new result is Theorem 6.1, which justifies simple definitions and proofs by induction in Kleene’s Basic System of intuitionistic analysis, and is then used in to give in the same system a rigorous definition of the Borel sets and prove that they are analytic; the formulation and proof of this last result is one example where methods from effective descriptive set theory are used in an essential way.
\(\Rightarrow\) We will outline our approach and (limited) aims in Section 1, marking with an arrow (like this one) those paragraphs which point to specific parts of the article. Suffice it to say here that our main aim is to identify a few, basic results of descriptive set theory which can be formulated and justified using principles that are both intuitionistically and classically acceptable; that we will concentrate on the mathematics of the matter rather than on history or philosophy; and that we will use standard, classical terminology and notation.
This is an elementary, mostly expository paper, broadly aimed at students of logic and set theory who also know the basic facts about recursive functions but need not know a lot about either intuitionism or descriptive set theory. The only (possibly) new result is Theorem 6.1, which justifies simple definitions and proofs by induction in Kleene’s Basic System of intuitionistic analysis, and is then used in to give in the same system a rigorous definition of the Borel sets and prove that they are analytic; the formulation and proof of this last result is one example where methods from effective descriptive set theory are used in an essential way.
References:
| [1] | Aczel, Peter, A constructive version of the Lusin Separation Theorem, (Lindström, S.; Palmgren, E.; Segerberg, K.; Stoltenberg, Logicism, Intuitionism and Formalism -What Has Become of Them?. Logicism, Intuitionism and Formalism -What Has Become of Them?, Synthese Library, vol. 341 (2009), Springer), 129-151 · Zbl 1171.03037 |
| [2] | Baire, René, Sur les fonctions de variables réelles, Ann. Mat. Pura Appl., 3, 1-122 (1899) · JFM 30.0359.01 |
| [3] | Borel, Emile, Lec̣ons sur la theéorie des fonctions (1898), Gauthier-Villars · JFM 29.0336.01 |
| [4] | Brouwer, L. E.J., Over de Grondslagen der Wiskunde (1907), Maas and van Suchtelen: Maas and van Suchtelen Amsterdam, Translated in [9] · JFM 38.0081.04 |
| [5] | L.E.J. Brouwer, The unreliability of the logical principles. English translation in [9]; L.E.J. Brouwer, The unreliability of the logical principles. English translation in [9] |
| [6] | L.E.J. Brouwer, Begründund der Mengenlehre unabhängig vom logische Satz vom Ausgeschlossen Dritten, p. 150 ff, in Brouwer [9]; L.E.J. Brouwer, Begründund der Mengenlehre unabhängig vom logische Satz vom Ausgeschlossen Dritten, p. 150 ff, in Brouwer [9] |
| [7] | Brouwer, L. E.J., Historical background, principles and methods of intuitionism, South African J. Sci., 49, 139-146 (1952) |
| [8] | Brouwer, L. E.J., Points and spaces, Canad. J. Math., 6, 1-17 (1954) · Zbl 0055.04601 |
| [9] | Brouwer, L. E.J., (Heyting, A., Collected Works (1975), North Holland: North Holland Amsterdam) · Zbl 0311.01021 |
| [10] | Burgess, John P., Brouwer and Souslin on transfinite cardinals, Z. Math. Log. Grundl. Math., 209-214 (1980) · Zbl 0432.03031 |
| [11] | Cantor, Georg, Über unendliche, lineare Punktmannigfaltigkeiten, V, Math. Ann., 21, 545-591 (1883), Published also by Teubner in the same with a Preface and a different title. English translation in Ewald [15], titled Foundations of a general theory of manifolds. A mathematical-philosophical investigation into the theory of the infinite · JFM 15.0452.03 |
| [12] | Cantor, Georg, Beiträge zur Begründung der transfiniten Mengenlehre, I, Math. Ann., 46, 481-512 (1895), English translation in Jourdain [22] · JFM 26.0081.01 |
| [13] | Cantor, Georg, Beiträge zur Begründung der transfiniten Mengenlehre, II, Math. Ann., 49, 207-246 (1897), English translation in Jourdain [22] · JFM 28.0061.08 |
| [14] | Dedekind, Richard, Was sind und was sollen die Zahlen? (1888), Whose second (1893) edition was translated into English by W. W. Beman and published in 1901 as Essays in the theory of numbers; reprinted in 1963 and available from Dover |
| [15] | (Ewald, William, From Kant to Hilbert: A Source Book in the Foundations of Mathematics, Vol. II (1996), Clarendon Press: Clarendon Press Oxford) · Zbl 0859.01002 |
| [16] | (Ewald, William; Sieg, Wilfried, David Hilbert’s Lectures on the Foundations of Arithmetic and Logic, 1917-1933. David Hilbert’s Lectures on the Foundations of Arithmetic and Logic, 1917-1933, David Hilbert’s Lectures on the Foundations of Mathematics and Physics, 1891-1933, vol. 3 (2013), Springer: Springer Berlin and Heidelberg) · Zbl 1275.03002 |
| [17] | Gentzen, Gerhard, Untersuchungen über das Logische Schliessen, Math. Z., 35 (1934-35), 175-210, 405-431. Exposited in [26, Chapter XV] · Zbl 0010.14501 |
| [18] | Hadamard, Jacques, Cinq lettres sur la théorie des ensembles, Bull. Soc. Math. France, 33, 261-273 (1905), Translated into English in [41, Appendix 1] · JFM 36.0099.01 |
| [19] | Heyting, Arend, Die formalen Regeln der intuitionistischen Logik, (Sitzungsberichte Der Preussischen Akademie Der Wissenschaften, Physikalisch-Mathematische Klasse (1930)), 42-56, English translation in Mancosu [38] · JFM 56.0823.01 |
| [20] | Heyting, Arend, Die formalen Regeln der intuitionistischen Mathematik, (Sitzungsberichte Der Preussischen Akademie Der Wissenschaften, Physikalisch-Mathematische Klasse (1930)), 57-71, Discussed in J.R. Moschovakis [44] · JFM 56.0823.01 |
| [21] | Hilbert, David, (Prinzipien der Mathematik. Prinzipien der Mathematik, Lecture notes by Paul Bernays. Winter-Semester 1917-18. Typescript. Bibliothek (1918), Mathematisches Institut, Universität Göttingen), Published in Ewald and Sieg [16] |
| [22] | (Jourdain, Philip E. B., Contributions to the Founding of Transfinite Numbers by Georg Cantor (1915)), English translation of Cantor [12] and Cantor [13] and with an introduction by the editor. Reprinted by Dover |
| [23] | Kanamori, Akihiro, The emergence of descriptive set theory, (Hintikka, Jaakko, from Dedekind To Gödel, Essays on the Development of the Foundations of Mathematics (2010), Kluwer), 241-281 |
| [24] | Kechris, A. S., (Classical Descriptive Set Theory. Classical Descriptive Set Theory, Graduate Texts in Mathematics, vol. 156 (1995), Springer-Verlag) · Zbl 0819.04002 |
| [25] | Kleene, Stephen C., On the interpretation of intuitionistic number theory, J. Symbolic Logic, 10, 109-124 (1945) · Zbl 0063.03260 |
| [26] | Kleene, Stephen C., Introduction to Metamathematics (1952), D. Van Nostrand Co, North Holland Co · Zbl 0047.00703 |
| [27] | Kleene, Stephen C., Formalized Recursive Functionals and Formalized Realizability (1969), Memoirs of the American Mathematical Society No 89 · Zbl 0184.02004 |
| [28] | Kleene, Stephen C.; Vesley, Richard Eugene, The Foundations of Intuitionistic Mathematics (1965), North Holland: North Holland Amsterdam · Zbl 0133.24601 |
| [29] | Kreisel, Georg, Analysis of Cantor-Bendixson Theorem by means of the analytic hierarchy, Bull. Acad. Pol. Sci., Ser. Sci. Math. Astron. Phys., 7, 621-626 (1959) · Zbl 0093.01401 |
| [30] | Krol, M. D., A topological model for intuitionistic analysis with Kripke’s Schema, Z. Math. Log. Grundl. Math., 24, 427-436 (1978) · Zbl 0418.03039 |
| [31] | Lebesgue, Henri, Sur les fonctions represéntables analytiquement, J. Math., 1, 6, 139-216 (1905) · JFM 36.0453.02 |
| [32] | Lusin, N., Sur la classification de M. Baire, C. R. Acad. Sci. Paris, 164, 91-94 (1917) · JFM 46.0390.03 |
| [33] | Lusin, N., Les proprietes des ensembles projectifs, C. R. Acad. Sci. Paris, 180, 1817-1819 (1925) · JFM 51.0169.03 |
| [34] | Lusin, N., Sur les ensembles projectifs de M. Henri Lebesgue, C. R. Acad. Sci. Paris, 180, 1572-1574 (1925) · JFM 51.0169.02 |
| [35] | Lusin, N., Sur un problème de M. Emile Borel et les ensembles projectifs de M. Henri Lebesgue: les ensembles analytiques, C. R. Acad. Sci. Paris, 180, 1318-1320 (1925) · JFM 51.0008.01 |
| [36] | Lusin, N., Sur les voies de la théorie des ensembles, (Proceedings of the 1928 International Congress of Mathematicians in Bologna (1928)), 295-299, Posted at http://www.mathunion.org/ICM/ICM1928.1/ · JFM 55.0657.01 |
| [37] | Lusin, N., Leçons sur les ensembles analytiques et leurs applications, (Collection de monographies sur la theorie des fonctions (1930), Gauthier-Villars: Gauthier-Villars Paris) · JFM 56.0085.01 |
| [38] | (Mancosu, P., From Brouwer to Hilbert: The Debate on the Foundations of Mathematics in the 1920s (1998), Oxford University Press: Oxford University Press New York and Oxford) · Zbl 0941.01003 |
| [39] | Markov, A. A., The continuity of constructive functions, Uspehi Mat. Nauk, 61, 226-230 (1954) · Zbl 0056.24901 |
| [40] | Michel, Alain, Remarks on the Supposed French ‘semi-’ or ‘pre-intuitionism, 149-162 (2008), In van Atten et al. [53] |
| [41] | Moore, Gregory H., Zermelo’s Axiom of Choice, its Origins, Development and Influence (1982), Springer-Verlag, distributed by Dover · Zbl 0497.01005 |
| [42] | Moschovakis, Joan Rand, Can there be no nonrecursive functions?, J. Symbolic Logic, 36, 309-315 (1971) · Zbl 0247.02036 |
| [43] | Moschovakis, Joan Rand, Classical and constructive hierarchies in extended intuitionistic analysis, J. Symbolic Logic, 68, 1015-1043 (2003) · Zbl 1059.03072 |
| [44] | Moschovakis, Joan Rand, (Gabbay, Dov; Woods, John, The logic of Brouwer and Heyting. The logic of Brouwer and Heyting, Handbook of the History of Logic, vol. 5 (2009), North Holland), 77-125 |
| [45] | Moschovakis, Joan Rand, Intuitionistic logic, (Zalta, Edward N., The Stanford Encyclopedia of Philosophy (Spring 2015 Edition) (2015)) · Zbl 0637.03058 |
| [46] | Moschovakis, Yiannis N., (Descriptive Set Theory. Descriptive Set Theory, Mathematical Surveys and Monographs, vol. 155 (2009), American Mathematical Society), Posted in ynm’s homepage · Zbl 1172.03026 |
| [47] | Moschovakis, Yiannis N., Classical descriptive set theory as a refinement of effective descriptive set theory, Ann. Pure Appl. Logic, 162, 243-255 (2010), Posted in ynm’s homepage · Zbl 1230.03077 |
| [48] | Moschovakis, Yiannis N., Kleene’s amazing second recursion theorem, Bull. Symbolic Logic, 16, 189-239 (2010), Posted in ynm’s homepage · Zbl 1211.03061 |
| [49] | Myhill, John, Notes towards an axiomatization of intuitionistic analysis, Logique et Anal. (N.S.), 9, 280-297 (1967) · Zbl 0187.26307 |
| [50] | Nelson, David, Recursive functions and intuitionistic number theory, Trans. Amer. Math. Soc., 61, 308-368 (1947) · Zbl 0058.24901 |
| [51] | Sierpinski, W., Sur une classe d’ensembles, Fund. Math., 7, 237-243 (1925) · JFM 51.0166.02 |
| [52] | Suslin, M., Sur une definition des ensembles measurables B sans nombres transfinis, C. R. Acad. Sci. Paris, 164, 88-91 (1917) · JFM 46.0296.01 |
| [53] | One hundred years of intuitionism (1907-2007), (van Atten, Mark; Boldini, Pascal; Bourdeau, Michel; Heinzmann, Gerhard, Proceedings of the 2007 Cerisy Conference (2008), Birkhäuser) · Zbl 1152.03004 |
| [54] | (Van Heijenoort, Jean, From Frege to Gödel, A Source Book in Mathematical Logic, 1879-1931 (1967), Harvard University Press: Harvard University Press Cambridge, Massachusetts, London, England) · Zbl 0183.00601 |
| [55] | Veldman, Wim, A survey of intuitionistic descriptive set theory, (Petkov, P. P., Mathematical Logic (1990), Plenum Press: Plenum Press New York), 155-174 · Zbl 0780.03029 |
| [56] | Veldman, Wim, The Borel hierarchy theorem from Brouwer’s intuitionistic perspective, J. Symbolic Logic, 73, 1-64 (2008) · Zbl 1148.03039 |
| [57] | Veldman, Wim, The fine structure of the intuitionistic Borel hierarchy, Rev. Symbolic Logic, 2, 30-101 (2009) · Zbl 1177.03061 |
| [58] | Zermelo, Ernst, Beweiss, dass jede Menge wohlgeordnet werden kann, Math. Ann., 59, 514-516 (1904), Translated into English in Van Heijenoort [54] · JFM 35.0088.03 |
| [59] | Zermelo, Ernst, Neuer Beweis für die Möglichkeit einer Wohlordnung, Math. Ann., 65, 107-128 (1908), Reprinted and translated into English in Zermelo [60]. Another English translation is in Van Heijenoort [54] · JFM 38.0096.02 |
| [60] | Zermelo, Ernst, (Ebbinhaus, Hans-Dieter; Fraser, Craig G.; Kanamori, Akihiro, Ernst Zermelo, Collected works, Gesammelte Werke, Vol. 1 (2010), Springer, Berlin, Heidelberg) · Zbl 1185.01054 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
