CS Paper Radar

Effective quasi-Polish categories of overt discrete spaces and compact Hausdorff spaces

Matthew de Brecht

cs.LO math.CTmath.LO ·submitted 2026-08-24 09:54 UTC · v1
unusual

Abstract

We construct the category of overt discrete quasi-Polish spaces and the category of compact Hausdorff quasi-Polish spaces (and some of their subcategories) as internal categories of the category of effective quasi-Polish spaces and computable maps. To demonstrate that the constructions are natural, we show that Stone duality is computable, in the sense that the dual contravariant functors and the natural transformations demonstrating their adjointness are computable.

Closest papers

Nearest neighbours by meaning across the whole index.

From Zero-Dimensional to Continuous Dualities: A Double-Categorical Account

cs.LO math.CTmath.GNmath.LO ·2026-10-06 ·Alexander Kurz, M. Andrew Moshier, Achim Jung
similarity 0.67
Abstract

We investigate how to systematically construct continuous dualities from zero-dimensional dualities, employing well-known methods from algebra, topology, category theory, and domain theory. While our method is general, this paper focusses on the move from Stone spaces to compact Hausdorff spaces and the move from Priestley spaces to compact ordered Hausdorff spaces. The engine of our approach is Stone duality for relations: on the space side quotienting by a preorder turns zero-dimensional spaces into continuous ones, while distributive lattices with a proximity relation are their algebraic duals. Our duality for relations is inherently order-enriched. Double categories organise both functional and relational morphism in the same structure. The move from zero-dimensional to continuous dualities is then a three-step construction: extend a duality from functional to relational morphism, split idempotents, restrict to maps.

0.17

On U_c-admitting spaces and U_c-completions of T_0 spaces

cs.LO math.GN ·2026-10-22 ·Kangming Lu, Qingguo Li, Shengwen Wang, Rongqi Xiao
theory similarity 0.59
Abstract

In this paper, we introduce a new class of spaces, termed U_c-admitting spaces, and investigate their relationships with U_s-admitting spaces and well-filtered spaces. Adopting the perspective of H-sobriety, we show that every U_c-admitting space is H-sober, so that U_c-admitting spaces arise as a special case of H-sober spaces. Consequently, the category U_c-Sob of U_c-admitting spaces and continuous maps is complete and forms a reflective subcategory of Top_0. In addition, we prove that a T_0 space X is U_c-admitting if and only if its Smyth power space is U_c-admitting. Finally, we present the standard U_c-completion of an arbitrary T_0 space.

0.25

Metrization of Quasi-Uniformities, Powerset Monads, and Qualitative Robustness Analysis

cs.LO math.GN ·2026-09-02 ·Francesco Dagnino, Amin Farjudian, Eugenio Moggi
theory similarity 0.53
Abstract · 24 pages

We study the relationship between quasi-uniform spaces, topological spaces, and quantale-valued metric spaces. Our main result is a metrization theorem establishing an equivalence between the category of quasi-uniform spaces and a category of quantale-valued metric spaces. We also obtain a quantale-based metrization theorem for arbitrary topological spaces that refines existing constructions. These results identify quasi-uniformities as the appropriate qualitative counterpart of quantale-valued metrics. Building on this correspondence, we show that the Hausdorff-Smyth monad on quantale-valued metric spaces, which is used in quantitative robustness analysis, arises as a lifting of a corresponding monad on quasi-uniform spaces along the equivalence. This provides a unified categorical framework connecting topology, quasi-uniformity, and quantitative robustness analysis.

0.23

Cartesian closedness of lax comma categories

cs.PL math.CTmath.LO ·2026-10-31 ·Maria Manuel Clementino, Fernando Lucatelli Nunes
theory similarity 0.52
Abstract · 7 pages

For a finitely complete category X, we prove that the lax comma category Cat//X is cartesian closed if and only if its free coproduct completion Fam(X) is cartesian closed. The proof uses a change-of-base theorem: postcomposition with a functor induces a left adjoint between lax comma categories precisely when that functor is a left multiadjoint. We describe the exponentials and derive examples from known results on family categories.

