page 1  (31 pages) 2

Domain Theory and Integration?

<_author_search_(abbas edalat)>Abbas Edalat

Department of Computing
Imperial College of Science, Technology and Medicine
180 Queen's Gate
London SW7 2BZ UK

Abstract
We present a domain-theoretic framework for measure theory and integration of bounded real-valued functions with respect to bounded Borel measures on compact metric spaces. The set of normalised Borel measures of the metric space can be embedded into the maximal elements of the normalised probabilistic power domain of its upper space. Any bounded Borel measure on the compact metric space can then be obtained as the least upper bound of an !-chain of linear combinations of point valuations (simple valuations) on the upper space, thus providing a constructive setup for these measures. We use this setting to define a new notion of integral of a bounded real-valued function with respect to a bounded Borel measure on a compact metric space. By using an !-chain of simple valuations, whose lub is the given Borel measure, we can then obtain increasingly better approximations to the value of the integral, similar to the way the Riemann integral is obtained in calculus by using step functions. We show that all the basic results in the theory of Riemann integration can be extended in this more general setting. Furthermore, with this new notion of integration, the value of the integral, when it exists, coincides with the Lebesgue integral of the function. An immediate area for application is in the theory of iterated function systems with probabilities on compact metric spaces, where we obtain a simple approximating sequence for the integral of a real-valued continuous function with respect to the invariant measure.

1 Introduction

The theory of Riemann integration of real-valued functions was developed by Cauchy, Riemann, Stieltjes, and Darboux, amongst other mathematicians of the 19th century. With its simple, elegant and constructive nature, it soon became, as it is today, a solid basis of calculus; it is now used in all branches of science. The theory, however, has its limitations in the following main areas, listed here not in any particular order of significance: ?To appear in Theoretical Computer Science, 1995.

(i) It only works for integration of functions defined in Rn.

(ii) It can only deal will integration of functions with respect to the Lebesgue measure, i.e. the usual measure, on Rn.

(iii) Unbounded functions have to be treated separately.

(iv) The theory lacks certain convergence properties. For example, the pointwise limit of a uniformly bounded sequence of Riemann integrable functions may fail to be Riemann integrable.

(v) A function with a `large' set of discontinuity, i.e. with non-zero Lebesgue measure, does not have a Riemann integral.

In the early years of this century, Lebesgue and Borel, amongst others, laid the foundation of a new theory of integration. With its further development, the new theory, the so-called Lebesgue integration, has become the basis of measure theory and functional analysis. A special case of the Lebesgue integral, the so-called Lebesgue-Stieltjes integral, has also played a fundamental role in probability theory. The underlying basis of the Lebesgue theory is in sharp contrast to that of the Riemann theory. Whereas, in the theory of Riemann integration, the domain of the function is partitioned and the integral of the function is approximated by the lower and upper Darboux sums induced by the partition, in the theory of Lebesgue integration, the range of the function is partitioned to produce simple functions which approximate the function, and the integral is defined as the limit of the integrals of these simple functions. The latter framework makes it possible to define the integral of measurable functions on abstract measurable spaces, in particular on topological spaces equipped with Borel measures. Lebesgue integration also enjoys very general convergence properties, giving rise to the complete Lp-spaces. Moreover, when the Riemann integral of a function exists, so does its Lebesgue integral and the two values coincide, i.e. Lebesgue integration includes Riemann integration. Nevertheless, despite these desired features, Lebesgue integration is quite involved and much less constructive than Riemann integration. Consequently, Riemann integration remains the preferred theory wherever it is adequate in practice, in particular in advanced calculus and in the theory of differential equations.

A number of theories have been developed to generalise the Riemann integral while trying to retain its constructive quality. The most well-known and successful is of course the Riemann-Stieltjes integral. In more recent times, E. J. McShane [22] has developed a Riemann-type integral, which includes for example the Lebesgue-Stieltjes integral, but it unfortunately falls short of the constructive features of the Riemann integral.

A new idea in measure theory on second countable locally compact Hausdorff spaces was presented in [9]. It was shown that the set of normalised Borel measures on such a space can be embedded into the maximal elements of the probabilistic power domain of its upper space. The image of the embedding consists of all normalised valuations on the

upper space which are supported in the set of maximal elements of the upper space, i.e. the singletons of the space. This upper space is an !-continuous dcpo (directed complete partial order), and it follows that its probabilistic power domain is also an !-continuous dcpo with a basis consisting of linear combinations of point valuations (simple valuations) on the upper space. The important consequence is that any bounded Borel measure on the space can be approximated by simple valuations on the upper space, and we have a constructive framework for measure theory on locally compact second countable Hausdorff spaces.

In this paper, we use the above domain-theoretic framework to present a novel approach in the theory of integration of bounded functions with respect to a bounded Borel measure on a compact metric space. Instead of approximating the function with simple functions as it is done in the Lebesgue theory, we approximate the normalised measure with normalised simple valuations on the upper space; this provides us with generalised lower and upper Darboux sums, which we use to define the integral. The ordinary theory of Riemann integration, as well as the Riemann-Stieltjes integration, is precisely a particular case of this approach, since any partition of, say, the closed unit interval in fact provides a simple normalised valuation on the upper space of the interval which gives an approximation to the Lebesgue measure.

We therefore work in the normalised probabilistic power domain of the upper space and develop a new theory of integration, called R-integration, with the following results.

ffl R-integration satisfies all the elementary properties required for a theory of integration.

ffl For integration with respect to the Lebesgue measure on compact real intervals, R-integration and Riemann integration are equivalent.

ffl All the basic results in the theory of ordinary Riemann integration can be generalised to R-integration. In particular, a function is R-integrable with respect to a bounded Borel measure on a compact metric space iff it is continuous almost everywhere.

ffl When the R-integral of a function (with respect to a bounded Borel measure on a compact metric space) exists so does its Lebesgue integral and the two integrals are equal.

Therefore, our theory, which includes the Lebesgue-Stieltjes integral, is a faithful and sound generalisation of Riemann integration; it overcomes the limitations (i) and (ii) mentioned above, while retaining the constructive nature of Riemann integration. In practice, we are often only interested in the integral of functions which are not too discontinuous, i.e. R-integration is sufficient at least for bounded functions.

We apply the new theory to obtain a simple approximating sequence for the integral of a real-valued almost everywhere continuous function with

respect to the unique invariant measure of an iterated function system with probabilities on any compact metric space.

2 A Constructive Framework for Measure Theory

In this section, we first review the domain-theoretic framework for measure theory on locally compact second countable spaces which was established in [9]. We will also present some of the background results, in particular from [17], that we need here.

We will use the standard terminology and notations of domain theory, as for example in [18]. Given a dcpo (D; v) and a subset A ? D, we let

"A = fd 2 D j 9a 2 A: a v dg and ""A = fd 2 D j 9a 2 A: a o dg

where o is the way-below relation in D. We denote the lattice of open sets of a topological space X by ?X . Given a mapping f : X ! Y of topological spaces and a subset a ? X , we denote the forward image of a by f [a], i.e. f [a] = ff(x) j x 2 ag. Finally, for a subset a ? X of a compact metric space X , the diameter of a is denoted by jaj.

2.1 The Upper Space

Recall [25] that given any Hausdorff topological space X , its upper space UX is the set of all non-empty compact subsets of X with the upper topology which has basic open sets ?a = fC 2 UX j C ? ag for any open set a 2 ?X . The following properties are easy consequences of this definition. (See [9].) The specialisation ordering vu of UX is reverse inclusion, i.e.

A vu B def
() 8a 2 ?X [A ? a ) B ? a] () A ? B:

Furthermore (UX; ?) is a bounded complete dcpo, in which the least upper bound of a directed set of elements is the intersection of these elements and the Scott topology refines the upper topology. The singleton map

s : X ! UX
x 7! fxg

embeds X onto the set of maximal elements of UX .

Proposition 2.1 [9] Let X be a second countable locally compact Hausdorff space.

(i) The dcpo (UX; ?) is !-continuous.

(ii) The Scott topology on (UX; ?) coincides with the upper topology.

(iii) The way below relation B o C holds in (UX; ?) iff C is contained in the interior of B as subsets of X.

(iv) (UX; ?) can be given an effective structure. From any countable basis B of X consisting of relatively compact neighbourhoods1, we can get an order basis of UX consisting of the finite unions of elements of B. ?

Therefore, any second countable locally compact Hausdorff space X , can be embedded into its upper space UX which can be given an effective structure. We would like to have a similar embedding for the set of bounded Borel measures on X . For this, we use the probabilistic power domain of UX .

2.2 The Probabilistic Power Domain

Recall from [7, 24, 21, 16] that a valuation on a topological space Y is a map ? : ?Y ! [0; 1) which satisfies:

(i) ?(a) + ?(b) = ?(a [ b) + ?(a b)

(ii) ?(;) = (iii) a ? b ) ?(a) <= ?(b)

A continuous valuation [21, 17, 16] is a valuation such that whenever A ? ?(Y ) is a directed set (wrt ?) of open sets of Y , then

?( [

O2A
O) = sup O2A?(O):

For any b 2 Y , the point valuation based at b is the valuation ?b : ?(Y ) ! [0; 1) defined by

?b(O) =

(
1 if b 2 O
otherwise:

Any finite linear combination nX

i=1
ri?bi

of point valuations ?bi with constant coefficients ri 2 [0; 1), (1 <= i <= n) is a continuous valuation on Y , which we call a simple valuation.

The probabilistic power domain, PY , of a topological space Y consists of the set of continuous valuations ? on Y with ?(Y ) <= 1 and is ordered as follows:

? v ? iff for all open sets O of Y , ?(O) <= ?(O):

The partial order (PY; v) is a dcpo with bottom in which the lub of a directed set h?iii2I is given by F
i ?i = ?, where for O 2 ?(Y ) we have

?(O) = sup i2I?i(O):

The probabilistic power domain gives rise to a functor P : DCPO ! DCPO on the category of dcpo's and continuous 1A relatively compact subset of a topological space is one whose closure is compact

functions [16]. Given a continuous function f : Y ! Z between dcpo's Y and Z, the continuous function Pf : PY ! PZ is defined by Pf(?)(O) = ?(f?1(O)). For convenience, we therefore write Pf(?) = ? ffi f?1. For later use we need the following property of this functor.

Proposition 2.2 The functor P : DCPO ! DCPO is locally continuous, i.e. it is Scott continuous on homsets.

Proof Let hfiii2I be a directed family of maps fi : Y ! Z in the function space Y ! Z. Let f = F
i2I fi. It is easy to see that for any open set
O ? Z, we have f?1(O) = S
i f?1
i (O). Now let ? 2 PY . Then, we get:

(P F
i fi)(?)(O) = (Pf)(?)(O) = ?(f?1(O)) = ?(S
i f?1
i (O))

= sup i?(f?1
i (O)) = F
i(? ffi f?1
i )(O) = (F
i Pfi)(?)(O): ?

It is easy to see that, if Y is a dcpo, the map

? : Y ! PY
b 7! ?b

is continuous. Furthermore, there is a nice characterisation of the partial order on simple valuations on a dcpo, aptly called the splitting lemma by Jones.

Proposition 2.3 [16, page 84] Let Y be a dcpo. For two simple valuations

?1 = X

b2B
rb?b ?2 = X

c2C
sc?c

in PY , we have: ?1 v ?2 iff, for all b 2 B and all c 2 C, there exists a nonnegative number tb;c such that

X

c2C
tb;c = rb
X

b2B
tb;c <= sc

and tb;c <> implies b v c.

Proof The `if ' part is the splitting lemma [16, page 84]. For the `only if ' part, assume the condition above holds and let O 2 ?Y . Put A = O B. Then, we have:

