Patrik Eklund recently asked about a "double covariant power set monad". Such a monad exists. I called it the families monad in Monads of sets, Handbook of Algebra, vol. 3...it is introduced in Example 2.12 and verified on pages 78-79. In a paper under preparation on distributive laws, joint with Philip Mulry, we show that the families monad arises by a distributive law of the power set monad P over itself. To describe that law, first establish some notation as follows. For AA in PPX a family of subsets of X, let C(AA) be the cartesian product of AA, that is, the set of all choice families x = (x_A : A in AA) with x_A in A. Let I(x) be the image of x, i.e. {x_A : A in AA}. The distributive law in question, PPA -> PPA, maps AA to {I(x) : x \in C(AA)}. Based on the general theory in Beck's original paper on distributive laws, P is a submonad of PP in two ways, A |--> {A} and A |--> { {x} : x in A}. But P is also a quotient monad. As Beck has taught us, the PP-algebras are (X,a,b) with (X,a), (X,b) P-algebras married by a commutative diagram, call it (D), involving the distributive law. Think of a, b as the supremum operation of a complete semilattice structure. Then (X,a,a) satisfies (D) so that P-algebras are a variety of PP-algebras as claimed. A more interesting example is the variety of PP-algebras of form (X,a,a^op). Here (D) is known as the "complete distributive law" in the lattice literature. Thus free such algebras exist and the free algebra generated by a cardinal k has cardinality at most 2^(2^k). 16-Feb-2005 10:53:49 -0400,3817;000000000000-00000000
Ernie Manes wrote:
In a paper under preparation on distributive laws, joint with Philip Mulry, we show that the families monad arises by a distributive law of the power set monad P over itself.
Though this self-distributivity of P is formally elegant, it seems (unless I've missed something) to need the axiom of choice and I wondered what its constructive content was. I encountered a similar problem in [1], albeit with the Kuratowski powerset F instead of P. For constructivist reasons I had to use not Ernie's C(AA) of choice *functions*, but a set Ch(AA) of finite total choice *relations* - in other words, you are allowed to choose more than one element from each set. But then AA |-> {I(x) | x in Ch(AA)} does not give a distributivity (though I never thought of looking at this at the time). If you generalize from sets to preorders the problem seems to go away, at least for F, and my sense is that the danger arises when you ignore the natural order on FX when calculating FFX. However, the two copies of F become two different monads F_L and F_U, corresponding to two preorders (lower and upper) on FX when X is preordered. I haven't ploughed through all the details, but I am reasonably confident that the two monads distribute over each other using the "Ch(AA)" construction, and commute. (The category of preorders has to be one in which the morphisms are equivalence classes of monotone functions.) In any case, it is known that if you work with partial orders and factor out equivalence modulo the preorders, then you find that F_L and F_U give free join and meet semilattices, and their composite (either way round) is the free distributive lattice. Related phenomena appear in the category of locales [2] - the lower and upper powerlocale monads P_L and P_U distribute mutually and commute. Intriguingly [2], the composite double powerlocale monad PP can be expressed as an iteration of a contravariant functor PX = $^X (where $ = Sierpinski), and [3] this makes sense even in the non-locally compact case where the exponential $^X doesn't exist. Steve Vickers. Papers available from www.cs.bham.ac.uk/~sjv : [1]: @ARTICLE{EntSys, AUTHOR={Vickers, Steven}, TITLE={Entailment Systems for Stably Locally Compact Locales}, JOURNAL={Theoretical Computer Science}, ISSN={0304-3975}, VOLUME={316}, PAGES={259--296}, YEAR={2004} } [2]: @ARTICLE{PPExp, AUTHOR={Vickers, S.J.}, TITLE={The Double Powerlocale and Exponentiation: A Case Study in Geometric Reasoning}, JOURNAL={Theory and Applications of Categories}, VOLUME={12}, YEAR={2004}, PAGES={372--422} } [3]: @ARTICLE{UniCharPP, AUTHOR={Vickers, S.J. and Townsend, C.F.}, TITLE={A Universal Characterization of the Double Powerlocale}, JOURNAL={Theoretical Computer Science}, ISSN={0304-3975}, VOLUME={316}, YEAR={2004}, PAGES={297--321} } 16-Feb-2005 10:53:49 -0400,1500;000000000000-00000000
I don't think anything goes wrong if AC fails as far as establishing a distributive law is concerned. No doubt much further discussion would be needed to understand well what happens, precisely, but note that many AA (e.g. principal filters) have non-empty C(AA). In any case, a sub-example obtains replacing P with the finite subsets monad, in which case no AC is needed. Ernie ----- Original Message ----- From: "Steve Vickers" <s.j.vickers@cs.bham.ac.uk> To: <categories@mta.ca> Sent: Wednesday, February 16, 2005 5:23 AM Subject: categories: Re: double covariant power set
Ernie Manes wrote:
In a paper under preparation on distributive laws, joint with Philip Mulry, we show that the families monad arises by a distributive law of the power set monad P over itself.
Though this self-distributivity of P is formally elegant, it seems (unless I've missed something) to need the axiom of choice and I wondered what its constructive content was.
I encountered a similar problem in [1], albeit with the Kuratowski powerset F instead of P. For constructivist reasons I had to use not Ernie's C(AA) of choice *functions*, but a set Ch(AA) of finite total choice *relations* - in other words, you are allowed to choose more than one element from each set. But then
AA |-> {I(x) | x in Ch(AA)}
does not give a distributivity (though I never thought of looking at this at the time).
If you generalize from sets to preorders the problem seems to go away, at least for F, and my sense is that the danger arises when you ignore the natural order on FX when calculating FFX. However, the two copies of F become two different monads F_L and F_U, corresponding to two preorders (lower and upper) on FX when X is preordered. I haven't ploughed through all the details, but I am reasonably confident that the two monads distribute over each other using the "Ch(AA)" construction, and commute. (The category of preorders has to be one in which the morphisms are equivalence classes of monotone functions.) In any case, it is known that if you work with partial orders and factor out equivalence modulo the preorders, then you find that F_L and F_U give free join and meet semilattices, and their composite (either way round) is the free distributive lattice.
Related phenomena appear in the category of locales [2] - the lower and upper powerlocale monads P_L and P_U distribute mutually and commute. Intriguingly [2], the composite double powerlocale monad PP can be expressed as an iteration of a contravariant functor PX = $^X (where $ = Sierpinski), and [3] this makes sense even in the non-locally compact case where the exponential $^X doesn't exist.
Steve Vickers.
Papers available from www.cs.bham.ac.uk/~sjv :
[1]: @ARTICLE{EntSys, AUTHOR={Vickers, Steven}, TITLE={Entailment Systems for Stably Locally Compact Locales}, JOURNAL={Theoretical Computer Science}, ISSN={0304-3975}, VOLUME={316}, PAGES={259--296}, YEAR={2004} }
[2]: @ARTICLE{PPExp, AUTHOR={Vickers, S.J.}, TITLE={The Double Powerlocale and Exponentiation: A Case Study in Geometric Reasoning}, JOURNAL={Theory and Applications of Categories}, VOLUME={12}, YEAR={2004}, PAGES={372--422} }
[3]: @ARTICLE{UniCharPP, AUTHOR={Vickers, S.J. and Townsend, C.F.}, TITLE={A Universal Characterization of the Double Powerlocale}, JOURNAL={Theoretical Computer Science}, ISSN={0304-3975}, VOLUME={316}, YEAR={2004}, PAGES={297--321} }
17-Feb-2005 15:44:27 -0400,5941;000000000000-00000000
Ernie Manes wrote:
I don't think anything goes wrong if AC fails as far as establishing a distributive law is concerned. No doubt much further discussion would be needed to understand well what happens, precisely, but note that many AA (e.g. principal filters) have non-empty C(AA). In any case, a sub-example obtains replacing P with the finite subsets monad, in which case no AC is needed.
Ernie
Dear Ernie, Here is why I think the distributive law goes wrong if AC fails. The original definition was this:
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
In a paper under preparation on distributive laws, joint with Philip Mulry, we show that the families monad arises by a distributive law of the power set monad P over itself. To describe that law, first establish some notation as follows. For AA in PPX a family of subsets of X, let C(AA) be the cartesian product of AA, that is, the set of all choice families x = (x_A : A in AA) with x_A in A. Let I(x) be the image of x, i.e. {x_A : A in AA}. The distributive law in question, PPA -> PPA, maps AA to {I(x) : x \in C(AA)}. <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< One of the conditions of a distributivity is that the following diagram commutes: PPPX ---- P mu X ------> PPX | | sigma PX | | | v | PPPX sigma | | P sigma X | | | v v PPPX ---- mu P X ------> PPX where mu is the multiplication and sigma is the distributivity. (Hope the format was clear. Down the left we have three copies of PPPX, with vertical morphisms involving sigma and P. Down the left are two copies of PPX, with vertical morphism sigma. Across are two horizontal morphisms involving mu and P.) Start from AAA at top left. Going across and down gives {I(x) | x in C{U(AA)) | AA in AAA}} (1) where U is union (i.e. mu). Going down and across gives {I(z) | (exists y in C(AAA)) z in C(I(y))} (2) Suppose we have such an x in C{U(AA)) | AA in AAA}. We want to find corresponding y and z to demonstrate that I(x) is in (2). Now for each AA in AAA, x chooses an element x_U(AA) in U(AA) and so there is some A in AA with x_U(AA) in A. We'd like our y in C(AAA) to have y_AA as such an A, but unfortunately A is not uniquely defined and so we need the axiom of choice to find such a y. Similar uses of choice appear in other places, so that is why it appears to me that the distributive law depends on AC. If we replace P by a finite powerset F, then we have a separate question: How do we know, if AA is in FFX, that sigma(AA) is finite? This depends on the constructive notion of finiteness. In my work I was using Kuratowski finiteness (for which the finite powerset monad is the free semilattice monad), and for that we find that C(AA) is not finite in general - which is why I replaced it with Ch(AA), using total choice relations instead of choice functions. But that definition of sigma does not give a distributivity even classically. All the best, Steve. 17-Feb-2005 15:44:28 -0400,1085;000000000000-00000000
Steve: You raise an interesting example, one that will be duly noted in the paper with Phil Mulry. You are right that the logical way to try to establish commutativity of the Beck law you cite below is to invoke the axiom of choice. I would submit that the diagram commutes without AC as well. Phil and I establish this in an entirely different way. It begins with an historical accident. I introduced the families monad (PP,eta,mu) and proved that the monad axioms hold in detail on pages 78-79 of Monads of Sets, Handbook of Algebra vol. 3. My point there was to consider an example where the less-standard monad axioms which don't iterate the functor would prove useful, since the usual mu-law requires chasing P^6, which is miserable. It was only later that we asked if this composite monad arises from a distributive law. Jon Beck --surely the Georg Cantor of distributive laws, who missed little of importance-- anticipated this situation. According to one of his theorems, if (P,e,m) is the power-set monad then the families monad arises via a distributive law of the power-set monad over itself if and only if Pe, eP : P --> PP are monad maps and mu (P eta P) = id : PP --> PP. In that case, the corresponding distributive law is mu (eta PP eta) : PP --> PP. Now it is quite routine to check these three conditions and, moreover, the formula for the distributive law is that which I gave earlier since that's how we came up with it to begin with. These proofs as well as Beck's equivalence proof have nothing to do with AC. The only place that AC could creep in is in the proof of the monad axioms. There, one indeed sees an argument of the general form "if this choice family exists than that one does and they behave this way" but I don't see any place where it is asserted that any choice family exists. Since this proof is in print, I leave it to you to see if you agree. Regarding the finite sub-example, I fully plead guilty to working in the "classical" environment of ZF where a cartesian product of finitely-many finite sets is indeed finite. All the Best Ernie ----- Original Message ----- From: "Steve Vickers" <s.j.vickers@cs.bham.ac.uk> To: <categories@mta.ca> Sent: Thursday, February 17, 2005 6:59 AM Subject: categories: Re: double covariant power set
Ernie Manes wrote:
I don't think anything goes wrong if AC fails as far as establishing a distributive law is concerned. No doubt much further discussion would be needed to understand well what happens, precisely, but note that many AA (e.g. principal filters) have non-empty C(AA). In any case, a sub-example obtains replacing P with the finite subsets monad, in which case no AC is needed.
Ernie
Dear Ernie,
Here is why I think the distributive law goes wrong if AC fails.
The original definition was this:
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
In a paper under preparation on distributive laws, joint with Philip Mulry, we show that the families monad arises by a distributive law of the power set monad P over itself. To describe that law, first establish some notation as follows. For AA in PPX a family of subsets of X, let C(AA) be the cartesian product of AA, that is, the set of all choice families x = (x_A : A in AA) with x_A in A. Let I(x) be the image of x, i.e. {x_A : A in AA}. The distributive law in question, PPA -> PPA, maps AA to {I(x) : x \in C(AA)}. <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
One of the conditions of a distributivity is that the following diagram commutes:
PPPX ---- P mu X ------> PPX
| |
sigma PX |
| |
v |
PPPX sigma
| |
P sigma X |
| |
v v
PPPX ---- mu P X ------> PPX
where mu is the multiplication and sigma is the distributivity. (Hope the format was clear. Down the left we have three copies of PPPX, with vertical morphisms involving sigma and P. Down the left are two copies of PPX, with vertical morphism sigma. Across are two horizontal morphisms involving mu and P.)
Start from AAA at top left. Going across and down gives
{I(x) | x in C{U(AA)) | AA in AAA}} (1)
where U is union (i.e. mu). Going down and across gives
{I(z) | (exists y in C(AAA)) z in C(I(y))} (2)
Suppose we have such an x in C{U(AA)) | AA in AAA}. We want to find corresponding y and z to demonstrate that I(x) is in (2). Now for each AA in AAA, x chooses an element x_U(AA) in U(AA) and so there is some A in AA with x_U(AA) in A. We'd like our y in C(AAA) to have y_AA as such an A, but unfortunately A is not uniquely defined and so we need the axiom of choice to find such a y.
Similar uses of choice appear in other places, so that is why it appears to me that the distributive law depends on AC.
If we replace P by a finite powerset F, then we have a separate question: How do we know, if AA is in FFX, that sigma(AA) is finite? This depends on the constructive notion of finiteness. In my work I was using Kuratowski finiteness (for which the finite powerset monad is the free semilattice monad), and for that we find that C(AA) is not finite in general - which is why I replaced it with Ch(AA), using total choice relations instead of choice functions. But that definition of sigma does not give a distributivity even classically.
All the best,
Steve.
18-Feb-2005 12:18:20 -0400,5847;000000000000-00000000
participants (2)
-
Ernie Manes -
Steve Vickers