0.23

The category of nominal sets is locally monoidal closed

cs.LO math.CT ·2026-09-18 ·Fahimeh Bayeh, Peng Fu, Peter Selinger
published similarity 0.52
Abstract

The category Nom of nominal sets was proposed by Pitts and Gabbay as a setting for the semantics of abstract syntax with variable bindings. It is well-known that Nom is a topos, also known as the Schanuel topos, and in particular it follows that Nom is locally closed, i.e., every slice category Nom/X is cartesian-closed. In this paper, we show that Nom has a much stronger property: every monoidal (closed) structure on Nom induces a monoidal (closed) structure on all slice categories Nom/X. One monoidal closed structure of particular interest on Nom is the separated product A * B, whose right adjoint A -* B is called the separated function space. In particular, it follows that Nom is locally separatedly closed.

0.37

Freely Generated Categorical Structures and Automatic Differentiation, PhD Thesis (Introduction and Conclusion)

cs.PL cs.LOmath.CT ·2026-09-30 ·Fernando Lucatelli Nunes
similarity 0.49
Abstract · PhD thesis, Utrecht University, 2026. Introduction, conclusion, and English and Dutch summaries only; the six research papers constituting C…

This version contains the introduction and conclusion of my PhD thesis, "Freely Generated Categorical Structures and Automatic Differentiation", together with its English and Dutch summaries. The full thesis consists of an introductory chapter, six joint research papers, and a concluding chapter, developed during my PhD studies at Utrecht University under the supervision of Gabriele Keller and Matthijs Vákár. The research papers are available separately and are not reproduced here. The introduction presents the scope of the thesis, explains the contributions of the six papers and their connections, and introduces the categorical foundations of our approach. The guiding idea is that programming languages, viewed as freely generated categorical structures, provide a principled setting for constructing structure-preserving program transformations and proving their correctness. Automatic differentiation supplies the central application: we study forward- and reverse-mode differentiation for expressive typed languages, including higher-order functions, recursive types, iteration and partiality. The semantic requirements of these transformations also motivate independent mathematical results on free distributive and extensive categories, cartesian closedness, and Grothendieck constructions. The conclusion brings these contributions together, discusses their limitations, and outlines further directions. Throughout, the thesis develops a dialogue between theory and practice: categorical semantics guides the construction of reliable and practically useful program transformations, while the demands of computation lead to new categorical structures and results.

0.22

Type classifiers

cs.LO math.CT ·2026-10-30 ·Martin E. Bidlingmaier
similarity 0.49
Abstract · 7 pages

We extend dependent type theory by type classifiers and construct an interpretation in the category of contextual categories with families. Type classifiers extend contexts by type variables, complementing the usual context extensions by term variables of specified types. This allows statements with arbitrary type parameters to be formulated without assuming a universe. We show that substituting isomorphic types induces isomorphisms between the resulting types even in extensional type theory, giving an analogue of the invariance supplied by the univalence axiom in homotopy type theory. Omitting function types from the theory, so that all type formers are covariant, extends this naturality to arbitrary, possibly noninvertible maps.

0.25

Monad Structures on Topological Spaces Comprising Mislove's Random Variables

cs.LO ·2026-08-19 ·Chengyu Zhou, Qingguo Li
similarity 0.48
Abstract

Mislove, Goubault and Varacca investigated how to define random variables in Domain theory to form monads over the category of bounded complete domains. They intended to model probabilistic programming languages with their random variables monads. In this paper, we focus on the random variables defined by Mislove from a topological perspective. We provide a topology for $\surd$-max continuous random variables on a $T_0$ space, we construct a new $T_0$ space, where $\surd$-max property is essential for the monad structures. We show that the spaces of normalized $\surd$-max simple random variables form a monad over the category of $T_0$ spaces and that the spaces of normalized $\surd$-max continuous random variables give a monad over the category of d-spaces. In addition, on a sober space, the space of normalized $\surd$-max continuous random variables is the sobrification of the space of normalized $\surd$-max simple random variables.

0.22