Qfyilyi

Many authors treat algrebras of the powerset monad as a trivial example. It is really not trivial to me.

Can anyone help me with a detailed construction of such algebras. If you know of any article or book that explicitly construct such algebras which will be easy for a beginner to follow, please help out. Or if you can construct it as an answer here, I would really appreciate it.

Thank you.

Algebras for the powerset monad are essentially sup lattices, that is complete ordered sets $S$ with a given operation $bigvee$ which takes a subset of $S$ to its least upper bound, and algebra maps are (weakly) monotone maps between them that preserve said operation.

Let's call our monad $(T,mu,eta)$.

An algebra for $T$ is a set $S$ with a map $h: TSto S$ : this will be interpreted as the lub map $bigvee$.

Define $leq_h$ on $S$ as follows : for $x,yin S$, $h({x,y})in S$. Define $xleq_h y$ if and only if $h({x,y}) = y$. This is a well-defined relation, let's now prove that it's a partial order.

It's clearly antisymmetric. To show that its reflexive, note that since $h:TSto S$ defines a $T$-algebra, we have $Sto^{eta_S} TSto^h S = Sto^{id_S} S$, and so $h({x,x}) = h({x}) = hcirceta_S(x) = x$, thus $xleq_h x$.

We now have to prove that it's transitive : assume $xleq_h y, yleq_h z$. Note that ${x,y,z} = {x,y}cup{y,z}= mu ({{x,y}, {y,z}})$. Since $h$ makes $S$ into a $T$-algebra, we have that $hcirc mu_S = hcirc T(h)$. Thus $h({x,y,z}) = h({h({x,y}), h({y,z})})= h({y,z}) = z$.

But also ${x,y,z}= {x}cup {y,z} = mu({{x}, {y,z}})$ and so we get $h({x,y,z}) = h({h({x}), h({y,z})}) = h({x,z})$. Thus $h({x,z}) = z$ and so $xleq_h z$.

Therefore $leq_h$ defines an order on $S$. Let $Asubset S$ : we now want to prove that $h(A)$ is the least upper bound of $A$ for $leq_h$.

Once we prove this, it will be clear that the desired result is true : indeed the definition of $leq_h$ proves that a $T$-algebra map preserves the order, and the least upper bounds, and it will be clear that a map that preserves least upper bounds will be a $T$-algebra map.

Let $xin A$. Then $A=Acup{x}$ thus $h(A) = hcirc mu_S ({A,{x}}) = hcirc T(h) ({A, {x}}) = h({h(A), h({x})}) = h({h(A), x})$, therefore $xleq_h h(A)$ : $h(A)$ is an upper bound of $A$.

Let $y$ be an upper bound of $A$. Then $h({y, h(A)}) = h({h({y}), h(A)}) = h({y}cup A)$. So it suffices to prove that if $z$ is the maximum of $B$, then $h(B) = z$.

But $B = displaystylebigcup_{xin B}{x,z} = mu_S({{x,z}mid xin B})$, thus $h(B) = hcirc mu_S({{x,z}mid xin B})= hcirc T(h) ({{x,z}mid xin B})= h({h({x,z})mid xin B}) = h({zmid xin B})$ because $h({x,z}) = z$ for $xin B$ by assumption, and thus $h(B) = h({z}) = z$ : for $B=Acup{y}, z=y$, this gets us $h(A)leq_h y$ : $h(A)$ is the least upper bound of $A$, and we are done.

Of course my choice of sup lattices instead of inf lattices is arbitrary, but of course this comes from the fact that the category of sup lattices is isomorphic to the category of inf lattices, so there's no problem here.