?1(O) = P
b2A rb = P
b2A
P
bvc tb;c

<= P
c2C"A
P
bvc tb;c <= P
c2C"A sc = ?2(O):

Therefore ?1 v ?2. ?

If Y is a continuous dcpo, then there is an analogue of the splitting lemma for the way-below relation. First we need the following characterisation of the way-below relation.

Proposition 2.4 [19, page 46] Let ? = P
b2B rb?b be a simple valuation
and ? a continuous valuation on a continuous dcpo. Then ? o ? iff for all A ? B we have X

b2A
rb < ?(""A): ?

Proposition 2.5 Let Y be a continuous dcpo. For two simple valuations

?1 = X

b2B
rb?b ?2 = X

c2C
sc?c

in PY , we have ?1 o ?2 iff, for all b 2 B and all c 2 C, there exists a nonnegative number tb;c such that

X

c2C
tb;c = rb
X

b2B
tb;c < sc

and tb;c <> implies b o c.

Proof The `only if ' part is shown in [16, page 87]. For the `if ' part, assume the above condition holds for ?1 and ?2. Let A ? B, then

P
b2A rb = P
b2A
P
boc tb;c

<= P
c2C""A
P
boc tb;c

< P
c2C""A sc

= ?2(""A):

It follows, by Proposition 2.4, that ?1 o ?2. ?

The following important result was established in [16, pages 94-98] and appears in [17].

Theorem 2.6 If Y is an (!)-continuous dcpo then PY is also (!)-continuous and has a basis consisting of simple valuations. ?

2.3 Extending Valuations to Measures

We also need some results about the extensions of continuous valuations to Borel measures. Recall that a Borel measure ? on a locally compact Hausdorff space is regular if for all Borel subsets B of X , we have:

?(B) = inf f?(O) j B ? O; O openg = sup f?(K) j B ? K; K compactg:

Any bounded measure on a oe-compact and locally compact Hausdorff space is regular [23, page 50]. In particular any bounded Borel measure on a second countable locally compact Hausdorff space is regular [20, page 344]. Furthermore, we have:

Proposition 2.7 [9] On a locally compact second countable Hausdorff space, bounded Borel measures and continuous valuations coincide. ?

We also recall the following result of J. Lawson. First, recall that the lattice ?Y of open sets of a locally quasi-compact sober space Y is a continuous distributive lattice and Y is in fact isomorphic with the spectrum Spec(?Y ), consisting of non-unit prime elements of ?Y with the hull-kernel topology. The Lawson topology on ?Y induces a topology on Spec(?Y ) and hence on Y which is finer than the original topology of Y . (See [13, page 252].)

Proposition 2.8 [21, page 221] Any continuous valuation on a second countable locally quasi-compact sober space Y extends uniquely to a regular Borel measure on Y equipped with the relative Lawson topology induced from ?Y . ?

For an !-continuous bounded complete dcpo Y , the relative Lawson topology induced from ?Y coincides with the Lawson topology on Y which is compact and Hausdorff [1, Exercise 7.3.19.8]. We then obtain the following.

Corollary 2.9 Any continuous valuation on an !-continuous bounded complete dcpo Y extends uniquely to a regular measure on Y equipped with its compact Lawson topology. ?

For !-continuous dcpo's with bottom, which we will only be concerned with in the next sections, we can give a more direct extension result using a lemma by Saheb-Djahromi as follows.

Lemma 2.10 [24, page24] The lub of any !-chain h?iii>=0 of simple valuations ?i on a dcpo Y with ?i(Y ) = 1 extends uniquely to a Borel measure on Y . ?

Proposition 2.11 Any continuous valuation ? on an !-continuous dcpo Y with bottom extends uniquely to a Borel measure on Y .

Proof If ?(Y ) = 0, then the result is trivial. Otherwise, we can assume without loss of generality, i.e. by a rescaling, that ?(Y ) = 1. By Theorem 2.6, there exists an !-chain h?iii>=0 of simple valuations with F
i ?i = ?. For each i >= 0, let ?+i = ? + (1 ? ?(Y ))??. Then, it is easy to check that h?+i ii>=0 is an !-chain of simple valuations with ?i(Y ) = 1 and with lub ?. It follows by Lemma 2.10 that ? extends uniquely to a Borel measure on Y . ?

2.4 Measure Theory via Domain Theory

