Given an \omega -chain:

The colimit (or inverse limit) is the cpo of \omega -tuples: D_\infty \; \triangleq \; \left \{ (x_0, x_1, \dots ) \mid x_i \in D_i \land x_i = g_i(x_{i+1}) \right \} That is, it is countable sequence of elements, one for each domain D_i, where each element is consistent with earlier elements.

Ordering: The ordering is the pointwise ordering of products, naturally generalised to \omega -tuples. Under this ordering, D_\infty is a cpo. In fact if each D_i is a Scott domain, so is D_\infty .

Proof.

• Liam O'Connor

We shall prove that D_\infty is an upper bound of the \omega -chain. Proof that it is the least upper bound is straightforward but tedious, and is omitted.

We must construct a family of retraction pairs: \left \{ D_i \xtofrom [\theta _{\infty ,i}]{\theta _{i,\infty }} D_\infty \middle |\;\; i \in \mathbb {N}\;\; \right \} such that the following diagram commutes:

Defining the projection of the retraction pair D_i \xtofrom [\theta _{\infty ,i}]{\theta _{i,\infty }} D_\infty is straightforward: \theta _{\infty ,i}(x_0,x_1,\dots ) \; \triangleq \; x_i However, to define the embedding \theta _{i,\infty } requires us to, for a given value x \in D_i, produce an \omega -tuple of values consistent with x in every domain D_k. We do this by defining \theta _{i,\infty } in terms of helper functions \theta _{i,j}: \theta _{i,\infty }(x) \; \triangleq \; (\theta _{i,0}(x),\theta _{i,1}(x),\theta _{i,2}(x),\dots ) The helper functions \theta _{i,j} are defined by composing sequences of embeddings (fs) or projections (gs), depending on whether i < j or j < i. For example, when i = 2: \begin {array}{lcl} \theta _{2,\infty }(x) &=& (\theta _{i,0}(x),\theta _{i,1}(x),\theta _{i,2}(x),\theta _{i,3}(x),\theta _{i,4}(x),\dots ) \\[1em] &=& (\underbrace {g_0(g_1(x))), g_1(x)}_{\text {\emph {approximations} to}\ x}, x, \underbrace {f_2(x), f_3(f_2(x)),\dots }_{\text {\emph {equivalent} to}\ x}) \end {array}