\documentstyle[10pt]{article}  % -*- Mode:TeX -*-
\input /jj/ariola/macros/prelude.tex


%                    HERE BEGINS THE DOCUMENT


\begin{document}

\begin{definition}
A relation $\sqsubseteq$ is a partial ordering upon $D$ iff $\sqsubseteq$ is:
\begin{enumerate}
\item
reflexive: $\forall x \in D$, $x \sqsubseteq x$.
\item
antisymmetric: $\forall x, y \in D$, $x \sqsubseteq y$ and $y \sqsubseteq x$
$\Longrightarrow x = y$.
\item
transitive: $\forall x, y, z \in D$, $x \sqsubseteq y$ and $y \sqsubseteq z$
$\Longrightarrow x \sqsubseteq z$.
\end{enumerate}
\end{definition}

\begin{definition}
Let the set $S$ be a subset of the partial order $X$ then
\[ S \sqsubseteq y, \;\; \mbox{if} \forall\; x \in S\;\; [x \sqsubseteq y]
\]
\end{definition}

\begin{definition}[Least Upper Bound]
Let the set $X$ be partially ordered by R,
$x$ is the least upper bound of a subset $S$ of $X$ (denoted as $\bigsqcup S$)
iff:
\begin{enumerate}
\item
$S \sqsubseteq x$.
\item
$\forall y \in X$, $S \sqsubseteq y \Longrightarrow x \sqsubseteq y$
\end{enumerate}
\end{definition}



\begin{definition}[Directed set]
Let the set $X$ be partially ordered by $\sqsubseteq$. A nonempty set $S$ is
directed iff:
\[ \forall x_1, x_2 \in S, \mbox{  }\exists x_3 \mbox{ } \in S \mbox{ such that }
x_1 \sqsubseteq x_3 \mbox{ and } x_2 \sqsubseteq x_3.
\]
\end{definition}

To give an analogy, directed sets are like
the Cauchy sequences in analysis.\\


\noindent
{\bf Example 1:} Given a set $X$, define $S$ to be the set of all finite subsets of X:
\[ S = \{ F \subseteq X: \mbox{  }\mid F\mid < \omega \}
\]
$S$ is partially ordered by subset inclusion and is directed: 
\begin{center}
$\forall F_1, F_2 \in S,\mbox{ } F_1 \cup F_2 \in S$  is an upper bound.
\end{center}

\begin{definition}[Chain]
For a partially ordered set $X$, a subset $S$ of $X$ is a chain iff $S$ is nonempty,
and $\forall x_1, \mbox{ }x_2 \in S, \mbox{ }x_1 \sqsubseteq x_2 \mbox{ } or \mbox{ }x_2 \sqsubseteq x_1$.
\end{definition}
Directed sets are more general than chains.
In Example 2, if X is uncountable then no chain of elements
in $S$ has the same lub as S.

\begin{definition}[CPO]
A partially ordered set $(X, R)$ is a complete partial order (cpo) iff:
\begin{enumerate}
\item
$\exists \bot \in X$ s.t. $\bot \sqsubseteq X$.
\item
$\forall$ directed $S \subseteq X$, \mbox{ }$\bigsqcup S \in X$ exists.
\end{enumerate}
\end{definition}

Despite the technical distinction between chains and directed sets the
difference won't bother us. For example, $cpo_{chain}  = cpo_{dir}$, since if
every chain has a lub then every directed set has a lub.\\

\noindent
{\bf Example 1:} $(P(X), \subseteq)$ is a cpo:
\begin{enumerate}
\item
there exists the least element $\bot = \emptyset$;
\item
$\forall$ directed $S \subseteq P(X)$, \mbox{  }$\bigsqcup S = \bigcup S \in P(X)$.
\end{enumerate}

\begin{definition}[Lattice]
A lattice is a partially ordered set D=(D,$\sqsubseteq$) such
that for all $a,d \in D$, both $a \sqcup b$ and $a \sqcap b$ exist.  
\end{definition}

\begin{definition}[Complete Lattice]
A complete lattice is a partially ordered set D=(D,$\sqsubseteq$) such
that for all $X \subseteq D$ $\bigsqcup X \in D$ exists.
\end{definition}

Any finite lattice is a complete lattice.
Not all lattices are complete; consider the set $F=\{x \; \mid \;
x \mbox{ is a finite subset of N}\}$ partially ordered by
set inclusion. $F$ is clearly a lattice, as joins and meets
of finite sets yield finite sets, but $F$ is not complte,
for the lub of the set $S=\{\{zero\},\{zero,one\},\{zero,one,two\}, \cdots \}$
is exactly N, which is not in $F$.