In [9], a suitable computational framework for measure theory on a locally compact Hausdorff space X has been established using the probabilistic power domain of the upper space of X . We recall the main results here. Since UX is !-continuous so is therefore PUX .

Proposition 2.12 [9, Proposition 5.8] For any open set a 2 ?X, the singleton map s : X ! UX induces a Gffi subset s[a] ? UX. ?

Corollary 2.13 Any Borel subset B ? X induces a Borel subset s[B] ? UX. ?

For ? 2 PUX , let ?? be its unique extension to a Borel measure on UX given by Proposition 2.11 above. Let S(X) ? PUX denote the set of valuations which are supported on the Borel set s[X ] of maximal elements of UX , i.e. S(X) = f? 2 PUX j ??(UX ? s[X]) = g. We have ? 2 S(X)
iff ?(?a) = ??(s[a]) for all a 2 ?X . Furthermore, S(X) will be a subdcpo of PUX . Let M(X) be the set of Borel measures ? on X which are bounded by one (?(X) <= 1). Define a partial order on M(X) by ? v ? iff ?(O) <= ?(O) for all open sets O 2 ?X . Then M(X) will also be a dcpo. Let M1(X) ? M(X) be the subset of normalised measures (?(X) = 1). Similarly, define P 1UX ? PUX and S1(X) ? S(X).

Proposition 2.14 [9, Proposition 5.17] If ? 2 S1(X) then ? is a maximal element of PUX. ?

The main result is the following.

Theorem 2.15 [9, Theorem 5.20] The dcpo's M(X) and S(X) are isomorphic via the maps e : M(X) ! S(X) with e(?) = ? ffi s?1 and j : S(X) !M(X) with j(?) = ?? ffi s. Moreover, these maps restrict to give an isomorphism between M1(X) and S1(X). ?

We can therefore identify M(X) with S(X) ? PUX . But PUX has a basis consisting of simple valuations which can be used to provide it with an effective structure. This therefore gives us a constructive framework for bounded Borel measures on X .

Important Note: For convenience, we often identify ? with e(?) and write ? instead of e(?). Therefore, depending on the context, ? can either be a Borel measure on X or a valuation on UX which is supported on s[X ]. We will also write the unique extension ?? simply as ?.

Example 2.16 Let X = [0; 1] be the unit interval with the Lebesgue measure >=. Each partition

q : = x0 < x1 < ? ? ? < xj?1 < xj < xj+1 < ? ? ? < xN?1 < xN = 1

of [0; 1] gives rise to a simple valuation

?q =
N
X

j=1
rj?bj

where bj = [xj?1; xj ] and rj = xj ? xj?1.

Now consider the !-chain h?qiii>=0 of simple valuations which are obtained by the sequence of partitions hqiii>=0, where qi consists of dyadic numbers xij = j=2i for j = ; 1; 2; 3; ? ? ? ; 2i. In more detail,

?qi =
2i
X

j=1

1

2i ?bj with bj = [ j ? 1

2i ; j

2i ]:

For any open interval a ? [0; 1], the number ?qi(?a) is the largest distance between dyadic numbers xij which are contained in a. For an arbitrary open set, the contributions from individual connected components (intervals) add up. It is easy to see that ?qi v >= for all i >= 0. Furthermore, we have:

Proposition 2.17 The valuation ? = F
i>=0 ?qi is supported in s[X ] and
j(?) is the Lebesgue measure >= on [0; 1].

Proof Let hakik2Jn , n >= 1, be the collection of all open balls in [0; 1] with radius at most 1=n, and put

On = [

k2Jn
?ak :

Then, hOnin>=1 is a decreasing sequence of open sets in U[0; 1] and s[[0; 1]] = T
n>=1 On. But for each n >= 1, ?qi(On) = 1 if 1=2i < 1=n, i.e. if i is large enough. Hence, ?(On) = supi ?qi(On) = 1 for all n >= 1. Therefore,

?(s[[0; 1]]) = infn>=1?(On) = 1

showing that ? 2 S1([0; 1]). To show that j(?) is the Lebesgue measure, it is sufficient by Proposition 2.7 to check that they have the same value on open sets. Since any open set in [0; 1] is the countable union of disjoint open (or half-open half-closed at or 1) intervals, it suffices to check this
on such intervals. But since the dyadic numbers are dense in [0; 1], it is easy to see, for example, that

?(?(x; y)) = supi?qi(?(x; y)) = y ? x = >=((x; y)): ?

3 The Normalised Probabilistic Power Domain

In this section, we consider the subset of normalised valuations of the probabilistic power domain and extend and sharpen the results in Subsection 2.2 for this subset.

For any topological space Y , let P 1Y ? PY be the set of continuous valuations ? on Y which are normalised, i.e. ?(Y ) = 1. Note that if Y has bottom ?, then P 1Y has bottom ??. Let DCPO? denote the category of dcpo's with bottom and continuous maps. Define P 1 on morphisms as for P , i.e. for f : Y ! Z, put Pf(?) = ? ffi f?1. Then

P 1 : DCPO? ! DCPO?

is, like P , a locally continuous functor, which we call the normalised probabilistic power domain functor.

We will now extend the results of subsection 2.2 to the normalised power domain. In the rest of this paper, we denote the way-below relations in PY and P 1Y by o and o1 respectively. Let Y be a dcpo with bottom. We get the analogue of Proposition 2.3.

Proposition 3.1 For two simple valuations

?1 = X

b2B
rb?b ?2 = X

c2C
sc?c

in P 1Y , we have: ?1 v ?2 iff, for all b 2 B and all c 2 C, there exists a nonnegative number tb;c such that

X

c2C
tb;c = rb
X

b2B
tb;c = sc

and tb;c <> implies b v c.

Proof The `if ' part follows from Proposition 2.3. For the `only if ' part, we know from the `only if ' part of that proposition that there exist nonnegative numbers tb;c such that

X

c2C
tb;c = rb
X

b2B
tb;c <= sc

and tb;c <> implies b v c. If for any c 2 C, we have P
b tb;c < sc, then we

1 = X

b
rb = X

b

X

c
tb;c = X

c

X

b
tb;c < X

c
sc = 1:

It follows that P
b tb;c = sc for all c 2 C. ?

Define the maps

m+ : PY ! PY m? : PY ! PY

? 7! ?+ ? 7! ??

where

?+(O) =

(
?(O) if O <> Y
1 otherwise

and

??(O) =

(
?(O) if O <> Y
?(Y ? f?g) otherwise.

Note that Y ? f?g is an open set, and hence ?? is well-defined. The map m+ puts the missing mass of ? on the bottom ? of Y to produce a normalised valuation ?+. The map m? removes any mass that may exist on ?. The following properties are easy consequences of the definitions; the proofs are omitted.

Proposition 3.2 (i) The maps m+ and m? are well-defined, continuous and satisfy:

m+ ffi m+ = m+ w 1 m? ffi m? = m? v 1
m? ffi m+ = m? m+ ffi m? = m+

where 1 is the identity map on PY .

(ii) ? o ? & ? 2 P 1Y ) ?+ o1 ?.

(iii) ? o1 ? ) ?? o ?? v ?. ?

Corollary 3.3 If Y is an (!)-continuous dcpo with bottom, then P 1Y is also an (!)-continuous dcpo with a basis of normalised simple valuations.

Proof Note that P 1Y is the image of the continuous idempotent function m+ : PY ! PY . But the image of any continuous idempotent function (i.e. retract) on an (!)-continuous dcpo is another (!)-continuous dcpo [1, Theorem 3.14]. ?

To prove an analogue of Proposition 2.5 for P 1Y , we need a technical lemma. Assume in the rest of this section that Y is a continuous dcpo with bottom.

Lemma 3.4 Suppose ?; ? 2 P 1Y . Then ? o1 ? implies ?(Y ? f?g) < 1.

Proof Assume ? o1 ?. For n >= 1, let ?n = 1n ?? + (1 ? 1n )?. We have ?n(Y ) = 1 and ?n(O) = (1? 1n )?(O) for any n >= 1 and any open set O <> Y . It follows that h?nin>=1 is an increasing chain with lub ?. Therefore, ? v ?n for some n >= 1. We conclude that

?(Y ? f?g) <= ?n(Y ? f?g) = (1 ? 1

n)?(Y ? f?g) <= 1 ? 1

n < 1

as required. ?

Proposition 3.5 For two simple valuations

?1 = X

b2B
rb?b ?2 = X

c2C
sc?c

in P 1Y , we have ?1 o1 ?2 iff ? 2 B with r? <> , and, for all b 2 B and
all c 2 C, there exists a nonnegative number tb;c with t?;c <> such that

X

c2C
tb;c = rb
X

b2B
tb;c = sc

and tb;c <> implies b o c.

Proof For the `if ' part, note that the conditions above imply, by Proposition 2.5, that

??1 = X

b2B?f?g
rb?b o X

c2C
sc?c = ?2:

Now Proposition 3.2(ii) implies ?1 = (??1 )+ o1 ?2. For the `only if ' part, first note that by Lemma 3.4 we must have ? 2 B with r? <> 0. Therefore by Proposition 3.2(iii)

??1 = X

b2B?f?g
rb?b o X

c2C
sc?c = ?2:

Hence, by Proposition 2.5, there exists, for each b 2 B ? f?g and c 2 C, a nonnegative tb;c with

rb = X

c2C
tb;c (b <> ?) sc > X

b6=?
tb;c

such that tb;c <> ) b o c. Put

