Computability on Quasi-Polish Spaces

Mathieu Hoyrup, Cristobal Rojas, Victor L. Selivanov, Donald M. StullDCFS 2019 · DOI · OpenReview

Abstract

In classical mathematics, Descriptive Set Theory (DST) provides a powerful framework for studying Polish spaces. However, computer science frequently encounters non-Hausdorff structures, such as Scott domains, which require the broader class of quasi-Polish spaces. This paper investigates the "effectivization" of these spaces, seeking a definition for effective quasi-Polish spaces that is both robust and mathematically versatile. The authors demonstrate that the most stable definition is based on computable, effectively open images of the Baire space. Crucially, they reveal a fundamental divergence from classical theory: while all classical quasi-Polish spaces are quasi-metrizable, this equivalence does not hold in the computable realm.

Introduction

Descriptive Set Theory (DST) has traditionally focused on Polish spaces—topological spaces that are both complete and separable. While these spaces are ideal for modeling the real numbers or other Hausdorff settings, they are often insufficient for the non-Hausdorff structures prevalent in theoretical computer science, such as the domains used in denotational semantics.

Quasi-Polish spaces were introduced to extend the reach of DST to these non-Hausdorff environments. While the classical theory of quasi-Polish spaces is well-understood, the "effective" or computable version of this theory remained fragmented. This paper addresses this gap by identifying a robust definition of effective quasi-Polish spaces that aligns with existing notions of computable Polish spaces and $\omega$-continuous domains.

Defining Effective Quasi-Polish Spaces

The authors seek a definition that satisfies three primary criteria: robustness (admitting multiple equivalent characterizations), inclusiveness (subsuming existing classes like computable Polish spaces), and functionality (supporting a rich effective DST hierarchy).

To achieve this, they employ tools from Computable Analysis and Effective DST. A central component of their approach is the Baire space ($\mathcal{N}$), the space of infinite sequences of natural numbers, which serves as a universal starting point. By defining effective quasi-Polish spaces as the computable, effectively open images of the Baire space, the authors establish a definition that is remarkably stable.

Another key tool is the Scott domain $\mathcal{P}(\omega)$ (the power set of natural numbers). By mapping topological spaces into this domain, the authors can analyze their properties through the lens of enumeration operators. They also utilize the concept of computable overtness, which describes sets where one can effectively list the basic open sets they intersect.

The Metric Gap: A Fundamental Divergence

One of the most significant contributions of this work is the discovery of the "Metric Gap." In classical topology, a space is quasi-Polish if and only if it is completely quasi-metrizable. This equivalence is a cornerstone of the classical theory.

However, the authors prove that this equivalence fails in the computable world. They demonstrate that some effective quasi-Polish spaces cannot be represented by computable (specifically, right-c.e.) quasi-metrics. This suggests that the topological definition of effectiveness is more general than the metric-based one.

To illustrate this, the authors use specific real numbers tied to the halting problem to construct counterexamples. For a subspace defined by the interval $[ \alpha, 1 ]_<$, they show that whether the space is effectively quasi-Polish or computably quasi-metric depends entirely on the specific computability properties of the boundary $\alpha$.

Key Results and Theorems

The paper culminates in several pivotal results that solidify the proposed framework:

  • Theorem 4.1 (Characterization): This theorem establishes three equivalent characterizations of effective quasi-Polish spaces, confirming that the definition is mathematically sound and robust.
  • Theorem 5.2: The authors show that every complete, right-c.e. quasi-metric space is an effective quasi-Polish space, providing a bridge between the metric and topological views.
  • Corollary 6.1 (The Divergence): This corollary formally proves the existence of an effective quasi-Polish space that lacks a right-c.e. quasi-metric presentation, highlighting the unique nature of effective topology.

Furthermore, the authors confirm that their definition successfully subsumes all previously studied computable Polish spaces and computable $\omega$-continuous domains, ensuring backward compatibility with established research.

Conclusion and Future Directions

By establishing a "correct" definition for effective quasi-Polish spaces, this paper provides a foundation for a more comprehensive effective Descriptive Set Theory. However, the authors note that classical quasi-Polish spaces possess numerous characterizations—at least ten—many of which have not yet been effectivized.

Future research may explore whether these spaces can be characterized as subspaces of non-compact elements in $\omega$-algebraic or $\omega$-continuous domains. Additionally, the relationship between these findings and other existing notions of computable metrizability remains a fertile ground for investigation.

Summary updated

Abstract

We investigate the effectivizations of several equivalent definitions of quasi-Polish spaces and study which characterizations hold effectively. Being a computable effectively open image of the Baire space is a robust notion that admits several characterizations. We show that some natural effectivizations of quasi-metric spaces are strictly stronger.
BibTeX
@inproceedings{hoyrup2019computability,
  author = {Mathieu Hoyrup and Cristobal Rojas and Victor L. Selivanov and Donald M. Stull},
  title = {{Computability on Quasi-Polish Spaces}},
  booktitle = {DCFS},
  year = {2019},
  doi = {10.1007/978-3-030-23247-4\_13},
}

Loading related content...

Figure