


\documentstyle[11pt]{article}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\begin{document}
\title{Function Spaces of Domains}
 \author{K.A.Kale\\
 Department of Pure Mathematics and Mathematical Statistics\\
16 Mill Lane\\
 Cambridge\\
 CB2 1SB}
\date{}
\maketitle


\begin{abstract}

 We prove a number of results, including the following:  If $D$ is an 
$\omega$-algebraic poset which is not an antichain, and $E$ is an
$\omega$-continuous poset,  then there exists a Scott-continuous 
order-embedding from
$E$ to $[D \to D]$;  in particular, there exists a 
Scott-continuous order-embedding from (P($\omega$),$\subseteq$) to $[D \to D]$.
The proof of this main result
does not use the Axiom of Choice.
\end{abstract}


\section{Introduction} 

 In recent years, theoretical computer scientists have studied 
various classes of partially ordered sets, with the object of using 
these to provide mathematical models for various programming languages.
The thesis of Gunter (1985) is a reference for the background to this activity. 


 The following result (attributed to Plotkin) was proved in a paper 
by Mislove (1985):  If $D$ is an $\omega$-algebraic poset with bottom element, 
and every chain in $D$ has a supremum, and $D$ satisfies the domain 
equation $D \cong  [D \to D]$, then there is an order-embedding from 
(P($\omega$),$\subseteq$) 
to $D$ which preserves suprema of non-empty sets, and infima of non-empty 
chains.  In this paper we shall show that if $D$ is any 
$\omega$-algebraic poset which is not an antichain, then there 
exists such an 
order-embedding from (P($\omega$),$\subseteq$) to $[D \to D]$.
We shall also use the 
methods of our main proof to derive a number of other results. 



\section{Preliminaries}
 
In this section we shall summarize a number of definitions and 
results from the literature. 



A substructure $C$ of a poset is a chain if it is non-empty and for 
all $x,y \in C, x \leq y$ or $y \leq x$.  A poset $P$ is a chain-complete partial order 
(ccpo) if every chain in $P$ has a supremum in $P$. An element 
$x \in P$ is 
compact if whenever $C$ is a chain in $P$ such that $\bigvee C$
exists and $x \leq \bigvee C$, 
there exists a $c \in C$ with $x \leq c$.
(Compact elements are sometimes referred
to as finite elements.)  We write $B(P)$ for the set of compact elements 
of $P$.  A substructure $D$ of a poset $P$ is directed if it is non-empty and
every pair of elements of $D$ has an upper bound in $D$.  A poset 
$P$ is $\omega$-algebraic if for every member $x$ of $P$ the set 
$\{y:y\leq x,y \in B(P)\}$ is 
directed with supremum $x$, and $B(P)$ is countably infinite.

