Theorem. Submonoids 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.

Context

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.

Definition. Boring 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.

Definition. Compactness [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.

Example. Compact 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.

Example. Compact 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.

Theorem. Submonoids 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.

Exercise. Both 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.

Backlinks

Exercise. Both 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.

Example. $\omega$ -algebraic cpos [dt-0042]

Liam O'Connor

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.

Related

Definition. Complete partial order [dt-001D]

Liam O'Connor

A complete partial order or cpo (more specifically a directed complete partial order or dcpo) is a poset where lubs exist for the empty set and for all directed subsets. That is, a cpo is a poset $A$ such that:

$A$ has a bottom element $\bot \in A$ , that is the lub of the empty set, and
$\bigsqcup X$ exists for all directed $X \subseteq A$ .

Definition. Least upper bound [dt-0017]

Liam O'Connor

Let $X \subseteq Y$ be a subset of a poset $Y$ . An element $y \in Y$ is a least upper bound (or lub) for $X$ iff:

It is an upper bound: $\forall x \in X.\ x \sqsubseteq y$
It is less than any other upper bound: $\forall y' \in Y.\ (\forall x \in X. x \sqsubseteq y') \Rightarrow y \sqsubseteq y'$

It follows that lubs are unique if they exist. We write the lub of a set

X

as

\bigsqcup X

, and usually write

x \sqcup y

as a shorthand for

\bigsqcup \{x,y\}

.

Definition. Monoid [dm-000O]

Liam O'Connor

A monoid $(S, \iota , \bullet )$ consists of a set $S$ , an identity element $\iota \in S$ , and a binary operator $(\bullet ) : S \times S \rightarrow S$ which satisfies, for all $x,y,z \in S$ :

associativity: $x \bullet (y \bullet z) = (x \bullet y) \bullet z$
left identity: $\iota \bullet x = x$
right identity: $x \bullet \iota = x$

Definition. Submonoid [dm-000R]

Liam O'Connor

A submonoid of a monoid $(X, \iota , \bullet )$ is a subset $Y \subseteq X$ such that $Y$ is closed under $\bullet$ and $\iota \in Y$