Computable Bases

Basic Information

• Paper ID: 2510.09850
• Title: Computable Bases
• Authors: Vasco Brattka (Universität der Bundeswehr München & University of Cape Town), Emmanuel Rauzy (Université Paris-Est Créteil)
• Classification: math.LO (Logic)
• Publication Date: October 14, 2025
• Paper Link: https://arxiv.org/abs/2510.09850

Abstract

In computable analysis, topological spaces with countable bases are typically considered. The Kreitz-Weihrauch theorem establishes that subbasis representations of second-countable $T_0$ spaces are admissible with respect to the topology generated by the subbasis. This paper generalizes this setting to representable but not necessarily countable bases. The authors introduce the concepts of computable presubbase and computable prebase, proving a generalization of the Kreitz-Weihrauch theorem for presubbase representations, demonstrating that any such representation is admissible with respect to the topology generated by compact intersections of presubbase elements. For computable prebases, representations are obtained that are admissible with respect to the topology they generate. These concepts provide natural methods for studying many topological spaces in computable analysis.

Research Background and Motivation

Problem Background

1. Traditional Limitations: Classical computable analysis is primarily restricted to topological spaces with countable bases, limiting the scope of the theory
2. Limitations of the Kreitz-Weihrauch Theorem: The classical Kreitz-Weihrauch theorem applies only to second-countable $T_0$ spaces and cannot handle more general topological spaces
3. Demands of Representation Theory: A unified framework is needed to handle representations of different types of topological spaces

Research Motivation

1. Theoretical Refinement: Extending the foundational theory of computable analysis to more general topological spaces
2. Practical Applications: Providing a computability framework for uncountable topological spaces encountered in practice
3. Unified Perspective: Uniformly treating different topological constructions through the concept of presubbases

Core Contributions

1. Introduction of New Concepts: Proposing the concepts of computable presubbase and computable prebase, generalizing traditional countable subbase theory
2. Main Theorem: Proving the presubbase theorem (Theorem 7), an important generalization of the Kreitz-Weihrauch theorem
3. Topological Characterization: Establishing equivalences between computable Kolmogorov spaces and various types of bases (Theorem 23)
4. Closure Properties: Proving closure properties of computable Kolmogorov spaces under various topological constructions
5. Galois Connection: Revealing the underlying Galois connection structure between presubbases and representations

Methodology Details

Core Concept Definitions

Presubbase

Definition 5: Let $X$ be a set. A family $(B_y)_{y \in Y}$ is called a presubbase of $X$ if $Y$ is a represented space and its transpose $B^T: X \to \mathcal{O}(Y), \quad x \mapsto \{y \in Y: x \in B_y\}$ is well-defined and injective.

Presubbase Representation

Definition 6: Given a presubbase $(B_y)_{y \in Y}$, the presubbase representation $\delta^B: \subseteq \mathbb{N}^\mathbb{N} \to X$ is defined as $\delta^B(p) = x \iff \delta_{\mathcal{O}(Y)}(p) = \{y \in Y: x \in B_y\}$

Main Theoretical Results

Presubbase Theorem

Theorem 7: Let $(B_y)_{y \in Y}$ be a presubbase of a set $X$. Then $(X, \delta^B)$ is a computable Kolmogorov space, and $\delta^B$ is admissible with respect to the topology $\tau$ generated by the base set $X$ and $\bigcap_{y \in K} B_y$ for each compact set $K \subseteq Y$.

Characterization of Computable Kolmogorov Spaces

Theorem 23: For a represented space $X$, the following conditions are equivalent:

1. $X$ is a computable Kolmogorov space
2. $X$ has a computable presubbase
3. $X$ has a computable prebase
4. $X$ has a computable base
5. $X$ has a computable Lacombe base
6. $\text{id}: \mathcal{O}(X) \to \mathcal{O}(X)$ is a computable Lacombe base of $X$

Technical Innovations

1. Compact Intersection Topology: Using intersections of compact sets rather than finite intersections to define the topology, a key innovation
2. Sequential Processing: Handling differences between general and countable cases through sequentialization of topologies
3. Hyperspace Methods: Utilizing relationships between Scott topology and compact-open topology
4. Transposition Technique: Establishing connections between bases and representations through the transpose mapping $B^T$

Experimental Setup

This is a pure theoretical mathematics paper and contains no experimental section. All results are obtained through rigorous mathematical proofs.

Main Results

Theoretical Results

Closure Properties

Corollary 31: If $X$ and $Y$ are computable Kolmogorov spaces, then the following spaces are also computable Kolmogorov spaces:

1. $X \times Y$, $X \sqcup Y$, $X \sqcap Y$, $Y^\mathbb{N}$, and every subspace of $X$
2. $C(X,Y)$, $\mathcal{O}(X)$, $\mathcal{A}^+(X)$, $\mathcal{A}^-(X)$, $\mathcal{A}(X)$, $\mathcal{K}^-(X)$, and $\mathcal{K}(X)$