Define the relation $<<$ on $P$ as follows:  $x<<y$ iff 
for every chain $C$ 
such that $\bigvee C$ exists and $y< \bigvee C$, there exists 
$c \in C$ with $x \leq c$.  We say that 
$P$ is $\omega$-continuous if there exists a countably 
infinite set $B$ (called 
the base of $P$) such that for every element $x$ of $P$, 
$\{y:y \in B,y<<x\}$ is 
directed with supremum $x$.  
(Note that trivially, $x<<y$ implies $x \leq y$.
We write $\uparrow\! x$ for the set $\{y:x \leq y\}$, and 
$\hat{\uparrow\!}x$ for 
the set $\{y:x<<y\}$.  Similarly,if $S \subseteq P$, we write 
$\uparrow\! S$ for 
the set $\{y: \exists s \in S, 
s \leq y\}$ and $\hat{\uparrow\!}S$ for the set $\{y: \exists s \in S, s<<y\}$. 


 If $D$ and $E$ are posets, and $f:D \to E$ is a function, we 
say that $f$ is 
monotone increasing (m.i.) if $x\leq y$ implies $f(x) \leq f(y)$.  
We say that $f$ is 
an order-embedding if it is monotone increasing and $f(x)\leq f(y)$
 implies 
$x \leq y$.  We say that $f$ is Scott-continuous 
(or sometimes just continuous)
if for every chain $C$ such that $\bigvee C$ exists, 
$f(\bigvee C)= \bigvee f(C)$.  We write $[D \to E]$ 
$([D \stackrel{m}{\to} E] )$ for the poset of continuous 
(monotonic) functions from $D$
to $E$ with the pointwise ordering.  If $D$ and $E$ are 
posets with bottom 
elements $\emptyset_D, \emptyset_E$ respectively, then we say 
that a function $f:D \to E$ is 
strict if $f(\emptyset_D) = \emptyset_E$. We write 
$[D \stackrel{s}{\to} E]$ for the poset of strict 
continuous functions from $D$ to $E$ with the pointwise ordering. 


If $P$ is a poset, we can define a topology on $P$, called the Scott 
topology, as follows: say that a subset $O$ of $P$ is open if (i) for all 
$x \in O$ and all $y \in P$, $x\leq y$ implies $y \in O$
 and (ii) whenever $C$ is a chain in $P$ 
such that $\bigvee C$ exists and $\bigvee C \in O$, 
$C \cap O \neq \emptyset$. 


A substructure $A$ of $P$ is an antichain if it is 
non-empty and for all
$x,y \in A$ with $x \not=y, x\not\leq y$ and $y \not\leq x$. 
An upward (downward) $\omega$-chain in a poset
$P$ is the image of a m.i.~injection from $\omega$ $(\omega^{op})$
to $P$. 

If $S$ is a subset of a poset $D$, and $x$ an element of $D$, we 
write $S \leq x$
to denote that $s \leq x$ for all $s \in S$.  We write
$a_1, \ldots, a_n \leq x$ to mean $a_1 \leq x, \ldots, a_n \leq x$. 
We define $\downarrow\! T$ (for $T$ a subset of a 
poset $D$) by $\downarrow\! T:=\{d \in D: \exists t \in T \ d\leq t \}$. 



A subset $S \subseteq \omega$ is cofinite iff $\omega \setminus S$ 
has finite cardinality.  If $A$ and
$B$ are sets, we write $|A| \leq  |B|$ to mean that 
the cardinality of $B$ is at 
least that of $A$;  by definition, this means that there exists an 
injection from $A$ to $B$. 



If $D$ is a poset, we define $D_\bot$ to be the poset 
$D \times \{0\} \cup 1 \times \{1\}$, ordered by 
$\langle x,0\rangle \leq \langle y,0 \rangle$ iff $x,y \in D$ 
and $x \leq y$ in $D$, and 
$\langle 0,1 \rangle \leq \langle d,0 \rangle$ for all $d \in D$. 


We follow Markowsky(1976) and Markowsky and Rosen (1976) in using 
definitions couched in terms of chains rather than directed sets, 
because we feel that these are mathematically more natural. It was 
proved by Cohn (1981) that if $P$ is a ccpo, then every directed set 
in $P$ has a supremum. (A stronger version of this result was proved by 
Markowsky (1976).)  These proofs of this general result both use the 
Axiom of Choice.  However, if $P$ is an $\omega$-continuous poset, then by a 
slight generalization of a result in Markowsky and Rosen (1976), we 
can prove this equivalence without using the Axiom of Choice, by
working with the countable set of base elements.

Throughout this paper, we shall use the symbol ``[AC]'' to denote a 
proof which uses Choice. 


A topological space is said to be $T_0$ if for each pair $\{x,y\}$ of 
distinct elements, either there exists an open set $U$ containing 
$x$ but 
not $y$, or there exists an open set $V$ containing $y$ but not $x$. 


The following propositions are well known in the domain-theoretic 
community. (The thesis of Jung (1989) includes an overview of some 
basic results in domain theory, including these;  we have been unable 
to trace the original sources.) 
\begin{proposition}  \label{pr:1}
Let $D$ and $E$ be posets. Then a function $f:D \to E$ is 
continuous in the sense defined above if and only if it is 
topologically continuous with reference to the Scott topologies 
on $D$ and $E$. 
\end{proposition}
\begin{proposition} \label{pr:2}
Let $D$ be an $\omega$-continuous poset.  Then the Scott-topology
on $D$ is countably based and $T_0$. 
\end{proposition}
The following propositions of $T_0$ topology are trivial. 
\begin{proposition} \label{pr:3}
Let $(X,T)$ be a $T_0$ topological space. Then there exists 
an injection from $X$ to $T$. 
\end{proposition}
\begin{proposition} \label{pr:4}
Let $(X,T)$ be any topological space, and $(Y,U)$ be a $T_0$
topological space with base $B$. Write $S(X,Y)$ for the set of 
topologically continuous functions from $X$ to $Y$. Then 
$|S(X,Y)| \leq |T|^{|B|}$. 
Consequently, if $X$ and $Y$ are countably based, 
$|S(X ,Y)| \leq  |P(\omega)|$. 
\end{proposition}
Proof: The only aspect of the result which is not obvious is the fact
that it can be proved without Choice. We assert that 
$(2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}$. 

For let $f \in [0,1)^\omega$.
Write $f(n)=0.a^n_0 a^n_1 a^n_2 \ldots$, where each 
$a^n_i \in \{0,1\}$, 
and the $a^n_i$ are 
chosen so that the expansion does not terminate in an infinite string 
of 1's. 


Define $\psi(f)= 0.a^0_0 a^1_0 a^0_1 a^2_0 a^1_1 a^0_2 \ldots$. 
Then $\psi : [0,1)^\omega  \to [0,1]$ is an injection. For if 
$\psi(f)= \psi(g)$ with $f\neq g$, 
then $\psi(f)$ (or $\psi(g)$) must terminate in an infinite string of ones,
and by the definition of $\psi$ this implies that $f(n)$ terminates in an 
infinite string of 1's for all $n$ (or that $g(n)$ does).  Contradiction. $\Box$


The following two combinatorial results are exercises in Crawley \& 
Dilworth (1973) and Priestley (1988) respectively; they are both 
immediate consequences of Ramsey's theorem, which is proved (for 
example) in Hodges (1992). 
\begin{theorem}  \label{th:5}
[AC]: Let $(P,\leq)$ be an infinite poset.Then $P$ has an infinite 
chain or an infinite antichain. 
\end{theorem}
\begin{theorem}  \label{th:6}
[AC]: Let $(P,\leq)$ be an infinite chain.  Then $P$ has an upward 
$\omega$-chain or a downward $\omega$-chain. 
\end{theorem}


Note that in theorems 5 and 6, if we know that 
the underlying sets 
are well-orderable, then we can dispense with the Axiom of Choice in 
the proofs. 


\section{The results} 

It is easy to construct an example which shows that if $D$ and $E$ 
are different $\omega$-algebraic ccpos,
then the continuous function space $[D \to E]$ 
may only be countable: for example, let $D$ be the ordinal 
$\omega+1$, and $E$ 
the countably infinite antichain with a bottom element added. This 
makes our results all the more surprising. 
 By using a topological argument, it is easy to see why 
$2^{\aleph_0}$ is an 
upper bound for $[D \to D]$, where $D$ is $\omega$-continuous. 


\begin{theorem}  \label{th:7}
Let $D$ be an $\omega$-continuous poset. Then there is an 
injection from $[D \to D]$ to $P(\omega)$. 
\end{theorem}

Proof: Suppose $f \in [D \to D]$. Then by Proposition 1, $f$ is topologically 
continuous with respect to the Scott topology on D. By Proposition 2, $D$ regarded as  a topological space
(with the Scott topology) is countably based and $T_0$. The result 
follows by Proposition 4. $\Box$
\begin{lemma}  \label{le:8}
There is an order-embedding from $(P(\omega),\subseteq)$ to 
$[ \omega \stackrel{m}{\to} \omega]$ (the poset of m.i.~maps 
on the ordinal $\omega$) which preserves 
all non-empty suprema and infima.

