Computability on measurable functions

Abstract

For a computable measure space with computable σ-finite measure we study computability on the space of measurable functions. First we prove that for a natural multi-representation finite union and intersection and countable union are computable. We introduce a natural multi-representation of the measurable functions to a computable topological space and prove that composition with continuous functions is computable. Canonically, for a computable metric space the associated computable topological space has a basis of balls $B (a, s)$ with center from the dense set and rational radius. From a given sequence ${(μ_{k})}_{k}$ of finite Borel measures we can compute a dense sequence ${(r_{j})}_{j}$ of radii such that $μ_{k} (S) = 0$ for all k and all spheres $S = S (a, r_{j})$ with a from the dense set and $j \in N$ . For measurable functions to computable compact computable metric spaces the natural multi-representation is equivalent to a multi-representation via fast uniformly converging sequences of simple functions. For non-negative measurable numerical functions the sequences can be chosen to be non-decreasing. Some results on integration are added.

Keywords

Computable analysis measurable functions

1. Introduction

In this article we study computability in elementary measure theory in the framework of TTE (Type 2 theory of effectivity, the representation approach). TTE has turned out to be the most useful approach for studying and understanding computability and computational complexity in Analysis [1,8,9,11,17,19]. This article continues [20] (which is of free open access) where several new representations of measurable sets have been introduced.

In measure theory measurable sets, measurable functions, integrable functions etc. and the corresponding equivalence classes w.r.t. the measure are studied simultaneously. In Section 2 we summarize some technical definitions of TTE. Then we study how computability of multi-functions induced by multi-representations of point sets with equivalence relations is related to computability induced by the corresponding representation of the set of equivalence classes.

In Section 3 we define three multi-representations $ζ_{+}$ , $ζ_{-}$ and ζ of the measurable sets for a computable measure on a computable σ-algebra. They correspond straightforwardly to three representations of the equivalence classes of measurable sets introduced in [20].

In Section 4 we show that finite union and intersection are computable for $ζ_{+}$ , $ζ_{-}$ and ζ and that countable union is computable for $ζ_{+}$ .

In Section 5 we define three multi-representations of the measurable functions from a computable measure space to a computable topological space. We prove their equivalence and show that composition with continuous functions is a computable operator.

In Section 6 we consider computable Borel measures on computable metric spaces. Let D be the dense set of the computable metric space. As a technical result we prove that from a sequence ${(μ_{i})}_{i \in N}$ of finite Borel measures we can compute a dense sequences ${(r_{i})}_{i \in N}$ of radii such that $μ_{i} (S) = 0$ for all i and all spheres $S = S (a, r_{j})$ with $a \in D$ and $j \in N$ .

In Section 7 we show that the limit operator on fast uniformly converging Cauchy sequences of measurable functions to a computable metric space is computable. On the other hand, if the space is computable compact then for every measurable function we can compute a sequence of simple functions converging to it fast uniformly.

A non-negative function $f : Ω \to \overline{R}$ is measurable iff $f = {sup}_{n} s_{n}$ for a sequence $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots$ of simple functions $s_{n} : Ω \to R$ . In this Section 8 we study computability on the measurable numerical functions $f : Ω \to \overline{R}$ and in particular prove a computable version of this theorem. Finally in Section 9 we study computable integration of measurable functions.

2. Basic TTE, factorization of multi-representations

For studying computability we use the TTE, representation approach to computable analysis [1,17]. Let Σ be a fixed finite alphabet such that $0, 1 \in Σ$ . $Σ^{*}$ denotes the set of finite words over Σ and $Σ^{ω}$ denotes the set of infinite sequences $p : N \to Σ$ . A partial function $f : \subseteq Y_{1} \times \dots \times Y_{k} \to Y_{0}$ (where $Y_{i} = Σ^{*}$ or $Y_{i} = Σ^{ω}$ ) is computable, iff it can be computed by a Type-2 Turing machine. For encoding pairs and longer tuples of elements from $Σ^{*}$ and $Σ^{ω}$ we use tupling functions all of which are denoted by $⟨ ⟩$ [17, Definition 2.1.7]. For the wrapping function $ι : Σ^{*} \to Σ^{*}$ , $ι (a_{1} a_{2} \dots a_{k}) : = 110 a_{1} 0 a_{2} \dots 0 a_{k} 011$ , two wrapped words cannot overlap properly. For $w_{i} \in Σ^{*}$ and $p_{i} \in Σ^{ω}$ let $⟨ w_{1}, \dots, w_{n} ⟩ : = ι (w_{1}) ι (w_{2}) \dots ι (w_{n})$ , $⟨ w_{0}, p_{0} ⟩ : = ⟨ p_{0}, w_{0} ⟩ : = ι (w_{0}) p_{0} \in Σ^{ω}$ , $⟨ p_{0}, p_{1} ⟩ : = (p_{0} (0) p_{1} (0) p_{0} (1) p_{1} (1) \dots)$ , $⟨ p_{0}, p_{1}, \dots ⟩ ⟨ i, j ⟩ : = p_{i} (j)$ (where $π : N^{2} \to N$ , $⟨ i, j ⟩ = π (i, j)$ is a standard computable bijection), etc. The tupling functions and the projections of their inverses are computable. We will use definitions of the form “p is a list of all pairs $(u, v) \in Σ^{*} \times Σ^{*}$ such that $Q (u, v)$ ” meaning: $ι (⟨ u, v ⟩)$ is a subword of p iff $Q (u, v)$ .

We use canonical representations $ν_{N} : \subseteq Σ^{*} \to N$ , $ν_{Q} : \subseteq Σ^{*} \to Q$ , of the natural numbers and the rational numbers, respectively. For the real numbers let $ρ_{<} (p) = x$ iff p is a list of all u such that $ν_{Q} (u) < x$ , $ρ_{>} (p) = x$ iff p is a list of all u such that $ν_{Q} (u) > x$ and $ρ ⟨ p, q ⟩ = x$ iff $ρ_{<} (p) = x$ and $ρ_{>} (q) = x$ .

A representation of a set X is a partial surjective function $δ : \subseteq Y \to X$ where $Y = Σ^{*}$ or $Y = Σ^{ω}$ . For representations $δ_{i} : \subseteq Y_{i} \to X_{i}$ ( $i = 1, 2$ ), a function $h : \subseteq Y_{1} \to Y_{2}$ (operating on names) realizes the (abstract) function $f : \subseteq X_{1} \to X_{2}$ , iff $f \circ δ_{1} (p) = δ_{2} \circ h (p)$ for all $p \in dom (f \circ δ_{1})$ . A function f is called $(δ_{1}, δ_{2})$ -continuous (-computable), iff it is realized by a continuous (computable) function. A representation $δ_{1}$ is reducible to (translatable to) $δ_{2}$ , $δ_{1} ⩽ δ_{2}$ , iff the identity function $id : x \mapsto x$ is $(δ_{1}, δ_{2})$ -computable, that is, there is a computable function h such that $δ_{1} (p) = δ_{2} \circ h (p)$ for all $p \in dom (δ_{1})$ . Correspondingly, $δ_{1}$ is topologically reducible to $δ_{2}$ , $δ_{1} ⩽_{t} δ_{2}$ , iff there is a continuous function h such that $δ_{1} (p) = δ_{2} \circ h (p)$ for all $p \in dom (δ_{1})$ . The two representations are equivalent, $δ_{1} \equiv δ_{2}$ , iff $δ_{1} ⩽ δ_{2}$ and $δ_{2} ⩽ δ_{1}$ . Accordingly, they are topologically equivalent, $δ_{1} \equiv_{t} δ_{2}$ , iff $δ_{1} ⩽_{t} δ_{2}$ and $δ_{t} ⩽_{t} δ_{1}$ . Equivalent representations induce the same computability on the represented sets. For more details see [1,17].

Formally, a multi-function $f : X ⇉ Y$ is a triple $f = (X, Y, R)$ where $R \subseteq X \times Y$ . The set $dom (f) : = {x \in X ∣ (\exists y \in Y) (x, y) \in R}$ is called the domain of f. A multi-function f is called single-valued or a partial function denoted by $f : \subseteq X \to Y$ as usual, if for every $x \in dom (f)$ there is exactly one $y \in Y$ such that $(x, y) \in R$ which is called $f (x)$ .

Usually, for a multi-function $f : X ⇉ Y$ , $x \in dom (f)$ and $A \subseteq dom (f)$ , $f (x) : = {y \in Y ∣ (x, y) \in R}$ and $f [A] : = {y \in Y ∣ (\exists x \in A) (x, y) \in R}$ .

If f is single-valued and $(x, y) \in R$ then $f (x) = y$ on the one hand and $f (x) = {y}$ on the other hand. For avoiding this formal inconsistency, in this section we do not use “ $f (x)$ ” for multi-functions f and introduce two new functions, instead.

Definition 2.1.
Let $f = (X, Y, R)$ be a multi-function. Define partial functions $f^{} : \subseteq X \to 2^{Y}$ and $f^{+} : \subseteq 2^{X} \to 2^{Y}$ by $\begin{array}{l} dom (f^{}) : = dom (f), \\ f^{} (x) : = {y \in Y ∣ (x, y) \in R}, \\ A \in dom (f^{+}) : ⟺ A \subseteq dom (f), \\ f^{+} (A) : = {y \in Y ∣ (\exists x \in A) (x, y) \in R} . \end{array}$

The multi-function $f = (X, Y, R)$ is well-defined by $f^{}$ and also by $f^{+}$ since $(x, y) \in R ⟺ y \in f^{+} ({x}) = f^{} (x)$ . Notice that ${x} \in dom (f^{+}) ⟺ x \in dom (f)$ and $f^{+} (A) = ⋃_{x \in A} f^{+} ({x})$ for $A \in dom (f^{+})$ . If $f : \subseteq X \to Y$ is a partial function then $f^{+} ({x}) = f^{} (x) = {f (x)}$ .

We will use multi-functions with two different meanings of “ $(x, y) \in R$ ” depending on the context: [18, Section 3]: $\begin{array}{l} (1) & x is a name (or f -name) of y, \\ (2) & f maps x to some y \in f^{} (x) . \end{array}$

In the case of (1) we call f a “multi-representation”. Usually $X = N, Σ^{}$ or $Σ^{ω}$ . In general for a multi-representation $β : X ⇉ Y$ , $range (β^{})$ is not a partition.1
¹
A non-trivial useful example is the multi-representation $[γ \to_{p} δ]$ of the partial functions $f : \subseteq X \to Y$ with continuous realizations for representations $γ : \subseteq Σ^{ω} \to X$ and $δ : \subseteq Σ^{ω} \to Y$ [17,19].

The meaningful composition for multi-representations is the relational composition2
²
For $f = (X, Y, R)$ and $g = (Y, Z, S)$ , $g ⊙ f : = (X, Z, T)$ where $T : = {(x, z) ∣ (\exists y) ((x, y) \in R \land (y, z) \in S)}$ .

which, however, we will not use in this article [18, Lemma 22].

If we study computability of a multi-function we use the interpretation (2).3
³
As an example consider the multi-function $f : R ⇉ N$ mapping every real number to some upper bound in $N$ , $f^{} : x \mapsto {n \in N ∣ x < n}$ often written as $f : x \mapsto {n \in N ∣ x < n}$ .

In this case in [18, Definition 6] composition of multi-functions $f : X ⇉ Y$ and $g : Y ⇉ Z$ is usually defined as follows: $x \in dom (g \circ f)$ iff $x \in dom (f)$ and $f (x) \subseteq dom (g)$ and $(g \circ f) (x) : = g [f (x)]$ . In our terminology ${(g \circ f)}^{+} ({x}) = g^{+} \circ f^{+} ({x})$ . Since $f^{+} (A) = ⋃_{x \in A} f^{+} ({x})$ we obtain:
Lemma 2.2.
For multi-functions $f : X ⇉ Y$ and $g : Y ⇉ Z$ , ${(g \circ f)}^{+} = g^{+} \circ f^{+}$ .

Here $g^{+} \circ f^{+}$ is the well-known composition of partial functions, such that $A \in dom ({(g \circ f)}^{+})$ iff $A \in dom (f^{+})$ and $f^{+} (A) \in dom (g^{+})$ . Suppose f and g are partial functions, that is, single-valued multi-functions. Then ${(g \circ f)}^{+} ({x}) = g^{+} \circ f^{+} ({x}) = g^{+} ({f (x)}) = {g (f (x))}$ , hence $(g \circ f) (x) = g (f (x))$ . Therefore, in this special case the composition $g \circ f$ defined for multi-functions coincides with the ordinary composition of partial functions as expected. Since composition of partial functions is associative, it follows straightforwardly from Lemma 2.2 that composition of multi-functions is associative.

According to the interpretations (1) and (2) realization is defined as follows.
Definition 2.3.
Let $γ : Σ^{ω} ⇉ X$ and $δ : Σ^{ω} ⇉ Y$ be multi-representations.
Let $f : X ⇉ Y$ be a multi-function. Then a function $F : \subseteq Σ^{ω} \to Σ^{ω}$ realizes f w.r.t. $(γ, δ)$ iff $\begin{array}{rcl} (3) & (\forall x \in dom (f)) (\forall p) (x \in γ^{} (p) ⟹ f^{} (x) \cap δ^{} (F (p)) \neq \emptyset) . \end{array}$

The multi-function f is $(γ, δ)$ -continuous (-computable), iff it has a continuous (computable) realization [18, Definition 17].

γ is continuously reducible to δ, $γ ⩽_{t} δ$ , iff $X \subseteq Y$ and the embedding $x \mapsto x$ is $(γ, δ)$ -continuous. γ is reducible to δ, $γ ⩽ δ$ , iff $X \subseteq Y$ and the embedding $x \mapsto x$ is $(γ, δ)$ -computable.

Notice that $x \in γ^{} (p)$ means “p is a γ-name of x”. Therefore, F realizes the multi-function f iff $F (p)$ is a δ-name of some $y \in f^{} (x)$ whenever p is a γ-name of x. By (3), $γ ⩽_{t} δ$ iff $γ^{} (p) \subseteq δ^{} \circ F (p)$ for some continuous F and $γ ⩽ δ$ iff $γ^{} (p) \subseteq δ^{} \circ F (p)$ for some computable F.4
⁴
Cf. [15, Lemma 3.2 and Theorem 3.3].

If γ and δ are given by the context we say simply “computable” instead of “ $(γ, δ)$ -computable”.

Let $(X, \sim)$ be an equivalence relation.5
⁵
Examples: $(X, =)$ for a set X. For a topological space $(X, τ)$ let $x \sim y : ⟺ (\forall U \in τ) (x \in U ⟺ y \in U)$ . Then the quotient topology is $T_{0}$ . For a pseudo-metric space $(X, d)$ let $x \sim y : ⟺ d (x, y) = 0$ . Then the quotient is a metric space. For a measure $(A, μ)$ let $A \sim B : ⟺ μ (A Δ B) = 0$ .

