Lambek and Scott, Example T2

The T-algebras of the Covariant Power Set Monad

The T-algebras here are phi:PA->A with phi({a})=a and phi(Union(X))=phi({phiX|X in X}).

Given any sup-complete lattice (A,<=,sup), we have sup:PA->A. It is easy to check that sup satisfies the properties above: sup({a}) = a, sup(Union(X)) = sup({sup(X)|X in X}). To check the second property, we first check that every x in X in X is smaller than the RHS since x<=sup(X). Next, we check that every sup(X) is smaller than the LHS since for every x in X, x is in Union(X), so x is smaller than the LHS.

Next note that the sup is enough to recover the ordering. In fact, there is more than one way to recover the ordering. We have x <= y iff sup({x,y})=y. We also have x <= y iff Union({X|sup(X)=x}) subset Union({Y|sup(Y)=y}) (i.e., x <= y iff {a|a<=x} subset of {a|a<=y}). This key observation allows us to define an ordering on A given a "sup" operation phi:PA->A.

Proof 1 uses the characterization x <= y iff sup({x,y})=y and is noticably simpler.

Proof 2 uses the characterization x <= y iff Union({X|sup(X)=x}) subset Union({Y|sup(Y)=y}) and requires more work. It has the advantage that a Galois correspondence makes an appearance.

Proof 1. Suppose we are given a phi:PA->A satisfying the properties above. Define an ordering on A by x <= y iff phi({x,y})=y. This is a partial ordering since it is reflexive (phi({x,x})=x), antisymmetric (x=phi({y,x})=phi({x,y})=y), and transitive. Transitivity is shown by assuming phi({x,y})=y and phi({y,z})=z and computing phi({x,z})=phi({phi{x},phi{y,z}})=phi({x,y,z})=phi({phi{x,y},phi{y,z}})=phi({y,z})=z, so x<=z.

Now, for any subset X of A, we can show phiX is the sup of X as follows. First, for every x in X, phi({x,phiX})=phi({phi{x},phiX})=phi({x} Union X)=phiX, so x<=phiX. Next, suppose we have a in A so that for every x in X, x<=a. This means phi({x,a})=a for every x in X. So, phi(X Union {a}) = phi(Union{{x,a}|x in X}) = phi({phi{x,a}|x in X}) = phi({a}) = a. End of proof 1!

Proof 2. Suppose we are given a phi:PA->A satisfying the properties. Let phi*:A->PA be defined by phi*(x) = Union({X|phiX=x}).

Claim 1: phi o phi* = 1_A.

Proof: phi(phi*(x)) = phi(Union({X|phiX=x})) = phi({phiX|phiX=x}) = phi({x}) = x.

Now, define the ordering on A by x<=y iff phi*(x) subset phi*(y). This is clearly reflexive and transitive. Antisymmetry follows from claim 1, since x<=y and y<=x implies phi*(x)=phi*(y) implies x = phi(phi*(x)) = phi(phi*(y)) = y.

Claim 2: X subset phi*(phi(X)) for every subset X of A.

Proof: Since X is a member of {Y|phiY=phiX}, we easily see X is a subset of Union({Y|phiY=phiX}).

Claim 3: phiX<=y iff X subset phi*(y). So, we have phi -| phi*, i.e., an adjunction (Galois correspondence)!

Proof: Suppose phiX<=y. By definition, phi*(phi(X)) subset phi*(y). By claim 2, X subset phi*(phi(X)) subset phi*(y), completing this direction. Suppose X is a subset of phi*(y). In order to show phi(X)<=y, we need to show, by definition, phi*(phi(X)) is a subset of phi*(y). Suppose a is in phi*(phi(X))=Union({Z|phiZ=phiX}). Then there is some Z with a in Z and phiZ=phiX. Now, a is in (Z Union phi*(y)), and we have phi(Z Union phi*(y)) = phi({phiZ,phi(phi*(y))}) = phi({phiX,phi(phi*(y))}) = phi(X Union phi*(y)) = phi(phi*(y)) = y. So, a is in phi*(y).

By the way, if you noticed phi(phi*(y))=y in that last chain of equalities, then good for you! But if I had simplified the expression, my proof would not have worked. (So, perhaps rewriting is not always a good idea? You already knew that, right?)

Also, notice that since we have a Galois correspondence, phi* o phi:PA->PA is a closure operation.

The Big Result. For any subset X of A, phi(X) is the sup of X.

Proof: Suppose x is in X. Then, we have {x} subset X subset phi*(phi(X)), and by the Claim 3, phi({x})<=phi(X), i.e., x<=phi(X). Now, suppose we have a in A with x<=a for all x in X. That is, phi*(x) is a subset of phi*(a) for all x in X. Since phi({x})=x, we easily see that x is in phi*(x) (for any x), so X is a subset of phi*(a). Use the Galois correspondence to conclude phi(X)<=a. And that finishes off the proof!

Now, what about the T-algebra homomorphisms? These are maps a:A->A' such that phi'({a(x)|x in X}) = a(phi(X)). That is, a must preserve sups. But this, of course, forces it to preserve order as well (since order is definable from the sup function). End of proof 2!

PS: Okay, you may be bothered by the fact that I'm saying these are lattices, but the fact is that sup-completeness gives a way of defining top (as the sup of everything), bottom (as the sup of the empty set), and even arbitrary infs (with inf(X) = sup({y|forall x in X . y<=x})). So, sup-completeness implies we have a sup-complete and inf-complete lattice.