Re: "prime" monads?

Re: "prime" monads?

[Vaughan Pratt]

(This supersedes my previous post, responding to Fred Linton, which was
written too hastily in retrospect.  The following is hopefully more
accurate.)

In my response to Fred, "method A" imposed the condition on the
coefficients of the linear combinations constituting the operations of
Vct_R that they come from a subrig C of R, in line with Bill Lawvere's
mention of rigs.  Earlier I had pointed out that affine spaces arose
from a submonad of vector spaces obtained by requiring the weight of
every operation (sum of its coefficients) to be 1, i.e. the condition W
= {1} where W is the set of permitted weights.  The latter construction
evidently generalizes to all submonads produced by method A.

I then wrote,

 > Method B is to limit the operations to those whose weight (sum of
 > coefficients) is drawn from a submonoid of the monoid R under
 > multiplication.

Sorry, that attempt at generalizing method A doesn't produce submonads
after all (the \mu of Vct_R produces operations with weights outside W,
as I'll make clearer shortly).

Worse, I can't see what the right fix should be.  In fact I can't think
of any other submonads T of "Vct_C", namely those for which T(1) is the
underlying set of a subrig C of R, such that C contains a coefficient
greater than 1, other than those submonads with W = R or W = {1}.
Conjecture: there are none.

Monads probably aren't the most convenient framework for talking about
submonads of Vct_R, certainly for the typical reader of the American
Math Monthly, who would surely understand them better in terms of
ordinary finite matrices and their multiplication since the submonads
all have the same equational theory forming the basis for matrix
multiplication, just restricted to fewer operations.

To make the connection between matrix algebra and the Kleisli category
KT for any submonad T of Vct_R, the object n of KT for n a finite set is
(from the standpoint of the morphisms of KT) a free algebra A_n on a set
that can be viewed schizophrenically as a set of n variables and a basis
for A_n.   (Semantics qua EM doesn't specify a basis but syntax qua
Kleisli does.)  KT(1,m) = T(m) is schizophrenically the m-ary operations
and the points of A_m understood as column vectors.  KT(n,1) = T(1)^n is
the set of permitted row vectors aka dual points.  More generally
KT(n,m) is the set of permitted mxn matrices over T(1) representing the
morphisms from n to m in the Kleisli category of this particular
submonad T of Vct_R.

It follows that submonads can only constrain rows by constraining T(1),
which amounts to constraining the coefficients; what I've been calling
the set C of permitted coefficients is T(1).  Submonads can constrain
columns in more general ways, but not too general.

Restating my conjecture above in this mixed monad-matrix language, given
any submonad T of the monad for Vct_R for which T(1) contains a
coefficient c > 1, the only proper submonad of T that leaves the
permitted matrix entries (the set T(1)) unchanged is that for which
every column of the permitted matrices sums to 1.

This is almost how affine geometry is standardly implemented in
computational geometry and computer graphics (CG), the difference being
that the last row of each matrix is constrained to be a unit vector with
its 1 in the "translation" column (projective geometry projected from
infinity - the translation column specifies the vector translating the
transformed point).

The following is the generic affine transformation of a generic point
(x,y) in the plane in the CG approach.

( a b s )  ( x )  =  ( ax + by + s)
( c d t )  ( y )  =  ( cx + dy + t)
( 0 0 1 )  ( 1 )  =  (      1     )

The 2x2 matrix at the top left performs an ordinary linear
transformation of the plane.  The "translation column" is at the right,
and acts by translating the plane right s and up t.

This constraint on the last row, with no constraints on the columns,
seems in total violation of the above.  However the violation is not an
essential one as the matrix

     ( a b s )
A = ( c d t )
     ( 0 0 1 )

is similar (http://en.wikipedia.org/wiki/Similar_matrix) to

  -1       (    a+s         b+s         s    )
P  A P  = (        c+t         d+t       t  )
           ( 1-(a+s+c+t) 1-(b+s+d+t) 1-(s+t) )

where

     ( 1 0 0 )
P = ( 0 1 0 )
     ( 1 1 1 )

(Similarity is the matrix algebra counterpart of functoriality in
category theory.  That is, the evident nxn counterparts of P for all n
exhibit an equivalence, in fact an isomorphism, between the CG
representation of the category for affine spaces and its CT counterpart
as presented by its Kleisli category.)

It is easily seen that after applying this functor the column sums are
now 1, while a counting argument for degrees of freedom (6) shows that
the rows are no longer at all constrained.  The determinant remains
ad-bc while the trace remains a+d+1, and eigenvalues also remain unchanged.

(I only noticed this isomorphism of the two categories today.  In
retrospect it is a routine application of similarity, but is CG aware of
this particular functor?)

Other conditions on the morphisms, such as that they be orthogonal
matrices, will not in general produce submonads because they tamper with
the rows in what is likely to be an essential way that destroys
algebraicity.

The matrix viewpoint makes it a lot easier to see where my method B
breaks down: the only constraints on column sums that seem to work when
C (aka T(1)) = R are W = R and W = {1} (the conjecture above).

So what restrictions *can* we impose on the columns that preserve
algebraicity, specifically that preserve the equational theory of Vct_R?

The sets I = [0,1] and I- = (0,1] look like they could work
independently for each of C and W.  However for n > 1 we need 0 for the
unit vectors (\eta in the monad), ruling out C = I- and leaving C = I as
the only possibility here.   This still leaves the two possibilities W =
I and W = I-, the latter corresponding to disallowing zero column vectors.

The free algebras A_n on n generators for these two submonads can be
visualized geometrically as follows.

C = W = I: Unit simplexes with n+1 vertices, namely the origin and the n
unit vectors.  These are closed, containing their (n+1 choose d+1)
d-dimensional subfaces.  So n generators create ordinary n-dimensional
linear algebra confined to a simplex.

C = I, W = I- : Ditto less one point, namely the origin.

In the latter case, if the one zeroary operation (constant) 0 in T(0) is
understood as having weight 0, W = I- rules it out whence that constant
disappears.  So the 0-dimensional space A_0 is empty while A_1 is (0,1],
A_2 is a triangle less the origin, etc.

To summarize, we have as submonads of Vct_R the following:

1.  Vct_S obtained by subsetting T(1) to a subrig S of R, and
independently requiring either W = S (no constraint on W) or W = {1}
(the strongest possible constraint on W).  S could be the natural
numbers for example, with or without 0, but not the integers mod n
because that would not be a subrig of R (it would introduce new
equations we're trying to avoid).

2.  The pair of monads C = W = I and C = I, W = I-, intersected with S
as per 1 and so giving rise to lots of variants of the pair.

Does Vct_R have any other submonads?  Keep in mind the conditions that 1
belong to C and W (consider \eta) and that the rows be T(1)^n.

Vaughan

Re: "prime" monads?

[Vaughan Pratt]

From: Fred Linton
> I was relying on the Axiom of Choice (AC) to know that every vector space
> (scalars from an arbitrary field) has a basis. Paraphrasing: every
> vector space is free. Thinking (loosely) of the Kleisli category as
> the full subcategory of the EM category consisting of the free algebras,
> this means the K and the EM categories "coincide" (to within equivalence
> of categories). The exact nature of the field is irrelevant. But AC (or
> something else strong enough to guarantee every vector space has a basis)
> is crucial.

This seems right for ordered fields.  Is it also true for finite fields
and other non-ordered fields like the complex numbers?

If every Archimedean field k gives rise to a Klem (Kleisli ~ EM) monad
Vct_k, that's uncountably many Klem monads right there, all in the
lattice of submonads of Vct_R.  (The submonads of a monad must form a
complete lattice, more precisely a complete semilattice, if they're
closed under arbitrary intersection; is it always an algebraic
semilattice, as for algebras?)

k doesn't even need to be a field or an additive group, any subrig of R
will do, as Bill was hinting at.  (The coefficients have to form a rig
for T to be functorial.)  Call this Method A for forming a submonad of
Vct_R.

Method B is to limit the operations to those whose weight (sum of
coefficients) is drawn from a submonoid of the monoid R under
multiplication.  (It has to be a submonoid for the multiplication mu and
unit eta to remain defined.)  The smallest such monoid is {1}, which
gave rise to the affine spaces as per my previous post.  R has plenty of
other multiplicative submonoids, such as the set {c^i} for any real c >
0 and i ranging over any submonoid of Z under addition, or for any real
c and i ranging over any submonoid of N under addition.  This can be
combined with Method A (coefficients from a subrig of R) to get even
more submonads.

Questions:

1.  Do all submonads of Vct_R arise as above (coefficients limited to a
subrig of R, weights limited to a multiplicative submonoid of R)?

2.  Among the submonads of Vct_R, are the Klem ones exactly those for
which the set of coefficients is dense in some open interval of R?

>> But not for 1+1+X: the free bipointed sets are in a natural bijection
>> with the non-free ones, the latter having the two points
>> identified
>
> I'm not entirely sure what's "natural" here. Certainly the free bipointed
> sets are in bijective correspondence with the (just plain) sets: that's a
> "consequence," if you like, of the canonical functor from SETS to any
> Kleisli category over SETS being a bijection on objects. So the non-free
> bipointed sets, coinciding as they do with the (singly) pointed sets, are
> likewise in bijective correspondence with the (just plain) sets. But the
> same is true for the free algebras over ANY monad on sets. So? "This"?
>
>> ... --this must be about the simplest nontrivial instance of
>> obtaining an algebra as a quotient of a free algebra, not a bad
>> introductory example when explaining how to get algebras from free
> algebras.

Point taken.  I was trying to say that identifying the two constants of
a free bipointed set was the canonical way of producing any nonfree
bipointed set.  What's a slicker way to say this?

Vaughan

Re: "prime" monads?

[Vaughan Pratt]

Fred E.J. Linton wrote:
> There ARE a few monads for which the Kleisli and E-M categories
> "coincide," however, beyond the identity monads. First example
> coming to mind is the FreeVectorSpace monad on SETS. I'm sure
> other Categories-readers will point out more.

Fred, your numbering makes the example preceding your "first example"
(the identity monad) your zeroth example, but I'll number them 1 and 2
anyway.  Example 2 should work for all Archimedean fields (and
presumably all ordered fields).  Does it also work for fields not of
characteristic 0, or for the complex number field?

For more examples, all on Set, how about the following?  Example 3
extends example 1 (i.e. the identity monad is a submonad of example 3),
the rest (examples 4-9) are submonads of example 2.  This should bring
the crop of examples of Kl=EM up to 6 if I'm not mistaken (a big if),
with examples 7-9 not contributing.  All of 1-9 are finitary monads,
unlike for example the covariant power set monad whose signature is a
proper class.

3.  The lift monad 1+X on Set.  Obviously Kl=EM in this case.

But not for 1+1+X: the free bipointed sets are in a natural bijection
with the non-free ones, the latter having the two points
identified--this must be about the simplest nontrivial instance of
obtaining an algebra as a quotient of a free algebra, not a bad
introductory example when explaining how to get algebras from free algebras.

4.  The FreeAffineSpace monad on Set as the submonad of example 2
consisting of those operations whose coefficients sum to 1, i.e.
barycentric weightings where the individual weights can be any real.  I
noticed this the other day and assumed it must be well known (is it?).
It gives an alternative to France Dacar's equations yesterday showing
that the affine spaces are algebraic over Set.  The Kleisli-EM
identification certainly holds for finite-dimensional affine spaces (any
quotient is a space of lower dimension, but all spaces of a given finite
dimension are dense and therefore isomorphic); is there any reason why
the proof (with Choice) for infinite-dimensional vector spaces would not
go through for the affine case?

By way of insight into this monad, if you take those operations whose
coefficients sum to 3 say (still as a "submonad" of example 2), the
multiplication produces exactly the operations whose coefficients sum to
9, so that would-be monoid isn't closed under multiplication.  If you
think to fix this by taking the operations whose coefficients sum to 0
(remember we're allowing negative coefficients) then that attempt
doesn't have a unit.  That just leaves the barycentric operations as the
only possible submonad of example 2 consisting of operations of a fixed
total weight.

My guess would be that Kl=EM for the next two, by density (cf. examples
7 and 8).  Do statisticians know about these monads?

5.  Conservative statistics.  The submonad of example 4 where the
coefficients must be positive (and hence in (0,1]).  The next example
shows the sense in which this is "conservative."

6.  Lossy statistics.  The submonad of example 2 where both the
individual coefficients *and* their sum (over the coefficients of an
operation) are in (0,1].  Lossy statistics permits its sample spaces to
leak out through a wormhole.

The following two are examples in this vein where EM > Kl.

7.  The lattice monad (JAMS-friendly lattices, not that quaint
order-theoretic stuff that went out with the Bauhaus,
http://www.math.rutgers.edu/~zeilberg/Opinion81.html).  The submonad of
example 2 restricted to integer coefficients.  The free lattice on n
generators is Z^n; for n <= 2 I think all non-free quotients must be a
circle, cylinder, or torus, but for n = 3, (x,y,z) |--> (2x+z,2y+z)
produces the 2D checkerboard as an infinite quotient of Z^3 with no
cycles, pointing up the role of density in 4 above.

8.  Affine lattices.  The intersection of examples 4 and 7 (still
allowing negative coefficients).   This is the appropriate monad for
studying crystalline structure, which has no origin.  The free lattices
are the cubical crystals and all other crystalline structures are
non-free.  Unless I'm missing something the quotient (x,y,z) |-->
(2x+z,2y+z) works here too to show EM > Kl.

9.  The intersection of examples 5 and 7 (same as 6 and 7).  Isn't this
just example 1?

The chances of all my guesses being right are pretty slim, but if they
are we'd now be up to six examples of Kl=EM, namely 1 to 6 above.

What is the structure of the submonads of a monad on Set?  Anything like
algebraic lattices?

Vaughan

Re: "prime" monads?

[Ross Street]

Has someone already mentioned that Eilenberg-Moore algebra categories
and Kleisli categories "coincide" for all idempotent monads? The
forgetful is full.
Ross

> There ARE a few monads for which the Kleisli and E-M categories
> "coincide," however, beyond the identity monads. First example
> coming to mind is the FreeVectorSpace monad on SETS. I'm sure
> other Categories-readers will point out more.

Re: "prime" monads?

[George Janelidze]

Dear Fred,

If we are talking about funny things - all right, let us talk about funny
things:

I claim that there is exactly one pair (C,T) in which:

1. C is a category, and T is a monad on C;
2. the only adjoint situations giving rise to T are determined by the
Kleisli and the Eilenberg-Moore categories.

Even though "unfortunately", in this case the Kleisli and the
Eilenberg-Moore categories coincide.

In this unique pair C is the empty category. Indeed, if C is non-empty, then
take any category A with zero object and look at the projection
AxAlg(T) ---> Alg(T) composed with the forgetful functor Alg(T) ---> C. This
composite together with its obvious left adjoint will give rise to T.

Just coincidence of the Kleisli and the Eilenberg-Moore categories is
another story of course...

George Janelidze

----- Original Message -----
From: "Fred E.J. Linton" <fejlinton@usa.net>
To: <categories@mta.ca>
Sent: Friday, September 14, 2007 12:50 AM
Subject: categories: Re: "prime" monads?


Greg Meredith asks,

> ... are there monads such that the only adjoint
> situations giving rise to them are the Kleisli and Eilenberg-Moore
algebras?

NOt even the identity monad on SETS has this property, as it is
the adjunction monad also for the adjoint pair

[underlying pointset]: [topological spaces] --> SETS ,
[discrete topology on]: SETS --> [topological spaces] .

There ARE a few monads for which the Kleisli and E-M categories
"coincide," however, beyond the identity monads. First example
coming to mind is the FreeVectorSpace monad on SETS. I'm sure
other Categories-readers will point out more.

-- Fred

Re: "prime" monads?

[Greg Meredith]

Fred,

Thanks. My 'intuition' is that there are some adjoint decompositions that
genuinely reveal internal structure of the monad and others that ... make no
such disclosure ;-). But, perhaps i can disabuse myself of this with some
application to calculation.

Best wishes,

--greg

On 9/13/07, Fred E.J. Linton <fejlinton@usa.net> wrote:
>
> Greg Meredith asks,
>
> > ... are there monads such that the only adjoint
> > situations giving rise to them are the Kleisli and Eilenberg-Moore
> algebras?
>
> NOt even the identity monad on SETS has this property, as it is
> the adjunction monad also for the adjoint pair
>
> [underlying pointset]: [topological spaces] --> SETS ,
> [discrete topology on]: SETS --> [topological spaces] .
>
> There ARE a few monads for which the Kleisli and E-M categories
> "coincide," however, beyond the identity monads. First example
> coming to mind is the FreeVectorSpace monad on SETS. I'm sure
> other Categories-readers will point out more.
>
> -- Fred

Re: "prime" monads?

[Fred E.J. Linton]

Greg Meredith asks,

> ... are there monads such that the only adjoint
> situations giving rise to them are the Kleisli and Eilenberg-Moore
algebras?

NOt even the identity monad on SETS has this property, as it is
the adjunction monad also for the adjoint pair 

[underlying pointset]: [topological spaces] --> SETS ,
[discrete topology on]: SETS --> [topological spaces] .

There ARE a few monads for which the Kleisli and E-M categories
"coincide," however, beyond the identity monads. First example
coming to mind is the FreeVectorSpace monad on SETS. I'm sure
other Categories-readers will point out more.

-- Fred

"prime" monads?

[Greg Meredith]

Categorically-minded,

Is there a notion of prime monad where the notion of (de-)composition is
adjoint situation? For example, are there monads such that the only adjoint
situations giving rise to them are the Kleisli and Eilenberg-Moore algebras?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com