\end{lemma}

Proof:  For $S \subseteq \omega$, define $\phi_S:\omega \to \omega$ by
\begin{eqnarray*}
\phi_S(n) & = & n+1 \mbox{ if } n \in S \\
& & n \mbox{ if } n \not\in S
\end{eqnarray*} 
$\Box$






We now prove our main results. 

\begin{theorem}  \label{th:9}
Let $D$ be an $\omega$-algebraic poset which is not itself an 
antichain. Then there is an order-embedding from 
$(P(\omega),\subseteq)$ to 
$[D \to D]$ 
which preserves suprema of all non-empty sets, and infima of all 
chains. 
\end{theorem}
Proof: Case 1. Suppose there exists an element 
$x_0 \in B(D)$ such that $\uparrow\! x_0$
is infinite. 

Case 1a. Suppose that there exists an element 
$a \in \uparrow\! x_0 \setminus B(D)$. 
(The reasoning for this case is similar to that of Plotkin's result
as quoted in Mislove (1985). However, whereas he mapped arbitrary 
subsets of $\omega$ into $[D \to D]$ and then used the identification 
$[D \to D] \cong D$, 
we shall use our Lemma 8. We avoid using any global hypothesis of 
chain-completeness by substituting our case assumption that there 
exists a non-compact element above $x_0$.) 
Find an upward $\omega$-chain  $\{a_r: r \in \omega \}$ in $B(D) \cap \uparrow\! x_0$ 
with supremum $a$. 
Let $S$ be a subset of $\omega$. 
Define $f_S:D \to D$ by 
\begin{eqnarray*}
f_S(x) & = & a_{\phi_S(i)}  \mbox{ if } i=\max\{r:a_r \leq x\} 
\mbox{ exists }\\
& & a \mbox{ if } a_i \leq x \mbox{ for all } i \in \omega\\
& & a_0 \mbox{ otherwise }.
\end{eqnarray*} 
Clearly $f_S$ is Scott continuous, and $S \to f_S$ has the properties 
 required. 
Case 1b. Suppose $\uparrow\! x_0 \subseteq B(D)


Case 1b(i). Suppose $\uparrow\! x_0$ has an upward $\omega$-chain
$a_0 <a_1 <a_2 < \ldots $.  (By the Case 1b hypothesis, this chain must consist of 
compact elements.)  For $S \subseteq \omega$, define $f_S :D \to D$ as follows: 
\begin{eqnarray*}
f_S(x) &=& a_{\phi_S(i)} \mbox{ if }
i= \max \{r:a_r \leq x\} \mbox{ exists }\\ 
&& x \mbox{ if } a_i \leq x \mbox{ for all } i \in \omega\\
&& a_0 \mbox{ otherwise }
\end{eqnarray*}
By the Case 1b assumption that $\uparrow\! x_0 \subseteq B(D)$, 
it follows that $f_S$ is 
Scott-continuous. Also, $S \to f_S$ is an order-embedding which preserves 
suprema  and infima of non-empty sets.


Case 1b(ii). Suppose $\uparrow\! x_0$ has a downward $\omega$-chain 
$a_0 > a_1 >a_2 >\ldots > x_0$. 
For $S \subseteq \omega$, define $f_S :D \to D$ as follows:
\begin{eqnarray*} 
f_S(x) & = & a_{\phi_S(i)} \mbox{ if } i=\min\{r:a_r \leq x\} 
\mbox{ exists }\\ 
& & x_0 \mbox{ if for all } r, a_r \not\leq x. 
\end{eqnarray*}
Then the map $\phi :(P(\omega), \subseteq )^{op} \to [D \to D]$ 
given by $S \to f_S$ is an order-embedding which preserves suprema of chains and infima of all non-empty
sets in $(P(\omega), \subseteq )$; thus there exists an 
order-embedding from $(P(\omega), \subseteq)$ to $[D \to D]$ which preserves suprema  and infima of all non-empty sets.
 



Case 1b(iii). Suppose that $\uparrow\! x_0$ has no infinite chain. 
Then by Theorem 5, it must have an infinite antichain, $A$ say.  

Case 1b(iii).1. Suppose that $\uparrow\! x_0$ has infinitely many 
maximal elements.
Enumerate these as $\{a\} \cup \{a_i :i \in \omega \}$. 
For $S \subseteq \omega$, define 
\begin{eqnarray*}
f_S(x) & = & a \mbox{ if } x=a \mbox{ or }
x \in \{a_i :i \in S\}\\
& &  x_0 \mbox{ otherwise }
\end{eqnarray*}
Then $S \to f_S$ is an order-embedding which preserves suprema and infima 
of all non-empty sets. 

 

Case 1b(iii).2. Suppose that $\uparrow\! x_0$ has only finitely many maximal
elements.  The absence of any infinite chains in $\uparrow\! x_0$ implies (without 
recourse to the Axiom of Choice, since $\uparrow\! x \subseteq B(D)$, which is countable) that every $x \in A$ must be below at least
one of these maximal elements. So there is an infinite subset 
$Y$ of $A$ 
such that every element of $Y$ is below some maximal element, $c$ say. 
Enumerate the elements of $Y$ as $\{y_i :i \in S \}$. 
For $S \subseteq \omega$, define 
\begin{eqnarray*}
f_S(x) &= &c  \mbox{ if } x \in \uparrow\!\{y_i :i \in S \}\\ 
& & x_0 \mbox{ otherwise }. 
\end{eqnarray*}
Then $S \to f_S$ is an order-embedding which preserves all non-empty 
suprema and infima. 
 


Case 2. Suppose for all $x \in B(D)$, $\uparrow\! x$ is finite. 