Topological Characterization

Corollary 33: For represented $T_0$ spaces $X$ and $Y$:

1. $\mathcal{O}(X \times Y) = \text{seq}(\mathcal{O}(X) \otimes \mathcal{O}(Y))$
2. $\mathcal{O}(X^\mathbb{N}) = \text{seq}(\bigotimes_{i \in \mathbb{N}} \mathcal{O}(X))$
3. $\mathcal{O}(Z) = \text{seq}(\mathcal{O}(X)|_Z)$ (for subspace $Z \subseteq X$)
4. $\mathcal{O}(X \sqcap Y) = \text{seq}(\mathcal{O}(X) \wedge \mathcal{O}(Y))$

Hyperspace Topology

Theorem 35: For a represented space $X$ and a $T_0$ space $Y$ with admissible representation:

1. $\mathcal{O}(X)$ has the Scott topology, which is the sequentialization of the compact-open topology
2. $\mathcal{K}^-(X)$ and $\mathcal{K}(X)$ have the upper Vietoris and Vietoris topologies sequentialized
3. $\mathcal{A}^+(X)$ and $\mathcal{A}(X)$ have the lower Fell and Fell topologies sequentialized
4. $C(X,Y)$ has the compact-open topology sequentialized

Galois Connection

Theorem 36: For fixed representable space $X$, each $\delta \in \text{REP}_0$ and $B \in \text{PRE}_0$, $\delta \leq \delta^B \iff B \leq B_\delta$

This establishes an order-reversing Galois connection between representations and presubbases.

Related Work

Historical Development

1. Kreitz-Weihrauch (1985): Established admissibility theory for countable subbases
2. Schröder (2002): Developed general theory of computable topology, introducing the concept of qcb spaces
3. de Brecht et al. (2016): Investigated complexity classification of general indexed bases

Contributions Compared to Prior Work

1. Scope of Generalization: Extending from countable bases to general representable bases
2. Unified Framework: Providing a unified method for handling various topological constructions
3. Theoretical Depth: Revealing the underlying Galois connection structure between representations and bases

Conclusions and Discussion

Main Conclusions

1. Theoretical Refinement: Successfully generalizing the Kreitz-Weihrauch theorem to the uncountable case
2. Equivalent Characterizations: Establishing multiple equivalent characterizations of computable Kolmogorov spaces
3. Closure Properties: Proving important closure properties demonstrating the stability of the theory
4. Practical Value: Providing tools for computability analysis of practical topological spaces

Limitations

1. Complexity: The general case requires handling compact intersections rather than finite intersections, increasing complexity
2. Sequentialization: Many results yield only sequentialized topologies rather than the original topologies
3. Open Problems: Problem 24 concerning the relationship between computable bases and Lacombe bases remains unsolved

Future Directions

1. Algorithm Implementation: Developing concrete algorithms for handling computations with uncountable bases
2. Application Extension: Applying the theory to more concrete mathematical domains
3. Complexity Analysis: Investigating computational complexity of different types of bases

In-Depth Evaluation

Strengths

1. Theoretical Depth: The paper has high theoretical value, generalizing important classical results
2. Systematicity: Establishing a complete theoretical framework with tight connections between concepts
3. Technical Innovation: The treatment of compact intersection topology and Galois connections demonstrates profound mathematical insight
4. Applicability: Providing tools for computable analysis to handle more general spaces

Weaknesses

1. Level of Abstraction: The theory is quite abstract, lacking concrete application examples
2. Computational Complexity: Insufficient analysis of computational complexity for practical computation
3. Open Problems: Leaving some important unresolved questions

Impact

1. Disciplinary Contribution: Important contribution to the intersection of computable analysis and topology
2. Theoretical Value: Providing important theoretical tools for subsequent research
3. Long-term Influence: Potentially influencing the development direction of computable mathematics

Applicable Scenarios

1. Theoretical Research: Applicable to theoretical research in computable analysis and topology
2. Space Analysis: Applicable to computational problems requiring handling of uncountable topological spaces
3. Foundational Mathematics: Providing new theoretical foundations for computational mathematics

References

The paper cites important literature in computable analysis, including:

• Kreitz & Weihrauch (1985): Establishing classical subbase representation theory
• Schröder (2002a, 2002b): Developing systematic theory of computable topology
• Pauly (2016): Providing concise introduction to computable topology
• de Brecht, Schröder & Selivanov (2016): Investigating base complexity classification of QCB₀ spaces

This paper is an important theoretical contribution to computable analysis. By introducing the concepts of presubbase and prebase, it successfully generalizes the classical Kreitz-Weihrauch theorem to more general settings, providing powerful theoretical tools for handling uncountable topological spaces.