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 [11].

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’ [19]. 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 [20] 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 [6] or the relationship between well-structured transition systems and Noetherian spaces revealed by Goubault-Larrecq [7] 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 [3] 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 QCB₀-spaces, i.e. T₀-quotients of countably-based spaces) [24]. 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 [8].

Synthetic DST

de Brecht and Pauly observed a connection between synthetic topology (which in turn can be seen as the theory of functional programming [6]), 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 [12]. 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 [13], building on earlier work by J. Miller [17]. 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 ([9], also [21]) on the number of sigma-homeomorphism types of Polish spaces in [13].

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 [14]. 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 [15].

coPolish spaces and computational complexity

In general, it seems that computational complexity of algorithms from computable analysis needs second-order complexity (Kawamura and Cook [10]). For certain spaces, however, runtimes of algorithms are still first-order objects [25]. 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.

Seminar structure

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.

References

1. 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.
2. Uri Andrews, Gregory Igusa, Joseph S. Miller, and Mariya I. Soskova. Characterizing the continuous degrees. Israel Journal of Mathematics, 234:743–767, 2019.
3. Matthew de Brecht. Quasi-Polish spaces. Annals of Pure and Applied Logic, 164(3):354–381, 2013.
4. 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.
5. 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.
6. Martín Escardó. Synthetic topology of datatypes and classical spaces. Electronic Notes in Theoretical Computer Science, 87, 2004.
7. Jean Goubault-Larrecq. Non-Hausdorff Topology and Domain Theory. New Mathematical Monographs. Cambridge University Press, 2013.
8. Mathieu Hoyrup. Results in descriptive set theory on some represented spaces. arXiv 1712.03680, 2017.
9. J. E. Jayne. The space of class α Baire functions. Bull. Amer. Math. Soc., 80:1151–1156, 1974.
10. Akitoshi Kawamura and Stephen Cook. Complexity theory for operators in analysis. ACM Transactions on Computation Theory, 4(2), 2012.
11. A.S. Kechris. Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer, 1995.
12. Takayuki Kihara. Decomposing Borel functions using the Shore-Slaman join theorem. Fundamenta Mathematicae, 230, 2015. arXiv 1304.0698.
13. Takayuki Kihara and Arno Pauly. Point degree spectra of represented spaces. arXiv:1405.6866, 2014.
14. Jack Lutz. The dimensions of individual strings and sequences. Information and Computation, 187:49–79, 2003.
15. 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.
16. Ethan McCarthy. Cototal enumeration degrees and their application to computable mathematics. Proceedings of the AMS, 146:3541–3552, 2018.
17. Joseph S. Miller. Degrees of unsolvability of continuous functions. Journal of Symbolic Logic, 69(2):555 – 584, 2004.
18. Joseph S. Miller and Mariya I. Soskova. Density of the cototal enumeration degrees. Annals of Pure and Applied Logic, 2018.
19. Yiannis N. Moschovakis. Descriptive Set Theory, volume 100 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1980.
20. 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.
21. 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.
22. Arno Pauly and Matthew de Brecht. Non-deterministic computation and the Jayne Rogers theorem. Electronic Proceedings in Theoretical Computer Science, 143, 2014. DCM 2012.
23. 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.
24. Matthias Schröder. Extended admissibility. Theoretical Computer Science, 284(2):519–538, 2002.
25. Matthias Schröder. Spaces allowing type-2 complexity theory revisited. Mathematical Logic Quarterly, 50(4/5):443–459, 2004.
26. Matthias Schröder and Victor Selivanov. Hyperprojective hierarchy of QCB0-spaces. Computability, 4, 2015. arXiv 1404.0297.
27. 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.
28. Victor L. Selivanov. Difference hierarchy in φ-spaces. Algebra and Logic, 43(4):238–248, 2004.
29. Victor L. Selivanov. Towards a descriptive set theory for domain-like structures. Theoretical Computer Science, 365(3):258–282, 2006.

Creative Commons BY 4.0

Mathieu Hoyrup, Arno Pauly, Victor Selivanov, and Mariya I. Soskova