Case 2a. Suppose that there exists $y \in B(D)$ which is not above a
minimal element of $B(D)$. Then we can find a chain 
$y=a_0 >a_1 >a_2 >\ldots$.
For $S \subseteq \omega$, define 
\begin{eqnarray*}
f_S(x) & = & a_0 \mbox{ if } x \not\leq a_r \mbox{ for all } 
r \in \omega\\
& & a_{\phi_S(i)} \mbox{ if } i=\max\{r:x \leq a_r \} 
\mbox{ exists }. 
\end{eqnarray*}
Note that the functions $f_S$ $(S \subseteq \omega)$ are fully 
defined on $D$: if there
 existed an $x$ with $x \leq a_r$ for all $r \in \omega$, then by 
algebraicity of $D$ we 
could pick $z \in B(D)$ with $z \leq x$; then $\uparrow\! z$ would be infinite, 
contradicting the Case 2 hypothesis. 
It can be verified that 
$\phi :(P(\omega), \subseteq )^{op} \to [D \to D]$ 
given by $S \to f_S$ is an
order-embedding which preserves all non-empty suprama and infima. 

Case 2b. Suppose that every $y \in B(D)$ is above some 
minimal element of
$B(D)$. Then by the Case 2 hypothesis, $B(D)$ has infinitely many minimal 
elements. 

Case 2b(i). Suppose that no two minimal elements of $B(D)$ 
have a common
upper bound. As $D$ is by assumption not an antichain, we can find a 
minimal element $a \in B(D)$ and another element $b  \in B(D)$ 
such that $a<b$. 
Enumerate the minimal elements of $B(D)$ as
$\{a\} \cup \{a_i :i \in \omega\}$.
For $S \subseteq \omega$, define $f_S(x)$ as follows: 
\begin{eqnarray*}
f_S(x) & = & a \mbox{ if } x \geq a \mbox{ or } 
\exists i \in \omega \setminus S \mbox{ with } x \geq a_i\\
& & b \mbox{ if } x \geq a_i \mbox{ for some } i \in S. 
\end{eqnarray*}
Then $S \to f_S$ is an order-embedding of $(P(\omega), \subseteq )$ 
into $[D \to D]$ which 
preserves suprema and infima of non-empty sets. 



Case 2b(ii). Suppose there are two minimal elements of 
$B(D)$ ($a, b$ say)
which have a common upper bound $c$. Enumerate the minimal elements of 
$B(D)$ as $\{a,b\} \cup \{a_i :i \in \omega \}$.  
For $S \subseteq \omega$, define $f_S$ as follows:
\begin{eqnarray*} 
f_S(x) & = & x \mbox{ if } x=a \mbox{ or } x=b \mbox{ or } x=c\\ 
& = & c \mbox{ if } x=a_i, i \in S \mbox{ or } x \not\in 
\{a,b,c\} \cup \{a_i :i \in \omega \}\\ 
& = & a \mbox{ if } x=a_i, i \not\in S. 
\end{eqnarray*}
It can be checked that $S \to f_S$ is an order-embedding which preserves 
suprema and infima of non-empty sets. $\Box$


 


 




 The condition that 
$B(D)$ has an 
unbounded upward $\omega$-chain is not in general equivalent to the 
condition that $D$ has an unbounded upward $\omega$-chain, even when $D$ is 
algebraic, and so the following proposition may be useful in 
applications. 

\begin{proposition}  \label{pr:12}
Let $D$ be an $\omega$-continuous poset with base $B$. Suppose $D$
has an upward $\omega$-chain which has no upper bound in $D$. Then $B$ has an 
upward $\omega$-chain which has no upper bound in $D$.
\end{proposition} 

Proof: Let $d_0 <d_1 <d_2 <\ldots$ be an unbounded 
$\omega$-chain in $D$. 
Define $S:=\{y:y \in B, \exists n \in \omega \ y << d_n \}$. $S$ is finite or countable, 
so write it (possibly with 
repetitions) as $\{c_i :i \in \omega \}$. 
 Define $S_n := \{c_i :0\leq i \leq n, c_i <<d_n\}$, for 
$n \in \omega$. 
 Then $S_0 \subseteq S_1 \subseteq S_2 \ldots$, and 
$\bigcup_{n \in \omega} S_n = S$.
 Pick $b_0 \in B$ such that $S_0 <<b_0$ (by which we mean 
that for every $s \in S_0$, 
$s<<b_0$), and $b_0 <<d_0$. 
 Suppose inductively that we have 
$b_0 <b_1 <b_2 <\ldots < b_n <<d_n$, and $S_n <<b_0$. 
 There exists $e_{n+1}$ with $e_{n+1} \in B, e_{n+1} <<d_{n+1}$, and 
$e_{n+1} \not\leq d_n$. So there exists $b_{n+1} \in  B$ with 
 $S_{n+1}, b_n, e_{n+1} \leq b_{n+1}  <<d_{n+1}$ (using an obvious notation). 
 Now $b_n <b_{n+1}$. (For if $b_n =b_{n+1}$, then 
$c_{n+1} \leq b_n \leq d_n$, contradiction.) 

 Suppose for a contradiction that $b_0 <b_1 <b_2 <\ldots$ had a bound 
$d \in D$.
 For all $i \in  \omega $ there exists $j \in \omega$  such that 
$c_i \in S_j$ , and so $c_i \leq b_j \leq d$. Thus for each 
$n \in \omega$,
$d =\bigvee\{y \in B:y<<d_n\} \leq d$. So 
$\{d_n :n \in \omega \}$ is bounded.  $\Box$

 Note that this result does not in general hold for continuous posets
(or even algebraic posets) which are not countably based: consider 
$D:=\{T: T \subseteq \aleph_{\omega}, |T| \leq \aleph_0\}$, ordered by inclusion. 