As usual $[a] : = {x \in X ∣ x \sim a}$ is the equivalence class containing $a \in X$ and $X / \sim : = {[x] ∣ x \in X}$ is the quotient set of X by ∼. Remember that for $γ : Σ^{ω} ⇉ X$ , $γ^{} (p) = {x ∣ (p, x) \in R_{γ}}$ . The following simple observation is applied everywhere in mathematics. Let $(X, \sim_{X})$ and $(Y, \sim_{Y})$ be equivalence relations and let $f : \subseteq X \to Y$ be a partial function. If $\begin{array}{rcl} (4) & (x \in dom (f) \land x \sim_{X} x^{'}) & ⟹ & (x^{'} \in dom (f) \land f (x) \sim_{Y} f (x^{'})) \end{array}$ then a partial function $g : \subseteq X / \sim_{X} \to Y / \sim_{Y}$ is well-defined by $g ([x]) : = [f (x)]$ for all $x \in dom (f)$ .

We generalize the consistency property (4) to multi-functions and show that for consistent multi-functions $f : X ⇉ Y$ , $(γ, δ)$ -computability on the sets X, Y is the same as $(γ^{}, δ^{})$ -computability on the sets of equivalence classes.
Definition 2.4.
Let $(X, \sim_{X})$ and $(Y, \sim_{Y})$ be equivalence relations and let $f : X ⇉ Y$ be a multi-function.
A multi-representation $γ : Σ^{ω} ⇉ X$ is compatible with the equivalence relation $(X, \sim_{X})$ iff $range (γ^{}) = X / \sim_{X}$ .

For a multi-function $f : X ⇉ Y$ define the factorization $Q (f) : X / \sim_{X} ⇉ Y / \sim_{Y}$ of f by $R_{Q (f)} : = {([x], [y]) ∣ (x, y) \in R_{f}}$ .

For a multi-function $g : X / \sim_{X} ⇉ Y / \sim_{Y}$ define the defactorization $D (g) : X ⇉ Y$ by $(x, y) \in R_{D (g)} : ⟺ ([x], [y]) \in R_{g}$ .

A multi-function $f : X ⇉ Y$ is consistent iff $\begin{array}{rcl} (5) & ((x, y) \in R_{f} \land x^{'} \in dom (f) \land x \sim_{X} x^{'}) ⟹ (\exists y^{'}) ((x^{'}, y^{'}) \in R_{f} \land y \sim_{Y} y^{'}) . \end{array}$

The multi-representation $γ : Σ^{ω} ⇉ X$ is compatible with $(X, \sim_{X})$ iff $x \in γ^{} (p) ⟺ [x] = γ^{} (p)$ for all $p \in dom (γ)$ . Although formally $γ^{} : Σ^{ω} \to 2^{X}$ has the codomain $2^{X}$ we use it like a representation with codomain $X / \sim_{X}$ . If γ is compatible and $\sim_{X}$ is the equality on X, then γ is single-valued and $γ^{}$ is a representation of the set ${{x} ∣ x \in X}$ such that $γ^{} (p) = {γ (p)}$ . Formula (5) means: if $x, x^{'} \in dom (f)$ are equivalent then they must be mapped to equivalent points. Notice that for single-valued functions f, (5) implies (4).
Lemma 2.5.

For $g : X / \sim_{X} ⇉ Y / \sim_{Y}$ , $Q D (g) = g$ and $D (g)$ is consistent.

For $f : X ⇉ Y$ , $D Q (f)$ extends f, that is $R_{f} \subseteq R_{D Q (f)}$ .

Proof.
Obvious. □

By the following theorem computation of a consistent multi-function f is the same as computation of its factorization.
Theorem 2.6.
Let γ and δ be multi-representations compatible with $(X, \sim_{X})$ and $(Y, \sim_{Y})$ , respectively. Let $f : X ⇉ Y$ be a consistent multi-function and let $F : \subseteq Σ^{ω} \to Σ^{ω}$ be a partial function. Then $\begin{array}{l} (6) & F realizes f (via (γ, δ)) ⟺ F realizes Q (f) (via (γ^{}, δ^{})), \\ (7) & f is (γ, δ) -computable ⟺ Q (f) is (γ^{}, δ^{}) -computable, \\ (8) & f is (γ, δ) -continuous ⟺ Q (f) is (γ^{}, δ^{}) -continuous . \end{array}$ In ( 6 ), the implication “⟹” holds true also if the function f is not consistent.
Proof.
“F realizes f” and “F realizes $Q (f)$ ” can be formalized as follows: $\begin{array}{l} (9) & (x \in γ^{} (p) \land x \in dom (f)) ⟹ (\exists y) ((x, y) \in R_{f} \land y \in δ^{} F (x)), \\ (10) & ([x] = γ^{} (p) \land [x] \in dom (Q (f))) ⟹ (\exists y) (([x], [y]) \in R_{Q f} \land [y] = δ^{} F (p)) . \end{array}$

(6) “⟹” Suppose f realizes f. Then $\begin{array}{l} [x] = γ^{} (p) \land [x] \in dom (Q (f)) \\ ⟹ (\exists x^{'}) (x \sim_{X} x^{'} \land x^{'} \in γ^{} (p) \land x^{'} \in dom (f)) \\ ⟹ (\exists x^{'}, y) (x \sim_{X} x^{'} \land (x^{'}, y) \in R_{f} \land y \in δ^{} F (p)) \\ ⟹ (\exists x^{'}, y) (x \sim_{X} x^{'} \land ([x^{'}], [y]) \in R_{Q (f)} \land [y] = δ^{} F (p)) \\ ⟹ (\exists x^{'}, y) (x \sim_{X} x^{'} \land ([x], [y]) \in R_{Q (f)} \land [y] = δ^{} F (p)) \\ ⟹ (\exists y) (([x], [y]) \in R_{Q (f)} \land [y] = δ^{} F (p)), \end{array}$ hence (10). We have not applied consistency of the function f.

(6) “⟸” Suppose (10). Then $\begin{array}{l} x \in γ^{} (p) \land x \in dom (f) \\ ⟹ [x] = γ^{} (p) \land [x] \in dom (Q (f)) \land x \in dom (f) \\ ⟹ (\exists y) (([x], [y]) \in R_{Q f} \land [y] = δ^{} F (p) \land x \in dom (f)) \\ ⟹ (\exists y, x^{'}, y^{'}) (x \sim_{X} x^{'} \land y \sim_{Y} y^{'} \land (x^{'}, y^{'}) \in R_{f} \land [y] = δ^{} F (p) \land x \in dom (f)) \\ ⟹ (\exists x^{'}, y^{'}) (x \sim_{X} x^{'} \land (x^{'}, y^{'}) \in R_{f} \land [y^{'}] = δ^{} F (p) \land x \in dom (f)) \\ ⟹ (\exists x^{'}, y^{'}, y^{″}) ((x, y^{″}) \in R_{f} \land y^{'} \sim_{Y} y^{″} \land [y^{'}] = δ^{} F (p)) \\ ⟹ (\exists y^{″}) ((x, y^{″}) \in R_{f} \land y^{″} \in δ^{} F (p)) \end{array}$ (where the 6th line follows by consistency of f), hence (9).

(7) and (8) follow from (6). □

For multi-representations $γ : Σ^{ω} ⇉ X$ and $δ : Σ^{ω} ⇉ Y$ the conjunction is the multi-representation $(γ \land δ) : Σ^{ω} ⇉ (X \cap Y)$ defined by ${(γ \land δ)}^{} ⟨ p, q ⟩ : = γ^{} (p) \cap δ^{} (q)$ .6
⁶
$⟨ p, q ⟩$ is a $(γ \land δ)$ -name of x if p is a γ-name of x and q is a δ-name of x.

$(γ \land δ)$ is (up to equivalence) the greatest lower bound of γ and δ, that is, $(γ \land δ) ⩽ γ$ , $(γ \land δ) ⩽ δ$ and $ϕ ⩽ (γ \land δ)$ if $ϕ ⩽ γ$ and $ϕ ⩽ δ$ . This holds accordingly for continuous reducibility $⩽_{t}$ .
Corollary 2.7.
Let γ and δ be multi-representations compatible with the equivalence relations $(X, \sim_{X})$ and $(Y, \sim_{Y})$ , respectively.
The function $F : \subseteq Σ^{ω} \to Σ^{ω}$ translates γ to δ iff F translates $γ^{}$ to $δ^{}$ .

$γ ⩽_{t} δ ⟺ γ^{} ⩽_{t} δ^{}$ and $γ ⩽ δ ⟺ γ^{} ⩽ δ^{}$ .

${(γ \land δ)}^{} = γ^{} \land δ^{}$ .

Proof.
1. Translation means computing the identity $f : x \mapsto x$ on X. The identity on X is consistent by (4) or (5). Apply Theorem 2.6.

2. This follows from 1.

3. ${(γ \land δ)}^{} ⟨ p, q ⟩ = [x] ⟺ (γ^{} (p) = [x] \land δ^{} (q) = [x]) ⟺ (γ^{} \land δ^{}) ⟨ p, q ⟩ = [x]$ . □

Lemma 2.5 and Theorem 2.6 hold true also for n-ary and for ω-ary functions.

For $f : X ⇉ Y$ and $x \in dom (x)$ , in the literature usually “ $f (x)$ ” is written instead of “ $f^{} (x)$ ”. Then for single-valued f, $f (x) : = f^{} (x) = {f (x)}$ . Despite of this formal inconsistence for avoiding overloaded symbols in the following we will write “ $f (x)$ ” instead of “ $f^{*} (x)$ ”. Then “ $y \in f (x)$ ” means $(x, y) \in R_{f}$ and for single-valued f, “ $f (x) = y$ ” means $(x, y) \in R_{f}$ as well.
3. Computable measures on computable σ-algebras

We use the terminology from [20, Section 3] which summarizes some basic facts from measure theory.

Definition 3.1 (Computable σ-algebra, computable measure).

A computable σ-algebra is a tuple $(Ω, A, R, α)$ such that $R$ is a countable ring in Ω, $Ω = ⋃ R$ , $A$ is the σ-algebra generated by $R$ , and $α : \subseteq Σ^{*} \to R$ is a notation of $R$ such that $dom (α)$ is recursive and the functions $(A, B) \mapsto A \cup B$ and $(A, B) \mapsto A ∖ B$ are computable (w.r.t. α).

A measure μ on a computable σ-algebra $(Ω, A, R, α)$ is computable, if $μ (R)$ is finite for all $R \in R$ and $R \mapsto μ (R)$ , the restriction of μ to $R$ , is $(α, ρ)$ -computable.

In the following let μ be a computable measure on a computable σ-algebra $(Ω, A, R, α)$ . Computable measures on computable σ-algebras have been used for example in [7,21–24]. In measure theory, measurable sets $A, B \in A$ are considered to be equivalent if they differ by a set of measure 0. $\begin{matrix} A \sim B : ⟺ μ (A Δ B) = 0 . \end{matrix}$ Let $[A] : = {B \in A ∣ A \sim B}$ be the equivalence class containing $A \in A$ , and for $E \subseteq A$ let $[E] : = {[A] ∣ A \in E}$ .

In the past various representations of the measurable sets for computable measures on computable σ-algebras [20–23] have been defined and compared. For more special measures further representations could be of interest, for example for regular Borel measures on $T_{2}$ -spaces via countable intersection of open sets or countable union of compact sets (cf. [2] for Cantor space). The following representations are the multi-valued versions of representations introduced in [20]. According to the discussion in [20, Section 7] they seem to be particularly natural. This is confirmed by the results of this article.

Definition 3.2 ([20]).

Define multi-representations $ζ_{+}, ζ_{-}, ζ : Σ^{ω} ⇉ A$ of the set $A$ of measurable sets as follows:

$A \in ζ_{+} (p) : ⟺ p$ is (encodes) a list of all $⟨ u, v ⟩$ such that $ν_{Q} (u) < μ (α (v) \cap A)$ ,

$A \in ζ_{-} (p) : ⟺ p$ is (encodes) a list of all $⟨ v, w ⟩$ such that $μ (α (v) \cap A) < ν_{Q} (w)$ ,

$A \in ζ (p) : ⟺ p$ is (encodes) a list of all $⟨ u, v, w ⟩$ such that $ν_{Q} (u) < μ (α (v) \cap A) < ν_{Q} (w)$ .

Here “ $A \in ζ_{+} (p)$ ” means $A \in ζ_{+}^{*} (p)$ ( $ζ_{+}^{*}$ from Definition 2.1), that is, $(p, A) \in R_{ζ_{+}}$ with the interpretation “p is a $ζ_{+}$ -name of A” etc.

Warning.
The single-valued representations $ζ_{+}$ , $ζ_{-}$ and ζ of the set of equivalence classes defined and studied in [20, Definition 4.2] must now be called $ζ_{+}^{}$ , $ζ_{-}^{}$ and $ζ^{}$ , respectively.
Lemma 3.3.
The multi-representations* $ζ_{+}$ , $ζ_{-}$ and ζ are compatible with the equivalence on $A$ , that is, $A \in ζ_{+} (p) ⟺ [A] = ζ_{+} (p)$ etc.
Proof.
By [20, Lemma 3.6], $A \sim B ⟺ (\forall R \in R) μ (R \cap A) = μ (R \cap B)$ . □

The multi-representation ζ is up to equivalence the greatest lower bound of $ζ_{+}$ and $ζ_{-}$ . Lemma 3.4.

$ζ \equiv ζ_{+} \land ζ_{-}$ , in particular, $ζ ⩽ ζ_{+}$ and $ζ ⩽ ζ_{-}$ ,

$ζ_{+} ≰_{t} ζ_{-}$ , $ζ_{-} ≰_{t} ζ_{+}$ , $ζ_{+} ≰_{t} ζ$ , $ζ_{-} ≰_{t} ζ$ .

Proof.
This follows from [20, Lemma 4.5 and Theorem 4.8] and Corollary 2.7. □

4. Boolean operations are computable

As a supplement to [20] in this section we study computability of the Boolean operations for $ζ_{+}$ , $ζ_{-}$ and ζ. Let $(Ω, A, R, α)$ be a computable σ-algebra with computable measure μ. Among others we will use the following formulas for measurable sets: $\begin{array}{l} (11) & | μ (X) - μ (Y) | ⩽ μ (X Δ Y) if μ (X), μ (Y) < \infty, \\ (12) & (A_{1} ♢ A_{2}) Δ (B_{1} ♢ B_{2}) \subseteq (A_{1} Δ B_{1}) \cup (A_{2} Δ B_{2}) if ♢ \in {\cup, \cap, ∖} . \end{array}$

By [20, Lemma 4.4], for every multi-representation γ of a subset of $A$ , $\begin{matrix} (13) & γ ⩽ ζ_{+} ⟺ (A, R) \mapsto μ (R \cap A) is (γ, α, ρ_{<}) -computable \end{matrix}$ (accordingly with $(ζ_{-}, ρ_{>})$ and $(ζ, ρ)$ instead of $(ζ_{+}, ρ_{<})$ ).

For every multi-representation δ define the multi-representations $δ^{< ω}$ and $δ^{ω}$ by $\begin{array}{l} (x_{1}, \dots, x_{n}) \in {(δ^{< ω})}^{*} ⟨ n, ⟨ p_{1}, \dots, p_{n} ⟩ ⟩ : ⟺ (x_{1} \in δ^{*} (p_{1}) \land \dots \land x_{n} \in δ^{*} (p_{n})), \\ (x_{0}, x_{1}, \dots) \in {(δ^{ω})}^{*} ⟨ p_{0}, p_{1}, \dots ⟩ : ⟺ (x_{0} \in δ^{*} (p_{0}) \land x_{1} \in δ^{*} (p_{1}) \land \dots) . \end{array}$

Theorem 4.1.
On the set $A$ of measurable sets
the complement function is $(ζ_{+}, ζ_{-})$ -computable, $(ζ_{-}, ζ_{+})$ -computable and $(ζ, ζ)$ -computable,

union and intersection are computable for $ζ_{+}$ , $ζ_{-}$ and ζ,

finite union $⋃_{< ω} : (A_{1}, \dots, A_{n}) \mapsto A_{1} \cup \dots \cup A_{n}$ is $(δ^{< ω}, δ)$ -computable for $δ \in {ζ_{+}, ζ_{-}, ζ}$ ,

finite intersection $⋂_{< ω} (A_{1}, \dots, A_{n}) \mapsto A_{1} \cap \dots \cap A_{n}$ is $(δ^{< ω}, δ)$ -computable for $δ \in {ζ_{+}, ζ_{-}, ζ}$ ,

countable union $⋃_{ω} : (A_{0}, A_{1}, \dots) \mapsto ⋃_{i \in ω} A_{i}$ is $(ζ_{+}^{ω}, ζ_{+})$ -computable,

countable intersection $⋂_{ω} : (A_{0}, A_{1}, \dots) \mapsto ⋂_{i \in ω} A_{i}$ is $(ζ_{-}^{ω}, ζ_{-})$ -computable.

Proof.
Complement: Since $μ (R) = μ (R \cap A) + μ (R \cap A^{c})$ and $R \mapsto μ (R)$ is $(α, ρ)$ -computable, there is a computable function which given a list of all $⟨ u, v ⟩$ such that $ν_{Q} (u) < μ (α (v) \cap A)$ finds a list of all $⟨ u^{'}, v ⟩$ such that $μ (α (v) \cap A^{c}) < ν_{Q} (u^{'})$ . Therefore, $A \mapsto A^{c}$ is $(ζ_{+}, ζ_{-})$ -computable. Correspondingly, complementation is $(ζ_{-}, ζ_{+})$ -computable.

By Lemma 3.4 $A \mapsto A$ is $(ζ, ζ_{+})$ -computable and $(ζ, ζ_{-})$ -computable. By the above result, $A \mapsto A^{c}$ is $(ζ, ζ_{-})$ -computable and $(ζ, ζ_{+})$ -computable. Again by Lemma 3.4 it is $(ζ, ζ)$ -computable.

Union for $ζ_{+}$ : In the following “ $♢$ ” means union “∪”. From $A, B \in A$ we want to compute $A ♢ B$ , that is, from a list of all $(a, R)$ such that $a < μ (R \cap A)$ and a list of all $(a, R)$ such that $a < μ (R \cap B)$ we want to compute a list of all $(a, R)$ such that $a < μ (R \cap (A ♢ B))$ . More formally, from $p, q \in dom (ζ_{+})$ we want to compute a list of all $⟨ u, v ⟩$ such that $ν_{Q} (u) < μ (α (v) \cap (ζ_{+} (p) ♢ ζ_{+} (q)))$ .

By [20, Lemma 4.7] the relation $μ (Q ∖ A) < ε$ (where $Q \in R$ ) is recursively enumerable w.r.t. α, $ζ_{+}$ and $ν_{Q}$ . Therefore, there is a machine which on input $(p, q)$ produces a list of all $⟨ u, v ⟩$ such that there are $S, T \in R$ and $ε \in Q_{+}$ with $\begin{array}{l} (14) & μ ((R \cap S) ∖ A) < ε, \\ (15) & μ ((R \cap T) ∖ B) < ε, \\ (16) & ν_{Q} (u) < μ (R \cap (S ♢ T)) - 2 ε, \end{array}$ where $A : = ζ_{+} (p)$ , $B : = ζ_{+} (q)$ and $R : = α (v)$ .

First we show that $ν_{Q} (u) < μ (α (v) \cap (A ♢ B))$ for every $⟨ u, v ⟩$ produced by the machine. Suppose (14)–(16). Since $X Δ (X \cap Y) = X ∖ Y$ , by (11) and (12), $\begin{array}{l} | μ ((R \cap S) ♢ (R \cap T)) - μ ((R \cap S \cap A) ♢ (R \cap T \cap B)) | \\ ⩽ μ (((R \cap S) ♢ (R \cap T)) Δ ((R \cap S \cap A) ♢ (R \cap T \cap B))) \\ ⩽ μ (((R \cap S) Δ (R \cap S \cap A)) \cup ((R \cap T) Δ (R \cap T \cap B))) \\ = μ (((R \cap S) ∖ A) \cup ((R \cap T) ∖ B)) \\ < 2 ε . \end{array}$ Therefore by (16), $\begin{matrix} ν_{Q} (u) < μ (R \cap (S ♢ T)) - 2 ε = μ ((R \cap S) ♢ (R \cap T)) - 2 ε ⩽ μ ((R \cap S \cap A) ♢ (R \cap T \cap B)) ⩽ μ (R \cap (A ♢ B)) . \end{matrix}$

Notice that $♢$ is monotone and $(R \cap A) ♢ (R \cap B) = R \cap (A ♢ B)$ for $♢ = \cup$ and for $♢ = \cap$ . Therefore, the machine produces a list of $⟨ u, v ⟩$ such that $ν_{Q} (u) < μ (α (v) \cap (A ♢ B))$ .

