Oleg's gists — Archive

Semi semi semi semi

Posted on 2019-11-07 by Oleg Grenrus

Semigroups, semigroupoids... are there more semithings?

#Group, Semigroup, Monoid

Let’s start "from the beginning". Groups is 19th century thing. A group is a set G with a binary operation \bullet , identity element e and inverse element a^{-1} for each a \in G . With an obvious laws you can imagine relating these.

If we remove identity element from a group, "obviously" we get a semigroup. Because if there’s any element x \in G , we can recover the identity element by e = x \bullet x^{-1} .

So what’s a semigroup with identity element? For sometimes it were just that, until we started call it monoid. Go figure, naming is hard, not only in programming, but also in mathematics.

#Category, Groupoid, Semigroupoid

You are hopefully familiar with a concept of a category. I repeat a definition here:

Definition (Awodey 1.1) A category consist of the following data

  • Objects: A, B, C, \ldots

  • Arrows: f, g, h, \ldots

  • For each arrow f , there are given objects

    \mathrm{dom}(f), \qquad \mathrm{cod}(f)

    called the domain and codomain of f . We write

    f : A \to B

    to indicate that A = \mathrm{dom}(f) and B = \mathrm{cod}(f) .

  • Given arrows f : A \to B and g : B \to C , that is, with

    \mathrm{cod}(f) = \mathrm{dom}(g)

    there is given an arrow

    g \circ f : A \to C

    called the composite of f and g .

  • For each object A , there is given an arrow

    1_A : A \to A

    called the identity arrow of A .

  • Associativity:

    h \circ (g \circ f) = (h \circ g) \circ f

    for all f : A \to B , g : B \to C , h : C \to D .

  • Unit:

    f \circ 1_A = f = 1_B \circ f

    for all f : A \to B .

If you think hard (or read a book), you’ll learn that a single object category is a monoid: category arrows are monoid elements, and the laws work out.

The group analogue is called groupoid. In addition to category data, we require that for each arrow f : A \to B there is an inverse arrow f^{-1} : B \to A , such that f \circ f^{-1} = 1_B and f^{-1} \circ f = 1_A . Or more succinctly: that each arrow is an isomorphism.

But we can also remove stuff: if we remove identity arrows, and unit law we get semigroupoid.

Definition A semigroupoid consist of the following data

  • Objects: A, B, C, \ldots

  • Arrows: f, g, h, \ldots

  • For each arrow f , there are given objects

    \mathrm{dom}(f), \qquad \mathrm{cod}(f)

    called the domain and codomain of f . We write

    f : A \to B

    to indicate that A = \mathrm{dom}(f) and B = \mathrm{cod}(f) .

  • Given arrows f : A \to B and g : B \to C , that is, with

    \mathrm{cod}(f) = \mathrm{dom}(g)

    there is given an arrow

    g \circ f : A \to C

    called the composite of f and g .

  • Associativity:

    h \circ (g \circ f) = (h \circ g) \circ f

    for all f : A \to B , g : B \to C , h : C \to D .

A reader probably ask themselves: are there interesting, not-contrived examples of semigroupoids, which aren’t also categories? There are. If poset (set with partial order) is an example of category, then a set with strict order1, is an example of semigroupoid.

As a concrete example, natural numbers with an unique arrow between n and m when n < m is a semigroupoid.

0 < 1 < 2 < 3 < 4 < \cdots

There are no identity arrow, as n \not< n , but associativity works out: if n < m and m < p then n < p . Let’s call this semigroupoid \mathbf{LT} .

Finally, a plot twist. nLab calls semigroupoids semicategories, and don’t even mention a semigroupoid as an alternative name!

#Functors, Semifunctors...

Recall a definition of functor.

Definition (Awodey 1.2) A functor

F : \mathbf{C} \to \mathbf{D}

between categories \mathbf{C} and \mathbf{D} is a mapping of objects to objects and arrows to arrows, in such a way that

  • F (f : A \to B) = F(f) : F(A) \to F(B) ,

  • F(1_A) = 1_{F(A)} ,

  • F(g \circ f) = F(g) \circ F(f) .

That is, F preserves domains and codomains, identity arrows, and composition. A functor F : \mathbf{C} \to \mathbf{D} thus gives a sort of "picture" – perhaps distorted – of \mathbf{C} in \mathbf{D} .

Functors preserve identities, but semigroupoids don’t have identities to be preserved. We need a weaker concept:

Definition A semifunctor

F : \mathbf{C} \to \mathbf{D}

between semigroupoids \mathbf{C} and \mathbf{D} is a mapping of objects to objects and arrows to arrows, in such a way that

  • F (f : A \to B) = F(f) : F(A) \to F(B) ,

  • F(g \circ f) = F(g) \circ F(f) .

That is, F preserves domains and codomains, and composition. A functor F : \mathbf{C} \to \mathbf{D} thus gives a sort of "picture" – perhaps distorted – of \mathbf{C} in \mathbf{D} .

An identity functor is obviously a semifunctor, also a successor functor S : \mathbf{N} \to \mathbf{N} is a semifunctor \mathbf{LT} \to \mathbf{LT} .

In Haskell, that would be silly to define a class for (endo)semifunctors:

-- semimap f . semimap g = semimap (f . g)
class Semifunctor f where
    semimap :: (a -> b) -> f a -> f b

It’s the Functor type-class without an identity law. On the other hand, something like

data Mag a b t where
    Map   :: (x -> t) -> Mag a b x -> Mag a b t
    One   :: a -> Mag a b b

instance Semifunctor (Mag a b) where
    fmap f (Map g x) = Map (f . g) x
    fmap f x         = Map f x

would be valid.

#Semimonad?

Now as we have semifunctors, would it make sense to ask whether endosemifunctors can form a monad

Semimonad A semimonad on semigroupoid C consists of

  • an endosemifunctor T : C \to C

  • semi natural transformation \eta : 1_C \to T (return)

  • semi natural transformation \mu : T^2 \to T (join)

  • Associativity (as semi natural transformations T^3 \to T )

    \mu \circ T \mu = \mu \circ \mu T

  • Identity (as semi natural transformations T \to T )

    \mu \circ T\eta = \mu \circ \eta T = 1_T

Looks a lot like monad, but for semifunctors. I have an example: the S semifunctor is a semimonad. Feels like (I didn’t check) that all strictly monotonic functions would fit. We need to find some more structured semigroupoid than \mathbf{LT} to find more interesting semimonads, but I haven’t yet.

I end with a catchy phrase:

A semimonad is a monoid (!) in the category of endosemifunctors.

What would be a semigroup in the category of endofunctors2, or a semigroup in the category of endosemifunctors?

Naming is hard.

#References: More on the theory of semi-functors

There’s a paper The theory of semi-functors by Raymond Hoofman https://doi.org/10.1017/S096012950000013X.

  1. http://mathworld.wolfram.com/StrictOrder.html, I not dare to call the set with strict order a soset↩︎

  2. in Haskell we call it Bind, at least now (or Apply for different semigroup)↩︎

This work is licensed under a “CC BY SA 4.0” license.
Oleg's gists — Archive

twitter github email linkedin stackoverflow

Site proudly generated by Hakyll