Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-16T23:12:19.908Z Has data issue: false hasContentIssue false
  • English
  • Français

The Borel Hierarchy Theorem from Brouwer's intuitionistic perspective

Published online by Cambridge University Press:  12 March 2014

Wim Veldman
Wim Veldman*
Affiliation:
Institute for Mathematics, Astrophysics and Particle Physics Faculty of Science, Radboud University Nijmegen Postbus9044, 6500 Kd Nijmegen, The Netherlands, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In intuitionistic analysis, Brouwer's Continuity Principle implies, together with an Axiom of Countable Choice, that the positively Borel sets form a genuinely growing hierarchy: every level of the hierarchy contains sets that do not occur at any lower level.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 1 , March 2008 , pp. 1 - 64
Copyright
Copyright © Association for Symbolic Logic 2008

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

REFERENCES

[1]Bishop, E. and Bridges, D., Constructive analysis, Springer-Verlag, Berlin, 1985.CrossRefGoogle Scholar
[2]Bockstaele, P., Het intuïtionisme bij de Franse wiskundigen, Verhandelingen van de Vlaamse Academie voor Wetenschappen, Letteren en Schone Kunsten, Jaargang XI, No. 32, Brussel, 1949.Google Scholar
[3]Borel, É., Leçons sur les fonctions de variables réelles et les développements en séries de polynomes, Gauthier-Villars, Paris, 1905, esp. Note III, page 156: Sur l'existence des fonctions de classe quelconque.Google Scholar
[4]Borel, É., La théorie de la mesure et la théorie de l'intégration, 1914, Note VI in [5], pp. 217–256.Google Scholar
[5]Borel, É., Leçons sur la théorie des fonctions, deuxième ed., Gauthier-Villars, Paris, 1914.Google Scholar
[6]Borel, É., Les polémiques sur le transfini, 1914, Note IV in [5], pp. 135–177.Google Scholar
[7]Bridges, D. and Richman, F., Varieties of constructive mathematics, Cambridge University Press, 1987.CrossRefGoogle Scholar
[8]Brouwer, L.E.J., Begründung der Mengenlehre unabhängig vom logischen Satz vom ausgeschlossenen Dritten. Erster Teil: Allgemeine Mengenlehre, Koninklijke Nederlandsche Akademie van Wetenschappen, Verhandelingen, le sectie 12 no.5, 43 pp., 1918, also [13], pp. 150–190, with footnotes, pp. 573#x2013;585.Google Scholar
[9]Brouwer, L.E.J., Über Definitionsbereiche von Funktionen, Mathematische Annalen, vol. 97 (1927), pp. 60–75, also in [13], pp. 390–405, see also [22], pp. 446–463.CrossRefGoogle Scholar
[10]Brouwer, L.E.J., Essentieel-negatieve eigenschappen (Essentially negative properties), Koninklijke Nederlandse Akademie van Wetenschappen Proc., vol. 51 (1948), pp. 963–964, also in: Indagationes Mathematicae vol. 10 (1948), pp. 322–323, also in [13], pp. 478–479.Google Scholar
[11]Brouwer, L.E.J., De non-aequivalentie van de constructieve en de negatieve orderelatie in het continuum, The non-equivalence of the constructive and the negative order relation on the continuum, Koninklijke Nederlandse Akademie van Wetenschappen Proc., vol. 52 (1949), pp. 122–124, also in: Indagationes Mathematicae, vol. 11 (1949), pp. 37–39, also in [13], pp. 495–496.Google Scholar
[12]Brouwer, L.E.J., Points and spaces, Canadian Journal of Mathematics, vol. 6 (1954), pp. 1–17, also in: [13], pp. 522–538.CrossRefGoogle Scholar
[13]Brouwer, L.E.J., Collected works, Vol. I: Philosophy and foundations of mathematics (Heyting, A., editor), North-Holland, Amsterdam, 1975.Google Scholar
[14]Brouwer, L.E.J., Intuitionismus, Wissenschaftsverlag, Mannheim etc., 1992, herausgegeben, eingeleitet und kommentiert von D. van Dalen.Google Scholar
[15]van Dantzig, D., On the principles of intuitionistic and affirmative mathematics, Koninklijke Ned-erlandse Akademie van Wetenschappen Proc., vol. 50 (1947), pp. 918–929 and 1092–1103, = Indagationes Mathematical vol. 9 (1947), pp. 429–440 and 506–517.Google Scholar
[16]Dragalin, A.G., Mathematical intuitionism, introduction to proof theory, Translations of Mathematical Monographs, vol. 67, American Mathematical Society, Providence, Rhode Island, 1987.Google Scholar
[17]Franchella, M., Brouwer and Griss on intuitionistic negation. Modern Logic, vol. 4 (1994), pp. 256–265.Google Scholar
[18]Gentzen, G., Die Widerspruchsfreiheit der reinen Zahlentheorie, Mathematische Annalen, vol. 112 (1936), pp. 493–565, see also [19], pp. 132–213.CrossRefGoogle Scholar
[19]Gentzen, G., The collected papers of Gerhard Gentzen (Szabo, M.E., editor), North Holland Publishing Company, Amsterdam and London, 1969.Google Scholar
[20]Griss, G.F.C., Negationless intuitionistic mathematics, Koninklijke Nederlandse Akademie van Wetenschappen Proc., vol. 49 (1946), pp. 1127–1133, vol. 53 (1950), pp. 456–463, vol. 54 (1951), pp. 193–199 and 452–471 = Indagationes Mathematicae, vol. 8 (1946), pp. 675–681, vol. 12 (1950), pp. 108–115, vol. 13 (1951), pp. 193–199 and 452–471.Google Scholar
[21]Hausdorff, F., Über halbstetige Funktionen und deren Verallgemeinerung, Mathematische Zeitschrift, vol. 5 (1921), pp. 292–309.CrossRefGoogle Scholar
[22]van Heijenoort, J., From Frege to Gödel, a source book in mathematical logic, 1879–1931, Harvard University Press, Cambridge, Mass., 1967.Google Scholar
[23]Heyting, A., Intuitionism, an introduction, North-Holland Publishing Company, Amsterdam etc., 1956, second, revised edition 1966, third, revised edition 1972.Google Scholar
[24]Howard, W.A. and Kreisel, G., Transfinite induction and bar induction of types zero and one, and the role of continuity in intuitionistic analysis, this Journal, vol. 31 (1966), pp. 325–358.Google Scholar
[25]Kechris, A.S., Classical descriptive set theory, Springer-Verlag, Berlin, 1996.Google Scholar
[26]Kleene, S.C., Recursive predicates and quantifiers, Transactions of the American Mathematical Society, vol. 53 (1943), pp. 41–73.CrossRefGoogle Scholar
[27]Kleene, S.C. and Vesley, R.E., The foundations of intuitionistic mathematics, especially in relation to recursive functions, North-Holland Publishing Company, Amsterdam, 1965.Google Scholar
[28]Kuroda, S., Intuitionistische Untersuchungen der formalistischen Logik, Nagoya Mathematical Journal, vol. 2 (1951), pp. 35–47.CrossRefGoogle Scholar
[29]Lebesgue, H., Sur les fonctions représentables analytiquement, Journal de Math. 6e série, vol. 1 (1905), pp. 139–216.Google Scholar
[30]Lusin, N., Sur la classification de M. Baire, Comptes Rendus de l'Académie des Sciences, vol. 164 (1917), pp. 91–94.Google Scholar
[31]Lusin, N., Sur les ensembles non measurables B et l'emploi de la diagonale de Cantor, Comptes Rendus de l'Académie des Sciences, vol. 181 (1925), pp. 95–96.Google Scholar
[32]Lusin, N., Leçons sur les ensembles analytiques et leurs applications, Paris, 1930, second edition: Chelsea Publishing Company, New York 1972.Google Scholar
[33]Martin-Löf, P., Notes on constructive mathematics, Almquist and Wiksell, Stockholm, 1968.Google Scholar
[34]Martino, E. and Giaretta, P., Brouwer, Dummett and the bar theorem, Attidelcongressonazionale di logica, Montecatini Terme, 1–5 ottobre 1979 (a cura di Sergio Bernini), Bibliopolis, Napoli, 1981, pp. 541–558.Google Scholar
[35]Moschovakis, J.R., Hierarchies in intuitionistic arithmetic, Gjuletchica, Bulgaria, 12 2002.Google Scholar
[36]Moschovakis, J.R., Classical and constructive hierarchies in extended intuitionistic analysis, this Journal, vol. 68 (2003), pp. 1015–1043.Google Scholar
[37]Moschovakis, J.R., The effect of Markov's Principle on the intuitionistic continuum, Oberwolfach reports, vol. 2(1), European Mathematical Society, 2005, Proceedings of Oberwolfach Proof Theory week.Google Scholar
[38]Moschovakis, Y.N., Descriptive set theory, North-Holland, Amsterdam, 1980.Google Scholar
[39]Mostowski, A., On definable sets of positive integers, Fundamenta Mathematicae, vol. 34 (1946), pp. 81–112.CrossRefGoogle Scholar
[40]Souslin, M., Sur une définition des ensembles mesurables B sans nombres transfinis, Comptes Rendus de l'Académie des Sciences, vol. 164 (1917), pp. 88–91.Google Scholar
[41]Troelstra, A.S. (editor), Metamathematical investigation of intuitionistic arithmetic and analysis, Lecture Notes in Mathematics, vol. 344, Springer-Verlag, Berlin etc., 1973.CrossRefGoogle Scholar
[42]Troelstra, A.S. and van Dalen, D., Constructivism in mathematics, volume I, North-Holland, Amsterdam, 1988.Google Scholar
[43]Veldman, W., Investigations in intuitionistic hierarchy theory, Ph.D. thesis, Katholieke Universiteit Nijmegen, 1981.Google Scholar
[44]Veldman, W., A survey of intuitionistic descriptive set theory, Mathematical logic (Petkov, P.P., editor), Proceedings of the Heyting Conference 1988, Plenum Press, New York and London, 1990, pp. 155–174.CrossRefGoogle Scholar
[45]Veldman, W., Some intuitionistic variations on the notion of a finite set of natural numbers, Perspectives on negation (de Swart, H.C.M. and Bergmans, L.J.M., editors), Essays in honour of Johan J. de Iongh on the occasion of his 80th birthday, Tilburg University Press, Tilburg, 1995, pp. 177–202.Google Scholar
[46]Veldman, W., On sets enclosed between a set and its double complement, Logic and foundations of mathematics (Cantini, A.et al., editors), Proceedings Xth International Congress on Logic, Methodology and Philosophy of Science, Florence 1995, Volume III, Kluwer Academic Publishers, Dordrecht, 1999, pp. 143–154.CrossRefGoogle Scholar
[47]Veldman, W., Understanding and using Brouwer's continuity principle, Reuniting the antipodes, constructive and nonstandard views of the continuum (Berger, U., Osswald, H., and Schuster, P., editors), Proceedings of a Symposium held in San Servolo/Venice, 1999, Kluwer Academic Publishers, Dordrecht, 2001, pp. 285–302.CrossRefGoogle Scholar
[48]Veldman, W., On the persistent difficulty of disjunction, Philosophical dimensions of logic and science (Rojszczak, A., Cachro, J., and Kurczewski, G., editors), Selected Contributed Papers from the 11th International Congress on Logic, Methodology and Philosophy of Science, Kraków, 1999, Kluwer Academic Publishers, Dordrecht, 2003, pp. 77–90.CrossRefGoogle Scholar
[49]Veldman, W., An intuitionistic proof of Kruskal's theorem, Archive for Mathematical Logic, vol. 43 (2004) , pp. 215–264.CrossRefGoogle Scholar
[50]Veldman, W., Brouwer's Fan Theorem as an axiom and as a contrast to Kleene's Alternative, Technical Report 0509, Department of Mathematics, Radboud University Nijmegen, 07 2005.Google Scholar
[51]Veldman, W., Perhaps the Intermediate Value Theorem, Constructivity, computability and logic. A collection of papers in honour of the 60th birthday of Douglas Bridges. Journal of Universal Computer Science (Calude, C.S. and Ishihara, H., editors), vol. 11, 2005, pp. 2142–2158.Google Scholar
[52]Veldman, W., Two simple sets that are not positively Borel, Annals of Pure and Applied Logic, vol. 135 (2005), pp. 151–209.CrossRefGoogle Scholar
[53]Veldman, W., The Borel hierarchy and the projective hierarchy from Brouwer's intuitionistic perspective, Technical Report 0604, Department of Mathematics, Radboud University Nijmegen, the Netherlands, 06 2006.Google Scholar
[54]Veldman, W., Brouwer's real thesis on bars, Philosophia Scientiae, (2006), pp. 21–42, Cahier spécial 6.Google Scholar
[55]Waaldijk, F., Modern intuitionistic topology, Ph.D. thesis, Katholieke Universiteit Nijmegen, 1996.Google Scholar