t?;c = sc ? X

b6=?
tb;c:

Then, it is easy to check that
X

c2C
t?;c = X

c2C
(sc ? X

b6=?
tb;c) = 1 ? X

b6=?;c2C
tb;c = 1 ? X

b6=?
rb = r?:

Furthermore we clearly have
X

b2B
tb;c = t?;c + X

b6=?
tb;c = sc

as required. ?

4 The Generalised Riemann Integral

We will now use the results of the previous sections to define the generalised Riemann integral. In this section and in the rest of the paper, let f : X ! R be a bounded real-valued function on a compact metric space (X; d) and let ? be a bounded Borel measure on X . Let m = inf f [X ] and M = sup f [X ]. Without loss of generality, i.e. by a rescaling, we can assume that ? is normalised. By Theorem 2.15, ? corresponds to a unique valuation e(?) = ? ffi s?1 2 S1(X) ? P 1UX , which is supported in s[X ] and is, by Proposition 2.14, a maximal element of P 1UX . Recall that we write ? instead of e(?).

4.1 The Lower and Upper R-Integrals

We will define the generalised Riemann integral by using generalised Darboux sums as follows.

Definition 4.1 For any simple valuation ? = P
b2B rb?b 2 PUX , the lower
sum of f with respect to ? is

S`X(f; ?) = X

b2B
rbinf f [b]:

Similarly, the upper sum of f with respect to ? is

SuX(f; ?) = X

b2B
rbsup f [b]: ?

Note that, since f is bounded, the lower sum and the upper sum are well-defined real numbers. When it is clear from the context, we drop the subscript X and simply write S`(f; ?) and Su(f; ?). Clearly, we always have S`(f; ?) <= Su(f; ?).

Proposition 4.2 Let ?1; ?2 2 P 1UX be simple valuations with ?1 v ?2, then
S`(f; ?1) v S`(f; ?2) and Su(f; ?2) v Su(f; ?1):

Proof Assume

?1 = X

b2B
rb?b and ?2 = X

c2C
sc?c:

Let tb;c be the nonnegative numbers given by Proposition 3.1. Then,

S`(f; ?1) = P
b rbinf f [b] = P
b
P
c tb;cinf f [b]

<= P
b
P
c tb;cinf f [c] = P
c
P
b tb;cinf f [c] = P
c scinf f [c]

= S`(f; ?2):

Su(f; ?1) = P
b rbsup f [b] = P
b
P
c tb;csup f [b]

>= P
b
P
c tb;csup f [c] = P
c
P
b tb;csup f [c] = P
c scsup f [c]

= Su(f; ?2): ?

Note that, in the above proof, it is essential that the simple valuations are normalised, i.e. that we work in P 1UX , to deduce that the upper sum decreases. The latter would not hold in general for simple valuations in PUX .

Corollary 4.3 If ?1; ?2 2 P 1UX are simple valuations with ?1; ?2 o1 ?, then S`(f; ?1) <= Su(f; ?2).

Proof Since the set of normalised simple valuations way-below ? in P 1UX is directed, there exists a normalised simple valuation ?3 2 P 1UX such that ?1; ?2 v ?3 o1 ?. By Proposition 4.2, we therefore have

S`(f; ?1) <= S`(f; ?3) <= Su(f; ?3) <= Su(f; ?2): ?

Therefore, if we consider the directed set of simple valuations way-below ? in P 1UX , then every lower sum is bounded by every upper sum. This is similar to the situation which arises for Darboux sums in Riemann integration.

Definition 4.4 The lower R-integral of f with respect to ? on X is

R
Z

X
fd? = sup?o1?S`X(f; ?):

Similarly, the upper R-integral of f with respect to ? on X is

R
Z

Xfd? = inf?o1?SuX(f; ?): ?

Clearly, RR
Xfd? <= RR
Xfd?.

Definition 4.5 We say f is R-integrable with respect to ? on X , and write f 2 RX(?) if its lower and upper integrals coincide. If f is R-integrable, then the R-integral of f is defined as

R
Z

X fd? = R
Z

X
fd? = R
Z

Xfd?: ?

When there is no confusion, we simply write R(?) instead of RX(?) and R fd? instead of R R
X fd? (similarly for the lower and upper R-integrals).
The following characterisation of R-integrability, similar to the Lebesgue condition for the ordinary Riemann integral, is an immediate consequence of the definition.

Proposition 4.6 (The R-condition.) We have f 2 R(?) iff for all ffl > there exists a simple valuation ? 2 P 1UX with ? o1 ? such that

Su(f; ?) ? S`(f; ?) < ffl: ?

There is also an equivalent characterisation of the R-integral in terms of generalised Riemann sums with its well-known parallel in ordinary Riemann integration.

Definition 4.7 For a simple valuation ? = P
b2B rb?b 2 PUX and for a
choice of ?b 2 b for each b 2 B, the sum P
b2B rbf(?b) is called a generalised
Riemann sum for f with respect to ? and is denoted by S?(f; ?). ?

Note that we always have

S`(f; ?) <= S?(f; ?) <= Su(f; ?)

for any generalised Riemann sum S?(f; ?). We therefore immediately obtain:

Proposition 4.8 We have f 2 R(?) with R-integral value K iff for all ffl > there exists a simple valuation

? = X

b2B
rb?b 2 P 1UX

with ? o1 ? such that
jK ? S?(f; ?)j < ffl

for all generalised Riemann sums S?(f; ?) of f with respect to ?. ?

Having defined the notion of R-integrability with respect to simple valuations way below ? in P 1UX , we can now deduce the following results.

Proposition 4.9 If f is R-integrable and ? = F
i>=0 ?i, where h?iii>=0 is an
!-chain in PUX, then
Z
fd? = lim
i!1S`(f; ?i) = lim
i!1 Su(f; ?i) = lim
i!1S?i(f; ?i);

where S?i(f; ?i) is any generalised Riemann sum of f with respect ?i.

Proof Let ffl > be given. Let the simple valuation ? 2 P 1UX with
? o1 ? be such that Su(f; ?) ? S`(f; ?) < ffl. Since ? = F
i ?+i , there exists
N >= such that ? v ?+i and ?i(UX) > 1 ? ffl for all i >= N . Therefore, for all i >= N , ?+i = ?i + ri?X with ri = 1 ? ?i(UX) < ffl. For i >= N , we therefore have
S`(f; ?+i ) ? S`(f; ?i) = riinf f [X ] = rim

Su(f; ?+i ) ? Su(f; ?i) = risup f [X ] = riM

and also the inequalities

S`(f; ?) <= S`(f; ?+i ) <= Su(f; ?+i ) <= Su(f; ?)

S`(f; ?) <=
Z
fd? <= Su(f; ?):

