On Computable Metric Spaces Tietze-Urysohn Extension Is Computable

摘要

In this paper we prove computable versions of Urysohn's lemma and the Tietze-Urysohn extension theorem for computable metric spaces. We use the TTE approach to computable analysis [KW85,Wei00] where objects are represented by finite or infinite sequences of symbols and computations transform sequences of symbols to sequences of symbols. The theorems hold for standard representations of the metric space, the set of real numbers, the set of closed subsets and the set of continuous functions. We show that there are computable procedures determining the continuous functions from the initial data (closed sets, continuous functions). The paper generalizes results by Yasugi, Mori and Tsujii [YMT9] in two ways: (1) The Tietze-Urysohn extension applies not only to “strictly effectively σ-compact co-r.e.” sets but to all co-r.e. closed sets. (2) Not only computable functions exist for computable sets and functions, respectively, but there are computable procedures which determine continuous functions from arbitrary closed sets and continuous functions, respectively. These procedures, however, are not extensional on the names under consideration, and so they induce merely multi-valued computable functions on the objects.