It remains to show that the list contains all such $⟨ u, v ⟩$ . For fixed A, B let $⟨ u, v ⟩$ such that $a < μ (R \cap (A ♢ B))$ where $a = ν_{Q} (u)$ and $R = α (v)$ . There are some $ε \in Q$ and $S, T \in R$ such that $\begin{array}{l} a < μ (R \cap (A ♢ B)) - 4 ε, \\ μ (S Δ (R \cap A)) < ε, \\ μ (T Δ (R \cap B)) < ε . \end{array}$ Since $(R \cap S) ∖ A = (R \cap S) ∖ (R \cap A) \subseteq S ∖ (R \cap A) \subseteq S Δ (R \cap A)$ , $μ ((R \cap S) ∖ A) < ε$ . Correspondingly $μ ((R \cap T) ∖ B) < ε$ . Therefore, (14) and (15) are satisfied. We have $\begin{matrix} (R \cap S) Δ (R \cap A) = ((R \cap S) ∖ (R \cap A)) \cup ((R \cap A) ∖ (R \cap S)) \subseteq (S ∖ (R \cap A)) \cup ((R \cap A) ∖ S) = S Δ (R \cap A) \end{matrix}$ and correspondingly $(R \cap T) Δ (R \cap B) \subseteq T Δ (R \cap B)$ . Since $\begin{array}{rcl} | μ (R \cap (S ♢ T)) - μ (R \cap (A ♢ B)) | & = & | μ ((R \cap S) ♢ (R \cap T)) - μ ((R \cap A) ♢ (R \cap B)) | \\ ⩽ & μ (((R \cap S) ♢ (R \cap T)) Δ ((R \cap A) ♢ (R \cap B))) \\ ⩽ & μ (((R \cap S) Δ (R \cap A)) \cup ((R \cap T) Δ (R \cap B))) \\ ⩽ & μ (S Δ (R \cap A)) + μ (T Δ (R \cap B)) \\ < & 2 ε, \end{array}$ $a < μ (R \cap (A ♢ B)) - 4 ε < μ (R \cap (S ♢ T)) - 2 ε$ , hence (16) is satisfied.

Since for u and v there are S, T and ε such that (14)–(16) are satisfied, $⟨ u, v ⟩$ is in the list produced by the machine M on input $(p, q)$ . Therefore, M produces a $ζ_{+}$ -name of $A ♢ B$ .

Intersection for $ζ_{+}$ : Replace “ $♢$ ” in the above proof by “∩”.

Union and intersection for $ζ_{-}$ and ζ: As we have shown, from a $ζ_{-}$ -name of A and a $ζ_{-}$ -name of B we can compute a $ζ_{+}$ -name of $A^{c}$ and a $ζ_{+}$ -name of $B^{c}$ . As we have also shown, from these names we can compute a $ζ_{+}$ -name of $A^{c} \cap B^{c} = {(A \cup B)}^{c}$ and hence a $ζ_{-}$ -name of $A \cup B$ . Therefore, union is computable w.r.t. $ζ_{-}$ . Correspondingly intersection is computable w.r.t. $ζ_{-}$ . Computability of union and intersection w.r.t. ζ can be proved easily by Lemma 3.4.

Finite union and intersection: Let $f : \subseteq Σ^{ω} \times Σ^{ω} \to Σ^{ω}$ be a realization of binary union for $ζ_{+}$ . There is a computable function $h : \subseteq Σ^{ω} \to Σ^{ω}$ such that $h ⟨ 1, ⟨ p_{1} ⟩ ⟩ = p_{1}$ , $h ⟨ n + 1, ⟨ p_{1}, \dots, p_{n + 1} ⟩ ⟩ = f (h ⟨ n, ⟨ p_{1}, \dots, p_{n} ⟩ ⟩, p_{n + 1})$ . We show by induction that $(A_{1}, \dots, A_{n}) \in {(ζ_{+}^{< ω})}^{} ⟨ n, p_{1}, \dots, p_{n} ⟩$ implies $A_{1} \cup \dots \cup A_{n} \in ζ_{+}^{} \circ h ⟨ n, p_{1}, \dots, p_{n} ⟩$ . $\begin{array}{l} (A_{1}) \in {(ζ_{+}^{< ω})}^{} ⟨ 1, p_{1} ⟩ ⟹ A_{1} \in ζ_{+}^{} (p_{1}) = ζ_{+}^{} \circ h ⟨ 1, p_{1} ⟩, \\ A_{1}, \dots, A_{n + 1} \in {(ζ_{+}^{< ω})}^{} ⟨ n + 1, ⟨ p_{1}, \dots, p_{n}, p_{n + 1} ⟩ ⟩ \\ ⟹ A_{1} \in ζ_{+}^{} (p_{1}) \land \dots \land A_{n} \in ζ_{+}^{} (p_{n}) \land A_{n + 1} \in ζ_{+}^{} (p_{n + 1}) \\ ⟹ (A_{1}, \dots, A_{n}) \in {(ζ_{+}^{< ω})}^{} ⟨ n, p_{1}, \dots, p_{n} ⟩ \land A_{n + 1} \in ζ_{+}^{} (p_{n + 1}) \\ ⟹ A_{1} \cup \dots \cup A_{n} \in ζ_{+}^{} \circ h ⟨ n, p_{1}, \dots, p_{n} ⟩ \land A_{n + 1} \in ζ_{+}^{} (p_{n + 1}) \\ ⟹ A_{1} \cup \dots \cup A_{n + 1} \in ζ_{+}^{} \circ f (h ⟨ n, ⟨ p_{1}, \dots, p_{n} ⟩ ⟩, p_{n + 1}) \\ ⟹ A_{1} \cup \dots \cup A_{n + 1} \in ζ_{+}^{} \circ h ⟨ n + 1, ⟨ p_{1}, \dots, p_{n + 1} ⟩ ⟩ . \end{array}$ Therefore, the function h realizes finite union. The proofs for $ζ_{-}$ and ζ and for finite intersection are similar.

Countable union: The function $(n, (A_{0}, A_{1}, \dots)) \mapsto (A_{0}, A_{1}, \dots, A_{n})$ is $(ν_{N}, ζ_{+}^{ω}, ζ_{+}^{< ω})$ -computable. We have shown that finite union $⋃_{< ω}$ is $(ζ_{+}^{< ω}, ζ_{+})$ -computable. Since by (13) the function $(A, R) \mapsto μ (A \cap R)$ is $(ζ_{+}, α, ρ_{<})$ -computable, the function $\begin{matrix} (n, (A_{0}, A_{1}, \dots), R) \mapsto μ (R \cap (A_{1} \cup \dots \cup A_{n})) \end{matrix}$ is $(ν_{n}, ζ_{+}^{ω}, ρ_{<})$ -computable. Since $μ (R \cap (A_{1} \cup A_{2} \cup \dots)) = {sup}_{n} μ (R \cap (A_{1} \cup \dots \cup A_{n}))$ , and on the real numbers $(x_{0}, x_{1}, \dots) \mapsto {sup}_{n} x_{n}$ is $(ρ_{<}^{ω}, ρ_{<})$ -computable, the function $((A_{0}, A_{1}, \dots), R) \mapsto μ (R \cap (A_{0} \cup A_{1} \cup \dots))$ is $(ζ_{+}^{ω}, α, ρ_{<})$ -computable, hence there is a computable function h such that $\begin{matrix} μ (α (w) \cap ⋃_{ω} ζ_{+}^{ω} (q)) = ρ_{<} \circ h (w, q) . \end{matrix}$

Define a multi-representation γ of $A$ by $γ : = ⋃_{ω} ζ_{+}^{ω}$ . Then the function $(B, R) \mapsto μ (R \cap B)$ is $(γ, α, ρ_{<})$ -computable. By (13), $γ ⩽ ζ_{+}$ , hence the function $⋃_{ω}$ is $(ζ_{+}^{ω}, ζ_{+})$ -computable.

Countable intersection*: This can be reduced to countable union by $A_{1} \cap A_{2} \cap \dots = {(A_{0}^{c} \cup A_{1}^{c} \cup \dots)}^{c}$ since complementation is $(ζ_{-}, ζ_{+})$ -computable and $(ζ_{+}, ζ_{-})$ -computable. □

Remember, that computable operators map computable elements to computable elements. In general, countable union cannot be computed for $ζ_{-}$ or ζ, countable intersection cannot be computed for $ζ_{+}$ or ζ, and $lim sup A_{i}$ and $lim inf A_{i}$ cannot be computed for $ζ_{+}$ , $ζ_{-}$ or ζ (without proof).
5. Representations of measurable functions

In this section we study measurable functions from a measure space to a topological space. Let $(Ω, A, μ)$ be a measure space and let $(X, τ)$ be a second countable topological space, that is, a $T_{0}$ -space with countable base β. A function $f : Ω \to X$ is measurable if $f^{- 1} (V) \in A$ for every open set $V \in τ$ . Let $F$ be the set of measurable functions. Notice that f is measurable iff $f^{- 1} (U) \in A$ for every base set $U \in β$ . Let $A (β)$ be the σ-algebra on X generated by β. Then $f^{- 1} (B) \in A$ for all $B \in A (β)$ . Since τ is $T_{0}$ , for all $x \in X$ , ${x} = ⋂ {U \in β ∣ x \in U} ∖ ⋃ {U \in β ∣ x \notin U} \in A (β)$ , hence $f^{- 1} ({x}) \in A$ .

For measurable sets $A, B \in A$ and measurable functions f, g equivalences are defined by $\begin{array}{l} (17) & A \sim B ⟺ μ (A Δ B) = 0, \\ (18) & f \sim g ⟺ μ ({x \in Ω ∣ f (x) \neq g (x)}) = 0 . \end{array}$ As usual let $[A] : = {B \in A ∣ A \sim B}$ and $[f] : = {g \in F ∣ f \sim g}$ .

Lemma 5.1.
For all measurable functions $f, g : Ω \to X$ ,
${x \in Ω ∣ f (x) \neq g (x)} = ⋃_{U \in β} (f^{- 1} (U) Δ g^{- 1} (U))$ , in particular, this set and its complement are measurable,

$\begin{array}{rcl} f \sim g & ⟺ & f^{- 1} (U) \sim g^{- 1} (U) for every base set U \in β \\ ⟺ & f^{- 1} (V) \sim g^{- 1} (V) for every V \in τ \\ ⟺ & f^{- 1} (B) \sim g^{- 1} (B) for every B \in A (β) . \end{array}$

Proof.
1. Since τ is a $T_{0}$ -topology and $x \in f^{- 1} (U) Δ g^{- 1} (U) ⟹ f (x) \neq g (x)$ , $\begin{array}{rcl} f (x) \neq g (x) & ⟺ & (\exists U \in β) ((f (x) \in U \land g (x) \notin U) \lor (g (x) \in U \land f (x) \notin U)) \\ ⟺ & (\exists U \in β) x \in f^{- 1} (U) Δ g^{- 1} (U) \\ ⟹ & x \in ⋃_{U \in β} (f^{- 1} (U) Δ g^{- 1} (U)) \\ ⟹ & f (x) \neq g (x) . \end{array}$ The set ${x \in Ω ∣ f (x) \neq g (x)}$ is measurable since the base β is countable and $f^{- 1} (U)$ and $g^{- 1} (U)$ are measurable for every $U \in β$ .

2. By 1., $μ ({x ∣ f (x) \neq g (x)}) = 0$ iff $μ (f^{- 1} (U) Δ g^{- 1} (U)) = 0$ for all $U \in β$ , hence $f \sim g ⟺ f^{- 1} (U) \sim g^{- 1} (U)$ for all base sets $U \in β$ .

The σ-algebra $A (β)$ is generated from β by the operations “complement” and countable union. If $f^{- 1} (A) \sim g^{- 1} (A)$ then $f^{- 1} (X ∖ A) = Ω ∖ f^{- 1} (A) \sim Ω ∖ g^{- 1} (A) = g^{- 1} (X ∖ A)$ and if $f^{- 1} (A_{i}) \sim g^{- 1} (A_{i})$ for $i \in N$ then $f^{- 1} ⋃_{i} A_{i} = ⋃_{i} f^{- 1} (A_{i}) \sim ⋃_{i} f^{- 1} (A_{i}) = f^{- 1} ⋃_{i} A_{i}$ . By induction $f^{- 1} (B) \sim g^{- 1} (B)$ for every $B \in A (β)$ .

Since the base β is countable, $β \subseteq τ \subseteq A (β)$ . This implies the remaining implications. □

In the following let μ be a computable measure on a computable σ-algebra $(Ω, A, R, α)$ with multi-representations $ζ_{+}$ , $ζ_{-}$ and ζ of the set $A$ of measurable sets (Definition 3.2). Furthermore, let $X = (X, τ_{X}, β_{X}, ν_{X})$ be a computable topological space with the canonical representations $δ_{X}$ and $θ_{X}$ of the points and of the open subsets, respectively [19].