It follows that jS`(f; ?+i ) ? R fd?j < ffl and jSu(f; ?+i ) ? R fd?j < ffl for i >= N . We conclude that for i >= N ,

jS`(f; ?i) ?
Z
fd?j < (1 + jmj)ffl

jSu(f; ?i) ?
Z
fd?j < (1 + jM j)ffl;

and the result follows. ?

Corollary 4.10 If f is R-integrable and ? = F
i>=0 ?i, where h?iii>=0 is an
!-chain in P 1UX, then S`(f; ?i) increases to R fd? and Su(f; ?i) decreases to R fd?. ?

4.2 Elementary Properties of the R-Integral

We now show some simple properties of the R-integral.

Proposition 4.11 (i) If f; g 2 R(?) then f + g 2 R(?) and R (f + g) d? = R fd? + R gd?.

(ii) If f 2 R(?) and c 2 R, then cf 2 R(?) and R cf d? = c R fd?.

(iii) More generally, if f; g 2 R(?) so is their product h : X ! R with h(x) = f(x)g(x).

Proof We will only prove (i). For any nonempty compact subset b ? X we have:
sup (f + g)[b] <= sup f [b] + sup g[b]

inf (f + g)[b] >= inf f [b] + inf g[b]:

Hence, for any simple valuation ? o1 ?, we have

Su(f + g; ?) <= Su(f; ?) + Su(g; ?)

S`(f + g; ?) >= S`(f; ?) + S`(g; ?):

Let ffl > be given. There exist simple valuations ?1; ?2 o1 ? with

Su(f; ?1) <
Z
fd? + ffl=2 Su(g; ?2) <
Z
gd? + ffl=2:

Let the simple valuation ? be such that ?1; ?2 v ? o1 ?. Then Su(f; ?) <= Su(f; ?1) and Su(g; ?) <= Su(g; ?2), and we have:

Su(f + g; ?) <= Su(f; ?) + Su(g; ?) <= Su(f; ?1) + Su(g; ?2)
<= R fd? + R gd? + ffl:

Therefore, R (f +g) d? <= R fd?+R gd?. Similarly, R fd?+R gd? <= R (f +g) d?, and the result follows. ?

Given the function f : X ! R as before, define two functions f+; f? : X ! R by

f+(x) =

