Further categories of EM-algebras:
the distributive law \delta connceting the free monoid monad on
(-)^* and the (finite) power-set functor can equivalently be
described in two other forms:
. a monad on $set$ with the functor (-)^* P and a unit composed of
the original units (\delta shows up in the multiplication for
this monad)
. a monad on $mon$, the category of EM-algebras for the free monoid monad
that ``lifts'' the (finite) powerset monad.
fortunately, the categories of EM-algebras for both of these monads
coincide:
. for P we get the category $uqnt$ of unital quantales, i.e.,
complete lattices with a monoid structure, such that the
sup-function is a monoid homomorphism; morphisms are
monoid-homomorphisms that preserve arbitrary suprema.
. for F we get the category $udioid$ of unital dioids or idempotent
semi-rings with additive unit.
recall the notion of
- ring, an abelian group with a monoid structure
subject to classical distributivity
- replacing the abelian group with a commutative monoid yields
semi-rings with unit, also known as ``rigs'' (ring w/o negatives)
- replacing the abelian group with a commutative semigroup yields
semi-rings not neccessarily with unit (``rgs'' anyone?)
- the commutative monoid/semigroup can also be required to be
idempotent (a+a=a), which yields dioids or idempotent semirings,
with or w/o unit
important examples of idempotent semi-rings in CS are
* the ``tropical'' semiring IR (real numbers) with min as
addition and + as multiplication; in order to have an additive
unit, one has to add \infty and gets the ``tropical rig''
* the ``max-plus-algebra'' IR (real numbers) extended with
-\infty and with max as addition and + as multiplication.
Sets Bags and Tuples
. for sets, neither the order of the elements nor the (positive)
multiplicacy matter
. for ``bags'', the order does not matter but the multiplicity does
(sets with possible repetitions)
. for tuples the order matters, and hence automatically the
multiplicacy.
Each of these notions gives rise to a ``finite power-x'' monad:
. the finite power-set monad on sets, with EM-algebras the
sup-semilattices (with bottom; in case of non-empty subsets, there
need not be a bottom element)
. the finite power-bag monad on set, with EM-algebras the
commutative monoids; in case of non-empty bags one gets
commutative semigroups; idempotent commutative monoids/semigroups
are just sup-semilattices with or w/o bottom;
. the ``finite power-tuple'' monad (= free monoid monad) (-)^*, with
monoids as EM-algebras; in case of non-empty tuples one gets semigroups.
The free monoid monad (-)^* admits distributive laws with the other
two, and the categories of EM-algebras are dioids in case of finite
power sets, and (unital) semi-rings (rigs) in case of finite power bags.
Monads in 2-categories
The notion of monad makes sense as soon as we have a category whose
hom-sets are themselves categories (with composition then a family
of functors). Besides $cat$ and $Cat$, there are two simpler examples:
Rel, the category of sets, (bin) relations and inclusions:
HW: identify the monads in $rel$!
Spn, the category of sets, spans and span-morphisms:
a span from A to B is a set S with maps A <-s_0-- S --s_1-> B; the notion
is a generalization of directed graphs, in as far as A and B need
not be the same. If A <-t_0-- T --t_1-> B is another span from A
to B, a span-morphism is just a function S --f-> T making both
triangles commute.
alternatively, spans from A to B can be viewed as set-valued
AxB-matrices; their composition is like a matrix product, however
with disjoint union instead of addition and cartesian product
instead of multiplication.
HW: identify the monads in $spn$!
The other big important notion that can be formulated in any
2-category is the notion of adjoint. It may be useful to look at
adjoints first in simpler cases like $rel$ and $spn$ than in $cat$
or $Cat$.