Compactness and Finiteness [dt-0040]

Liam O'Connor

We begin by formalising the notion of an element in a cpo representing a finite amount of information.

DefinitionBoring and interesting sets [dt-003W]

Liam O'Connor

There are two kinds of directed sets:

Boring sets contain their lub.

Example: Finite directed sets are boring (but boring sets aren't all finite!).
Interesting sets don't contain their lub.

Example: $\mathbb {N}$ in the chain $\mathbb {N} \cup \{ \infty \}$ is interesting.

Following the above intuition, we might be tempted to say that the "infinite" elements of a cpo are those which are the lub of an interesting set, but this notion is too weak. Consider this cpo $X$ :

By the above definition, the only infinite element would be

\infty

, but if we consider the following isomorphic cpo, ordered by subset inclusion:

Then the set

x

cannot be a finite set, as any finite set would be a subset of one of the finite sets in the chain

\emptyset \sqsubseteq \Set { 0 } \sqsubseteq \Set {0,1} \sqsubseteq \cdots

. Thus, it makes more sense for us to call

x

an "infinite" element as well.

DefinitionCompactness [dt-003U]

Liam O'Connor

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} \}$

In the example cpo $X$ above, all the elements except $\infty$ and $x$ would be compact. Thus, compactness better captures our notion of an element representing a finite amount of information. This understanding of compact elements is a generalisation of the notion of a finite element from the theory of algebraic lattices.

ExampleCompact elements [dt-003V]

Liam O'Connor

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.

ExampleCompact elements with infinitely many approximations [dt-003X]

Liam O'Connor

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.

TheoremSubmonoids as a cpo [dt-003Y]

Liam O'Connor

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

ExerciseBoth infinite and compact [dt-003Z]

Liam O'Connor

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

Solution.

Liam O'Connor

Take $E \triangleq \{ n \in \mathbb {N} \mid n\ \text {is even}\}$ . Let $Y \subseteq \mathcal {P}(\mathbb {N})$ be directed and $E \subseteq \bigcup Y$ . Since $2 \in E$ there must exist $y \in Y$ such that $2 \in Y$ . Since $(y,0,+)$ is a monoid, every positive multiple of $2$ is also in $y$ , thus $E \subseteq y$ and therefore $E$ is compact.

Seeing as compact elements are also sometimes called finite, this is surprising as $E$ is an infinite set. The reason it is nonetheless compact is that $E$ is finitely generated — it is the smallest submonoid of $(\mathbb {N},0,+)$ such that the finite set $\{ 2 \} \subseteq E$ . In fact, the compact submonoids of $(\mathbb {N},0,+)$ are precisely the finitely generated ones.