(

f(x) if f(x) >= otherwise and f?(x) =

(

?f(x) if f(x) <= otherwise.

Proposition 4.12 If f 2 R(?), then f+; f? 2 R(?) and R fd? = R f+d? ? R f?d?.

Proof For any non-empty compact set b ? X , we have

sup f+[b] ? inf f+[b] <= sup f [b] ? inf f [b]

and therefore

Su(f+; ?) ? S`(f+; ?) <= Su(f; ?) ? S`(f; ?):

By the R-condition (Proposition 4.6), f+ 2 R(?). Similarly, f? 2 R(?). Since f = f+ ?f?, by Proposition 4.11, we get R fd? = R f+d??R f?d?. ?

The following properties are easily shown.

Proposition 4.13 (i) If f is nonnegative and f 2 R(?) then R fd? >= .

(ii) f 2 R(?) ) jf j 2 R(?) and

j
Z
fd?j <=
Z
jf jd?: ?

We will make frequent use of the following result in the next sections. As before, let ? be a normalised Borel measure on the compact metric space X .

Proposition 4.14 Let h?iii2I be a directed set of simple valuations

?i = X

b2Bi
ri;b?b

in P 1UX with lub ?. Then for all ffl > and all ffi > , there exists i 2 I
with X

b2Bi;jbj>=ffi
ri;b < ffl

where jbj is the diameter of the compact set b ? X.

Proof Let ffl > and ffi > be given. Let hakik2Jn , n >= 1, be the collection
of all open balls in X with radius at most 1=n, and put

On = [

k2Jn
?ak :

Then, for all n >= 1, we have s[X ] ? s[On] and hence ?(On) = ?(s[X]) = 1, since ? is supported in s[X ]. Now choose n > 2=ffi so that 1=n < ffi =2. Since supi2I?i(On) = ?(On) = 1, there exists i 2 I with ?i(On) > 1 ? ffl. It follows that X

b2Bi;jbj>=ffi
ri;b < ffl

as required. ?

5 R-integration and Riemann integration

In this section, we show that Riemann integration is equivalent to R-integration on compact real intervals with respect to the Lebesgue measure.
Let X = [0; 1] be the unit real interval with the Lebesgue measure >=. Recall from Example 2.16 that any partition

q : = x0 < x1 < ? ? ? < xj?1 < xj < xj+1 < ? ? ? < xN?1 < xN = 1

of [0; 1] gives rise to a simple valuation

?q =
N
X

j=1
rj?bj

where bj = [xj?1; xj] and rj = xj ? xj?1. Given any bounded function f : [0; 1] ! R, the lower and upper Darboux sums of f with respect to

the partition q in the ordinary Riemann integration of f are precisely the lower and upper sums S`(f; >=) and Su(f; >=) of R-integration. We will of course use this fact to show that f is Riemann integrable iff f 2 R(>=), and that when the two integrals exist, then they are equal, i.e.

R
Z

[0;1] fd>= =
Z 1
f(x)dx:

However, it can be easily shown that ?q is not way-below >= if N > 1. In fact, for i >= 1, let ?i = 1i ?[0;1] + (1 ? 1i )?i, where h?iii>=1 is the !-chain given in Proposition 2.17. Then, we have F
i>=1 ?i = >=, but there is no
i >= 1 with ?q v ?i, showing that ?q is not way-below >=. But, the following lemma shows that it is possible to obtain a valuation close to ?q which is way-below >=.

Lemma 5.1 Let q be any partition of [0; 1] inducing the simple valuation ?q as above, and let < ffl < 1. Then, ? = ffl?[0;1] + (1 ? ffl)?q o1 >=.

Proof By Proposition 3.2(ii), it suffices to prove that (1 ? ffl)?q o >=. Choose a real number ffi such that ffl > ffi > 0. For each j = 1; : : : ; N , let b0j = [xj?1 + 12 ffi rj; xj ? 12 ffi rj ]. Since b0j ? (xj?1; xj) ? bj , it follows that

bj o b0j holds in UX . Let ?0 = (1 ? ffi ) PNj=1 rj?b0j . By Proposition 2.5, with

tjj = (1 ? ffl)rj and tjj0 = for j <> j0, we have (1 ? ffl)?q o ?0. Since the
length of b0j is (1 ? ffi )rj and the intervals b0j , j = 1; : : : ; N , are disjoint, it easily follows that ?0 v >=. Thus, (1 ? ffl)?q o ?0 v >= as required.?

Theorem 5.2 A bounded real-valued function on a compact real interval is Riemann integrable iff it is R-integrable with respect to the Lebesgue measure. Furthermore, the two integrals are equal when they exist.

Proof Assume without loss of generality that the compact real interval is in fact the unit interval. For the `if ' part, assume f : [0; 1] ! R is R-integrable. Let ffl > be given. By the R-condition, there exists ? o1 >=
with Su(f; ?) ? S`(f; ?) < ffl. Now take, for example, the !-chain h?qiii>=0 of simple valuations of Proposition 2.17 whose lub is >=. Since ?qi 2 P 1U[0; 1] for all i >= 0, there is i >= with ? v ?qi . Hence

Su(f; ?qi) ? S`(f; ?qi) <= Su(f; ?) ? S`(f; ?) < ffl

and therefore the Riemann condition is satisfied and f is Riemann integrable. Since, by Corollary 4.10, the R-integral is the supremum of S`(f; ?qi) and the latter is also the Riemann integral of f , we conclude that the two integrals are equal when they exist. For the `only if ' part, assume f is Riemann integrable and let q : = x0 < x1 < ? ? ? < xN = 1
be a partition of [0; 1] with Su(f; ?q) ? S`(f; ?q) < ffl. By Lemma 5.1, ? = ffl?[0;1] + (1 ? ffl)?q is way-below >=. We also have

Su(f; ?) ? S`(f; ?) <= (M ? m)ffl + (1 ? ffl)ffl

< (M ? m+ 1)ffl:

We conclude that f satisfies the R-condition, and is therefore R-integrable. ?

We conclude that ordinary Riemann integration is a particular instance of R-integration.

6 Further Properties of R-integration

In this section, we will show that all the basic results for ordinary Riemann integration on a compact interval in R can be extended to R-integration. Assume as before that ? is a normalised Borel measure on the compact metric space X . We first show that continuous functions are R-integrable.

Theorem 6.1 Any continuous function f : X ! R is R-integrable with respect to ?.

Proof Let ffl > be given. By the uniform continuity of f on the compact
set X , there exists ffi > such that d(x; y) < ffi implies jf(x) ? f(y)j < ffl2 .
By Proposition 4.14, there exists a simple valuation ? = P b2B rb?b with
? o1 ? such that X

jbj>=ffi
rb <= ffl

2(M ? m+ 1) :

Therefore,

Su(f; ?) ? S`(f; ?) = X

b2B
rb(supf [b] ? inff [b])

= X

b2B;jbj<ffi
rb(supf [b] ? inff [b]) + X

b2B;jbj>=ffi
rb(supf [b] ? inff [b])

< ffl2 + (M?m)ffl
2(M?m+1)

< ffl:

It follows by the R-condition that f 2 R(?). ?

Next we will prove that a bounded function is R-integrable with respect to a Borel measure if and only if its set of discontinuities has measure zero. This will generalise the well-known Lebesgue criterion for ordinary Riemann integration of a bounded function on a compact real interval.

We need some definitions and properties relating to the oscillation of a bounded function f : X ! R which generalise those of a bounded function on a compact real interval as presented, for example, in [2]. For convenience and consistency, we will use the terminology in that work.

Definition 6.2 Let T ? X . The number

?f (T ) = supff(x) ? f(y) j x; y 2 Tg

is called the oscillation of f on T . For x 2 X , the number

!f (x) = lim
h!0+ ?f(B(x; h))

where B(x; h) ? X is the open ball of radius h > at x, is the oscillation
of f at x. For each r > 0, let

Dr = fx 2 X j !f (x) >= 1=rg: ?

The following properties then are straightforward generalisations of those in [2, pages 170-171].

Proposition 6.3 (i) f is continuous at x 2 X iff !f (x) = .

(ii) If !f (x) < ffl for all x 2 X, then there exists ffi > such that for all
compact subsets b ? X with jbj < ffi we have ?f (b) < ffl.

(iii) For any r > the set Dr is closed. ?

If D is the set of discontinuities of f , then using Definition 6.2 and Proposition 6.3(i), we can write D = S
n>=1 Dn where D1 ? D2 ? D3 ? : : :
is an increasing chain of closed sets. Hence, D is an Foe , and therefore a Borel, set. Recall that we assume ? to be a normalised measure on the compact metric space X .

Lemma 6.4 Let d ? X be compact, and let ? = P
b2B rb?b be a simple
valuation in P 1UX.

(i) If ? v ? then X

bd6=;
rb >= ?(d):

(ii) If ? o1 ?, then X

bffid6=;
rb >= ?(d)

where bffi is the interior of b.

Proof (i) We have

P
bd6=; rb = 1 ? P
bd=; rb since ?(UX) = 1

= 1 ? P
b?X?d rb

= 1 ? P
b2?(X?d) rb

= 1 ? ?(?(X ? d))

>= 1 ? ?(?(X ? d)) since ? v ?

= 1 ? (?(s[X]) ? ?(s[d])) since ? is supported in s[X ]

= ?(d)

(ii) By the interpolative property of o1, there exists a normalised simple valuation = P
c2C sc?c such that ? o1 o1 ?. Let tb;c be given as in

Proposition 3.5. Then

?(d) <= P
cd6=; sc by part (i)

= P
cd6=;
P
boc tb;c

<= P
bffid6=;
P
c2C tb;c

= P
bffid6=; rb: ?

Theorem 6.5 A bounded real-valued function on a compact metric space is R-integrable with respect to a bounded Borel measure iff its set of discontinuities has measure zero.

Proof Necessity. Let D be the set of discontinuities of f : X ! R and suppose ?(D) > 0. Since D = S
n>=1 Dn, we must have ?(Dn) > for some
n >= 1. Fix such n and let ? = P
b2B rb?b be any simple valuation with
? o1 ?. Then

Su(f; ?) ? S`(f; ?) = X

b
rb(supf [b] ? inff [b])

>= X

bffiDn <>;
rb(supf [b] ? inff [b])

>= X

bffiDn <>;
rb=n by definition of Dn

>= ?(Dn)=n > : by Lemma 6.4(ii)

Therefore, f does not satisfy the R-condition and is not R-integrable. Sufficiency. Assume ?(D) = 0. It follows that ?(Dn) = for all n >= 1.
Fix n >= 1. Since ? is regular, there exists an open set v 2 ?X with Dn ? v and ?(v) < 1=n. Choose an open set w 2 ?X which contains Dn and whose closure is contained in v. Let ffi1 > be the minimum distance
between X ? v and the closure of w. For x 2 X ?w we have !f (x) < 1=n. Therefore, by Proposition 6.3(ii) applied to X ?w, there exists ffi2 > such
that for any compact subset c ? X ? w with jcj <= ffi2 we have

?f(c) < 1=n: (1)

Let < ffi < min(ffi1; ffi2). By Proposition 4.14, there exists a simple valuation = P
b2B rb?b with o1 ? such that

X

jbj>=ffi
rb < 1=n: (2)

Observe that if jbj < ffi , then b is contained in at least one of the sets v or X ? w. We also have

(?v) <= ?(?v) = ?(v) < 1=n (3)

since ? is supported in s[X ]. Therefore,

Su(f; ) ? S`(f; ) = X

b2B
rb(supf [b] ? inff [b])

<= X

jbj>=ffi
? ? ? + X

jbj<=ffi;b?v
? ? ? + X

jbj<=ffi;b?X?w
? ? ?

<= M ? m

n + M ? m

n + X

jbj<=ffi;b?X?w

rb
n by (2), (3) and (1)

<= 2(M ?m)+ 1

n :

Since n >= 1 is arbitrary, f 2 R(?) by the R-condition. ?

If ? is a bounded Borel measure on X and C ? X is a closed subset, then the restriction ??C is a bounded Borel measure on C. For convenience, we write f 2 RC(?) and R
C fd?, if f is R-integrable on C with respect to this
restriction.

Corollary 6.6 If f 2 RX(?) then f 2 RC(?) for all closed subsets C ? X.

Proposition 6.7 If f 2 RX(?) and C; D ? X are closed subsets with C D = ;, then Z

C[D fd? =
Z

C fd? +
Z

D fd?:

Proof By Corollary 6.6, we know that the three integrals exist. Let h?iii>=0 be an !-chain of simple valuations in PUC with lub ??C . Similarly, let h iii>=0 be an !-chain of simple valuations in PUD with lub ??D. Then, it is straightforward to check that h?i + iii>=0 is an !-chain of simple valuations in PU(C [ D) with lub ??C[D. For each i >= 0, we have

S`C[D(f; ?i + i) = S`C(f; ?i) + S`D(f; i):

Therefore,

R
C[D fd? = limi!1 S`C[D(f; ?i + i)

= limi!1 S`C(f; ?i) + S`D(f; i)

= limi!1 S`C(f; ?i) + limi!1 S`D(f; i)

= R
C fd? + R
D fd?: ?

Next, we consider the R-integrability of the uniform limit of a sequence of R-integrable functions.

Theorem 6.8 If the sequence hfnin>=0 of R-integrable functions fn : X ! R is uniformly convergent to f : X ! R, then f is R-integrable and R fd? = limi!1 R fid?.

Proof Let ffl > be given. We show that f satisfies the R-condition. Let
N >= be such that jfn(x) ? f(x)j < ffl=3 for all n >= N and all x 2 X . Then for all simple valuations ? 2 P 1UX we have jSu(f ? fN ; ?)j < ffl=3 and jS`(f ? fN ; ?)j < ffl=3. Since fN is R-integrable, there exists a simple valuation ? o1 ? with Su(fN ; ?) ? S`(fN ; ?) < ffl=3. Therefore,

Su(f; ?) ? S`(f; ?) <= Su(f ? fN ; ?) + Su(fN ; ?) ? S`(f ? fN ; ?) ? S`(fN ; ?)

<= jSu(f ? fN ; ?)j + jS`(f ? fN ; ?)j + Su(fN ; ?) ? S`(fN ; ?)

< ffl3 + ffl3 + ffl3 = ffl

and, hence, f 2 R(?). Furthermore, for all n >= N , we have

j R fd? ? R fnd?j = j R f ? fnd?j

<= R jf ? fnjd?

<= ffl: ?

In the next section, we will also show the generalisation of Arzel?a's theorem for R-integration.

7 R-Integration and Lebesgue Integration

It is well known that when the ordinary Riemann integral of a bounded function on a compact real interval exists, so does its Lebesgue integral and the two integrals coincide. In this section, we will show that this result extends to R-integration.

In order to show that an R-integrable function is Lebesgue integrable, we construct an increasing sequence of simple measurable functions which tend to our function. We do this by considering the set of deflations on UX .
Recall [18] that a deflation on a dcpo Y is a continuous map

d : Y ! Y

which is below the identity d v 1Y and its image im(d) is finite. If b 2 B = im(d), then D = d?1(b) satisfies the following properties:

(i) x v y v z & x; z 2 D ) y 2 D.

(ii) For any directed set hxiii2I with F
i xi 2 D, we have xi 2 D for some
i 2 I .

(iii) For any directed set hxiii2I with xi 2 D for all i 2 I , we have F
i xi 2 D.

It follows [24] that D is a crescent, i.e. D = v ? w for some open sets v; w 2 ?Y . Now consider the map Pd : PY ! PY , induced by the probabilistic power domain functor P on the deflation d v 1Y . We have Pd(?) = ? ffi d?1 v ?, since d?1(O) ? O for all O 2 ?Y . Consider the unique extension of ? 2 PY to the ring generated by the open sets, i.e. put ?(D) = ?(v) ? ?(v w) for each crescent D = v ? w. Then it is easily seen that
? ffi d?1 = X

b2B
rb?b

with rb = ?(d?1(b)). Hence, for each deflation d and each continuous valuation ? on Y , we obtain a simple valuation ? ffi d?1 below ?. Note that if ? is normalised so is ? ffi d?1. Recall also that if Y is the retract of an SFP domain, then the set of deflations way-below the identity map is directed and has the identity as its lub [18, page 88]. We can now deduce:

Proposition 7.1 Any continuous valuation on a retract of an SFP domain is the lub of an !-chain of simple valuations induced from deflations below the identity map.

Proof Let Y be a retract of an SFP domain and ? be a continuous valuation on Y . By the above remark, there exists an !-chain hdiii>=0 of deflations on Y with 1Y = F
i di. By the local continuity of
P (Proposition 2.2), we have 1PY = F
i Pdi and therefore

? = G

i
Pdi(?) = G

i
? ffi d?1
i

as required. ?

We are now in a position to prove the main result in this section. For clarity we denote the Lebesgue integral of a real-valued function f : X ! R with respect to the Borel measure ? by L R
X fd? and the R-integral by
R R
X fd?. We also drop the subscript X .

Theorem 7.2 If a bounded real-valued function f is R-integrable with respect to a Borel measure ? on a compact metric space X, then it is also Lebesgue integrable and the two integrals coincide.

Proof Since UX is an !-continuous bounded complete dcpo with bottom, there exists by Proposition 7.1 an !-chain hdiii>=0 of deflations di : UX ! UX with F
i ? ffi d?1
i = ? and each i >= induces a simple valuation

?i = ? ffi d?1
i = X

b2Bi
ri;b?b

where Bi = imdi and ri;b = ?(d?1
i (b)). For each i >= 0, define two functions

f?i : X ! R f+i : X ! R

x 7! inff [s?1(d?1
i (di(s(x))))] x 7! supf [s?1(d?1
i (di(s(x))))]

where s : X ! UX is, as before, the singleton map. Since for each i >= and x 2 X , we have d?1
i (di(s(x))) = v ? w for some open sets v; w 2 ?UX ,

it follows easily that s?1(d?1
i (di(s(x)))) = s?1(v) ? s?1(w) is a crescent of
X . Moreover, as the image of di is finite, X is partitioned to a finite number of such crescents. Therefore, f?i and f+i are simple measurable functions. Is is easy to see that for each x 2 X we have:

m <= : : : <= f?i (x) <= f?i+1(x) <= : : : <= f(x) <= : : : <= f+i+1(x) <= f+i (x) <= : : : <= M

where m and M are, as before, the infimum and the supremum of f on X . Let

f? : X ! R f+i : X ! R

x 7! limi!1 f?i (x) x 7! limi!1 f+i (x):

Then f?(x) <= f(x) <= f+(x) for all x 2 X . By the monotone convergence theorem, f? and f? are Lebesgue integrable. We will calculate their Lebesgue integrals.
For each b 2 Bi, let

i;b = supf [s?1(d?1
i (b))] i;b = inff [s?1(d?1
i (b))]:

Since d?1
i (b) ? "b, we have s?1(d?1
i (b)) ? b. Hence, for all i >= and b 2 Bi,

inff [b] <= i;b <= i;b <= supf [b]:

We can now obtain the following estimates for the Lebesgue integrals of f?i and f+i :
L R f+i d? = P
b2Bi ri;b i;b

<= P
b2Bi ri;bsupf [b]

= Su(f; ?i)

and
L R f?i d? = P
b2Bi ri;b i;b

>= P
b2Bi ri;binff [b]

= S`(f; ?i):

Since f?i <= f+i implies L R f?i d? <= L R f+i d?, we obtain:

S`(f; ?i) <= L
Z
f?i d? <= L
Z
f+i d? <= Su(f; ?i):

As f is assumed to be R-integrable, we know by Propositions 4.2 and 4.9 that S`(f; ?i) increases to R R fd? and Su(f; ?i) decreases to R R fd?. Therefore,

L
Z
f?i d? ! R
Z
fd? and L
Z
f+i d? ! R
Z
fd?

as i !1. By the monotone convergence theorem, we have:

L
Z
f?d? = lim
i!1L
Z
f?i d? = R
Z
fd?

L
Z
f+d? = lim
i!1L
Z
f+i d? = R
Z
fd?:

It now follows that L R (f+ ? f?) d? = which implies that f+ = f? almost
everywhere. Therefore f = f? = f+ almost everywhere. We conclude that f is Lebesgue integrable and

L
Z
fd? = L
Z
f?d? = L
Z
f+d? = R
Z
fd?

as required. ?

We can now also obtain the generalisation of Arzel?a's theorem for R-integration.

Corollary 7.3 Suppose the sequence hfnin>=0 of real-valued and uniformly bounded functions on X is pointwise convergent to an R ? integrable function f . Then, we have:

R
Z
fd? = lim
n!1R
Z
fnd?:

Proof This follows immediately by applying Theorem 7.2 and using the Lebesgue dominated convergence theorem. ?

8 Applications to Fractals

An immediate area of application for R-integration is in the theory of iterated function systems (IFS) with probabilities. Recall [15, 3] that an IFS with probabilities, fX ; f1; : : : ; fN ; p1; : : : ; pNg, is given by a finite number of contracting maps fi : X ! X (1 <= i <= N) on a compact metric space X , such that each fi is assigned a probability weight pi with < pi < 1 and

NX

i=1
pi = 1:

An IFS with probabilities gives rise to a unique invariant Borel measure on X . If X ? Rn, then the support of this measure is usually a fractal i.e. it has fine, complicated and non-smooth local structure, some form of self-similarity and, usually, a non-integral Hausdorff dimension. Conversely, given any image regarded as a compact set in the plane, one uses a self-tiling of the image and Barnsley's collage theorem to find an IFS with contracting affine transformations, whose attractor approximates the image. The theory has many applications including in statistical physics [14, 6, 10], neural nets [5, 8] and image compression [3, 4].

It was shown in [9, Theorem 6.2], that the unique invariant measure ? of an IFS with probabilities as above is the fixed point of the map

T : P 1UX ! P 1UX
? 7! T (?)

defined by T (?)(O) = PNi=1 pi?(f?1
i (O)). This fixed point can be written
as F
m>=0 ?m where ?0 = ?X and for m >= 1,

?m = Tm(?X) =
NX

i1;i2;:::;im=1
pi1pi2 : : : pim?fi1fi2 :::fim(X):

Therefore, the unique invariant measure of the IFS with probabilities is the lub of an !-chain of simple valuations in P 1UX . This provides a better algorithm for fractal image decompression using measures [11], compared to the algorithms presented in [4].

Suppose now we have a bounded function f : X ! R whose set of discontinuities has ?-measure zero, then we know that its Lebesgue integral with respect to ? coincides with its R-integral with respect to ?. Fix x 2 X and, for each m >= 1, consider the generalised Riemann sum

Sx(f; ?m) =
NX

i1;i2;:::;im=1
pi1pi2 : : : pimf(fi1fi2 : : : fim(x)):

From Proposition 4.9, we immediately obtain:

Theorem 8.1 For an IFS with probabilities and a bounded real-valued function f which is continuous almost everywhere with respect to the invariant measure ? of the IFS, we have

L
Z
f d? = R
Z
f d? = lim
m!1Sx(f; ?m);

for any x 2 X. ?

If f satisfies a Lipschitz condition, then, for any ffl > 0, we can obtain a finite algorithm to estimate R f d? up to ffl accuracy [11]. The only other method for computing the integral is by Elton's ergodic theorem [12]: The time-average of f with respect to the non-deterministic dynamical system f1; f2; : : : ; fN : X ! X , where at each stage in the orbit of a point the map fi is selected with probability pi, tends, with probability one, to its space-average, i.e. to its integral. However, in this case, the convergence is only with probability one and there is no estimate for the rate of convergence. Therefore, the above theorem provides a better way of computing the integral.

Example 8.2 Finally, we consider a concrete example. Let C = f1; 2; ? ? ? ; Ng! be the Cantor space with the following metric

d(x; y) =
1
X

n=0

ffi (xn; yn)

2n

where the Kronecker delta is given by

ffi (k; l) =

(
if k = l
1 otherwise.

This metric is equivalent to the Cantor (product) topology, and is frequently used in mathematics and theoretical physics. Let fC; f1; : : : ; fN ; p1; : : : ; pNg be an IFS with probabilities on C, with

fk : C ! C
x 7! kx;

where kx is concatenation of k and x. Its unique invariant measure ? is defined on the closed-open subset

[i1i2 ? ? ? im] = fx 2 C j xj = ij ; 1 <= j <= mg

by
?([i1i2 ? ? ? im]) = pi1 pi2 ? ? ? pim :

In fact, we have

?m = Tm(?X) =
N
X

i1;i2;:::;im=1
pi1pi2 : : : pim?[i1i2:::im]:

Let
f : C ! R
x 7! d(x; 1!)

be the function which gives the distance of the point x to the point 1!. This function is continuous and therefore its Lebesgue integral with respect to ? coincides with its R-integral with respect to ?. The integral in fact represents the average distance in C from 1! with respect to the invariant measure. The R-integral is easily obtained using Theorem 8.1 above with x = 1!. In fact a straightforward calculation shows that

S1!(f; ?m) = 2(1 ? 1

2m )(1 ? p1) ! 2(1 ? p1)

as m !1. Therefore, L R fd? = R R fd? = 2(1 ? p1).

Acknowledgements

I would like to thank Achim Jung, Klaus Keimel and Philipp S?underhauf for discussions on continuous domains. I am in particular grateful to Achim Jung who suggested the idea of using deflations leading to Proposition 7.1. Many thanks to Reinhold Heckmann for suggesting shorter proofs for two lemmas. This work has been funded by the SERC Foundational Structures for Computer Science" at Imperial College.

References

[1] S. Abramsky and A. Jung. Domain theory. In S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, volume 3. Clarendon Press, 1994.

[2] T. M. Apostol. Mathematical Analysis. Addison-Wesley, 1974.

[3] M. F. Barnsley. Fractals Everywhere. Academic Press, 1988.

[4] M. F. Barnsley and L. P. Hurd. Fractal Image Compression. AK Peters, Ltd, 1993.

[5] U. Behn, J. L. van Hemmen, A. Lange R. K?uhn, and V. A. Zagrebnov. Multifractality in forgetful memories. Physica D, 68:401{415, 1993.

[6] U. Behn and V. Zagrebnov. One dimensional Markovian-field Ising model: Physical properties and characteristics of the discrete stochastic mapping. J. Phys. A: Math. Gen., 21:2151{2165, 1988.

[7] G. Birkhoff. Lattice Theory. American Mathematical Society, 1967.

[8] P. C. Bressloff and J. Stark. Neural networks, learning automata and iterated function systems. In A. J. Crilly, R. A. Earnshaw, and H. Jones, editors, Fractals and Chaos, pages 145{164. Springer-Verlag, 1991.

[9] A. Edalat. Dynamical systems, measures and fractals via domain theory (Extended abstract). In G. L. Burn, S. J. Gay, and M. D. Ryan, editors, Theory and Formal Methods 1993. Springer-Verlag, 1993. Full paper to appear in Information and Computation.

[10] A. Edalat. Domain of computation of a random field in statistical physics. In Proceedings of the Second Imperial College, Department of Computing, Theory and Formal Methods Workshop. 1994.

[11] A. Edalat. Power domains and iterated function systems. Technical Report Doc 94/13, Department of Computing, Imperial College, 1994. Submitted to Information and Computation.

[12] J. Elton. An ergodic theorem for iterated maps. Journal of Ergodic Theory and Dynamical Systems, 7:481{487, 1987.

[13] G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott. A Compendium of Continuous Lattices. Springer Verlag, Berlin, 1980.

[14] G. Gy?orgyi and P. Ruj?an. Strange attractors in disordered systems. J. Phys. C: Solid State Phys., 17:4207{4212, 1984.

[15] J. E. Hutchinson. Fractals and self-similarity. Indiana University Mathematics Journal, 30:713{747, 1981.

[16] C. Jones. Probabilistic Non-determinism. PhD thesis, University of Edinburgh, 1989.

[17] C. Jones and G. Plotkin. A Probabilistic Powerdomain of Evaluations. In Logic in Computer Science, pages 186{195. IEEE Computer Society Press, 1989.

[18] A. Jung. Cartesian Closed Categories of Domains, volume 66 of CWI Tract. Centrum voor Wiskunde en Informatica, Amsterdam, 1989.

[19] O. Kirch. Bereiche und bewertungen. Master's thesis, Technische Hochschule Darmstadt, 1993.

[20] S. Lang. Real Analysis. Addison-Wesley, 1969.

[21] J. D. Lawson. Valuations on Continuous Lattices. In Rudolf-Eberhard Hoffman, editor, Continuous Lattices and Related Topics, volume 27 of Mathematik Arbeitspapiere. Universit?at Bremen, 1982.

[22] E. J. McShane. A Riemann-type integral that includes LebesgueStieltjes, Bochner and stochastic integrals. American Mathematical Society, Memoir, 88, 1969.

[23] W. Rudin. Real and Complex Analysis. McGraw-Hill, 1966.

[24] N. Saheb-Djahromi. Cpo's of measures for non-determinism. Theoretical Computer Science, 12(1):19{37, 1980.

[25] M. B. Smyth. Powerdomains and predicate transformers: a topological view. In J. Diaz, editor, Automata, Languages and Programming, pages 662{675, Berlin, 1983. Springer-Verlag. Lecture Notes in Computer Science Vol. 154.