Notice that if D is a complete lattice, then
\begin{tightlist}
\item[(i)]
D has a largest element, $\top = \bigsqcup D$;
\item[(ii)]
D has a least element, $\top = \bigsqcup \emptyset$;
\item[(iii)]
every $X \subseteq D$ has a g.l.u, $\sqcap X = \bigsqcup \{y \mid
\; \forall \; x \in X, \; y \sqsubseteq x \}$.
\end{tightlist}

\begin{definition}[Upper Semilattice]
A partially ordered set (M, $\sqsubseteq$) is an upper
semilattice if for any two elements $a,b \in M$ a least upper bound,
$\bigsqcup \{a,b\} \in M$, exists. It is complete if each
subset of M has a least upper bound in M.
\end{definition}

\begin{definition}[Lower Semilattice]
A partially ordered set (M, $\sqsubseteq$) is a lower
semilattice if for any two elements $a,b \in M$ a greatest lower bound,
$\sqcap \{a,b\} \in M$, exists. It is complete if each
subset of M has a greatest lower bound in M.
\end{definition}

\begin{definition}[Lattice]
M is a lattice if it is a upper and a lower semilattice.
\end{definition}

\begin{definition}[Complete Lattice]
M is a complete lattice if it is a complete upper and a complete
lower semilattice.
\end{definition}

\begin{lemma}
If M is a complete lower semilattice which has a greatest element
then M is a complete lattice.
\end{lemma}

\begin{definition}[Ideal]
Let $\langle A, \leq_A \rangle$ be a partial order. An ideal in A,
I, is a nonempty subset of A which satisfies
\begin{tightlist}
\item[(i)]
$x,y \in I \; \Longrightarrow \; \exists z \in I,\; x \leq z \; \wedge \;
y \leq z$;  \ie I is {\em directed};
\item[(ii)]
$x \in I, y \leq x \; \Longrightarrow \; y \in I$; \ie I is {\em downward
closed}.
\end{tightlist}
\end{definition}

\begin{definition}[Compact]
Let A be a cpo. An element $a \in A$ is compact or finite if
\[ a \leq \sqcup D, \mbox{ with D a directed subset of A} 
\; \Longrightarrow \;
\exists d \in D, \; a \leq d \]
\end{definition}

\noindent
Let's consider the following example:
{\small
$$\begin{diagram}
& & \infty \\
& \NE  & \vdots\\
&  & \vLine\\
%&  & 2 \\
%\ast & & \vLine \\
\ast & & 1 \\
& \NW & \vLine  \\
%&  \vLine \\
& & \bot 
\end{diagram}$$
}

\noindent
Notice the the element $\ast$ is not compact because
$\ast \leq \sqcup N$ but $ \not\exists \; n \in N,\;\ast \leq n$.
Following the next definition the above structure will not be an algebraic cpo.
%Therefore, $\{ x \mid x \leq \ast \mbox{ and $x$ compact} \} = \{\bot\}$
%and obviuosly $\ast\neq \sqcup \{ \bot \}$.

\begin{definition}[Algebraic cpo]
A is an algebraic cpo if for every $a \in A$
\[ a = \sqcup \; \{d \mid d \leq a, d \mbox{ compact} \} \]
\end{definition}

\noindent
In other words, in an algebraic
cpo, each element is a directed limit of its ``finite'' (compact)
approximations.
%If D is algebraic and
%the set of compact elements of D
%is countable, then
%we will say that $D$ is a {\it domain}.
An an example,
the collection ${\cal P}(N)$ of subsets of $N$, ordered by subset inclusion
is an algebraic cpo whose compact elements are
just the finite subsets of $N$.

\noindent
Let ${\cal I}(A)$ be the set of all the ideals defined over A,
then
\begin{lemma}
If A has a least element then
$\langle {\cal I}(A),\subseteq \rangle$
is an algebraic cpo.
\end{lemma}
\begin{proof}
See \cite{Hennessy}.
\end{proof}

\begin{theorem}
$\langle {\cal I}(A),\subseteq \rangle$
is the unique cpo
(upto isomorphism) whose set of finite elements
are isomorphic to $\langle A, \leq_A \rangle$ as partial order.
\end{theorem}
\begin{proof}
See \cite{Hennessy}.
\end{proof}
\end{document}
