Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 87 / 3

Here a pointed complete partial order is a partially ordered set $D$ with a least element ${\perp }_D$ in which every nonempty directed set has a least upper bound. Directed means that every pair of its elements has an upper bound within that set. A Scott continuous map is monotone and preserves these directed suprema. It is not required to preserve the least element; restricting to strict maps would change the categorical claim. If completeness is instead formulated only for increasing countable chains, the same arguments below work with those chains.

Order the function space of complete partial orders $[D\to E]$ pointwise: $f\le g$ means $f(x)\le g(x)$ for every $x$. Its least element is the constant function with value ${\perp }_E$. For a directed family $\mathcal{F}$ of continuous maps, define $h(x)={\sup }_{f\in \mathcal{F}}f(x)$. This is well-defined and is its pointwise least upper bound. It is monotone. For any directed $A\subseteq D$,The interchange is valid because the combined family $\{f(a):f\in \mathcal{F},a\in A\}$ is directed, and either iterated supremum is its least upper bound. Thus $h$ is a Scott continuous map, proving that $[D\to E]$ is a pointed complete partial order.

Finite products carry the product order, componentwise suprema and least element $({\perp }_D,{\perp }_E)$. The one-element order is a terminal object. For the exponential, use the function space with evaluation $\mathrm{ev}(f,x)=f(x)$. To check joint continuity, take a directed family of pairs $(f_i,x_i)$. ThenIndeed, directedness supplies a $k$ above the pairs indexed by both $i$ and $j$, giving $f_i(x_j)\le f_k(x_k)$. Thus the diagonal values are cofinal in the double family, and evaluation preserves its supremum.

For a continuous $h:A\times D\to E$, its currying is $\Lambda h:A\to [D\to E]$, $(\Lambda h)(a)(d)=h(a,d)$. Each section is continuous because $d\mapsto (a,d)$ is; pointwise directed suprema in the $a$ coordinate show that $\Lambda h$ is continuous. Conversely a continuous $g:A\to [D\to E]$ gives the continuous map $\mathrm{ev}\circ (g\times {\mathrm{id}}_D)$. The two constructions are inverse, because they agree on every pair $(a,d)$. This gives the natural bijectionwith the required evaluation map. Together with the terminal object and products, it proves cartesian closure of pointed complete partial orders with non-strict continuous maps.

Choose mutually inverse maps $i:D^D\to D$ and $j:D\to D^D$. This is an extensional reflexive object in the Cartesian closed category. Define its application morphismFor endomorphisms $f,g:D\to D$, application in the underlying set $\mathrm{End}(D)$ is $f\cdot g=\mathrm{app}\circ ⟨f,g⟩$.

It is useful to define term interpretation uniformly over any context object $A$. An environment assigns each free variable $x$ a morphism $\rho (x):A\to D$. Variables are interpreted by their assigned maps, and application is interpreted by $\mathrm{app}$ and pairing. For lambda abstraction, lift the old environment along ${\pi }_A:A\times D\to A$, interpret the new variable by ${\pi }_D$, and let $h:A\times D\to D$ interpret the body. Then setTaking $A=D$ gives interpretations in the requested set of endomorphisms. Other context objects are needed in the recursive definition to handle bound variables correctly.

The beta reduction rule follows from $ji={\mathrm{id}}_{D^D}$ and the evaluation identity for currying. Applying the interpreted abstraction to a map $g:A\to D$ givesInduction on terms identifies this with interpretation of the capture-avoiding substitution of the argument for $x$.

For eta conversion, suppose $x$ is not free in $M$ and write $f:A\to D$ for the interpretation of $M$. The body $Mx$ on $A\times D$ is the uncurried form of $jf$. HenceThus beta-eta-equivalent terms have equal interpretations in $\mathrm{End}(D)$. The full isomorphism, rather than just a retract of the function object, provides the inverse law used in the eta step.