The following well-known interpolation property is stated (for 
directedly-complete posets, and with the relation $<<$ defined in terms 
of directed sets rather than chains) in Jung (1989), and the proof 
given there works for arbitrary continuous posets. However, as we
have chosen to define $<<$ in terms of chains, we need to impose a
countability restriction in order to ensure that the details of the
proof can be carried through.


\begin{proposition}  \label{pr:13}
Let $D$ be an $\omega$-continuous poset. Suppose $x<<y$ in $D$. 
Then there exists $z \in D$ with $x<<z<<y$. 
\end{proposition}

We now prove a version of Theorem 9 which holds for 
$\omega$-continuous posets. Case 1 of the proof assumes the existence of an 
upward $\omega$-chain $\{a_i :i \in \omega \}$ in a base $B$ of the given poset; since in 
the case of a continuous poset, $B$ need not consist of finite elements,
we may well have $\hat{\uparrow\!}a_i = \emptyset$  for one or more $i$, and so to ensure that the
map $S \to f_S$ is an order-embedding (and not merely order-preserving) we
shall need to define an auxiliary chain instead of using the $a_i$
directly.

\begin{theorem}  \label{th:12}
Let $D$ be an $\omega$-continuous poset which is not itself an 
antichain, and which has the property that every bounded chain in $D$ has
a supremum. Then there exists an order-embedding from 
$(P(\omega), \subseteq )$ to 
$[D \to D]$ which preserves suprema of non-empty sets 
and infima of chains.
\end{theorem}
Proof: Choose a countably infinite base $B$ for $D$.

Case 1. Suppose $B$ has an upward $\omega$-chain bounded in $D$. Call 
this chain $a_0 <a_1 <a_2 <\ldots$. 
Suppose inductively we have defined $c_0 <c_1 <c_2 <\ldots c_n <<a_n$. 
As $a_n <a_{n+1}$, there exists $b \in B$ such that 
$b<<a_{n+1}, b \not\leq a_n$.  As $\{x: x<<a_{n+1}, x \in B\}$ 
is directed, we can find $c_{n+1} \in B$ such that 
$b \leq c_{n+1}$, and $c_n <c_{n+1} <<a_{n+1}$. 
Now $c_{n+1} >c_n$. Also, $c_{n+1} <\not< a_n$. 
The chain $c_0 <c_1 <c_2 <\ldots$ is bounded, and so has a 
supremum $c$. 
For $S \subseteq \omega$, define $f_S(x)$ as follows: 
\begin{eqnarray*}
f_S(x) & = & c \mbox{ if } x>>c_i \mbox{ for all } i \in \omega\\
& & c_{\phi_S(i)} \mbox{ if } i=\max\{r:c_r <<x\} \mbox{ exists }\\
& & c_0 \mbox{ otherwise }
\end{eqnarray*}
For each $i \in \omega$, $i=\max\{r: c_r <<a_i \}$. This ensures that distinct
subsets $S,T$ of $\omega$ induce maps $f_S,f_T$ which have distinct 
effects on $D$. 

Case 2. Suppose that $B$ has no upward $\omega$-chain bounded in $D$. 
then $D=B(D)=B$, so in particular $D$ is algebraic and we can use
Theorem 9.   $\Box$


\begin{theorem}  \label{th:13}
Let $P$ be a countably infinite poset which is not itself an
antichain. Then there exists an order-embedding from 
$(P(\omega), \subseteq )$ to 
$[P \stackrel{m}{\to} P]$ which preserves suprema of non-empty sets and infima of chains. 
\end{theorem}

Proof: Case 1.
Suppose $P$ has an upward $\omega$-chain, $a_0 <a_1 <a_2 <\ldots$ say. 
For $S \subseteq \omega$, define $f_S$ as follows. 
\begin{eqnarray*}
f_S(x) & = & a_{\phi_S(i)} \mbox{ if } 
i=\max\{r:a_r \leq x\} \mbox{ exists }\\
& & x \mbox{ if } a_r \leq x \mbox{ for all } r \\
& & a_0 \mbox{ otherwise }
\end{eqnarray*}
(Note that $f_S$ need not be Scott-continuous.) 
Then $S \to f_S$ is the order-embedding required. 

Case 2. Suppose that $P$ has no upward $\omega$-chain. Then $P$ is 
$\omega$-algebraic, and a function on $P$ is 
monotone increasing if and only if it
is Scott-continuous. The conclusion then follows by 
Theorem 9. $\Box$








\begin{theorem}  \label{th:14}
Let $D$ be an $\omega$-algebraic poset, or an $\omega$-continuous poset
with the property that every bounded chain has a supremum. Then 
$|[D \to D]| =2^{\aleph_0}$.
\end{theorem}
Proof: If $D$ is an antichain, then clearly $[D \to D]$ is an antichain of
the required cardinality.  If $D$ is not an antichain, 
we can use Theorem 9 or Theorem 13 to show that 
$2^{\aleph_0} \leq |[D \to D]|$.  
The result now follows from Theorem 7. $\Box$


 After we had proved Theorem 14 independently, F.~Honsell observed that 
the following result of his is an exercise in Barendregt (1984): 
Let $D$
be a countable ccpo with bottom. Then $|[D \to D]| =2^{\aleph_0}$. Honsell's result 
does not appear to be equivalent to ours, and the suggested method of 
proof seems different. 

