A small example of algebra turns out to be a semi-lattice

In this article, we will introduce a concrete example (found in CWM) of interchanging distinct structures of algebra and order on a fixed set, where a set of monoid action infers a special type of order called lattice in a guise of T-algebra.

Proposition. A partially ordered set Q is called complete semi-lattice when every subset S\subset Q has supremum in Q.

Let \mathcal{P} be a covariant power set functor on Set. For a set X, \eta_X:X\to \mathcal{P}X maps x\in X to the set \{x\} and \mu_X:\mathcal{P}\mathcal{P}X\to \mathcal{P}X maps each family of sets to the union set.

a. \langle \mathcal{P},\eta,\mu \rangle is a monad on Set;
b. It holds that each \mathcal{P}-algebra \langle X,h\rangle is a complete semi-lattice if the order is defined by x\leq y \iff h\{x,y\} = y and for each set S, \sup S=hS;
c. Conversely, every small complete semi-lattice is \mathcal{P}-algebra;

Proof of a. For the unit \eta, we see that it commutes the diagram:

Rendered by QuickLaTeX.com

while for the product \mu, we see that it commutes the following diagram:

Rendered by QuickLaTeX.com

Note that every composition of the maps used in the left diagrams are horizontal compositions, where the functor P:{\bf Set}\to {\bf Set} is regarded as natural identity P:P\xrightarrow{\cdot} P. On the right side of the diagram, we depicted an instance of element mapping considering U_i\in PX as an element of powerset and as such.

Proof of b. First we show that X is partially ordered.

The antisymmetry trivially holds. The reflexivity is by definition of \mathcal{P}-algebra id_X=h\circ \eta_X. The transitivity is also followed by definition. Assume x\leq y and y\leq z, then it is shown that x\leq z as in the following commutative diagram:

Rendered by QuickLaTeX.com

which concludes that X is partially ordered.

To see X is a complete semi-lattice, we prove h indeed defines \sup for each subset S\subset X. For any z\in S, we have h\{z,hS\}=(h\circ \mu_X) \{\{z\},S\} = h(\{z\}\cup S)=hS and if there exists z\in X such that h\{z,hS\}=z, then hS\leq z by definition; therefore hS=\sup S.

Proof of c. Let X be a complete semi-lattice. Then \sup commutes the diagram:

Rendered by QuickLaTeX.com

while \sup(U_1\cup U_2)=\sup\{\sup U_1, \sup U_2 \} holds. Hence X is a \mathcal{P}-algebra with the structure map \sup.