There are two kinds of directed sets:

1. Boring sets contain their lub.
   
   Example: Finite directed sets are boring (but boring sets aren't all finite!).
2. Interesting sets don't contain their lub.
   
   Example: \mathbb {N} in the chain \mathbb {N} \cup \{ \infty \} is interesting.

Let A be a cpo. Then x \in A is compact (a.k.a. finite) iff for all directed X \subseteq A: x \sqsubseteq \bigsqcup X \implies \exists y \in X.\ x \sqsubseteq y In English: A compact element will approximate some element of a directed set if it approximates the lub. We write \mathsf {K}(A) for the set of compact elements of A, i.e.: \mathsf {K}(A) = \{x \in A \mid x\ \text {is compact} \}

• Every element in a finite cpo is compact. More generally, every element of a cpo of finite height (e.g. \mathbb {Z}_\bot ) is compact. This is because finite directed sets are always boring.
• Take the cpo \mathcal {P}(X) of subsets of X ordered by inclusion \subseteq , as seen in Exercise [dt-001G]. The compact elements of \mathcal {P}(X) are those of finite cardinality.
• Take the cpo \mathbb {N} \nrightarrow \mathbb {N} of partial functions on the natural numbers, ordered by inclusion of graphs. The compact elements of \mathbb {N} \nrightarrow \mathbb {N} are the functions which are defined only for finite domains.

Compact elements may still have an infinite number of approximations. Consider the cpo \mathbb {N} \cup \{ \infty , \infty + 1 \}, where we have tacked on an additional top element \infty + 1 to our normal cpo of natural numbers extended with infinity. Then, while \infty is not compact, \infty + 1 is compact — it is not the lub of an interesting directed set. If \infty + 1 is the lub of a set X then \infty + 1 must be in the set X. Nonetheless, there are an infinite number of approximations to \infty + 1, i.e., elements x such that x \sqsubseteq \infty + 1.

As an aside, requiring that our compact elements have a truly finite number of approximations is the basis for the theory of Berry domains and stable functions.

The submonoids of a monoid (X, \iota , \bullet ) form a cpo under \subseteq , where union gives the lub.

Find a set in the cpo of submonoids of (\mathbb {N},0,+) that is both infinite and compact.

A cpo is algebraic iff every element is the lub of its compact approximations. That is, a cpo D is algebraic iff for all x \in D,

1. \mathop {\downarrow }(x) = \{ y \in \mathsf {K}(D) \mid y \sqsubseteq x \} is directed;
2. x = \bigsqcup \mathop {\downarrow }(x)

Aside: Plotkin provides an equivalent definition of \omega -algebraic cpos in which directed sets are replaced with \omega -chains throughout. Hutton claims this is less appealing, as the definition speaks of an \omega -chain of compact approximations, rather than the directed set of such.

Many standard examples of cpos are \omega -algebraic cpos: finite cpos, subsets \mathcal {P}(X) of a set X, partial functions \mathbb {N} \nrightarrow \mathbb {N} and submonoids of a monoid. In general, any cpo of subalgebras (e.g. subgroups of a group, subrings of a ring etc.) is \omega -algebraic. This is the origin of the terminology.

In the cpo on the right (seen also in § [dt-0040]), the element x is not the lub of its compact approximations. The only compact element that approximates x is \bot , and the least upper bound of the set \{\bot \} is just \bot , not x. That is: \mathop {\downarrow }(x) = \{\bot \} but: x \neq \bigsqcup \{\bot \}

Let D and E be algebraic cpos. Then a function f : D \rightarrow E is continuous iff, for all x \in D: f(x) = \bigsqcup \ \{ f(a) \mid a \in \mathop {\downarrow }(x) \} In other words, in an algebraic cpo, continuous functions are completely defined by their behaviour for compact arguments.

This makes precise our earlier slogan in Definition [dt-001J], that continuous functions don't suddenly behave differently for infinite (i.e. non-compact) elements.

Let f : D \twoheadrightarrow E be a continuous function between algebraic cpos. Define: G_f = \{ (a,b) \in \mathsf {K}(D) \times \mathsf {K}(E) \mid b \sqsubseteq f(a) \} Then for all x \in D, prove that: f(x) = \bigsqcup \ \{ b \mid (a,b) \in G_f \land a \sqsubseteq x \}

This is powerful. For example, the continuous function f : \mathcal {P}(\mathbb {N}) \twoheadrightarrow \mathcal {P}(\mathbb {N}) on an uncountable cpo \mathcal {P}(\mathbb {N}) is completely determined by the countable relation G_f.

Given a poset Y, a set X \subseteq Y is down-closed iff, for all x \in X, any y \sqsubseteq x is in X.

A set is ideal iff it is both down-closed and directed.

The ideal completion of a set A, written sometimes as \mathsf {Id}(A), is the set of all ideal subsets of A, i.e.: \mathsf {Id}(A) = \{ X \subseteq A \mid X\ \text {is ideal}\}

Every algebraic cpo D is isomorphic to the ideal completion of its compact elements, ordered by subset inclusion. That is, \mathsf {Id}(K(D)) is an algebraic cpo such that D \simeq \mathsf {Id}(K(D)) .

A set of compact elements X \subseteq \mathsf {K}(A) is a basis for a cpo A iff for all x\in A, x= \bigsqcup \{a \in X \mid a \sqsubseteq x\}.

If X is a basis for A, then A is algebraic and \mathsf {K}(A) = X.

If D and E are algebraic cpos, then so is their product construction D \times E.

The lack of closure of algebraicity under the (continuous) function arrow, strict or non-strict, is not satisfying as it means that our semantic domains are not guaranteed to be algebraic even if they are composed from algebraic cpos. Instead, we must replace algebraic cpos with something stronger still.

Scott's original solution to this lack of closure was to use a complete lattice instead of cpos, i.e. requiring lubs for all subsets, not just directed ones. This solves the problem with \twoheadrightarrow but introduces new problems:

1. Complete lattices need a top element \top , but adding a fictitious top (representing inconsistent information) to cpos like \mathbb {B}_\bot is strange.
2. Extending the functions that capture our primitive semantic operations to complete lattices can spoil nice algebraic properties. Consider these two possible implementations of \mathsf {ite}, the function for the semantics of an \mathsf {if} expression: \mathsf {ite}(\top ,x,y) = x \sqcup y\quad \quad \quad \quad \quad \mathsf {ite}(\top ,x,y) = \top Either of these solutions results in the failure of useful and expected laws for \mathsf {if} expressions. For example, the left definition above results in the failure of the common equation to eliminate unreachable cases: \mathsf {ite}(b, \mathsf {ite}(b,x,y),z) = \mathsf {ite}(b,x,z) And the second definition above results in the failure of this equation that removes redundant checks: \mathsf {ite}(b,x,x) = x
3. The powerdomain construction does not generalise to complete lattices, so semantics for non-deterministic programs are difficult in this setting.

A poset A is consistent complete (or bounded complete) iff \bigsqcup X exists for all consistent X \subseteq A. That is, any set with an upper bound (a consistent set) has a least upper bound.

A cpo D is a Scott domain iff:

1. D is \omega -algebraic,
2. D is consistent complete,

The second requirement in Definition [dt-004G] can, in light of the first, be expressed equivalently as: x \sqcup y exists for all consistent x,y \in D. This is useful when needing to show that a given cpo is a Scott domain.

Scott domains are closed under all our cpo constructions, including sums +, products \times , continuous functions \twoheadrightarrow , smash sums \oplus , smash products \otimes and strict functions \mathbin {\circ \hspace{-0.4em}\twoheadrightarrow }.