Algebras of the powerset monad
up vote
6
down vote
favorite
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.
category-theory monads
add a comment |
up vote
6
down vote
favorite
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.
category-theory monads
add a comment |
up vote
6
down vote
favorite
up vote
6
down vote
favorite
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.
category-theory monads
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.
category-theory monads
category-theory monads
asked Nov 22 at 9:32
Percy
748
748
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
8
down vote
accepted
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.
Thank you @Max . It is very clear now. Does this paragraph cater for the converse? "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."
– Percy
19 hours ago
Yes (though obviously saying "it's clear" is not a proof, but I'm saying that it's easy enough that you should be able to do this exercise)
– Max
18 hours ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
accepted
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.
Thank you @Max . It is very clear now. Does this paragraph cater for the converse? "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."
– Percy
19 hours ago
Yes (though obviously saying "it's clear" is not a proof, but I'm saying that it's easy enough that you should be able to do this exercise)
– Max
18 hours ago
add a comment |
up vote
8
down vote
accepted
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.
Thank you @Max . It is very clear now. Does this paragraph cater for the converse? "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."
– Percy
19 hours ago
Yes (though obviously saying "it's clear" is not a proof, but I'm saying that it's easy enough that you should be able to do this exercise)
– Max
18 hours ago
add a comment |
up vote
8
down vote
accepted
up vote
8
down vote
accepted
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.
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.
answered Nov 22 at 10:54
Max
12.2k11038
12.2k11038
Thank you @Max . It is very clear now. Does this paragraph cater for the converse? "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."
– Percy
19 hours ago
Yes (though obviously saying "it's clear" is not a proof, but I'm saying that it's easy enough that you should be able to do this exercise)
– Max
18 hours ago
add a comment |
Thank you @Max . It is very clear now. Does this paragraph cater for the converse? "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."
– Percy
19 hours ago
Yes (though obviously saying "it's clear" is not a proof, but I'm saying that it's easy enough that you should be able to do this exercise)
– Max
18 hours ago
Thank you @Max . It is very clear now. Does this paragraph cater for the converse? "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."
– Percy
19 hours ago
Thank you @Max . It is very clear now. Does this paragraph cater for the converse? "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."
– Percy
19 hours ago
Yes (though obviously saying "it's clear" is not a proof, but I'm saying that it's easy enough that you should be able to do this exercise)
– Max
18 hours ago
Yes (though obviously saying "it's clear" is not a proof, but I'm saying that it's easy enough that you should be able to do this exercise)
– Max
18 hours ago
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008911%2falgebras-of-the-powerset-monad%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown