A comparison of concepts from computable analysis and effective descriptive set theory

Abstract

Computable analysis and effective descriptive set theory are both concerned with complete metric spaces, functions between them and subsets thereof in an effective setting. The precise relationship of the various definitions used in the two disciplines has so far been neglected, a situation this paper is meant to remedy. As the role of the Cauchy completion is relevant for both effective approaches to Polish spaces, we consider the interplay of effectivity and completion in some more detail.

accepted for publication in the special issue of "Mathematical Structures in Computer Science" dedicated to CCC 2013

References in corpus (4)

• Non-deterministic computation and the Jayne-Rogers Theorem
• Total Representations
• Towards Synthetic Descriptive Set Theory: An instantiation with represented spaces
• Products of effective topological spaces and a uniformly computable Tychonoff Theorem

Cited by in corpus (4)

• Finding descending sequences through ill-founded linear orders
• Game characterizations and lower cones in the Weihrauch degrees
• Effective aspects of Hausdorff and Fourier dimension
• Computable analysis on the space of marked groups