Descriptive set theory in the category of represented spaces. (English) Zbl 1395.03021
Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 438-449 (2015).
MSC:
| 03E15 | Descriptive set theory |
| 18B30 | Categories of topological spaces and continuous mappings (MSC2010) |
References:
| [1] | C. Aull and W. Thron, “Separation axioms between T0 and T1,” Proc. Nederl. Akad. Wet., 1962. · Zbl 0108.35402 |
| [2] | A. Bauer and D. Lesnik, “Metric spaces in synthetic topology,” Annals of Pure and Applied Logic, vol. 163, no. 2, pp. 87-100, 2012. · Zbl 1251.03081 |
| [3] | V. Brattka, “Limit computable functions and subsets,” unpublished. |
| [4] | V. Brattka, “Effective Borel measurability and reducibility of functions,” Mathematical Logic Quarterly, vol. 51, no. 1, pp. 19-44, 2005. · Zbl 1059.03074 |
| [5] | V. Brattka, M. de Brecht, and A. Pauly, “Closed choice and a uniform low basis theorem,” Annals of Pure and Applied Logic, vol. 163, no. 8, pp. 968-1008, 2012. · Zbl 1251.03082 |
| [6] | V. Brattka and G. Gherardi, “Borel complexity of topological operations on computable metric spaces,” Journal of Logic and Computation, vol. 19, no. 1, pp. 45-76, 2009. · Zbl 1169.03047 |
| [7] | V. Brattka and G. Presser, “Computability on subsets of metric spaces,” Theoretical Computer Science, vol. 305, no. 1-3, pp. 43-76, 2003. · Zbl 1071.03027 |
| [8] | A. M. Bruckner, J. B. Bruckner, and B. S. Thomson, Real Analysis. Prentice-Hall, 1997. · Zbl 0872.26001 |
| [9] | M. de Brecht, “Levels of discontinuity, limit-computability, and jump operators,” arXiv 1312.0697, 2013. |
| [10] | M. de Brecht, “Quasi-Polish spaces,” Annals of Pure and Applied Logic, vol. 164, no. 3, pp. 354-381, 2013. · Zbl 1270.03086 |
| [11] | M. de Brecht and A. Yamamoto, “Topological properties of concept spaces,” Information and Computation, vol. 208, no. 4, pp. 327-340, 2010. · Zbl 1192.68428 |
| [12] | M. de Brecht and A. Yamamoto, “¿¿^0 - admissible representations (extended abstract),” in 6th Int’l Conf. on Computability and Complexity in Analysis, A. Bauer, P. Hertling, and K.-I. Ko, Eds. Schloss Dagstuhl, 2009. [Online]. Available: http://drops.dagstuhl.de/opus/volltexte/2009/2264 |
| [13] | H. de Holanda Cunha Nobrega, “Game characterizations of function classes and Weihrauch degrees,” M.Sc. Thesis, University of Amsterdam, 2013. |
| [14] | M. Escardó, “Synthetic topology of datatypes and classical spaces,” Electronic Notes in Theoretical Computer Science, vol. 87, 2004. · Zbl 1270.68082 |
| [15] | M. Escardó, “Intersections of compactly many open sets are open,” 2009. [Online]. Available: http://www.cs.bham.ac.uk/mhe/papers/compactness-submitted.pdf |
| [16] | J.-Y. Girard, “Light linear logic,” in Logic and Computational Complexity, ser. Lecture Notes in Computer Science, D. Leivant, Ed. Springer Berlin Heidelberg, 1995, vol. 960, pp. 145-176. · Zbl 1540.03107 |
| [17] | V. Gregoriades, “Turning Borel sets into clopen sets effectively,” Fundamenta Mathematicae, vol. 219, no. 2, pp. 119-143, 2012. · Zbl 1276.03038 |
| [18] | V. Gregoriades, T. Kispéter, and A. Pauly, “A comparison of concepts from computable analysis and effective descriptive set theory,” arXiv:1401.3325, 2014. |
| [19] | V. Gregoriades and Y. N. Moschovakis, “Notes on effective descriptive set theory,” notes in preparation. |
| [20] | K. Higuchi and T. Kihara, “Inside the Muchnik degrees I: Discontinuity, learnability and constructivism,” Annals of Pure and Applied Logic, vol. 165, no. 5, pp. 1058-1114, 2014. · Zbl 1315.03071 |
| [21] | K. Higuchi and T. Kihara, “Inside the Muchnik degrees II: The degree structures induced by the arithmetical hierarchy of countably continuous functions,” Annals of Pure and Applied Logic, vol. 165, no. 6, pp. 1201-1241, 2014. · Zbl 1315.03072 |
| [22] | M. Hoyrup and C. Rojas, “On the information carried by programs about the objects they compute,” arXiv 1409.6977, 2014. [Online]. Available: http://arxiv.org/abs/1409.6977 |
| [23] | J. Jayne and C. Rogers, “First level Borel functions and isomorphisms,” Journal de Mathmatiques Pures et Appliques, vol. 61, pp. 177-205, 1982. · Zbl 0514.54026 |
| [24] | M. Ka¿ena, L. M. Ros, and B. Semmes, “Some observations on ”A new proof of a theorem of Jayne and Rogers’,” Real Analysis Exchange, vol. 38, no. 1, pp. 121-132, 2012/3. · Zbl 1272.03149 |
| [25] | A. Kechris, Classical Descriptive Set Theory, ser. Graduate Texts in Mathematics. Springer, 1995, vol. 156. · Zbl 0819.04002 |
| [26] | T. Kihara, “Decomposing Borel functions using the Shore-Slaman join theorem,” arXiv 1304.0698, 2013. |
| [27] | T. Kihara and A. Pauly, “Point degree spectra of represented spaces,” arXiv:1405.6866, 2014. |
| [28] | C. Kupke, A. Kurz, and Y. Venema, “Stone coalgebras,” Electronic Notes in Theoretical Computer Science, vol. 82, no. 1, 2003. · Zbl 1270.03142 |
| [29] | A. S. K. L. A. Harrington and A. Louveau, “A Glimm-Effros dichotomy for Borel equivalence relations,” Journal of the AMS, vol. 3, pp. 903- 928, 1990. · Zbl 0778.28011 |
| [30] | A. Louveau, “A separation theorem for ¿1^1 sets,” Trans. Amer. Math. Soc., vol. 260, no. 2, pp. 363-378, 1980. · Zbl 0455.03021 |
| [31] | J. S. Miller, “&Pi1^0 classes in computable analysis and topology,” Ph.D. dissertation, Cornell University, 2002. |
| [32] | E. Moggi, “Notions of computation and monads,” Information and Computation, vol. 93, no. 1, pp. 55 - 92, 1991, selections from 1989 IEEE Symposium on Logic in Computer Science. · Zbl 0723.68073 |
| [33] | Y. N. Moschovakis, Descriptive Set Theory, ser. Studies in Logic and the Foundations of Mathematics. North-Holland, 1980, vol. 100. · Zbl 0433.03025 |
| [34] | Y. N. Moschovakis, “Classical descriptive set theory as a refinement of effective descriptive set theory,” Annals of Pure and Applied Logic, vol. 162, pp. 243-255, 2010. · Zbl 1230.03077 |
| [35] | L. Motto-Ros, “A new characterization of the Baire class 1 functions,” Real Analysis Exchange, vol. 34, no. 1, pp. 29-48, 2008. · Zbl 1181.03048 |
| [36] | L. Motto Ros, “Game representations of classes of piecewise definable functions,” Mathematical Logic Quarterly, vol. 57, no. 1, pp. 95-112, 2011. · Zbl 1215.03060 |
| [37] | L. Motto Ros and B. Semmes, “A new proof of a theorem of Jayne and Rogers,” Real Analysis Exchange, vol. 35, no. 1, pp. 195-204, 2009. · Zbl 1217.03032 |
| [38] | A. Pauly, “Many-one reductions between search problems,” arXiv 1102.3151, 2011. [Online]. Available: http://arxiv.org/abs/1102.3151 |
| [39] | A. Pauly, “On the topological aspects of the theory of represented spaces,” http://arxiv.org/abs/1204.3763, 2012. |
| [40] | A. Pauly, “The descriptive theory of represented spaces,” arXiv:1408.5329, 2014. |
| [41] | A. Pauly, “Computability on the countable ordinals and the Hausdorff-Kuratowski theorem,” arXiv 1501.00386, 2015. |
| [42] | A. Pauly and M. de Brecht, “Non-deterministic computation and the Jayne Rogers theorem,” Electronic Proceedings in Theoretical Computer Science, vol. 143, 2014, dCM 2012. · Zbl 1464.03042 |
| [43] | M. Schröder, “Admissible representations for continuous computations,” Ph.D. dissertation, FernUniversität Hagen, 2002. · Zbl 1020.18005 |
| [44] | M. Schröder, “Extended admissibility,” Theoretical Computer Science, vol. 284, no. 2, pp. 519-538, 2002. · Zbl 1042.68050 |
| [45] | M. Schröder and V. Selivanov, “Hyperprojective hierarchy of QCB0-spaces,” arXiv 1404.0297, 2014. [Online]. Available: http://arxiv.org/abs/1404.0297 |
| [46] | M. Schröder and V. L. Selivanov, “Some hierarchies of QCB0-spaces,” Mathematical Structures in Computer Science, pp. 1-25, 11 2014, arXiv 1304.1647. |
| [47] | V. L. Selivanov, “Difference hierarchy in ¿-spaces,” Algebra and Logic, vol. 43, no. 4, pp. 238-248, 2004. · Zbl 1062.03042 |
| [48] | V. L. Selivanov, “Total representations,” Logical Methods in Computer Science, vol. 9, no. 2, 2013. · Zbl 1285.03064 |
| [49] | R. Shore and T. Slaman, “Defining the Turing jump,” Mathematical Research Letters, vol. 6, no. 5-6, pp. 711-722, 1999. · Zbl 0958.03029 |
| [50] | P. Taylor, “A lambda calculus for real analysis,” Journal of Logic & Analysis, vol. 2, no. 5, pp. 1-115, 2010. · Zbl 1285.03006 |
| [51] | P. Taylor, “Foundations for computable topology,” in Foundational Theories of Classical and Constructive Mathematics, ser. The Western Ontario Series in Philosophy of Science. Springer, 2011, vol. 76, pp. 265-310. · Zbl 1317.03041 |
| [52] | W. W. Wadge, “Degrees of complexity of subsets of the Baire space,” Notices of the AMS, vol. 19, pp. 714-715, 1972. |
| [53] | W. W. Wadge, “Reducibility and determinateness on the Baire space,” Ph.D. dissertation, University of California, Berkeley, 1983. |
| [54] | K. Weihrauch, Computability, ser. Monographs on Theoretical Computer Science. Springer-Verlag, 1987. · Zbl 0611.03002 |
| [55] | K. Weihrauch, Computable Analysis. Springer-Verlag, 2000. · Zbl 0956.68056 |
| [56] | M. Ziegler, “Real hypercomputation and continuity,” Theory of Computing Systems, vol. 41, pp. 177-206, 2007. · Zbl 1122.03039 |
| [57] | M. Ziegler, “Revising type-2 computation and degrees of discontinuity,” Electronic Notes in Theoretical Computer Science, vol. 167, pp. 255-274, 2007. · Zbl 1262.03150 |
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.