Let $η^{* ω}$ be the standard representations of the set $F^{* ω}$ of partial functions $f : \subseteq Σ^{} \to Σ^{ω}$ and let $η^{ω ω}$ be the standard representations of the set $F^{ω ω}$ of partial continuous functions $f : \subseteq Σ^{ω} \to Σ^{ω}$ with $G_{δ}$ -domain. They satisfy the universal Turing machine theorem and the smn-theorem [17].
Definition 5.2.
Define multi-representations $δ_{mf}$ , $δ_{mfb}$ and $δ_{mfo}$ (via pre-images of base sets and of open sets, respectively) of the set $F_{X}$ of measurable functions $f : Ω \to X$ as follows. $\begin{array}{l} (19) & f \in δ_{mf} (p) ⟺ \{\begin{matrix} p is a list of all (v, w, u) \in {(Σ^{})}^{3} \\ such that ν_{Q} (v) < μ (α (w) \cap f^{- 1} (ν_{X} (u))), \end{matrix} \\ (20) & f \in δ_{mfb} (p) ⟺ (\forall u \in dom (ν_{X})) f^{- 1} (ν_{X} (u)) \in ζ_{+} \circ η_{p}^{* ω} (u), \\ (21) & f \in δ_{mfo} (p) ⟺ (\forall q \in dom (θ_{X})) f^{- 1} (θ_{X} (q)) \in ζ_{+} \circ η_{p}^{ω ω} (q) . \end{array}$
Lemma 5.3.
The three multi-representations $δ_{mf}$ , $δ_{mfb}$ and $δ_{mfo}$ are compatible with the equivalence relation $(F_{X}, \sim)$ , that is, $f \in δ_{mf} (p) ⟹ [f] = δ_{mf} (p)$ etc.
Proof.
This follows immediately from Lemma 5.1. □
Theorem 5.4.
$δ_{mf} \equiv δ_{mfb} \equiv δ_{mfo}$ .
Proof.
$δ_{mf} ⩽ δ_{mfb}$ : By the definition of $ζ_{+}$ , $f^{- 1} (U) \in ζ_{+} (r)$ iff r is a list of all $(v, w)$ such that $ν_{Q} (v) < μ (α (w) \cap f^{- 1} (U))$ . There is a Type-2 machine M which on input $(p, u) \in Σ^{ω} \times Σ^{}$ writes a list r of all $(v, w)$ such that $(v, w, u)$ is in the list p. Suppose $f \in δ_{mf} (p)$ . Then $f_{M} (p, u)$ is a list of all $(v, w)$ such that $ν_{Q} (v) < μ (α (w) \cap f^{- 1} (ν_{X} (u)))$ , hence $f^{- 1} (ν_{X} (u)) \in ζ_{+} \circ f_{M} (p, u)$ . By the smn-theorem for $η^{ ω}$ there is a computable function h such that $f_{M} (p, u) = η_{h (p)}^{* ω} (u)$ . Since $f^{- 1} (ν_{X} (u)) \in ζ_{+} \circ η_{h (p)}^{* ω} (u)$ , $f \in δ_{mfb} (h (p))$ . Therefore, $δ_{mf} ⩽ δ_{mfb}$ .

$δ_{mfb} ⩽ δ_{mfo}$ : Suppose $f \in δ_{mfb} (p)$ and $q \in dom (θ_{X})$ . Define $u ⊲ p : ⟺ ι (u)$ is a subword of p (“u is listed in p”). Then $[f^{- 1} (θ_{X} (q))] = ⋃_{u ⊲ q} [f^{- 1} (ν_{X} (u))] = ⋃_{u ⊲ q} ζ_{+} \circ η_{p}^{* ω} (u)$ . Since by Theorem 4.1 countable union on $F$ is computable for $ζ_{+}$ , by the universal Turing machine theorem for $η^{* ω}$ there is a computable function $h : \subseteq Σ^{ω} \times Σ^{ω} \to Σ^{ω}$ such that $[f^{- 1} (θ_{X} (q))] = ζ_{+} \circ h (p, q)$ . By the smn-theorem for $η^{ω ω}$ there is a computable function $d : Σ^{ω} \to Σ^{ω}$ such that $[f^{- 1} (θ_{X} (q))] = ζ_{+} \circ η_{d (p)}^{ω ω} (q)$ . This means $f \in δ_{mfo} (d (p))$ . Therefore, d translates $δ_{mfb}$ to $δ_{mfo}$ .

$δ_{mfo} ⩽ δ_{mf}$ : There is a computable function $d : Σ^{} \to Σ^{ω}$ such that $ν_{X} (u) = θ_{X} \circ d (u)$ . For all $u \in dom (ν_{X})$ , $f^{- 1} (ν_{X} (u)) = f^{- 1} (θ_{X} (d (u)))$ . Suppose $f \in δ_{mfo} (p)$ . Then $f^{- 1} (ν_{X} (u)) = ζ_{+} \circ η_{p}^{ω ω} \circ d (u)$ .

By the universal Turing machine theorem for $η^{ω ω}$ and the definition of $ζ_{+}$ , from $(p, u)$ we can compute a list of all $(v, w)$ such that $ν_{Q} (v) < μ (α (w) \cap f^{- 1} (ν_{X} (u)))$ , hence from p we can compute a list r of all $(v, w, u)$ such that $ν_{Q} (v) < μ (α (w) \cap f^{- 1} (ν_{X} (u)))$ . Therefore, from p we can compute some r such that $f \in δ_{mf} (r)$ , hence $δ_{mfo} ⩽ δ_{mf}$ . □

The representation $δ_{mfo}$ is the direct effective version of the definition of measurable (the pre-image of open is measurable). For proving $δ_{mfb} ⩽ δ_{mfo}$ we use that countable union of measurable sets is computable. Therefore, $δ_{mfb} ⩽ δ_{mfo}$ cannot be proved if in (20) and (21) $ζ_{+}$ is replaced by ζ or by $ζ_{-}$ .

Another multi-representation of measurable functions which is used in [21, Definition 7.1] and [12, Definition 3.4] can be defined in our context as follows: $\begin{array}{rcl} (22) & f \in δ^{'} (p) & ⟺ & \{\begin{matrix} p is a list of all (v, u) \in {(Σ^{})}^{2} \\ such that ν_{Q} (v) < μ (f^{- 1} (ν_{X} (u))) . \end{matrix} \end{array}$ While for every base element U a $δ_{mf}$ -name of f allows to compute the measure $μ (R \cap f^{- 1} (U))$ from below for all ring elements R, hence a $ζ_{+}$ -name of $f^{- 1} (U)$ , a $δ^{'}$ -name of f allows to compute only the measure of the sets $f^{- 1} (U)$ from below. In general the representation $δ^{'}$ is not compatible with the equivalence relation $(F_{X}, \sim)$ (Definition 2.4, Lemma 5.3). Example: For the Lebesgue measure on the unit interval, the functions $f, g : [0; 1] \to R$ , $f (x) : = x$ and $g (x) : = 1 - x$ . have the same $δ^{'}$ -names but are not equivalent.

If $f : Ω \to X$ and $g : Ω \to Y$ are measurable then $h : Ω \to X \times Y$ , $h (x) : = (f (x), g (x))$ , is measurable. We prove a computable version of this theorem. Let $Y = (Y, τ_{Y}, β_{Y}, ν_{Y})$ be another computable topological space with the canonical representations $δ_{Y}$ and $θ_{Y}$ of the points and of the open subsets, respectively. Let $X \times Y = (X \times Y, τ, β, ν)$ be the product space where $ν (⟨ u, v ⟩) = ν_{X} (u) \times ν_{Y} (v)$ , $β : = range (ν)$ and τ is the topology generated by β as a base. $X \times Y$ is a computable topological space [13,19] with canonical representations δ and θ of the points and of the open sets, respectively.

Let $δ_{mfX}$ , $δ_{mfXb}$ and $δ_{mfXo}$ be the multi-representations from (19), (20) and (21), respectively, of the set $F_{X} = {f ∣ f : Ω \to X, f measurable}$ , let $δ_{mfY}$ , $δ_{mfYb}$ and $δ_{mfYo}$ be the multi-representations from (19), (20) and (21), respectively, of the set $F_{Y} = {f ∣ f : Ω \to Y, f measurable}$ , and let $δ_{mf}$ , $δ_{mfb}$ and $δ_{mfo}$ be the multi-representations from (19), (20) and (21), respectively, of the set $F_{X \times Y} = {f ∣ f : Ω \to X \times Y, f measurable}$ .
Theorem 5.5.
The function $π : F_{X} \times F_{Y} \to F_{X \times Y}$ , $π (f, g) (a) : = (f (a), g (a))$ ,
is well-defined such that $f \sim f^{'}$ and $g \sim g^{'}$ implies $π (f, g) \sim π (f^{'}, g^{'})$ , and

is $(δ_{mfX}, δ_{mfY}, δ_{mf})$ -computable.
The theorem holds accordingly for $n > 2$ arguments.
Proof.
Since ${(π (f, g))}^{- 1} (U \times V) = f^{- 1} (U) \cap g^{- 1} (V)$ for $U \in β_{X}$ and $V \in β_{Y}$ , $π (f, g) : Ω \to X \times Y$ is measurable. Therefore, π is well-defined. Since ${a ∣ (f, g) (a) \neq (f^{'}, g^{'}) (a)} = {a ∣ f (a) \neq f^{'} (a)} \cup {a ∣ g (a) \neq g^{'} (a)}$ , $f \sim f^{'}$ and $g \sim g^{'}$ implies $π (f, g) \sim π (f^{'}, g^{'})$ by (18).

Finally, by Theorem 5.4 it suffices to prove $(δ_{mfXb}, δ_{mfYb}, δ_{mfb})$ -computability. Suppose $f \in δ_{mfXb} (p)$ and $g \in δ_{mfYb} (q)$ . There is a computable function $h : \subseteq Σ^{ω} \times Σ^{ω} \to Σ^{ω}$ which realizes intersection on $A$ for $ζ_{+}$ . By (20) for all $⟨ u, v ⟩ \in dom (ν)$ , $\begin{array}{rcl} {(π (f, g))}^{- 1} (ν (⟨ u, v ⟩)) & = & {x ∣ f (x) \in ν_{X} (u), g (x) \in ν_{Y} (v)} \\ = & f^{- 1} (ν_{X} (u)) \cap g^{- 1} (ν_{Y} (v)) \\ = & ζ_{+} \circ η_{p}^{* ω} (u) \cap ζ_{+} \circ η_{q}^{* ω} (v) \\ = & ζ_{+} \circ h (η_{p}^{* ω} (u), η_{q}^{* ω} (v)) . \end{array}$ By the universal Turing machine theorem for $η^{* ω}$ there is a computable function $h^{'}$ such that $h (η_{p}^{* ω} (u), η_{q}^{* ω} (v)) = h^{'} (⟨ p, q ⟩, ⟨ u, v ⟩)$ . By the smn-theorem for $η^{* ω}$ there is a computable function $d : Σ^{ω} \to Σ^{ω}$ such that $h^{'} (⟨ p, q ⟩, ⟨ u, v ⟩) = η_{d (⟨ p, q ⟩)}^{* ω} (⟨ u, v ⟩)$ , hence ${(π (f, g))}^{- 1} (ν (⟨ u, v ⟩)) = ζ_{+} \circ η_{d (⟨ p, q ⟩)}^{* ω} (⟨ u, v ⟩)$ . By (20), $π (f, g) \in δ_{mfb} (d (⟨ p, q ⟩))$ . Therefore, the function π is $(δ_{mfXb}, δ_{mfYb}, δ_{mfb})$ -computable. By induction the result can be extended to products of $n > 2$ factors. □

If $f : Ω \to X$ is measurable and $g : X \to Y$ is continuous then $g \circ f : Ω \to Y$ is measurable. We will prove a computable version of this theorem, that is, from f and g we want to compute $g \circ f$ . We want to define composition and prove computability also for partial continuous functions $g : \subseteq X \to Y$ with $range (f) \subseteq dom (g)$ . For a partial function g with $range (f) \subseteq dom (g)$ possibly $range (f^{'}) ⊈ dom (g)$ for some $f^{'} \sim f$ .
Definition 5.6.
For measurable $f : Ω \to X$ and partial continuous $g : \subseteq X \to Y$ define the composition operator Comp as follows: $\begin{array}{l} (23) & (g, f) \in dom (Comp) : ⟺ range (f) \subseteq dom (g), \\ (24) & Comp (g, f) : = g \circ f . \end{array}$
Lemma 5.7.
If $f \sim f^{'}$ , $(g, f) \in dom (Comp)$ and $(g, f^{'}) \in dom (Comp)$ then $Comp (g, f) \sim Comp (g, f^{'})$ .
Proof.
This follows from Lemma 5.1.2. □

Let $[δ_{X} \to_{p} δ_{Y}]$ be the canonical multi-representation of the set of partial continuous functions $g : \subseteq X \to Y$ defined by $g \in [δ_{X} \to_{p} δ_{Y}] (p)$ iff $η_{p}^{ω ω}$ realizes g w.r.t. $(δ_{X}, δ_{Y})$ [19, Definition 28].
Theorem 5.8.
The composition operator Comp is $([δ_{X} \to_{p} δ_{Y}], δ_{mf X}, δ_{mf Y})$ -computable.
Proof.
By [19, Theorem 29], for computable topological spaces $[δ_{X} \to_{p} δ_{Y}] \equiv δ_{X Y}$ where $\begin{matrix} g \in δ_{X Y} (p) ⟺ (\forall q \in dom (θ_{Y})) g^{- 1} (θ_{Y} (q)) = θ_{X} \circ η_{p}^{ω ω} (q) \cap dom (g) . \end{matrix}$ Therefore, by Theorem 5.4 it suffices to prove $(δ_{mfXo}, δ_{X Y}, δ_{mfYo})$ -computability. There is a computable function $h : Σ^{ω} \times Σ^{ω} \to Σ^{ω}$ such that $η_{p_{1}}^{ω ω} \circ η_{p}^{ω ω} = η_{h (p_{1}, p)}^{ω ω}$ [17].

Suppose $f \in δ_{mfXo} (p_{1})$ , that is $f^{- 1} (θ_{X} (q)) \in ζ_{+} \circ η_{p_{1}}^{ω ω} (q)$ , $g \in δ_{X Y} (p)$ and $(g, f) \in dom (Comp)$ . Then $\begin{array}{rcl} {(g \circ f)}^{- 1} (θ_{Y} (q)) & = & f^{- 1} (g^{- 1} (θ_{Y} (q))) \\ = & f^{- 1} (θ_{X} \circ η_{p}^{ω ω} (q) \cap dom (g)) \\ = & f^{- 1} (θ_{X} \circ η_{p}^{ω ω} (q)) \\ \in & ζ_{+} \circ η_{p_{1}}^{ω ω} \circ η_{p}^{ω ω} (q) \\ = & ζ_{+} \circ η_{h (p_{1}, p)}^{ω ω} (q), \end{array}$ hence $g \circ f \in δ_{mfYo} (h (p_{1}, p))$ by (21). Therefore, Comp is $(δ_{mfXo}, δ_{X Y}, δ_{mfYo})$ -computable and hence $([δ_{X} \to_{p} δ_{Y}], δ_{mf X}, δ_{mf Y})$ -computable. □

For every $a \in X$ the function $f_{a} : Ω \to X$ , $f (z) = a$ for all $z \in Ω$ , is measurable. We prove a computable version of this observation.
Theorem 5.9.
The function $H : X \to F$ , $H (a) : = f_{a}$ , is $(δ_{X}, δ_{mfX})$ -computable.
Proof.
By definition, $δ_{X} (p) = a$ iff p is (encodes) a list of all $u \in dom (ν_{X})$ such that $a \in ν_{X} (u)$ .

By (19) from $p \in Σ^{ω}$ such that $δ_{X} (p) = a$ we want to compute a list of all $(v, w, u)$ such that $ν_{Q} (v) < μ (α (w) \cap f_{a}^{- 1} (ν_{X} (u)))$ where $μ (α (w) \cap f_{a}^{- 1} (ν_{X} (u))) = μ (α (w))$ if $a \in ν_{X} (u)$ and $μ (α (w) \cap f_{a}^{- 1} (ν_{X} (u))) = 0$ otherwise.

There is a machine M that on input p produces a list of all $(v, w, u)$ with $ν_{Q} (v) < 0$ , $w \in dom (α)$ and $u \in dom (ν_{X})$ and merges this list with a list of all $(v, w, u)$ such that u is listed in p and $ν_{Q} (v) < μ (α (w))$ . Then $f_{M} (p)$ is $δ_{mfX}$ -name of $f_{a}$ . Therefore, the function H is $(δ_{X}, δ_{mfX})$ -computable. □

By the following theorem which combines Theorems 5.5, 5.8 and 5.9 numerous measurable functions can be computed from given ones by continuous functions.

For $i = 1, \dots, k$ let $X_{i}$ be a computable topological space with standard representation $δ_{X_{i}}$ . For $j = 1, \dots, m$ let $Y_{j}$ be a computable topological space and let $δ_{mfj}$ be the multi-representation from (19) of the set of $F_{j} : = {f ∣ f : Ω \to Y_{j}, f is measurable}$ . Let $\overline{δ}$ be the standard representation of the product space $\overline{X} : = X_{1} \times \dots \times X_{k} \times Y_{1} \times \dots \times Y_{m}$ and let ${\overline{δ}}_{mf}$ be the representation from (19) of the set of ${f ∣ f : Ω \to \overline{X}, f is measurable}$ . Let Z be a computable topological space with canonical representation $δ_{Z}$ of the points and representation $δ_{mfZ}$ from (19) of the set ${f ∣ f : Ω \to Z, f is measurable}$ . For the continuous partial functions $h : \subseteq \overline{X} \to Z$ we use the representation $[\overline{δ} \to_{p} δ_{Z}]$ . Theorem 5.10.
Define a function H by $H : (h, x_{1}, \dots, x_{k}, f_{1}, \dots, f_{m}) \mapsto f$ ( $x_{i} \in X_{i}$ , $f_{j} \in F_{j}$ ) where $(h, x_{1}, \dots, x_{k}, f_{1}, \dots, f_{m}) \in dom (H)$ iff $h (x_{1}, \dots, x_{k}, f_{1} (u), \dots, f_{m} (u))$ exists for all $u \in Ω$ and $f (u) : = h (x_{1}, \dots, x_{k}, f_{1} (u), \dots, f_{m} (u))$ for $u \in Ω$ . The function H is $([\overline{δ} \to_{p} δ_{Z}], δ_{X_{1}}, \dots, δ_{X_{k}}, δ_{mf 1}, \dots, δ_{mfm}, δ_{mfZ})$ -computable.
Proof.
By the definitions, $\begin{array}{rcl} (25) & f (u) & = & h (f_{x_{1}} (u), \dots, f_{x_{k}} (u), f_{1} (u), \dots, f_{m} (u)) \\ (26) & = & h \circ π^{k + m} (f_{x_{1}}, \dots, f_{x_{k}}, f_{1}, \dots, f_{m}) (u) . \end{array}$

By Theorem 5.9 from $(x_{1}, \dots, x_{k})$ we can compute $(f_{x_{1}}, \dots, f_{x_{k}})$ . By Theorem 5.5 from $(f_{x_{1}}, \dots, f_{x_{k}}, f_{1}, \dots, f_{m})$ we can compute (a ${\overline{δ}}_{mf}$ -name of) $(f_{x_{1}}, \dots, f_{x_{k}}, f_{1}, \dots, f_{m})$ . By Theorem 5.8 with a $[\overline{δ} \to_{p} δ_{Z}]$ -name of h we can compute (a $δ_{mfZ}$ -name of) f. □

6. Borel measures on computable metric spaces

In this section let $(X, d, D, ν_{D})$ be a computable metric space with Cauchy representation $δ_{C}$ [17]. It induces a natural notation $ν_{X}$ of the set $β_{X}$ of the open “rational balls” $B (x, r) = {y ∣ d (x, y) < r}$ where $x \in D$ and $r \in Q_{+}$ . Let $τ_{X}$ be the topology generated by $β_{X}$ as a base. Then $(X, τ_{X}, β_{X}, ν_{X})$ is a computable topological space such that $δ_{X} \equiv δ_{C}$ where $δ_{X}$ is the canonical representation of the points of the computable topological space. Let $θ_{X}$ be the standard representation of the set $τ_{X}$ of open subsets of X [17,19].

In the proof of Theorems 6.5 and 7.5 we apply Theorem 6.2 about Borel measures on computable metric spaces which is of interest by its own. A Borel measure on the computable metric space $(X, d, D, ν_{D})$ is a measure on the space $(X, B)$ where $B : = A (τ_{X}) = A (β_{X})$ is the σ-algebra of Borel sets. A finite measure μ on $(X, A (τ_{X}))$ is already defined by its values on the finite unions of base balls $U_{1} \cup \dots \cup U_{k}$ ( $U_{i} \in β_{X}$ ). Let $M$ be the set of all finite Borel measures on the metric space.

Definition 6.1.
We define a representation of the set $M$ of the finite Borel measures as follows. $δ_{M} ⟨ p, q ⟩ = μ$ iff $ρ (p) = μ (X)$ and q is (encodes) a list of all $⟨ u, ⟨ v_{1}, w_{1} ⟩, \dots, ⟨ v_{n}, w_{n} ⟩ ⟩$ such that $\begin{array}{rcl} (27) & ν_{Q} (u) < μ (B (ν_{D} (v_{1}), ν_{Q} (w_{1})) \cup \dots \cup B (ν_{D} (v_{n}), ν_{Q} (w_{n}))) . \end{array}$

This means, from a name of a measure μ we can compute (a ρ-name of) $μ (X)$ and for every finite set ${B_{1}, \dots, B_{n}} \subseteq β_{X}$ of balls from the base we can compute $μ (B_{1} \cup \dots \cup B_{n})$ from below, that is, a $ρ_{<}$ -name of this number (cf. [16], [3, Lemma 2], [6, Theorem 4.2.1]). Obviously, $(μ, U) \mapsto μ (U)$ is $(δ_{M}, θ_{X}, ρ_{<})$ -computable.

For every interval $I \subseteq R_{+}$ and $x \in D$ define $B (x, I) : = {y \in X ∣ d (x, y) \in I}$ . Then $B (x, I)$ is an annulus with center x if I is a proper interval and $B (x, {r})$ is the circle with center x and radius r. Since $B (x, r) \in A (β_{X})$ , $B (x, I) \in A (β_{X})$ . For a representation δ let $δ^{ω} ⟨ p_{0}, p_{1}, \dots ⟩ : = (δ (p_{0}), δ (p_{1}), \dots)$ .
Theorem 6.2.
The following multi-function T is $(δ_{M}^{ω}, ρ^{ω})$ -computable. T maps every sequence $(μ_{0}, μ_{1}, \dots)$ of finite measures to some injective sequence of real numbers $(r_{0}, r_{1}, \dots)$ which is dense in the interval $(0; \infty)$ such that $\begin{array}{rcl} (28) & (\forall x \in D) (\forall i, j) μ_{i} (B (x, {r_{j}})) = 0 . \end{array}$

By (28) for every measure $μ_{i}$ , every center $x \in D$ and every j, the circle with center x and radius $r_{j}$ has measure 0. The theorem generalizes [14, Lemma 2.15], [6, Lemma 5.1.1] [5, Lemma 3.0.10 with corollaries], [21, Theorem 6.4] and [10, Proposition 2.3]. The theorem can be generalized to other appropriate families ${(B_{z})}_{z \in S}$ for real intervals S.

Let μ be $δ_{M}$ -computable. Then $μ (X)$ is computable and T maps $(μ, μ, \dots)$ to some computable sequence $(r_{0}, r_{1}, \dots)$ . Let $a \in D$ and $j \in N$ . Since $X = B (a, r_{j}) \cup {x ∣ d (a, x) = r_{j}} \cup {x \in X ∣ d (a, x) > r_{i}}$ , by (28) the ρ-computable number $μ (X)$ is the sum of the two $ρ_{<}$ -computable numbers $μ (B (a, r_{j}))$ and $μ ({x \in X ∣ d (a, x) > r_{j}})$ , which therefore must be even ρ-computable. Since $μ (B (a, r_{j}))$ and $μ (X ∖ B (a, r_{j})) = μ ({x \in X ∣ d (a, x) > r_{i}})$ are ρ-computable, $B (a, r_{j})$ can be used in a ring $R$ on which μ has computable values.

We prepare the proof of Theorem 6.2 by two lemmas.
Lemma 6.3.
The following multifunction is $(δ_{M}, ν_{D}, ν_{I}, ν_{N}, ν_{I})$ -computable. H maps every finite Borel measure μ on the computable metric space $(X, d, D, ν_{D})$ , every point $x \in D$ , every interval $I = (a; b)$ ( $a, b \in Q$ , $0 < a < b$ ) and every $n \in N$ to some rational interval J such that $\begin{array}{rcl} (29) & \overline{J} \subseteq I, length (J) < 2^{- n} and μ (B (x, J)) < 2^{- n} . \end{array}$
Proof.
Since $μ (X)$ is finite, for all $x \in D$ and all I, $\begin{array}{rcl} (30) & (\forall ε > 0) (\exists c \in I \cap Q) μ (B (x, {c})) < ε . \end{array}$ Let $m > 2^{n + 1} \cdot μ (X)$ . By (30) there are numbers $a_{0} < a_{1} < \dots < a_{m}$ such that $a_{i} \in I \cap Q$ and $\sum_{i = 1}^{m} μ (B (x, {a_{i}})) < 2^{- n - 1}$ . Let $\begin{matrix} (31) & \begin{matrix} A_{0} & : = & B (x, a_{0}), \\ A_{i} & : = & B (x, (a_{i - 1}; a_{i})) for i ⩽ i ⩽ m, \\ A_{m + 1} & : = & B (x, (a_{m}; \infty)) . \end{matrix}\} \end{matrix}$ Then $\begin{array}{rcl} μ (X) - 2^{- n - 1} < μ (X) - \sum_{i = 1}^{m} μ (B (x, {a_{i}})) = μ (A_{0}) + \sum_{i = 1}^{m} μ (A_{i}) + μ (A_{m + 1}) ⩽ μ (X) . \end{array}$ There are rational numbers $c_{0} < μ (A_{0})$ , …, $c_{m + 1} < μ (A_{m + 1})$ such that $\begin{array}{rcl} (32) & μ (X) - 2^{- n - 1} & < & c_{0} + \sum_{i = 1}^{m} c_{i} + c_{m + 1} ⩽ μ (X) . \end{array}$

From $(μ, x, i, n)$ we can compute some m such that $m > 2^{n + 1} \cdot μ (X)$ . By (27) for given rational numbers $a_{0} < a_{1} < \dots < a_{m}$ with $a_{i} \in I$ we can compute $ρ_{<}$ -names of $μ (A_{i})$ for $0 ⩽ i ⩽ m + 1$ . Since “ $c < μ (A_{i})$ ” is r.e., by exhaustive search we can find rational numbers $a_{0} < a_{1} < \dots < a_{m}$ and $c_{0}, \dots, c_{m + 1}$ such that $a_{i} \in I$ , $c_{i} < μ (A_{i})$ and (32).

By (32) there is some $1 ⩽ j ⩽ m$ such that $c_{j} < μ (X) / m$ . Since a ρ-name of $μ (X)$ is supplied by (a name of) μ, we can find such a number j.

Suppose $c_{j} < μ (A_{j}) - 2^{- n - 1}$ . Since $c_{i} < μ (A_{i})$ for $i \neq j$ , by (32), $\begin{array}{rcl} (33) & μ (X) - 2^{- n - 1} & < & c_{0} + \sum_{i = 1}^{m} c_{i} + c_{m + 1} \\ (34) & < & μ (A_{0}) + \sum_{i = 1}^{m} μ (A_{i}) + μ (A_{m + 1}) - 2^{- n - 1} \\ (35) & ⩽ & μ (X) - 2^{- n - 1} . \end{array}$ Contradiction. Therefore, $c_{j} ⩾ μ (A_{j}) - 2^{- n - 1}$ . Since $c_{j} < μ (X) / m < 2^{- n - 1}$ , $\begin{matrix} μ (B (x, (a_{j - 1}; a_{j}))) = μ (A_{j}) ⩽ c_{j} + 2^{- n - 1} < 2^{- n - 1} + 2^{- n - 1} = 2^{- n} . \end{matrix}$ From $(a_{j - 1}; a_{j})$ we can compute some rational subinterval J with $length (J) < 2^{- n}$ . Then (29) is true. □
Lemma 6.4.
The multi-valued function mapping every sequence of real numbers that is dense in $(0; \infty)$ to some injective subsequence that is dense in $(0; \infty)$ is $(ρ^{ω}, ρ^{ω})$ -computable.
Proof.
Let ${(L_{n})}_{n \in N}$ be a computable numbering of all rational intervals $(a, b) \subseteq (0; \infty)$ . Find some number m such that $r_{m} \in L_{0}$ and let $r_{0}^{'} : = r_{m}$ . Since the relation “ $y \in J$ ” is $(ρ, I)$ -r.e. and $(r_{0}, r_{1}, \dots)$ is dense, such a number m can be computed. Suppose $r_{0}^{'}, \dots, r_{n}^{'}$ have been computed. Find some number m such that $r_{m} \in L_{n + 1}$ and $r_{m} \neq r_{i}^{'}$ for $i = 1, \dots, n$ . Since the relation “ $y \in J$ ” is $(ρ, I)$ -r.e., the relation “ $x \neq y$ ” is $(ρ, ρ)$ -r.e. and $(r_{0}, r_{1}, \dots)$ is dense, such a number m can be computed. Let $r_{n + 1}^{'} : = r_{m}$ . The sequence $(r_{0}^{'}, r_{1}^{'}, \dots)$ is injective by construction and dense since $r_{n}^{'} \in L_{n}$ . □
Proof of Theorem 6.2.
Let ${(L_{n})}_{n \in N}$ be a computable numbering of all rational intervals $(a, b) \subseteq (0; \infty)$ . Let H be the multi-function from Lemma 6.3. Let $(x_{0}, x_{1}, \dots)$ be a computable numbering of the dense set D of the metric space.

For a sequence $(μ_{0}, μ_{1}, \dots)$ of finite Borel measures on X and $j \in N$ let $(I_{0}, I_{1}, \dots)$ be a sequence of rational intervals such that: $\begin{array}{l} I_{0} = L_{j}, \\ I_{n} \in H (μ_{i}, x_{m}, I_{n - 1}, n) where (\exists l) n = ⟨ i, m, l ⟩ . \end{array}$ Since by Lemma 6.3 for $n > 0$ , ${\overline{I}}_{n} \subseteq I_{n - 1}$ and $length (I_{n}) < 2^{- n}$ , the sequence $(I_{0}, I_{1}, \dots)$ is nested and converges to some $r_{j} \in R$ .

For fixed $(i, m)$ let $n_{l} : = ⟨ i, m, l ⟩$ . The subsequence ${(I_{n_{l}})}_{l \in N}$ converges also to $r_{j}$ . By Lemma 6.3, $μ_{i} (B (x_{m}, I_{n_{l}})) < 2^{- n_{l}} ⩽ 2^{- l}$ . Since $B (x_{m}, {r_{j}}) = ⋂_{l} B (x_{m}, I_{n_{l}})$ , $μ_{i} (B (x_{m}, {r_{j}})) = 0$ . Therefore, (28) is true.

Since H is computable, from $(μ_{0}, μ_{1}, \dots)$ and j we can compute (a ρ-name of) some $r_{j}$ , hence from $(μ_{0}, μ_{1}, \dots)$ we can compute (a $ρ^{ω}$ -name of) a sequence $(r_{0}, r_{r}, \dots)$ such that (28) is true. Since $r_{j} \in L_{j}$ , the sequence $(r_{0}, r_{r}, \dots)$ is dense in $(0; \infty)$ . By Lemma 6.4 it can be transformed to an injective dense subsequence. □

For a computable measure μ on a computable σ-algebra $(Ω, A, R, α)$ , $μ (R)$ must be ρ-computable for every ring element $R \in R$ [20,24]. However, for a $δ_{M}$ -computable measure μ for every ball $B (x, r) \in β_{X}$ , $μ (B (x, r))$ is only $ρ_{<}$ -computable but not ρ-computable in general. Therefore, the ring $R$ generated by the base $β_{X}$ cannot be used to define a computable σ-algebra for which μ is a computable measure.

By these considerations the concepts of “computable measure on a computable σ-algebra” and “computable Borel measure” in Definition 6.1 seem to be incompatible. But both concepts have already been used successfully in computable measure theory, for example, [7,24] and [4,12,16].

We solve the problem by realizing that the tacit choice of $Q_{+}$ as the set of radii in the definition of the base $β_{X}$ was too restrictive. By Theorem 6.2 for a $δ_{M}$ -computable Borel measure μ we can find a dense sequence $(r_{0}, r_{1}, \dots)$ of ρ-computable radii such that $μ ({y ∣ d (x, y) = r_{i}}) = 0$ for all $x \in D$ and all i. Then $μ (B (x, r_{i}))$ is ρ-computable for all $x \in D$ and all i, and set $β_{X}^{'}$ of all these balls can then be used to define a computable σ-algebra on which μ is a computable measure.

We apply Theorem 6.2 for showing that for every sequence ${(μ_{i})}_{i}$ of finite Borel measures on a computable metric space $(X, d, D, ν_{D})$ we can compute a computable σ-algebra $(X, A, R, α)$ such that for all $i \in N$ , $μ_{i}$ is a computable measure on this σ-algebra. More precisely:
Theorem 6.5.
Let $(X, d, D, ν_{D})$ be a computable metric space with associated computable topological space $(X, τ_{X}, β_{X}, ν_{X})$ (where the radii of the balls in $β_{X}$ are rational, see the beginning of this section). Then for every $δ_{M}^{ω}$ -computable sequence $(μ_{0}, μ_{1}, \dots)$ of Borel measures we can find a computable topological space $(X, τ_{X}, β^{'}, ν^{'})$ and a computable measure space $(X, B (τ_{X}), R, α^{'})$ such that
$(X, τ_{X}, β^{'}, ν^{'})$ is equivalent [ 19 , Section 7] to $(X, τ_{X}, β_{X}, ν_{X})$ ,

$R$ is the ring generated by the base $β^{'}$ with canonical notation $α^{'}$ and

$μ_{i}$ is a computable measure on this computable measure space for all $i \in N$ .

Therefore, “computable measure on a computable σ-algebra” is a more general concept than “computable Borel measure on a computable metric space”. Proof of Theorem 6.5.
By Theorem 6.2 from the sequence ${(μ_{i})}_{i}$ we can compute a sequence $(r_{0}, r_{1}, \dots)$ of positive real numbers which is dense in $(0; \infty)$ such that $μ_{i} ({y ∣ d (ν_{D} (u), y) = r_{j}}) = 0$ for all $u \in dom (ν_{D})$ and $i, j \in N$ .

Let $β^{'} : = {B (ν_{D} (u), r_{j}) ∣ u \in dom (ν_{D}), j \in N}$ and define a notation $ν^{'}$ of $β^{'}$ by $ν^{'} ⟨ u, 0^{j} ⟩ : = B (ν_{D} (u), r_{j})$ . Then $β^{'}$ is a base of the topology generated by the metric d and $(X, τ_{X}, β^{'}, ν^{'})$ is a computable topological space which is equivalent to $(X, τ_{X}, β_{X}, ν_{X})$ [19, Definition 21].

Let $R$ be the closure of $β^{'}$ under union and set difference. We define a notation $α^{'}$ of $R$ inductively by $α^{'} (0 w) : = ν^{'} (w)$ for $w \in dom (ν^{'})$ , $α^{'} (1 ⟨ v, w ⟩) : = α^{'} (v) \cup α^{'} (w)$ and $α^{'} (2 ⟨ v, w ⟩) : = α^{'} (v) ∖ α^{'} (w)$ . Since $dom (ν_{D})$ is recursive, also $dom (ν^{'})$ and $dom (α^{'})$ are recursive. Obviously $R = range (α^{'})$ and union and set difference on $R$ are computable for $α^{'}$ .

We show that on $R$ , $μ_{i}$ is $(α^{'}, ρ)$ -computable uniformly in i. For $B : = B (ν_{D} (u), r_{j}) \in β^{'}$ let $\tilde{B} : = {x \in X ∣ d (ν_{D} (u), x) > r_{j}}$ . Then for every $B \in β^{'}$ we can compute a $θ_{X}$ -name of B and a $θ_{X}$ -name of $\tilde{B}$ .

Since $μ_{i} ({y ∣ d (ν_{D} (u), y) = r_{j}}) = 0$ for all i, $\begin{array}{rcl} (36) & X ∖ B \sim_{μ_{i}} \tilde{B} for all i \in N and B \in β^{'} . \end{array}$

If $α^{'} (w) = A$ then A is a boolean combination of balls $B_{1}, \dots, B_{k} \in β^{'}$ which can (computably) be transformed into disjunctive normal form:

$A = C_{1} \cup \dots \cup C_{m}$ with pairwise disjoint $C_{l}$ such that $C_{l} = D_{l 1} \cap \dots \cap D_{l k}$ and $D_{l n} = B_{n}$ or $D_{l n} = X ∖ B_{n}$ for all $1 ⩽ l ⩽ m$ and $1 ⩽ n ⩽ k$ .

Let $E_{l n} : = B_{n}$ if $D_{l n} = B_{n}$ and $E_{l n} : = {\tilde{B}}_{n}$ if $D_{l n} = X ∖ B_{n}$ . By (36) for all i, l, $\begin{array}{rcl} (37) & μ_{i} (C_{l}) = μ_{i} (E_{l 1} \cap \dots \cap E_{l k}) . \end{array}$ Since intersection of open sets is computable for $θ_{X}$ [19] and $(i, U) \mapsto μ_{i} (U)$ is $(ν_{N}, θ_{X}, ρ_{<})$ -computable by (36), we can compute a $ρ_{<}$ -name of $μ_{i} (C_{l})$ for every i and l. Since the $C_{l}$ are pairwise disjoint, $μ (α^{'} (w)) = μ (C_{1}) + \dots + μ (C_{m})$ . Therefore, for every i we can compute a $ρ_{<}$ -name of $μ_{i} (α^{'} (w))$ . By the same arguments we can compute a $ρ_{<}$ -name also of $μ_{i} (X ∖ α^{'} (w))$ . Since from the name of $μ_{i}$ we have a ρ-name of $μ_{i} (X)$ and since $μ_{i} (X) = μ_{i} (α^{'} (w)) + μ_{i} (X ∖ α^{'} (w))$ , we can compute a ρ-name of $μ_{i} (α^{'} (w))$ .

Therefore, for every number i, $μ_{i}$ is a computable measure on the ring. □

7. Measurable functions to computable metric spaces

A measurable function $f : Ω \to \overline{R}$ is called simple if $range (f)$ is a finite subset of $R$ . By a well-known elementary theorem a non-negative function $f : Ω \to \overline{R}$ is measurable iff $f = {sup}_{n} s_{n}$ for a sequence $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots$ of simple functions $s_{n} : Ω \to R$ . In Section 8 we will prove a computable version of this theorem as a consequence of Theorem 7.5, a more general theorem for measurable functions to computable metric spaces. Again we apply Theorem 6.2.

Let $(Ω, A, R, α)$ be a computable σ-algebra with computable measure μ and let $(X, d, D, ν_{D})$ be a computable metric space. Let $(X, τ_{X}, β_{X}, ν_{X})$ be the associated computable topological space where $ν_{X}$ , $ν_{X} ⟨ u, v ⟩ : = B (ν_{D} (u), ν_{Q} (v))$ , is a natural notation of the set of open rational balls.

On the set $X^{Ω}$ of functions $f : Ω \to X$ we define the “uniform metric” $\tilde{d}$ by $\tilde{d} (f, g) : = {sup}_{x \in Ω} d (f (x), g (x))$ . The function $\tilde{d}$ is not a metric in the proper meaning since possibly, $\tilde{d} (f, g) = \infty$ .7

⁷
Infinite distances can be avoided by using the metric $d^{'} (x, y) : = d (x, y) / (1 + d (x, y))$ on X.

If a sequence

{(f_{i})}_{i \in N}

of measurable functions converges to

f : Ω \to X

, then f is measurable. We prove a computable version of this fact.

Theorem 7.1.

The operator $LIM$ mapping every sequence $(f_{0}, f_{1}, \dots)$ of measurable functions such that $(\forall i < j) \tilde{d} (f_{i}, f_{j}) < 2^{- i}$ which has a limit to its limit is $(δ_{mf}^{ω}, δ_{mf})$ -computable.

The limit of the sequence $(f_{0}, f_{1}, \dots)$ exists if the metric space is complete.

Proof.

Let $f : Ω \to X$ be the limit of the sequence $(f_{0}, f_{1}, \dots)$ . Then $d (f_{k} (x), f (x)) ⩽ 2^{- k}$ for all $x \in Ω$ . We prove $\begin{array}{rcl} (38) & f^{- 1} B (e, r) & = & ⋃ {f_{k}^{- 1} B (e^{'}, 2^{- k}) ∣ e^{'} \in D, d (e, e^{'}) < r - 2 \cdot 2^{- k}} \end{array}$ for all $e \in D$ and $r > 0$ .

Suppose $x \in f_{k}^{- 1} B (e^{'}, 2^{- k})$ for some $e^{'} \in D$ with $d (e, e^{'}) < r - 2 \cdot 2^{- k}$ . Since $d (e, f (x)) ⩽ d (e, e^{'}) + d (e^{'}, f_{k} (x)) + d (f_{k} (x), f (x)) < r - 2 \cdot 2^{- k} + 2^{- k} + 2^{- k} = r$ , $x \in f^{- 1} B (e, r)$ . This proves “⊇” in (38).

On the other hand suppose $x \in f^{- 1} B (e, r)$ . Since D is dense there are some k and some $e^{'} \in D$ such that $d (e, f (x)) < r - 4 \cdot 2^{- k}$ and $d (f_{k} (x), e^{'}) < 2^{- k}$ . Then $x \in f_{k}^{- 1} B (e^{'}, 2^{- k})$ and $d (e, e^{'}) ⩽ d (e, f (x)) + d (f (x), f_{k} (x)) + d (f_{k} (x), e^{'}) < r - 4 \cdot 2^{- k} + 2^{- k} + 2^{- k} = r - 2 \cdot 2^{- k}$ . This proves “⊆” in (38).

By Theorem 5.4 it suffices to prove $(δ_{mfb}^{ω}, δ_{mfb})$ -computability. Therefore, from $p = ⟨ p_{0}, p_{1}, \dots ⟩$ such that $f_{i} \in δ_{mfb} (p_{i})$ we want to compute some q such that $f \in δ_{mfb} (q)$ if $f = LIM (f_{0}, f_{1}, \dots)$ exists.

We show that using (38) from p and $⟨ u, v ⟩$ we can compute some $\overline{q} \in Σ^{ω}$ such that $f^{- 1} B (e, r) \in ζ_{+} (\overline{q})$ where $e = ν_{D} (u)$ and $r = ν_{Q} (v)$ , hence $B (e, r) = ν_{X} ⟨ u, v ⟩$ . From $⟨ u, v ⟩$ we can compute a list of all $(k, u^{'}, v^{'})$ such that $ν_{Q} (v^{'}) = 2^{- k}$ and $d (ν_{D} (u), ν_{D} (u^{'})) < ν_{Q} (v) - 2 \cdot 2^{- k}$ . By (20) and the universal Turing machine theorem for $η^{* ω}$ for every $(k, u^{'}, v^{'})$ in this list we can compute some $q^{'}$ such that $f_{k}^{- 1} B (ν_{D} (u^{'}), ν_{Q} (v^{'})) = f_{k}^{- 1} ν_{X} ⟨ u^{'}, v^{'} ⟩ \in ζ_{+} (q^{'})$ . By Theorem 4.1 we can compute a $ζ_{+}$ -name $\overline{q}$ of the union of all these $f_{k}^{- 1} B (ν_{D} (u^{'}), ν_{Q} (v^{'}))$ , that is, a $ζ_{+}$ -name of $f^{- 1} B (e, r) = f^{- 1} \circ ν_{X} ⟨ u, v ⟩$ by (38) if $f = LIM (f_{0}, f_{1}, \dots)$ exists.

This means that there is a computable function H such that $f^{- 1} ν_{X} (w) \in ζ_{+} \circ H (p, w)$ . By the smn-theorem for $η^{* ω}$ there is a computable function G such that $H (p, w) = η_{G (p)}^{* ω} (w)$ . By (20), $f \in δ_{mfb} \circ G (p)$ . □

Definition 7.2.

Let $F$ be the set of measurable functions $f : Ω \to X$ and let $SF$ be the set of functions $s \in F$ such that $range (s)$ is a finite subset of the dense set D.

Define a multi-representation $δ_{SF} ⇉ Σ^{ω} \to SF$ as follows:

$s \in δ_{SF} (p)$ iff for some $m ⩾ 1$ there are words $u_{1}, \dots, u_{m} \in dom (ν_{D})$ , sequences $p_{1}, \dots, p_{m} \in dom (ζ_{+})$ and sets $A_{1}, \dots, A_{m}$ such that $\begin{array}{l} (39) & p = ⟨ 0^{m}, ⟨ u_{1}, p_{1} ⟩, \dots, ⟨ u_{m}, p_{m} ⟩ ⟩, \\ (40) & A_{1} \cup \dots \cup A_{m} = Ω, A_{i} \cap A_{k} = \emptyset for i \neq k, \\ (41) & A_{i} \in ζ_{+} (p_{i}), \\ (42) & s (x) = ν_{D} (u_{i}) for x \in A_{i} . \end{array}$

In general the $A_{i}$ in (40) are not a partition since $A_{i} = \emptyset$ is allowed. Also $s (x) = s (y)$ if $x \in A_{i}$ and $y \in A_{j}$ for $i \neq j$ is allowed.

Lemma 7.3.

If $s, t \in δ_{SF} (p)$ then $s \sim t$ .

$δ_{SF} ⩽ δ_{mf}$ .

Define a representation $δ_{SF}^{'}$ in the same way as $δ_{SF}$ (Definition 7.2 ) but with ζ instead of $ζ_{+}$ . Then $δ_{SF}^{'} \equiv δ_{SF}$ .

Proof.

1. Suppose $s, t \in δ_{SF} (p)$ with p as in Definition 7.2. Let $A_{i}$ be measurable such that (40)–(41) and $B_{i}$ measurable sets such that correspondingly $B_{1} \cup \dots \cup B_{m} = Ω$ , $B_{i} \cap B_{k} = \emptyset$ for $i \neq k$ , $t (x) = ν_{D} (u_{i})$ for $x \in B_{i}$ and $B_{i} \in ζ_{+} (p_{i})$ .

We have $μ {x \in A_{i} \cap B_{i} ∣ s (x) \neq t (x)} = μ (\emptyset) = 0$ . Suppose $i \neq k$ . Since $A_{i} \cap A_{k} = \emptyset$ and $A_{k}, B_{k} \in ζ_{+} (p_{k})$ implies $A_{k} \sim B_{k}$ , that is, $μ (A_{k} Δ B_{k}) = 0$ , $μ ({x \in A_{i} \cap B_{k} ∣ s (x) \neq t (x)}) ⩽ μ (A_{i} \cap B_{k}) ⩽ μ (A_{i} \cap (A_{k} \cup (A_{k} Δ B_{k}))) ⩽ μ (A_{k} Δ B_{k}) = 0$ .

Since $Ω = ⋃_{i} A_{i} \cap ⋃_{k} B_{k} = ⋃_{i, k} A_{i} \cap B_{k}$ , $μ ({x \in Ω ∣ s (x) \neq t (x)}) = μ ({x \in ⋃_{i, k} A_{i} \cap B_{k} ∣ s (x) \neq t (x)}) ⩽ \sum_{i, k} μ ({x \in A_{i} \cap B_{k} ∣ s (x) \neq t (x)}) = 0$ . Therefore, $s \sim t$ by (18).

2. By Theorem 5.4 it suffices to prove $δ_{SF} ⩽ δ_{mfb}$ . Since $ν_{X} ⟨ u, v ⟩ = B (ν_{D} (u), ν_{Q} (v))$ , for $s \in δ_{SF} (p)$ as in Definition 7.2, $\begin{matrix} s^{- 1} ν_{X} ⟨ u, v ⟩ = ⋃ {A_{i} ∣ d (ν_{D} (u), ν_{D} (u_{i})) < ν_{Q} (v)}, \end{matrix}$ where $A_{i} \in ζ_{+} (p_{i})$ . There is a computable $p^{'} \in Σ^{ω}$ such that $\emptyset \in δ_{mf} (p^{'})$ . Since the distance on D is $(ν_{D}, ν_{D}, ρ)$ -computable, from $(p, ⟨ u, v ⟩)$ we can compute a sequence $⟨ q_{0}, q_{1}, \dots ⟩$ such that $\begin{matrix} {q_{i} ∣ i \in N} = {p^{'}} \cup ⋃ {p_{i} ∣ 1 ⩽ i ⩽ m, d (ν_{D} (u), ν_{D} (u_{i})) < ν_{Q} (v)} . \end{matrix}$ Since $A_{i} \in ζ_{+} (p_{i})$ and countable union is computable w.r.t. $ζ_{+}$ , there is a computable function H such that $s^{- 1} ν_{X} ⟨ u, v ⟩ \in ζ_{+} \circ H (p, ⟨ u, v ⟩)$ . By the smn-theorem there is a computable function $G : Σ^{ω} \to Σ^{ω}$ such that $H (p, w) = η_{G (p)}^{* ω} (w)$ . By Definition 5.2, $s \in δ_{mfb} \circ G (p)$ . Therefore, $δ_{SF} ⩽ δ_{mfb}$ .

3. $δ_{SF}^{'} ⩽ δ_{SF}$ follows from $ζ ⩽ ζ_{+}$ . On the other hand, suppose $s \in δ_{SF} (q)$ as in Definition 7.2. From the $ζ_{+}$ -names of the $A_{i}$ we want to compute ζ-names. Since Ω is the disjoint union of the $A_{i}$ , $A_{1} = Ω ∖ (A_{2} \cup \dots \cup A_{m})$ . By Theorem 4.1, from the $ζ_{+}$ -names of the $A_{i}$ we can compute a $ζ_{+}$ -name of $(A_{2} \cup \dots \cup A_{m})$ and hence a $ζ_{-}$ -name of its complement $A_{1}$ . By Lemma 3.4 we can compute a ζ-name of $A_{1}$ . Correspondingly we can compute ζ-names of the other sets $A_{i}$ . □

If $s \in δ_{SF} (p)$ , $t \in SF$ and $s \sim t$ , then in general $t \notin δ_{SF} (p)$ , since $range (s) \subseteq {ν_{D} (u_{1}), \dots, ν_{D} (u_{m})}$ but possibly for some set B of measure 0, $t (x)$ is not in this set for $x \in B$ .

Lemma 7.4.

Let $h : D \times D \to D$ be computable for $ν_{D}$ . Define $H : SF \times SF \to SF$ by $H (s, s^{'}) (x) : = h (s (x), s^{'} (x))$ . Then H is computable for $δ_{SF}$ .

Proof.

Let $t (x) : = h (s (x), s^{'} (x))$ . Suppose $s \in δ_{SF} (⟨ 0^{m}, ⟨ u_{1}, p_{1} ⟩, \dots, ⟨ u_{m}, p_{m} ⟩ ⟩)$ with sets $A_{1}, \dots, A_{m}$ as in Definition 7.2 and $s^{'} \in δ_{SF} (⟨ 0^{m^{'}}, ⟨ u_{1}^{'}, p_{1}^{'} ⟩, \dots, ⟨ u_{m}^{'}, p_{m}^{'} ⟩ ⟩)$ correspondingly with sets $A_{1}^{'}, \dots, {A_{m^{'}}}^{'}$ .

Then $x = ν_{D} (u_{i})$ for $x \in A_{i} \in ζ_{+} (p_{i})$ and $x = ν_{D} (u_{j}^{'})$ for $x \in A_{j}^{'} \in ζ_{+} (p_{j}^{'})$ .

Define a bijection $ϕ : {1, \dots, m} \times {1, \dots, m^{'}} \to {1, \dots, m \cdot m^{'}}$ by $ϕ (i, j) : = (i - 1) \cdot m^{'} + j$ . Then $\begin{matrix} t (x) = h (ν_{D} (u_{i}), ν_{D} (u_{j}^{'})) for x \in B_{ϕ (i, j)} : = A_{i} \cap A_{j}^{'} . \end{matrix}$ From the given data and i, j we can compute some $v_{ϕ (i, j)}$ such that $h (ν_{D} (u_{i}), ν_{D} (u_{j}^{'})) = ν_{D} (v_{ϕ (i, j)})$ (since h is computable) and some $r_{ϕ (i, j)}$ such that $A_{i} \cap A_{j}^{'} = ζ_{+} (r_{ϕ (i, j)})$ (since intersection on $A$ is computable for $ζ_{+}$ ). Then $\begin{matrix} t \in ζ_{+} (⟨ 0^{m \cdot m^{'}}, ⟨ v_{1}, r_{1} ⟩, \dots, ⟨ v_{m \cdot m^{'}}, r_{m \cdot m^{'}} ⟩ ⟩) . \end{matrix}$ Therefore, from $δ_{SF}$ -names of s and $s^{'}$ we can compute a $δ_{SF}$ -name of t. □

In general the set $SF$ is not dense in the metric space $(F, \tilde{d})$ of measurable functions $f : Ω \to X$ .

Example 7.1.

Consider the computable measure space $(R, B, R, α)$ where $R$ is the ring generated by the set $Int$ of rational intervals $(a; b)$ , $B = A (R)$ is the set of Borel sets, and α is a canonical notation of $R$ . Furthermore, let λ the Lebesgue measure on $B$ . For the co-domain consider the computable metric space $(R, d_{E}, Q, ν_{Q})$ with Euclidean metric $d_{E}$ . The identity $f : x \mapsto x$ is measurable since $f^{- 1} (I) = I$ is measurable for every rational open interval I. But for every measurable function s with finite range, $\tilde{d} (f, s) = \infty$ .

If, however, the metric space is compact then the set $SF$ is dense in the space $(F, \tilde{d})$ . We prove a computable version. In the proof we apply Theorem 6.2.

A computable topological space is computable compact iff $X \in κ (p)$ for some computable p ([19, Definition 5] (see also [17, Section 5.2] for the special case $X = R^{n}$ ). Therefore, the computable metric space $(X, d, D, ν_{D})$ is computable compact, iff X is compact and there is a computable listing of the set of all $⟨ 0^{n}, w_{1}, \dots, w_{n} ⟩$ such that $X = ν_{X} (w_{1}) \cup \dots \cup ν_{X} (w_{n})$ .

Theorem 7.5.

Let X be a computable compact computable metric space. Then the multi-function $C : F \times N ⇉ SF$ mapping every measurable function $f : Ω \to X$ and number n to some simple function $s : Ω \to X$ , $s \in SF$ , such that $\tilde{d} (f, s) < 2^{- n}$ is $(δ_{mf}, ν_{N}, δ_{SF})$ -computable.

In particular, the set $SF$ is dense in $F$ . However, in general the set $SF$ is not countable and the distance $\tilde{d}$ is not computable on $SF$ , hence we have no computable metric space for the set $F$ of measurable functions. Proof of Theorem 7.5.

Let $R_{0}, R_{1}, \dots$ be a computable numbering of the ring $R$ . Let n and (a $δ_{mf}$ -name of) f be given. Define a sequence $(μ_{0}, μ_{1}, \dots)$ of finite measures on the measure space $(X, A (τ_{X}))$ by $\begin{matrix} μ_{i} (B) : = μ (R_{i} \cap f^{- 1} (B)) \end{matrix}$ for $B \in A (τ_{X})$ .

First, from f and i we want to compute a $δ_{M}$ -name of $μ_{i}$ (Definition 6.1). By Theorem 5.4 and (20) from v, w we can compute a $ζ_{+}$ -name of $f^{- 1} (B (ν_{D} (v), ν_{Q} (w)))$ . Since union on $A$ is computable for $ζ_{+}$ (Theorem 4.1), from $(v_{1}, w_{1}, \dots, v_{m}, w_{m})$ we can compute a $ζ_{+}$ -name of $C : = f^{- 1} (B (ν_{D} (v_{1}), ν_{Q} (w_{1})) \cup \dots \cup B (ν_{D} (v_{m}), ν_{Q} (w_{m})))$ . By [20] we can compute a $ρ_{<}$ -name of $μ (C)$ . Therefore, we can produce a list of all $⟨ u, ⟨ v_{1}, w_{1} ⟩, \dots, ⟨ v_{n}, w_{n} ⟩ ⟩$ such that (27). Since a ρ-name of $μ_{i} (X) = μ (R_{i})$ can be computed we can compute a $δ_{M}$ -name of $μ_{i}$ . Therefore, we can compute a $δ_{M}^{ω}$ -name of the sequence $(μ_{0}, μ_{1}, \dots)$ .

By Theorem 6.2 we can compute an injective sequence of real numbers $(r_{0}, r_{1}, \dots)$ which is dense in the interval $(0; \infty)$ such that (28), that is, $(\forall x \in D) (\forall i, j) μ_{i} (B (x, {r_{j}})) = 0$ . For all $x \in D$ and j, $\begin{matrix} μ (B (x, {r_{j}})) = μ (⋃_{i} (R_{i} \cap B (x, {r_{j}}))) ⩽ \sum μ_{i} (B (x, {r_{j}})) = 0 . \end{matrix}$ Since our metric space is computable compact, for n we can find some m and words $v_{1}, w_{1}, \dots, v_{m}, w_{m}$ such that $(\forall j) ν_{Q} (w_{j}) < 2^{- n - 1}$ and $X = ⋃_{j = 1}^{m} B (ν_{D} (v_{j}), ν_{Q} (w_{j}))$ . Since the $r_{j}$ are dense, we can find $(l_{1}, \dots, l_{m})$ such that $(\forall j) ν_{Q} (w_{j}) < r_{l_{j}} < 2^{- n}$ . For $j = 1, \dots, m$ let $V_{j} : = f^{- 1} (B (ν_{D} (v_{j}), r_{l_{j}}))$ . Then $Ω = ⋃_{j = 1}^{m} V_{j}$ .

For $e = (e_{1}, \dots, e_{m}) \in {0, 1}^{m}$ let $V^{e} : = V_{1}^{e_{1}} \cap \dots \cap V_{m}^{e_{m}}$ where $V_{j}^{0} : = V_{j}$ and $V_{j}^{1} : = Ω ∖ V_{j}$ . Then $V^{e} \cap V^{e^{'}} = \emptyset$ for $e \neq e^{'}$ , $V^{(1, \dots, 1)} = \emptyset$ since $Ω = ⋃_{i} V_{i}$ , and $\begin{matrix} Ω = (V_{1}^{0} \cup V_{1}^{1}) \cap \dots \cap (V_{m}^{0} \cup V_{m}^{1}) = ⋃ {V^{e} ∣ e \in {0, 1}^{m}} . \end{matrix}$

For $e = (e_{1}, \dots, e_{m}) \neq (1, \dots, 1)$ let $k_{e}$ the smallest number j such that $e_{j} = 0$ . Define $s_{n} : Ω \to X$ by $\begin{matrix} s (x) : = ν_{D} (v_{k_{e}}) if x \in V^{e}, for all e \neq (1, \dots, 1) . \end{matrix}$ Since $V^{e} \subseteq V_{k_{e}}^{0} = V_{k_{e}} \subseteq f^{- 1} (B (ν_{D} (v_{k_{e}}), 2^{- n}))$ , $d (ν_{D} (v_{k_{e}}), f (x)) < 2^{- n}$ for all $x \in V^{e}$ . Since the sets $V^{e}$ are measurable, $s \in SF$ and $d (s (x), f (x)) < 2^{- n}$ for all $x \in Ω$ .

It remains to show that from f and n we can compute s. As we have already shown we can compute a sequence $r_{0}, r_{1}, \dots$ , we can compute some m and words $v_{1}, w_{1}, \dots, v_{m}, w_{m}$ , a sequence $(l_{1}, \dots, l_{m})$ and $k_{e}$ for every $e \neq (1, \dots, 1)$ . It remains to compute $ζ_{+}$ -names of the $V^{e}$ .

For every j we can compute a $θ_{X}$ -name of $B (ν_{D} (v_{j}), r_{l_{j}})$ , hence by Theorem 5.4 a $ζ_{+}$ -name of $V_{j}^{0} = V_{j} = f^{- 1} ({x ∣ d (ν_{D} (v_{j}), x) < r_{l_{j}}})$ . Correspondingly we can compute a $ζ_{+}$ -name of $W_{j} : = f^{- 1} ({x ∣ d (ν_{D} (v_{j}), x) > r_{l_{j}}})$ . Since $μ (B (ν_{D} (v_{j}), {r_{l_{j}}})) = 0$ , $W_{j} \sim Ω ∖ V_{j} = V_{j}^{1}$ . Therefore, for every j we can compute a $ζ_{+}$ -name of $V_{j}^{0}$ and a $ζ_{+}$ -name of $V_{j}^{1}$ . Since intersection is computable for $ζ_{+}$ (Theorem 4.1), we can compute $ζ_{+}$ names of the $V^{e}$ .

Therefore, from f and n we can compute a $δ_{SF}$ -name of a function s such that $\tilde{d} (f, s) < 2^{- n}$ . □

Corollary 7.6.

Let $(X, d)$ be a computable compact computable metric space.

The multi-function $K : F ⇉ {SF}^{ω}$ mapping every measurable function $f : Ω \to X$ to some sequence of simple functions $s_{0}, s_{1}, \dots$ such that $(\forall n) \tilde{d} (f, s_{n}) < 2^{- n}$ is $(δ_{mf}, δ_{SF}^{ω})$ -computable.

The function $L : {SF}^{ω} \to F$ mapping every sequence $s_{0}, s_{1}, \dots$ of simple functions such that $\tilde{d} (s_{m}, s_{n}) < 2^{- n}$ for all $n > m$ to its limit $f \in F$ is $(δ_{SF}^{ω}, δ_{mf})$ -computable.

Proof.

Observe that $(X, d)$ and remember $δ_{SF} ⩽ δ_{mf}$ . Apply Theorems 7.5 and 7.1. □

8. Measurable numerical functions

A non-negative function $f : Ω \to \overline{R}$ is measurable iff $f = {sup}_{n} s_{n}$ for a sequence $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots$ of simple functions $s_{n} : Ω \to R$ . In this section we study computability on the measurable numerical functions $f : Ω \to \overline{R}$ and in particular prove a computable version of this theorem.

Computability on the real line can be defined via the computable topological space $(R, τ_{R}, Int, ν_{I})$ where $τ_{R}$ is the real line topology, $Int : = {(a; b) ∣ a, b \in Q, a < b}$ (the set of rational open intervals) and $ν_{I} : \subseteq Σ^{*} \to Int$ is a canonical notation with recursive domain [1,17,19]. For the standard representation ρ of $R$ , $ρ (p) = x$ iff p is (encodes) a list of all $(a, b) \in Int$ such that $x \in I$ .

For functions $f : Ω \to \overline{R}$ we consider the computable topological space $(\overline{R}, \overline{τ}, \overline{β}, \overline{ν})$ where $\overline{R} : = R \cup {- \infty, \infty}$ is the extended real line, $\overline{ν}$ is a canonical notation of the set of intervals $\overline{β} : = {[- \infty; a), (a; b), (a; \infty] ∣ a, b \in Q, a < b}$ and $\overline{τ}$ is the topology generated by $\overline{β}$ as a base. Let $\overline{ρ}$ and $\overline{θ}$ be the standard representations of the points and the open sets, respectively [17,19]. A $\overline{ρ}$ -name of $x \in \overline{R}$ is a list of all $I \in \overline{β}$ such that $x \in I$ . The representation $\overline{ρ}$ is equivalent to ${\overline{ρ}}^{'}$ and to ${\overline{ρ}}^{″}$ where ${\overline{ρ}}^{'} (p) = x$ iff p is (encodes) a sequence $(I_{0}, I_{1}, \dots)$ of intervals from $\overline{β}$ such that $I_{0} \supseteq I_{1} \supseteq \dots$ and ${x} = ⋂_{i} I_{i}$ and ${\overline{ρ}}^{″} (p) = x$ iff p is (encodes) a sequence $(I_{0}, I_{1}, \dots)$ of intervals from $\overline{β}$ such that ${x} = ⋂_{i} I_{i}$ [17, Definition 4.1.21].

$(R, τ_{R})$ is a subspace of $(\overline{R}, \overline{τ})$ . The restriction of $\overline{ρ}$ to $R$ is equivalent to the standard representation ρ of $R$ : $\begin{array}{rcl} (43) & \overline{ρ} |^{R} & \equiv & ρ . \end{array}$

The functions $- x$ , $| x |$ , $max (x, y)$ , $x^{+} : = max (0, x)$ and $x^{-} : = max (- x, 0)$ have (straightforward) continuous extensions to $\overline{R}$ .

We extend addition to $\overline{R} \times \overline{R} ∖ {(\infty, - \infty), (- \infty, \infty)}$ by $\infty + x : = x + \infty : = \infty$ for $- \infty < x$ and $- \infty + x : = x - \infty : = - \infty$ for $x < \infty$ .

We extend multiplication on $R$ to $\overline{R}$ as follows: $x \cdot y$ is undefined for $(x, y) \in {(0, \infty), (\infty, 0), (0, - \infty), (- \infty, 0)}$ and for $0 < x < \infty$ , $x \cdot \infty : = (- x) \cdot (- \infty) : = \infty \cdot x : = (- \infty) \cdot (- x) : = \infty$ and $x \cdot (- \infty) : = (- x) \cdot \infty : = \infty \cdot (- x) : = (- \infty) \cdot x : = - \infty$ .

Addition and multiplication are associative. Distributivity is not true in general.8

⁸
$(2 - 1) \cdot \infty = 1 \cdot \infty = \infty$ but $2 \cdot \infty - 1 \cdot \infty$ is undefined.

Lemma 8.1.

For the representation $\overline{ρ}$ of $\overline{R}$ ,

the functions $- x$ , $| x |$ , $max (x, y)$ , $x^{+}$ and $x^{-}$ are computable,

addition is computable on $\overline{R} \times \overline{R} ∖ {(\infty, - \infty), (- \infty, \infty)}$ ,

multiplication is computable on $\overline{R} \times \overline{R} ∖ {(0, \infty), (\infty, 0), (0, - \infty), (- \infty, 0)}$ .

Proof.

For rational $a < b$ let $⟪ a; b ⟫ : = (a; b)$ , $⟪ - \infty; b ⟫ : = [- \infty; b)$ and $⟪ a; \infty ⟫ : = (a; \infty]$ .

$- x$ : There is a machine that transforms every sequence $(⟪ a_{0}; b_{0} ⟫, ⟪ a_{1}; b_{1} ⟫, \dots)$ to the sequence $(⟪ - b_{0}; - a_{0} ⟫, ⟪ - b_{1}; - a_{1} ⟫, \dots)$ . Then it maps every $\overline{ρ}$ -name of some $x \in \overline{R}$ to a $\overline{ρ}$ -name of $- x$ .

$x + y$ : There is a machine that on input $((⟪ a_{0}; b_{0} ⟫, ⟪ a_{1}; b_{1} ⟫, \dots), (⟪ a_{0}^{'}; b_{0}^{'} ⟫, ⟪ a_{1}^{'}; b_{1}^{'} ⟫, \dots))$ first searches for some k such that $⟪ a_{k} + a_{k}^{'}; b_{k} + b_{k}^{'} ⟫ \neq [- \infty; \infty]$ and then prints $⟪ a_{k + j} + a_{k + j}^{'}; b_{k + j} + b_{k + j}^{'} ⟫$ for $k = 0, 1, 2, \dots$ . This machine maps ${\overline{ρ}}^{'}$ -names of x and y such that ${x, y} \neq {- \infty, \infty}$ to a ${\overline{ρ}}^{'}$ -name of $x + y$ .

The other statements can be proved similarly. □

Addition on $\overline{R}$ has no continuous extension to any point from $(\infty, - \infty)$ and $(- \infty, \infty)$ . Multiplication on $\overline{R}$ has no continuous extension to any point from ${(0, \infty), (\infty, 0), (0, - \infty), (- \infty, 0)}$ .

In measure theory usually multiplication is extended from $[0; \infty)$ to $[0; \infty]$ by $0 \cdot \infty : = \infty \cdot 0 : = 0$ and $a \cdot \infty : = \infty \cdot a : = \infty$ for $0 < a ⩽ \infty$ . As a partial function on $\overline{R} \times \overline{R}$ this multiplication is not continuous in the points $(0, \infty)$ and $(\infty, 0)$ and therefore not $(\overline{ρ}, \overline{ρ}, \overline{ρ})$ -continuous and not $(\overline{ρ}, \overline{ρ}, \overline{ρ})$ -computable.

Let $δ_{mf}$ be the multi-representation of the measurable functions $f : Ω \to \overline{R}$ .

Corollary 8.2.

For $a \in \overline{R}$ and measurable functions $f, g : Ω \to \overline{R}$ , the operations $f \mapsto - f$ , $f \mapsto | f |$ , $(f, g) \mapsto max (f, g)$ , $f \mapsto f^{+}$ , $f \mapsto f^{-}$ , $(a, f) \mapsto a f$ , $(f, g) \mapsto (f + g)$ and $(f, g) \mapsto f \cdot g$ are computable for $\overline{ρ}$ and $δ_{mf}$ where the domains are defined in accordance with Theorem 5.10 .

Proof.

By Theorem 5.10 and Lemma 8.1. □

Lemma 8.3.

The function $A \mapsto 1_{A}$ is $(ζ_{+}, δ_{mf})$ -computable.

Proof.

Let $q_{0}$ be a list of all $⟨ u, v ⟩$ such that $ν_{Q} (u) < 0$ and $v \in dom (α)$ . Then $\emptyset \in δ_{mf} (q_{0})$ by Definition 3.2. There is a computable function $h : Σ^{ω} \times Σ^{*} \to Σ^{ω}$ such that $\begin{matrix} h (q, u) = \{\begin{matrix} q & if 1 \in \overline{ν} (u), \\ q_{0} & if 1 \notin \overline{ν} (u) . \end{matrix} \end{matrix}$ Then for $A \in δ_{mf} (q)$ , $\begin{matrix} {(1_{A})}^{- 1} (\overline{ν} (u)) \in \{\begin{matrix} ζ_{+} (q) & if 1 \in \overline{ν} (u), \\ ζ_{+} (q_{0}) & if 1 \notin \overline{ν} (u) \end{matrix} = ζ_{+} \circ h (p, u) . \end{matrix}$ By the smn-theorem there is a computable function $g : Σ^{ω} \to Σ^{ω}$ such that $h (q, u) = η_{g (q)}^{* ω} (u)$ . Since for all $u \in dom (ν_{Q})$ , ${(1_{A})}^{- 1} (\overline{ν} (u)) \in ζ_{+} \circ η_{g (q)}^{* ω} (u)$ , $1_{A} \in δ_{mbf} (g (p))$ by Definition 5.2. Since $1_{A} \in δ_{mbf} (g (p))$ if $A \in δ_{mf} (q)$ , $A \mapsto 1_{A}$ is $(ζ_{+}, δ_{mbf})$ -computable, hence $(ζ_{+}, δ_{mf})$ -computable by Theorem 5.4. □

We want to apply Theorem 7.5 to the set $F$ of measurable numerical functions $f : Ω \to \overline{R}$ . Therefore, we need a metric on $\overline{R}$ . Let further on $(\overline{R}, \overline{τ}, \overline{β}, \overline{ν})$ be the computable topological space for the extended real line.

Definition 8.4.

Define a computable metric space $(\overline{R}, \overline{d}, Q, ν_{Q})$ by $\overline{d} (x, y) : = | φ (x) - φ (y) |$ , where $φ (x) : = x / (1 + | x |)$ .

Notice that $φ (\infty) = 1$ , $φ (- \infty) = - 1$ and $φ^{- 1} (y) = y / (1 - | y |)$ . The function φ is increasing and hence a bijection from $\overline{R}$ to $[- 1; 1]$ . It maps $Q$ bijectively to $Q \cap [- 1; 1]$ . Therefore, $\overline{d}$ is a metric.

Lemma 8.5.

$(\overline{R}, \overline{d}, Q, ν_{Q})$ is a computable compact computable metric space. 9

⁹

See the definition before Theorem 7.5.

Let $(\overline{R}, τ^{'}, β^{'}, ν^{'})$ be the associated computable topological space where $ν^{'}$ is a canonical notation of the rational balls. 10

¹⁰

Called $(X, τ_{X}, β_{X}, ν_{X})$ at the beginning of Section 6.

Then

\overline{τ} = τ^{'}

\overline{β} = β^{'}

and

\overline{ν} \equiv ν^{'}

$(\overline{R}, \overline{τ}, \overline{β}, \overline{ν})$ and $(\overline{R}, τ^{'}, β^{'}, ν^{'})$ are equivalent computable topological spaces and induce the same computability on $\overline{R}$ .

Proof.

1. Since the restriction of φ to $Q$ is computable, $\overline{d}$ is computable on $Q$ , hence we have a computable metric space. The metric space $(\overline{R}, \overline{d})$ is compact. The property $\overline{R} = B (a_{1}, r_{1}) \cup \dots \cup B (a_{n}, r_{n})$ for rational $a_{i}$ , $r_{i}$ can be decided. Therefore, the set of all these finite unions can be enumerated.

2. Straightforward.

3. This follows from 2. □

We can now prove the main theorem of this section. Consider Definition 7.2 for the computable metric space $(\overline{R}, \overline{d}, Q, ν_{Q})$ . Notice that $range (s) \subseteq Q$ for every $s \in SF$ . Let $\tilde{d}$ be the distance on the set of measurable functions defined by $\tilde{d} (f, g) : = {sup}_{x \in Ω} \overline{d} (f (x), g (x))$ introduced at the beginning of Section 7. Theorem 8.6.

The multi-valued operator T mapping every non-negative measurable function $f : Ω \to \overline{R}$ to a sequence $(s_{0}, s_{1}, \dots)$ of functions $s_{n} \in SF$ such that $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots$ , $f = {sup}_{n} s_{n}$ and $(\forall x \in Ω) \overline{d} (s_{n} (x), f (x)) < 2^{- n}$ is $(δ_{mf}, δ_{SF}^{ω})$ -computable.

The inverse $T^{- 1}$ of T mapping every sequence $(s_{0}, s_{1}, \dots)$ of functions $s_{n} \in SF$ such that $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots$ and $(\forall x \in Ω) \overline{d} (s_{n} (x), f (x)) < 2^{- n}$ to $f : = {sup}_{n} s_{n}$ is $(δ_{SF}^{ω}, δ_{mf})$ -computable.

Proof.

1. Since the metric space $(\overline{R}, \overline{d}, Q, ν_{Q})$ is computable compact by Theorem 7.5 from f we can compute a sequence $(t_{0}, t_{1}, \dots)$ of functions in $SF$ such that for all n, $(\forall x \in Ω) \overline{d} (f (x), t_{n} (x)) < 2^{- n}$ . First, we compute a sequence $(t_{0}^{'}, t_{1}^{'}, \dots)$ in $SF$ such that $t_{n}^{'} ⩽ t$ and $(\forall x \in Ω) \overline{d} (f (x), t_{n} (x)) < 2^{- n}$ for all n.

For $x \in \overline{R}$ let $φ (x) : = x / (1 + | x |)$ . Define $g : N \times Q \to Q$ by $g (n, a) : = φ^{- 1} \circ max (0, φ (a) - 2^{- n - 1})$ . We show that for $z ⩾ 0$ , $\begin{matrix} (44) & \overline{d} (a, z) < 2^{- n - 1} ⟹ (g (n, a) ⩽ z and \overline{d} (g (n, a), z) < 2^{- n}) . \end{matrix}$ Suppose $\overline{d} (a, z) < 2^{- n - 1}$ . Then $φ (a) - 2^{- n - 1} < φ (z) < φ (a) + 2^{- n - 1}$ . Since $0 ⩽ φ (z)$ by $0 ⩽ z$ , $φ (z) - 2 \cdot 2^{- n - 1} < φ (a) - 2^{- n - 1} ⩽ max (0, φ (a) - 2^{- n - 1}) = φ \circ g (n, a) = max (0, φ (a) - 2^{- n - 1}) ⩽ φ (z)$ . Therefore, $g (n, a) ⩽ z$ and $\overline{d} (g (n, a), z) = | φ (z) - φ \circ g (n, a) | = φ (z) - φ \circ g (n, a) < 2^{- n}$ . This proves (44).

Suppose $t_{n + 1} \in δ_{SF} (q)$ where $q = ⟨ 0^{m}, ⟨ u_{1}, p_{1} ⟩, \dots, ⟨ u_{m}, p_{m} ⟩ ⟩$ with pairwise disjoint measurable sets $A_{i} \in ζ_{+} (p_{i})$ such that $Ω = ⋃ A_{i}$ and $\begin{matrix} (\forall 1 ⩽ j ⩽ m) t_{n + 1} (x) = ν_{Q} (u_{j}) if x \in A_{j} \end{matrix}$ (see Definition 7.2).

Define $t_{n}^{'}$ by $t_{n}^{'} (x) : = g (n, t_{n + 1} (x))$ . For every x, $\overline{d} (t_{n + 1} (x), f (x)) < 2^{- n - 1}$ , therefore by (44), $t_{n}^{'} (x) ⩽ f (x)$ and $\overline{d} (t_{n}^{'} (x), f (x)) < 2^{- n}$ . There is a computable function $h : N \times Σ^{*} \to Σ^{*}$ such that $g (n, ν_{Q} (u)) = ν_{Q} \circ h (n, u)$ . Then $q^{'} : = ⟨ 0^{m}, ⟨ h (n, u_{1}), p_{1} ⟩, \dots, ⟨ h (n, u_{m}), p_{m} ⟩ ⟩$ is a $δ_{SF}$ -name of $t_{n}^{'}$ .

Therefore, from the sequence $(t_{0}, t_{1}, \dots)$ we can compute a sequence $(t_{0}^{'}, t_{1}^{'}, \dots)$ such that $t_{n}^{'} ⩽ t$ and $(\forall x \in Ω) \overline{d} (f (x), t_{n} (x)) < 2^{- n}$ for all n. Notice that $t_{n}^{'} (x) ⩾ 0$ for all n, x since $g (n, a) ⩾ 0$ for all n and $a \in Q$ .

Let $s_{0} : = t_{0}$ and $s_{n} : = max (s_{n - 1}, t_{n})$ for $n > 0$ . Then $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots$ , $f = {sup}_{n} s_{n}$ and $(\forall x \in Ω) \overline{d} (s_{n} (x), f (x)) < 2^{- n}$ . By Lemma 7.4, $(s_{1}, s_{2}) \mapsto max (s_{1}, s_{2})$ is computable for $δ_{SF}$ . Therefore, the $s_{n}$ can be computed from the $t_{n}^{'}$ . Therefore, the operator T is $(δ_{mf}, δ_{SF}^{ω})$ -computable.

2. This follows immediately from Theorem 7.1 and Lemma 7.3. □

9. Integration

Commonly, integration in measure theory is introduced via simple functions, where $s : Ω \to R$ is called simple if it is measurable and has finite range. For every simple function there are real numbers $a_{1}, \dots, a_{n}$ and measurable sets $A_{1}, \dots, A_{n}$ such that $s = \sum_{i = 1}^{n} a_{i} \cdot 1_{A_{i}}$ where $1_{A}$ denotes the characteristic function of A. The integral of the simple function s is defined by $\begin{array}{rcl} (45) & \int (\sum_{i = 1}^{n} a_{i} \cdot 1_{A_{i}}) d μ & : = & \sum_{i = 1}^{n} a_{i} \cdot μ (A_{i}), \end{array}$ where $0 \cdot μ (A_{i}) : = 0$ also for $μ (A_{i}) = \infty$ . The integral $\int s d μ$ is well-defined since it can be shown that $\sum_{i = 1}^{n} a_{i} \cdot μ (A_{i}) = \sum_{i = 1}^{m} b_{i} \cdot μ (B_{i})$ if $\sum_{i = 1}^{n} a_{i} \cdot 1_{A_{i}} = \sum_{i = 1}^{m} b_{i} \cdot 1_{B_{i}}$ .

For every non-negative measurable function $f : Ω \to \overline{R}$ there is a sequence $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots$ of simple functions such that $f (x) = {sup}_{k} s_{k} (x)$ for all $x \in Ω$ . Then the Lebesgue integral of f is defined by $\begin{array}{rcl} (46) & \int f d μ : = sup_{k} \int s_{k} d μ . \end{array}$ This integral is well-defined since ${sup}_{k} \int s_{k} d μ = {sup}_{k} \int t_{k} d μ$ if ${sup}_{k} s_{k} = {sup}_{k} t_{k}$ for non-decreasing sequences of non-negative simple functions ${(s_{k})}_{k}$ and ${(t_{k})}_{k}$ .

Every measurable function $f : Ω \to \overline{R}$ can be written as $f = f^{+} - f^{-}$ where $f^{+} (x) : = max (f (x), 0)$ and $f^{-} (x) : = max (- f (x), 0)$ are non-negative measurable functions. By definition, $\begin{array}{rcl} (47) & \int f d μ : = \int f^{+} d μ - \int f^{-} d μ . \end{array}$ This integral exists iff the difference on $\overline{R}$ exists, that is, iff $\int f^{+} d μ < \infty$ or $\int f^{-} d μ < \infty$ (see Lemma 8.1).

In (46) it suffices to consider simple functions s with $range (s) \subseteq Q$ . For such a function there are rational numbers $a_{1}, \dots, a_{m}$ and measurable sets $B_{1}, \dots, B_{m}$ such that $Ω = B_{1} \cup \dots \cup B_{m}$ and $B_{i} \cap B_{j} = \emptyset$ for $i \neq j$ and $s = \sum_{i = 1}^{m} a_{i} \cdot 1_{A_{i}}$ . Therefore, it suffices to use only functions $s \in SF$ for which we have introduced the multi-representation $δ_{SF}$ in Definition 7.2.

We summarize some simple observations about integration of non-negative functions $s \in SF$ , $s : Ω \to R$ , and non-negative measurable functions $f \in F$ , $f : Ω \to \overline{R}$ .

Theorem 9.1.

Integration $s \mapsto \int s d μ$ for non-negative $s \in SF$ is $(δ_{SF}, {\overline{ρ}}_{<})$ -computable. The restriction to functions with finite integral is not $(δ_{SF}, ρ)$ -computable in general.

For non-negative measurable functions $f : Ω \to \overline{R}$ integration $f \mapsto \int f d μ$ is $(δ_{mf}, {\overline{ρ}}_{<})$ -computable but not $(δ_{mf}, \overline{ρ})$ -computable in general.

There are a computable measure with $μ (Ω) = 2$ and a $δ_{mf}$ -computable non-negative function $f : Ω \to R$ with non-computable finite integral.

Proof.
1. Let $s \in δ_{SF} (p)$ as in Definition 7.2. Then $\int f d μ = \sum ν_{Q} (u_{i}) \cdot μ (A_{i})$ . By [20, Lemma 4.10] from the $ζ_{+}$ -names of the $A_{i}$ we can compute ${\overline{ρ}}_{<}$ -names of the $μ (A_{i})$ and hence an ${\overline{ρ}}_{<}$ -name of $\int f d μ$ . There is a computable measure space with computable measure such that $μ (Ω) < \infty$ is not computable. Then the $δ_{SF}$ -computable function $s = 1 \cdot 1_{Ω}$ has no computable integral, hence the integral operator is not $(δ_{SF}, \overline{ρ})$ -computable.

2. By Theorem 8.6 from a $δ_{mf}$ -name of f we can compute ( $δ_{SF}$ -names of) functions $0 ⩽ s_{0} ⩽ s_{1}, \dots$ such that $f = {sup}_{i} s_{i}$ . By 1. we can compute ${\overline{ρ}}_{<}$ -names of the $\int s_{i} d μ$ , hence a ${\overline{ρ}}_{<}$ -name of $\int f d μ$ by (46).

A counterexample follows from (3) of this theorem.

3. See Example 9.1. □
Example 9.1 (Non-computable integral).

For a computable measure with $μ (Ω) = 2$ we construct a $δ_{mf}$ -computable function with non-computable integral.

Let $Ω : = N$ , let $R$ be the ring of finite subsets of $N$ with canonical notation α. Then $(N, 2^{N}, R, α)$ is a computable σ-algebra. Let $μ ({n}) : = 2^{- n}$ . Then μ is a computable measure such that $μ (Ω) = 2$ . Let $B \subseteq N$ be a r.e. set which is not recursive. Then B is the range of an injective computable function $d : N \to N$ . The real number $c : = \sum_{i} 2^{- d (i)}$ is $ρ_{<}$ -computable but not ρ-computable [17].

Define $f : Ω \to R$ by $f (n) : = 2^{n - d (n)}$ . Then $f : N \to Q$ is $({id}_{N}, ν_{Q})$ -computable. We show that f is $δ_{mf}$ -computable. By Definition 5.2 we must compute a list of all $(v, w, u)$ such that $ν_{Q} (v) < μ (α (w) \cap f^{- 1} (\overline{ν} (u)))$ . For a ring element $α (w) \in R$ (which is a finite subset of $Ω = N$ ) and an interval $\overline{ν} (u) \in \overline{β}$ , $\begin{matrix} α (w) \cap f^{- 1} (\overline{ν} (u)) = {n \in α (w) ∣ f (n) \in \overline{ν} (u)} . \end{matrix}$ Since f is $({id}_{N}, ν_{Q})$ -computable from $(w, u)$ we can compute (an α-name of) the finite set $α (w) \cap f^{- 1} (\overline{ν} (u))$ . Since μ is $(α, ν_{Q})$ -computable we can compute a list of all $(v, w, u)$ such that $ν_{Q} (v) < μ (α (w) \cap f^{- 1} (\overline{ν} (u)))$ . Therefore, f is a $δ_{mf}$ -computable measurable function.

Define functions $s_{i} : N \to \overline{R}$ by $s_{i} (n) : = f (n)$ for $n ⩽ i$ and $s_{i} (n) = 0$ otherwise. Then ${(s_{i})}_{i}$ is a sequence of simple functions such that $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots$ and ${sup}_{i} s_{i} = f$ . Since $\int s_{i} d μ = \sum_{n = 0}^{i} 2^{n - d (n)} \cdot 2^{- n} = \sum_{n = 0}^{i} 2^{- d (n)}$ , $\int f d μ = {sup}_{i} \int s_{i} d μ = c$ which is not ρ-computable. Notice that the function f is unbounded, see Theorem 9.2 below.

By Theorem 9.1, in general integration is not $(δ_{mf}, ρ)$ -computable not even on the non-negative integrable functions. Roughly speaking, $δ_{mf}$ -names of integrable functions do not provide enough finitely accessible information for computing (the ρ-name) of the integral. We obtain a positive result for bounded functions.

Theorem 9.2.

The function $(A, a, s) \mapsto \int_{A} s d μ$ for $μ (A) = a \in R$ is $(ζ_{+}, ρ_{>}, δ_{SF}, ρ)$ -computable.

The function $(A, a, f, k) \mapsto \int_{A} d μ$ for $μ (A) = a$ and $f (A) \subseteq (- k; k)$ is $(ζ_{+}, ρ_{>}, δ_{mf}, ν_{N}, ρ)$ -computable.

If $μ (Ω)$ is a computable real number, then $s \mapsto \int s d μ$ is $(δ_{SF}, ρ)$ -computable.

If $μ (Ω)$ is a computable real number, then the function $(f, k) \mapsto \int f d μ$ for $f (Ω) \subseteq (- k; k)$ is $(δ_{mf}, ν_{N}, ρ)$ -computable.

Proof.

1. From a $δ_{SF}$ -name of s we can compute $ζ_{+}$ -names of sets $A_{1}, \dots, A_{k}$ and $ν_{Q}$ -names of rational numbers $c_{1}, \dots, c_{k}$ such that $A_{1} \cup \dots \cup A_{k} = Ω$ , $A_{i} \cap A_{j} = \emptyset$ and $s (x) = c_{i}$ for $x \in A_{i}$ . Then $μ (A \cap A_{1}) + \dots + μ (A \cap A_{k}) = μ (A)$ . By Theorem 4.1 we can compute $ζ_{+}$ -names of the sets $A \cap A_{i}$ , hence $ρ_{<}$ -names of the real numbers $μ (A \cap A_{i})$ . Since $μ (A \cap A_{1}) = μ (A) - μ (A \cap A_{2}) - \dots - μ (A \cap A_{k})$ , we can compute a $ρ_{>}$ -name of $μ (A \cap A_{1})$ , hence a ρ-name of $μ (A \cap A_{1})$ . Correspondingly, we can compute ρ-names of the other $μ (A \cap A_{i})$ . Since $\int_{A} s d μ = c_{1} \cdot μ (A \cap A_{1}) + \dots + c_{k} \cdot μ (A \cap A_{k})$ we can compute a ρ-name of this integral.

2. First we prove the statement for non-negative f.

The function $A \mapsto 1_{A}$ is $(ζ_{+}, δ_{mf})$ -computable by Lemma 8.3 and the function $(g, f) \mapsto g \cdot f$ is $(δ_{mf}, δ_{mf}, δ_{mf})$ -computable by Lemma 8.2. Therefore, $g : = 1_{A} \cdot f$ can be computed from A and f.

By Theorem 8.6 from g we can compute ( $δ_{SF}$ -names of) functions $s_{i} \in SF$ such that $0 ⩽ s_{0} ⩽ s_{1} ⩽ \dots ⩽ g = {sup}_{i} s_{i}$ and for all i and all x, $\overline{d} (s_{i} (x), g (x)) < 2^{- i}$ (where $\overline{d} (y, z) = | y / (1 + | y |) - z / (1 + | z |) |$ ). For $n \in N$ choose $i \in N$ such that $2^{- i} < {(1 + k)}^{- 2} \cdot a^{- 1} \cdot 2^{- n - 1}$ . Then for all $x \in Ω$ (by $0 ⩽ s_{i} (x) ⩽ g (x) ⩽ k$ ), $g (x) / (1 + g (x)) - s_{i} (x) / (1 + s_{i} (x)) = \overline{d} (g (x), s_{i} (x)) ⩽ 2^{- i}$ hence $g (x) - s_{i} (x) ⩽ 2^{- i} \cdot (1 + g (x)) \cdot (1 + s_{i} (x)) ⩽ 2^{- i} \cdot {(1 + k)}^{2} < a^{- 1} \cdot 2^{- n - 1}$ . Since $\int s_{i} d μ$ can be computed, we can find some $a_{n} \in Q$ such that $| \int s_{i} d μ - a_{n} | < 2^{- n - 1}$ . Then $| \int g d μ - a_{n} | ⩽ | \int g d μ - \int s_{i} d μ | + | \int s_{i} d μ - a_{n} | ⩽ | \int (g - s_{i}) d μ | + 2^{- n - 1} ⩽ μ (A) \cdot a^{- 1} \cdot 2^{- n - 1} + 2^{- n - 1} = 2^{- n}$ . Since for every measurable set A, every non-negative measurable function f and every n we can find some rational number $a_{n}$ such that $| \int_{A} f d μ - a_{n} | < 2^{- n}$ , the function $(A, a, f, k) \mapsto \int_{A} f d μ$ such that $μ (A) = a$ and $(\forall x) 0 ⩽ f (x) ⩽ k$ is $(ζ_{+}, ρ, δ_{mf}, ν_{N})$ -computable.

Since $\int_{A} f d μ = \int 1_{A} \cdot f^{+} d μ - \int 1_{A} \cdot f^{-} d μ$ , and since $f^{+}$ and $f^{-}$ can be computed from f (Corollary 8.2), $\int_{A} f d μ$ can be computed also for measurable functions with possibly negative values.

3., 4. This follows from (1,2) for $A : = Ω$ . □

References

Brattka ,

Hertling and

Weihrauch , A tutorial on computable analysis, in: New Computational Paradigms: Changing Conceptions of What Is Computable,

S.B.

Cooper ,

Löwe and

Sorbi , eds, Springer, New York, 2008, pp. 425–491.

C.J.

Conidis , Effectively approximating measurable sets by open sets, Theoretical Computer Science 428 (2012), 36–46.

Gács ,

Hoyrup and

Rojas , Randomness on computable probability spaces – A dynamical point of view, in: STACS 2009: 26th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Vol. 3, Schloss Dagstuhl. Leibniz-Zent. Inform, Wadern, 2009, pp. 469–480.

Gács ,

Hoyrup and

Rojas , Randomness on computable probability spaces – A dynamical point of view, Theory Comput. Syst. 48(3) (2011), 465–485.

Galatolo ,

Hoyrup and

Rojas , Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, Inform. and Comput. 208(1) (2010), 23–41.

Hoyrup and

Rojas , Computability of probability measures and Martin–Löf randomness over metric spaces, Inform. and Comput. 207(7) (2009), 830–847.

Hoyrup ,

Rojas and

Weihrauch , Computability of the Radon–Nikodym derivative, Computability 1(1) (2012), 3–13.

Kawamura and

Cook , Complexity theory for operators in analysis, in: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC ’10, ACM, New York, 2010, pp. 495–502.

Kawamura ,

Ota ,

Rösnick and

Ziegler , Computational complexity of smooth differential equations, Logical Methods in Computer Science 10(1) (2014), 6.

10.

Kenshi ,

L^{1}

-computability, layerwise computability and Solovay reducibility, Computability 2(1) (2013), 15–29.

11.

K.-I.

Ko , Complexity Theory of Real Functions, Progress in Theoretical Computer Science, Birkhäuser, Boston, 1991.

12.

N.T.

Müller , Computability on random variables, Theoretical Computer Science 219 (1999), 287–299.

13.

Rettinger and

Weihrauch , Products of effective topological spaces and a uniformly computable Tychonoff theorem, Logical Methods in Computer Science 9(4) (2013), 14.

14.

Volker , Notions of probabilistic computability on represented spaces, Journal of Universal Computer Science 14(6) (2008), 956–995.

15.

Weihrauch , Computability on computable metric spaces, Theoretical Computer Science 113 (1993), 191–210.

16.

Weihrauch , Computability on the probability measures on the Borel sets of the unit interval, Theoretical Computer Science 219 (1999), 421–437.

17.

Weihrauch , Computable Analysis, Springer, Berlin, 2000.

18.

Weihrauch , The computable multi-functions on multi-represented sets are closed under programming, Journal of Universal Computer Science 14(6) (2008), 801–844.

19.

Weihrauch and

Grubba , Elementary computable topology, Journal of Universal Computer Science 15(6) (2009), 1381–1422.

20.

Weihrauch and

Tavana-Roshandel , Representations of measurable sets in computable measure theory, Logical Methods in Computer Science 10(3) (2014), 7.

21.

Wu , Computability on random events and variables in a computable probability space, Theoretical Computer Science 460 (2012), 54–69.

22.

Wu and

Ding , Computability of measurable sets via effective metrics, Mathematical Logic Quarterly 51(6) (2005), 543–559.

23.

Wu and

Ding , Computability of measurable sets via effective topologies, Archive for Mathematical Logic 45(3) (2006), 365–379.

24.

Wu and

Weihrauch , A computable version of the Daniell–Stone theorem on integration and linear functionals, Theoretical Computer Science 359(1–3) (2006), 28–42.

Computability on measurable functions

Abstract

Keywords

1. Introduction

2. Basic TTE, factorization of multi-representations

Definition 3.1 (Computable σ-algebra, computable measure).

Definition 3.2 ([20]).

7 Infinite distances can be avoided by using the metric d ′ ( x , y ) : = d ( x , y ) / ( 1 + d ( x , y ) ) on X.

8 ( 2 − 1 ) · ∞ = 1 · ∞ = ∞ but 2 · ∞ − 1 · ∞ is undefined.

References

⁷
Infinite distances can be avoided by using the metric $d^{'} (x, y) : = d (x, y) / (1 + d (x, y))$ on X.

⁸
$(2 - 1) \cdot \infty = 1 \cdot \infty = \infty$ but $2 \cdot \infty - 1 \cdot \infty$ is undefined.