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