Recall (for example from Smyth (1983) that if $C$ is a cartesian 
closed category (ccc) whose objects form a subclass of the class of all
posets, and whose morphisms are precisely the Scott-continuous 
functions between posets in the category, then whenever $D$ and $E$ are 
members of $C$, the function space $[D \to E]$ is also a 
member of $D$. 

In what follows, when we refer to a category of posets having a
particular property, we shall assume (unless we explicitly state 
otherwise) that the morphisms of the category are the Scott-continuous 
functions between objects of the category. 

\begin{corollary}  \label{co:15}
Let $D$ be a member of some ccc of $\omega$-continuous ccpos.
Then the set of Scott-open sets on the $\omega$-continuous ccpo 
$[D \to D]$ is
bijective with $P(\omega)$.
\end{corollary}

Proof: This follows from Propositions 2 and 3, 
together with Theorem 15. $\Box$

(As an aside, we mention that the cartesian closed subcategories of
the category of algebraic ccpos were classified by Jung (1989). More 
recently (1990), Jung has also classified the cartesian closed 
categories of the continuous ccpos. These results generalize the 
theorem published by Smyth (1983).) 


Theorems 9 and 12 give us a large class of domains which are
universal in a certain sense which will be made precise later. 



\begin{theorem}  \label{th:16}
Let $D$ be an $\omega$-continuous poset. Then there is a 
Scott-continuous order-embedding 
$\phi :D \to (P(\omega), \subseteq )$. If $D$ is $\omega$-algebraic, 
then there is an order-embedding 
$\phi :D \to (P(\omega), \subseteq )$ which is Scott-continuous and which preserves infima 
of non-empty sets where these exist in $D$. 
\end{theorem}
Proof: Let $B=\{x_r :r \in \omega \}$ be a base for $D$. Define $\phi$
by $\phi(x)=\{r: x_r <<x\}$. The required properties are 
readily verified. $\Box$

Note that if $D$ has a bottom element, by omitting it from the 
 enumeration $\{x_r :r \in \omega \}$, we can ensure that the map 
$\phi$ is strict. 
The reason that we cannot make the stronger statement for 
$\omega$-continuous posets that we did for $\omega$-algebraic 
posets is that if $S$ 
is a subset of a poset $P$, and the infimum of $S$ exists, then 
$x<<s$ for 
all $s \in S$ need not imply that $x<< \bigwedge S$, even if $P$ 
is $\omega$-algebraic. This 
is shown by the following example ({\em see Fig.~1 at end}):


$a_i <a$ for all $i \in \omega$
 
$b_i <b$ for all $i \in \omega$ 
 
$a<b$
 
$a_i <b_i$ for all $i \in \omega$
 
$c_i <c_j$ if $j<i< \omega$

$b<c_i$ for all $i$ 
(And extended by reflexivity and transitivity.) 

We have $a<<c_i$ for all $i \in \omega$, 
but $a <\not< b= \bigwedge \{c_i : i \in \omega \}$. 

\begin{corollary}  \label{co:17}
Let $D$ be an $\omega$-algebraic poset, or an 
$\omega$-continuous poset with the property that every bounded chain has a 
supremum. Suppose also that $D$ is not an antichain. 

(a) If $E$ is an $\omega$-continuous poset, then there exists a Scott-
continuous order-embedding from $E$ to $[D \to D]$. 

(b) If $E$ is an $\omega$-algebraic poset, then there exists an 
order-embedding from $E$ to $[D \to D]$ 
which preserves suprema and infima of 
non-empty chains whenever these exist in $E$. 
\end{corollary}

(It is proved in the thesis of Jung ((1989), Theorem 1.37) that if $D$ is
a ccpo such that $[D \to D]$ is continuous, then every chain in $D$ has both a
supremum and an infimum.) 

It is well known (see, for example, Proposition 2.2, Chapter 0, of 
Gierz et al. (1981), that if $D$ is a poset such that every subset of D
has a supremum, then every subset of $D$ has an infimum. However, 
if $f$ 
is a function on a poset $D$, and $f$ preserves all suprema, then $f$ need 
not preserve all infima: Take $D$ to be the interval [0,1] with the 
usual ordering, and define $f(x)=0$ if $x=0$, $f(x)=1$ otherwise. 

It is known in the mathematical community that 
$(P(\omega), \subseteq )$ contains 
chains of cardinality $2^{\aleph_0}$. Let {\bf R} and {\bf Q} have their usual orderings. 
Noting that {\bf R} and 
$\{ T:T \subseteq$ {\bf Q}, $T= \downarrow\! T \}$ are respectively
$\omega$-continuous and $\omega$-algebraic posets and using 
Theorem 16 immediately 
gives us two stronger results. 


It is also known that $(P(\omega), \subseteq )$ contains 
antichains of cardinality 
$2^{\aleph_0}$, and the following proof was communicated to me by Wilfrid Hodges: 
Partition $\omega$ into two  infinite disjoint subsets $A$ and $B$. Let 
$f:A \to B$ be a 
bijection. Let 
$\{X_i :i<2^{\aleph_0}\}$ be a chain of distinct elements of 
$(P(A), \subseteq)$. For $i<2^{\aleph_0}$,
define $Y_i :=B \setminus f(X_i) $. Then $\{Y_i : i<2^{\aleph_0} \}$
 is a chain of elements of 
$(P(B), \subseteq)$, and $\{X_i \cup Y_i : i<2^{\aleph_0}\}$ is 
an antichain in $\omega$ 
of cardinality $2^{\aleph_0}$. 

The standard domain constructors 
$\bot , + , \bigoplus, \times, [D \to D]$ are described in a
number of places, including the thesis of Gunter (1985). These are 
monotone increasing functors on the category 
whose objects are $\omega$-FS
domains (see Jung (1990) for a definition of this term) and whose 
morphisms are projection-embedding pairs (as defined in, for example, 
Jung (1989)). 

\begin{definition}  \label{de:18}
Let $D$ be an $\omega$-algebraic poset, or an 
$\omega$-continuous poset in which every bounded chain has a supremum. Then 
we say that $D$ is an applicable domain iff $D$ is a solution of a 
recursive domain equation $F(D) \cong D$, where 
(1) $F$ includes only monotone increasing domain constructors and 
(2) $F$ 
includes at least one occurrence of the constructor $[D \to D]$. 
\end{definition}

\begin{corollary}  \label{co:19}
 Let $D$ be an applicable domain. Write $c:=2^{\aleph_0}$. Then 
there exists an order-embedding from $(P(c), \subseteq)$ 
to $[D \stackrel{m} {\to} D]$, and so for 
any poset $E$ with $|E| \leq c$, there exists an order-embedding 
from $E$ to 
$[D \stackrel{m}{\to} D]$.
\end{corollary} 
Proof: By the discussion above, $D$ has an antichain whose elements can 
be enumerated as $\{a_i : i< c \}$. Clearly $D$ is not itself an antichain (for
if so, it could not be an applicable domain). Pick $a,b \in D$ with 
$a<b$. 
For $S \subseteq c$, define $f_S$ as follows: 
\begin{eqnarray*}
f_S(x) & = & b \mbox{ if } x \in \uparrow\!\{a_i : i \in S\}\\ 
& & a \mbox{ otherwise}. 
\end{eqnarray*}
Clearly $f_S$ is monotone increasing, and $S \to f_S$ is an 
order-embedding.  $\Box$

It follows from Corollary 19 that the number of monotone increasing
functions on an applicable domain is $2^c$, which is vastly greater 
than the number of Scott-continuous functions ($2^{\aleph_0}$). 
From the details of the proofs of Theorems 9 and 12, it can be seen
that if $D$ is a poset which satisfies the hypotheses of either of 
these theorems, and if $D$ has a bottom element, then 
$|[D \stackrel{s}{\to} D]| =2^{\aleph_0}$, 
and so $|[D \stackrel{s}{\to} D]| = |[D \to D]|$. At the expense 
of using the Axiom of 
Choice, we can show that $|[D \stackrel{s}{\to} D]| = |[D \to D]|$ under much wider 
conditions. 


\begin{theorem}  \label{th:20}
[AC] : Let $D$ and $E$ be posets with bottom elements $\emptyset_D$ 
and $\emptyset_E$ 
respectively. Then $|[D \stackrel{s}{\to} E]| = |[D \to E]|$ iff 
(a) $[D \stackrel{s}{\to} E]$ is infinite 
or (b) $|E| =1$. 
\end{theorem}
Proof: Suppose $[D \stackrel{s}{\to} E]$ is infinite. Write $D=(D')_\bot$,
so that $D'$ is $D$
with the bottom element removed. Then $f \to f|D'$ is an order-isomorphism 
from $[D \to E]$ to $[D' \to E]$. As 
$[D \stackrel{s}{\to} E]$ is infinite, $|D| \geq 2$. For $e \in E$, define
$f_e:D \to E$ as follows: 
\begin{eqnarray*}
f_e(x) & = & \emptyset_E \mbox{ if } x=\emptyset_D\\
& & e \mbox{ otherwise}. 
\end{eqnarray*}
As $e \to f_e$ is an injection, it follows that 
$|[D \to E]| \geq |E|$. 
$f \to (f|D',f(\emptyset_D))$ is an injection from $[D \to E]$ to 
$[D' \to E] \times E$. 
So $|[D \to E]| \leq |[D' \to~E]| \times |E| = 
|[D \stackrel{s}{\to} E]| . |E| = |[D \stackrel{s}{\to} E]|$. 

(a) Suppose $|E| =1$. Then trivially 
$|[D \stackrel{s}{\to} E]| = |[D \to E]|$. 

(b) Suppose $2\leq |E| < \aleph_0$. 

(i) Suppose $|D| =1$. Then 
$1= |[D \stackrel{s}{\to} E]| < |E| = |[D \to E]|$. 

(ii)  Suppose $2\leq |D| < \aleph_0$. Then $[D \to E]$ is finite. 
So $|[D \to E]| \geq |[D \stackrel{s}{\to} E]| + |E| -1 > |[D \stackrel{s}{\to} E]|$. 

(iii) Suppose $|D| \geq \aleph_0$. Let 
$e \in E \setminus \{\emptyset_E\}$. For $d \in D$, 
define $g_d$ as follows: 
\begin{eqnarray*}
g_d(x) & = & e \mbox{ if } x \not\leq d\\ 
& & \emptyset_E \mbox{ if } x \leq d. 
\end{eqnarray*}
Then $g_d$ is Scott-continuous, and $d \to g_d$ is an 
injection. So $|[D \stackrel{s}{\to} E]| \geq |D| \geq \aleph_0$. So by the first 
part of the proof, $|[D \stackrel{s}{\to} E]| = |[D \to E]|$. 

(c) Suppose $|E| \geq \aleph_0$. If $|D| =1$, then 
$|[D \stackrel{s}{\to} E]| =1 < |E| = |[D \to E]|$. 
If $|D| \geq 2$, then for $e \in E$, define $f_e$ as above. 
Then by the reasoning used in the first part of the 
proof, $|[D \stackrel{s}{\to} E]| \geq |E| \geq \aleph_0$, and so 
$|[D \stackrel{s}{\to} E]| = |[D \to E]|$.  $\Box$

Another interesting fact can be proved using Ramsey's theorem (via 
the decomposition results quoted as Theorem 5 and 
Theorem 6 above). 


\begin{theorem}  \label{th:21}
[AC] : Let $D$ be a poset with no downward
$\omega$-chains, and no infinite antichains. Let $E$ be any poset with no 
 upward $\omega$-chains. Then $[D \stackrel{m}{\to} E]$ has no upward 
$\omega$-chains (and so $[D \to E]$ has no upward $\omega$-chains).
\end{theorem} 
Proof: Suppose $f_0 <f_1 <f_2 < \ldots$ is an upward $\omega$-chain in 
$[D \stackrel{m}{\to} E]$. 
For all $r \in \omega$ there exists $x_r \in D$ such that 
$f_r(x_r)<f_{r+1}(x_r)$. 

Case I: Suppose $\{x_r : r \in \omega \}$ is infinite. Then it must have an upward
$\omega$-chain $x_{N_1} <x_{N_2} <x_{N_3} <\ldots$. 
Without loss of generality, we can assume that 
$N_0 <N_1 <N_2 <\ldots$. 
$$f_{N_i}(x_{N_i})<f_{1+N_i}(x_{N_i}) \leq f_{N_{i+1}}(x_{N_i}) \leq
f_{N_{i+1}}(x_{N_{i+1}}).$$ 
So $\{f_{N_i}(x_{N_i}): i \in \omega \}$ is an upward 
$\omega$-chain in $E$.  Contradiction.

Case II. Suppose $\{x_i : i \in \omega \}$ is finite. Then for some
$y \in D, y=x_{M_r}$ for some strictly monotone increasing sequence 
of natural numbers $\{M_r : r \in \omega \}$. 
$$ f_{M_r}(x_{M_r})<f_{M_r+1}(x_{M_r})<f_{M_{r+1}}(x_{M_r}) \mbox{ as } M_{r+1} \geq 1+M_r.$$ 
Then $\{f_{M_r}(y) : r \in \omega \}$ is an upward $\omega$-chain 
in $E$.  Contradiction.  $\Box$

We conclude by proving another theorem which makes use of some of 
the methods employed earlier in the paper. 

\begin{theorem}  \label{th:22}
Let $D$ be an $\omega$-algebraic poset with the property that 
every bounded chain in $D$ has a supremum in $D$. Suppose also that every 
continuous function on $D$ has a fixed point. Then $D$ is a ccpo.
\end{theorem}
Proof: Suppose for a contradiction that there exists a chain $C$ 
in $D$
with no supremum in $D$. Then $\downarrow\! C \cap B(D)$ is a countably infinite directed 
set, and so contains a cofinal upward $\omega$-chain 
$a_0 <a_1 <a_2 <\ldots$. Any 
supremum of $\{a_i : i \in \omega \}$ 
would be a supremum of $C$, and so the former must be unbounded. Define 
$f:D \to D$ as follows: 
\begin{eqnarray*}
 f(x) & = & a_{i+1}  \mbox{ if } i=\max\{r: a_r \leq x\} 
\mbox{ exists }\\
& &  a_0  \mbox{ otherwise}. 
\end{eqnarray*}
 Clearly $f$ is continuous but has no fixed point. Contradiction.
$\Box$

The poset in the diagram below ({\em see Fig.~2 at end}) shows that we cannot drop the 
assumption that every bounded chain in $D$ has a supremum.  Two related 
questions remain unanswered: Firstly, if $D$ is an $\omega$-algebraic poset 
and every continuous $f:D \to D$ has a least fixed point, must $D$ be a ccpo?
Secondly, does Theorem 22 hold with ``$\omega$-algebraic'' 
replaced by ``$\omega$-continuous''?

$a_i < a_j$ if $i < j < \omega$

$a_i < b$ for all $i \in \omega$

$a_i < c$ for all $i \in \omega$

$b < d$

$c < d$

(And extended by transitivity and reflexivity.)




\section{Acknowledgements} 
I would like to thank Dr Achim Jung, my (unofficial) supervisor 
during 1989/1990, for guidance and encouragement. Dr Jung provided 
the proof for Case 2a of an earlier version of Theorem 9; this 
 represented an improvement on my original proof for this case of the
 earlier result, and was elaborated into Case 2a as it stands in this 
paper. 
Dr Jung also completed the proof of Case 2b of the earlier result; 
again, this was developed into the present version. 
I would also like to thank Professor Wilfrid Hodges, my official 
supervisor, for helpful suggestions and for making detailed comments on
an earlier version of this paper, and 
Dr Manfred Droste for stimulating discussions. 
 Finally, I would like to thank SERC for giving me a grant. 



\begin{thebibliography}{99}
\bibitem{bar:1} Barendregt, H.P. The Lambda calculus: its syntax and semantics, 
North Holland, Amsterdam, 1984. 
\bibitem{coh:1}  Cohn, P.M. Universal Algebra, D.~Reidel, 1981. 
\bibitem{cra:1}  Crawley, P.~\& Dilworth,R. Algebraic Theory of Lattices, Prentice- 
Hall, 1973. 
\bibitem{gie:1} Gierz, G., Hofmann, K.H., Keimel, K., 
Lawson, J.D., Mislove, M., \& 
Scott, D.S., A Compendium of Continuous Lattices, 1981.
\bibitem{gun:1} Gunter, C. Profinite Solutions of Recursive Domain Equations, 
doctoral dissertation, University of Wisconsin, 1985. 
\bibitem{hod:1} Hodges, W. Model Theory, Cambridge University Press, to 
appear in 1992. 
\bibitem{jun:1} Jung, A. Cartesian Closed Categories of Domains, CWI Tract 66, 
1989. 
\bibitem{jun:2} Jung, A. The Classification of Continuous Domains, in: Logic in 
Computer Science, Proceedings of the 1990 Conference, IEEE Press, 1990.
\bibitem{mar:1} Markowsky, G. Chain-complete posets and directed sets with 
applications, Algebra Universalis, Volume 6, 1976, 
pp. 53-68. 
\bibitem{mar:2} Markowsky, G.~\& Rosen, B. Bases for Chain-complete posets, IBM 
Journal of Research and Development, 1976, 
pp. 138-147. 
\bibitem{mis:1} Mislove, M. Detecting Local Finite Breadth in Continuous Lattices
and Semilattices, in: Mathematical Foundations of Programming Language
Semantics, Springer LNCS 239, 1985, pp. 205-214. 
\bibitem{pri:1} Priestley, H.A. Lattices and Boolean Algebras, Mathematical 
Institute, Oxford,1988. 
\bibitem{smy:1} Smyth, M.B. The Largest Cartesian Closed Category of Domains, 
Theoretical Computer Science 27 (1983), 
pp. 109-119. 
\end{thebibliography}

\end{document}
