Descriptive Set Theory and Computable Topology
( 14. Nov – 19. Nov, 2021 )
- Mathieu Hoyrup (LORIA & INRIA Nancy, FR)
- Arno Pauly (Swansea University, GB)
- Victor Selivanov (A. P. Ershov Institute - Novosibirsk, RU)
- Mariya I. Soskova (University of Wisconsin - Madison, US)
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Jutka Gasiorowski (für administrative Fragen)
Computability and continuity are closely linked – in fact, continuity can be seen as computability relative to an arbitrary oracle. As such, concepts from topology and descriptive set theory feature heavily in the foundations of computable analysis. Conversely, techniques developed in computability theory can be fruitfully employed in topology and descriptive set theory, even if the desired results mention no computability at all.
In this Dagstuhl Seminar, we bring together researchers from computable analysis, from classical computability theory, from descriptive set theory, formal topology, and other relevant areas. Our goals are to identify key open questions related to this interplay, to exploit synergies between the areas and to intensify collaboration between the relevant communities.
Particular topics to be discussed include:
Quasi-Polish spaces as a common generalization of omega-continuous domains and Polish spaces. Many key results from descriptive set theory have already been extended to quasi-Polish spaces. Recently, reasonable candidates for computable quasi-Polish spaces were identified. We plan to continue the investigation of computability-aspects of quasi-Polish spaces.
The nascent synthetic descriptive set theory, where ideas from synthetic topology and category theory are linked to classical and effective descriptive set theory. The focus here is on properties of the spaces as a category rather than on their internal structures.
The connection between sigma-homeomorphism types of topological spaces and recursion-theoretic degree structures, in particular substructures of the enumeration degrees. In recent years, this connection has enabled Kihara and Pauly to solve a long-open problem by Jayne from topological dimension theory and has sparked significant new interest in the enumeration degrees.
CoPolish spaces as introduced by Schröder are a natural dual of the quasi-Polish spaces. They commonly arise in analysis (the space of real polynomials or of analytic functions are typical examples). They are also characterized as the class of spaces in computable analysis where complexity theory takes a familiar form.
Research area and topics
Descriptive set theory traditionally studies the complexity of subsets of and functions between Polish spaces (which are the completely metrizable separable spaces). As a mathematical area, it has well-established interactions with set theory and real analysis. Its canonical textbook is Kechris .
Following the developments in (classical) descriptive set theory, also the area of effective descriptive set theory flourished. In a way, this is the result of replacing continuous by computable everywhere, and by replacing arbitrary countable union by effective ones. Here, the canonical textbook is Moschovakis’ . While classical descriptive set theory is trivial on discrete spaces, the results from effective descriptive set theory on N often generalize results from computability theory. While this is rarely emphasized (see  for an exception), one can recover classical descriptive set theory from effective descriptive set theory by relativization – provided that theorems are phrased in the right way.
Recent years have seen a lot of interest in the interplay between descriptive set theory and theoretical computer science going beyond the natural meeting point of effective DST. Four core developments outlined below are particularly relevant for the meeting:
DST on spaces of interest for TCS
Certain classes of topological spaces were revealed as applicable to reasoning about the semantics of programming. The most famous example is domain theory, but Escardo’s synthetic topology  or the relationship between well-structured transition systems and Noetherian spaces revealed by Goubault-Larrecq  were also very influential. The spaces relevant for TCS are often not Hausdorff, and in particular not Polish. Selivanov pioneered the call for a development of descriptive set theory for these spaces [28, 29]. A break-through was achieved by de Brecht  with identifying the class of quasi-Polish spaces as a common generalization of Polish spaces and omega-continuous domains, and by showing that many core results of descriptive set theory can be extended to quasi-Polish spaces.
In computable analysis, we typically work with the category of admissible represented spaces (equivalently, with QCB0-spaces, i.e. T0-quotients of countably-based spaces) . This is a Cartesian-closed category, meaning that we can form function spaces. This is a very natural requirement from a TCS-perspective, but does not preserve being countably-based. How descriptive set theory works on non-countably-based spaces is still a mystery. de Brecht, Selivanov and Schröder have undertaken initial investigations, in particular into the Kleene-Kreisel spaces in [27, 26, 5]. Hoyrup has shown that even very simple non-countably-based spaces such as O(ωω) exhibit very unfamiliar behaviour compared to the usual DST .
de Brecht and Pauly observed a connection between synthetic topology (which in turn can be seen as the theory of functional programming ), models of hypercomputation and descriptive set theory [22, 23, 4]. This connection opens up the opportunity to apply reasoning styles about models of computation to descriptive set theory. Work by Kihara on the Jayne-Rogers conjecture has shown significant potential of this approach for solving open questions in descriptive set theory . There is also a hope that this theory can connect to other parts of TCS such as descriptive complexity.
DST and computability theory
Traditional computability theory, in particular the study of enumeration degrees, was related to the study of topological spaces via the notion of point degree spectrum introduced by Kihara and Pauly , building on earlier work by J. Miller . This lets us reason about the degrees of individual points in a topological space, and understand properties of the space in terms of what degrees are realized there. This technique was already used to resolve a long-standing open question by Jayne (, also ) on the number of sigma-homeomorphism types of Polish spaces in .
This connection is bidirectional, and also allows for the application of topological arguments in computability theory. As such, it has inspired a flurry of recent developments in the area of enumeration degrees by J. Miller, M. Soskova and others [2, 18, 1, 16]. Particularly remarkable here is the existence of non-total almost-total enumeration degrees. This is a purely recursion-theoretic statement, but the various known proofs all invoke topological arguments such as Brouwer’s Fixed Point theorem, Urysohn’s metrization theorem or Hurewicz’ and Wallmann’s characterization of countably-dimensional Polish spaces.
Of a similar flavour (but the precise connections are still unclear) is the approach to fractal geometry and Hausdorff dimension via effective dimension of points, defined via Kolmogorov complexity . This approach has already been demonstrated to provide strengthening of core results of fractal geometry, in many cases by rendering inessential restrictions to measurable sets. This includes a reproof of known answer to the two-dimensional Kakeyaconjecture .
coPolish spaces and computational complexity
In general, it seems that computational complexity of algorithms from computable analysis needs second-order complexity (Kawamura and Cook ). For certain spaces, however, runtimes of algorithms are still first-order objects . Ongoing work by de Brecht and Schröder has shown that this holds for the coPolish spaces, a dual notion to the quasi-Polish spaces. As such, it seems that “spaces where descriptive set theory is well-behaved” is the dual notion to “spaces where complexity theory is well-behaved”. This merits further attention by a broader community.
As our seminar brought together researchers from previously rather disconnected areas, we included several tutorial talks of one hour each to introduce the various facets of our seminar topics to everyone. The talks covered Quasi-Polish spaces (Matthew de Brecht), Quantitative Coding and Complexity Theory of Continuous Data (Martin Ziegler), CoPolish spaces and Effectively Hausdorff spaces (Matthias Schröder), New directions in Synthetic Descriptive Set Theory (Takayuki Kihara), Categorical aspects of Descriptive Set Theory (Ruiyuan Chen), Topology reflected in the enumeration degrees (Joseph S. Miller), Point-free Descriptive Set Theory (Alex Simpson) and Borel combinatorics fail in HYP (Linda Westrick).
In addition, we had many short (fifteen minute) talks introducing topics or open questions. The prompt for these talks was “What theorem do you want to prove during/following this workshop?”, and we are excited to learn what will come from this in the next months.
Challenges in hybrid Dagstuhl meetings
While the organizers and most participants had grown very accustomed to virtual meetings, the setting for our seminar was decidedly hybrid: About half of the participants were present in person, half were participating remotely. The same split applied to the organizing team.
The Dagstuhl team had equipped our main meeting room with multiple cameras and microphones (including microphones suspended from the ceiling throughout the room to pick up audience contributions). The equipment was controlled by several volunteers amongst the participants, and we are very grateful to Nikolay Bazhenov, Josiah Jacobsen-Grocott and Eike Neumann for having performed this crucial role. This setup made interactions in the lecture theatre between remote and in-person participants almost seamless.
A feature we felt was both crucial for a successful Dagstuhl seminar and difficult to accomplish in a hybrid setting are the informal discussions taking place in smaller groups. Our approach was to make those slightly less informal, and to use the collaboration platform Slack for arranging meetings. Slack also served for asking questions somewhat after the talks. This was somewhat successful, and several fruitful discussions involving both remote and in-person participants took place. It is difficult to ascertain though how much potential for additional discussions remained untapped.
- Uri Andrews, Hristo A. Ganchev, Rutger Kuyper, Steffen Lempp, Joseph S. Miller, Alexandra A. Soskova, and Mariya I. Soskova. On cototality and the skip operator in the enumeration degrees. preprint.
- Uri Andrews, Gregory Igusa, Joseph S. Miller, and Mariya I. Soskova. Characterizing the continuous degrees. Israel Journal of Mathematics, 234:743–767, 2019.
- Matthew de Brecht. Quasi-Polish spaces. Annals of Pure and Applied Logic, 164(3):354–381, 2013.
- Matthew de Brecht and Arno Pauly. Noetherian Quasi-Polish spaces. In Valentin Goranko and Mads Dam, editors, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), volume 82 of LIPIcs, pages 16:1–16:17. Schloss Dagstuhl, 2017.
- Matthew de Brecht, Matthias Schröder, and Victor Selivanov. Base-complexity classifications of QCB0-spaces. In Arnold Beckmann, Victor Mitrana, and Mariya Soskova, editors, Evolving Computability, pages 156–166. Springer, 2015.
- Martín Escardó. Synthetic topology of datatypes and classical spaces. Electronic Notes in Theoretical Computer Science, 87, 2004.
- Jean Goubault-Larrecq. Non-Hausdorff Topology and Domain Theory. New Mathematical Monographs. Cambridge University Press, 2013.
- Mathieu Hoyrup. Results in descriptive set theory on some represented spaces. arXiv 1712.03680, 2017.
- J. E. Jayne. The space of class α Baire functions. Bull. Amer. Math. Soc., 80:1151–1156, 1974.
- Akitoshi Kawamura and Stephen Cook. Complexity theory for operators in analysis. ACM Transactions on Computation Theory, 4(2), 2012.
- A.S. Kechris. Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer, 1995.
- Takayuki Kihara. Decomposing Borel functions using the Shore-Slaman join theorem. Fundamenta Mathematicae, 230, 2015. arXiv 1304.0698.
- Takayuki Kihara and Arno Pauly. Point degree spectra of represented spaces. arXiv:1405.6866, 2014.
- Jack Lutz. The dimensions of individual strings and sequences. Information and Computation, 187:49–79, 2003.
- Jack H. Lutz and Neil Lutz. Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension. In Heribert Vollmer and Brigitte Valleé, editors, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of LIPIcs, pages 53:1–53:13. Schloss Dagstuhl, 2017.
- Ethan McCarthy. Cototal enumeration degrees and their application to computable mathematics. Proceedings of the AMS, 146:3541–3552, 2018.
- Joseph S. Miller. Degrees of unsolvability of continuous functions. Journal of Symbolic Logic, 69(2):555 – 584, 2004.
- Joseph S. Miller and Mariya I. Soskova. Density of the cototal enumeration degrees. Annals of Pure and Applied Logic, 2018.
- Yiannis N. Moschovakis. Descriptive Set Theory, volume 100 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1980.
- Yiannis N. Moschovakis. Classical descriptive set theory as a refinement of effective descriptive set theory. Annals of Pure and Applied Logic, 162:243–255, 2010.
- Luca Motto Ros, Philipp Schlicht, and Victor Selivanov. Wadge-like reducibilities on arbitrary quasi-polish spaces. Mathematical Structures in Computer Science, pages 1–50, 11 2014. arXiv 1204.5338.
- Arno Pauly and Matthew de Brecht. Non-deterministic computation and the Jayne Rogers theorem. Electronic Proceedings in Theoretical Computer Science, 143, 2014. DCM 2012.
- Arno Pauly and Matthew de Brecht. Descriptive set theory in the category of represented spaces. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 438–449, 2015.
- Matthias Schröder. Extended admissibility. Theoretical Computer Science, 284(2):519–538, 2002.
- Matthias Schröder. Spaces allowing type-2 complexity theory revisited. Mathematical Logic Quarterly, 50(4/5):443–459, 2004.
- Matthias Schröder and Victor Selivanov. Hyperprojective hierarchy of QCB0-spaces. Computability, 4, 2015. arXiv 1404.0297.
- Matthias Schröder and Victor L. Selivanov. Some hierarchies of QCB0-spaces. Mathematical Structures in Computer Science, 25(8):1799–1823, 2015. arXiv 1304.1647.
- Victor L. Selivanov. Difference hierarchy in φ-spaces. Algebra and Logic, 43(4):238–248, 2004.
- Victor L. Selivanov. Towards a descriptive set theory for domain-like structures. Theoretical Computer Science, 365(3):258–282, 2006.
- Vasco Brattka (Bundeswehr University Munich, DE) [dblp]
- Riccardo Camerlo (University of Genova, IT) [dblp]
- Raphael Carroy (University of Torino, IT) [dblp]
- Jacques Duparc (University of Lausanne, CH) [dblp]
- Ivan Georgiev (Sofia University "St. Kliment Ohridski", BG) [dblp]
- Jun Le Goh (University of Wisconsin - Madison, US) [dblp]
- Vassilios Gregoriades (National Technical University of Athens, GR) [dblp]
- Mathieu Hoyrup (LORIA & INRIA Nancy, FR) [dblp]
- Steffen Lempp (University of Wisconsin - Madison, US) [dblp]
- Elvira Mayordomo (University of Zaragoza, ES) [dblp]
- Russell G. Miller (CUNY Queens College - Flushing, US) [dblp]
- Eike Neumann (MPI für Informatik - Saarbrücken, DE) [dblp]
- Adam Ó Conghaile (University of Cambridge, GB) [dblp]
- Arno Pauly (Swansea University, GB) [dblp]
- Marcin Sabok (McGill University - Montreal, CA) [dblp]
- Matthias Schröder (TU Darmstadt, DE) [dblp]
- Alexandra A. Soskova (University of Sofia, BG) [dblp]
- Martin Ziegler (KAIST - Daejeon, KR) [dblp]
- Alessandro Andretta (University of Torino, IT) [dblp]
- Nikolay Bazhenov (Sobolev Institute of Mathematics - Novosibirsk, RU)
- Ruiyuan (Ronnie) Chen (McGill University - Montreal, CA) [dblp]
- Matthew de Brecht (Kyoto University, JP) [dblp]
- Damir D. Dzhafarov (University of Connecticut - Storrs, US) [dblp]
- Olivier Finkel (University of Paris, FR) [dblp]
- Ekaterina Fokina (TU Wien, AT)
- Johanna N. Y. Franklin (Hofstra University - Hempstead, US) [dblp]
- Reinhold Heckmann (AbsInt - Saarbrücken, DE) [dblp]
- Daisuke Ikegami (Shibaura Institute of Technology - Tokyo, JP) [dblp]
- Corrie Ingall (University of Connecticut - Storrs, US)
- Josiah Jacobsen-Grocott (University of Wisconsin - Madison, US)
- Iskander Shagitovich Kalimullin (Kazan Federal University, RU) [dblp]
- Takayuki Kihara (Nagoya University, JP) [dblp]
- Margarita Korovina (Universität Trier, DE) [dblp]
- Davorin Lesnik (University of Ljubljana, SI) [dblp]
- Neil Lutz (Swarthmore College, US) [dblp]
- Alexander Melnikov (Victoria University - Wellington, NZ) [dblp]
- Joseph S. Miller (University of Wisconsin - Madison, US) [dblp]
- Luca Motto Ros (University of Torino, IT) [dblp]
- Takako Nemoto (Hiroshima Institute of Technology, JP) [dblp]
- Keng Meng Ng (Nanyang TU - Singapore, SG) [dblp]
- André Otfrid Nies (University of Auckland, NZ) [dblp]
- Alexey Ostrovsky (SUAI - Sankt-Peterburg, RU) [dblp]
- Jan Reimann (Pennsylvania State University - University Park, US) [dblp]
- Philipp Schlicht (University of Bristol, GB) [dblp]
- Victor Selivanov (A. P. Ershov Institute - Novosibirsk, RU) [dblp]
- Svetlana Selivanova (KAIST - Daejeon, KR) [dblp]
- Alex Simpson (University of Ljubljana, SI) [dblp]
- Theodore A. Slaman (University of California - Berkeley, US) [dblp]
- Mariya I. Soskova (University of Wisconsin - Madison, US) [dblp]
- Daniel Turetsky (Victoria University - Wellington, NZ) [dblp]
- Linda Westrick (Pennsylvania State University - University Park, US) [dblp]
- data structures / algorithms / complexity
- semantics / formal methods
- verification / logic
- computable analysis
- quasi-Polish spaces
- synthetic topology
- enumeration degrees