Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

What parts of the classical descriptive set theory done in Polish spaces still hold for more general topological spaces, possibly T0 or T1, but not T2 (i.e. not Hausdorff)? This question has been addressed by Selivanov in a series of papers centred on algebraic domains. And recently it has been considered by de Brecht for quasi-Polish spaces, a framework that contains both countably based continuous domains and Polish spaces. In this paper, we present alternative unifying topological spaces, that we call approximation spaces. They are exactly the spaces for which player Nonempty has a stationary strategy in the Choquet game. A natural proper subclass of approximation spaces coincides with the class of quasi-Polish spaces. We study the Borel and Hausdorff difference hierarchies in approximation spaces, revisiting the work done for the other topological spaces. We also consider the problem of effectivization of these results. Copyright © Cambridge University Press 2014.

Registro:

Documento: Artículo
Título:Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization
Autor:Becher, V.; Grigorieff, S.
Filiación:FCEyN, Universidad de Buenos Aires, CONICET, Buenos Aires, Argentina
LIAFA, CNRS, Université Paris Diderot - Paris 7, France
Laboratoire International Associé INFINIS, Universidad de Buenos Aires, Université Paris Diderot-Paris 7, France
Palabras clave:Set theory; Algebraic domains; Approximation spaces; Continuous domain; Descriptive set theory; Difference hierarchies; Hausdorff; Hausdorff hierarchy; Topological spaces; Topology
Año:2015
Volumen:25
Número:7
Página de inicio:1490
Página de fin:1519
DOI: http://dx.doi.org/10.1017/S096012951300025X
Título revista:Mathematical Structures in Computer Science
Título revista abreviado:Math. Struct. Comput. Sci.
ISSN:09601295
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09601295_v25_n7_p1490_Becher

Referencias:

  • Abramsky, S., Jung, A., Domain theory (1994) Handbook of Logic in Computer Science, 3. , Abramsky, S., Gabbay, Dov M. and Maibaum, T. S. E. (eds.) Oxford University Press
  • Bennett, H., Lutzer, D., Strong completeness properties in topology (2009) Questions and Answers in General Topology, 27, pp. 107-112
  • Choquet, G., Lectures on Analysis (1969) Integration and Topological Vector Spaces, 1. , Benjamin
  • De Brecht, M., Quasi-Polish spaces (2013) Annals of Pure and Applied Logic, 164 (3), pp. 356-381
  • Debs, G., (1984) An Example of an α-favourable Topological Space with No α-winning Tactic. Séminaire D'Initiation a L'Analyse, , Choquet-Rogalski-Saint Raymond
  • Debs, G., Stratégies gagnantes dans certains jeux topologiques (1985) Fundamenta Mathematicae, 126, pp. 93-105
  • Dehornoy, P., Turing complexity of the ordinals (1986) Information Processing Letters, 23 (4), pp. 167-170
  • Dorais, F.G., Mummert, C., Stationary and convergent strategies in Choquet games (2010) Fundamenta Mathematicae, 209, pp. 59-79
  • Edalat, A., Domains for computation in mathematics, physics and exact real arithmetic (1997) Bulletin of Symbolic Logic, 3 (4), pp. 401-452
  • Ershov, Y., On a hierarchy of sets II (1968) Algebra and Logic, 7 (4), pp. 15-47
  • Galvin, F., Telgárky, R., Stationary strategies in topological games (1986) Topology and Its Applications, 22, pp. 51-69
  • Gierz, G., Hofmann, K.H., Keimel, K., Lawson, J.D., Mislove, M., Scott, D.S., (2003) Continuous Lattices and Domains, , Cambridge University Press
  • Grigorieff, S., Every recursive linear ordering has an isomorphic copy in DTIME-SPACE(n, log(n)) (1990) Journal of Symbolic Logic, 55 (1), pp. 260-276
  • Hertling, P., (1996) Unstetigkeitgrade Con Funktionen in der Effektiven Analysis, , Ph.D. thesis, FernUniversity in Hagen
  • Hertling, P., Topological complexity with continuous operations (1996) Journal of Complexity, 12 (4), pp. 315-338
  • Kechris, A.S., (1995) Classical Descriptive Set Theory, , Springer
  • Künzi, H.-P., On strongly quasi-metrizable spaces (1983) Archiv der Mathematik, 41 (1), pp. 57-63
  • Kuratowski, K., (1966) Topology, 1. , Academic Press
  • Marker, D., (2002) Descriptive Set Theory, , http://homepages.math.uic.edu/~marker/math512/dst.ps, Lecture Notes. On Marker's home page. Available at
  • Moschovakis, Y., (1979) Descriptive Set Theory, 155. , American Mathematical Society First edition 1979, second edition 2009
  • Oxtoby, J.C., The Banach-Mazur game and Banach category theorem (1957) Annals of Mathematics Studies, 39, pp. 159-163. , Contributions to the theory of games, volume III
  • Schmidt, W.W., On badly approximable numbers and certain games (1966) Transactions of the American Mathematical Society, 123, pp. 178-199
  • Selivanov, V.L., Wadge degrees of ω-languages of deterministic Turing machines (2003) Theoretical Informatics and Applications, 37 (1), pp. 67-83
  • Selivanov, V.L., Wadge degrees of ω-languages of deterministic Turing machines (2003) Lecture Notes in Computer Science, 2607, pp. 97-108. , Extended abstract in STACS 2003 Proceedings
  • Selivanov, V.L., Hierarchies in φ-spaces and applications (2005) Mathematical Logic Quarterly, 51 (1), pp. 45-61
  • Selivanov, V.L., Towards a descriptive set theory for domain-like structures (2006) Theoretical Computer Science, 365 (3), pp. 258-282
  • Selivanov, V.L., On the difference hierarchy in countably based T<inf>0</inf>-spaces (2008) Electronic Notes in Theoretical Computer Science, 221, pp. 257-269
  • Spector, C., Recursive well-orderings (1955) Journal of Symbolic Logic, 20 (2), pp. 151-163
  • Tang, A., Wadge reducibility and Hausdorff difference hierarchy in Pω (1981) Lectures Notes in Mathematics, 871, pp. 360-371
  • Weihrauch, K., (2000) Computable Analysis. An Introduction, , Springer

Citas:

---------- APA ----------
Becher, V. & Grigorieff, S. (2015) . Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization. Mathematical Structures in Computer Science, 25(7), 1490-1519.
http://dx.doi.org/10.1017/S096012951300025X
---------- CHICAGO ----------
Becher, V., Grigorieff, S. "Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization" . Mathematical Structures in Computer Science 25, no. 7 (2015) : 1490-1519.
http://dx.doi.org/10.1017/S096012951300025X
---------- MLA ----------
Becher, V., Grigorieff, S. "Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization" . Mathematical Structures in Computer Science, vol. 25, no. 7, 2015, pp. 1490-1519.
http://dx.doi.org/10.1017/S096012951300025X
---------- VANCOUVER ----------
Becher, V., Grigorieff, S. Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization. Math. Struct. Comput. Sci. 2015;25(7):1490-1519.
http://dx.doi.org/10.1017/S096012951300025X