2
$\begingroup$

The analogous result to Cayley’s theorem or Yoneda lemma in semigroup theory represents semigroups as semigroups of functions from a set to itself. This suggests that a semigroup action consists of a semigroup $S$, a set $A$, and a mapping of the elements of the semigroup $S$ to functions from the set $A$ to itself. But the analogous result for inverse semigroups requires partial symmetries, i.e. partial functions instead of total functions. But if we allow partial functions, then what do we do with removable singularities?

Here comes the desire to turn all this into "somebody else's problem", by using a general definition of semigroup action in terms of category theory. We can then work in the category of sets and (total) functions, if we don't need partial functions for the semigroup action. If we need partial functions, then we can work in the category of sets and partial functions. And if we worry about removable singularities, then we can work in the appropriate category where these are removable.

Edit (because of requests for clarification): Before going into details why it is unclear to me whether this proposed "solution" will fix the issues of the apparent "incompatibility" between semigroup action and the inverse semigroup representation theorem, here are questions that I "hope" can be answered:

  • How does the definition of semigroup action in terms category theory look like?
  • (main question) Does this definition make sense when applied to an inverse semigroup? Does it lead to the intended representation theorem if used with the category of sets and partial function?
  • Is there an analogous definition of groupoid action? Are the various connections between semigroups and groupoids compatible with these definitions of an action?

But how should such a definition look like? I'm not sure, but let's look at a (potential) similar definition for groupoid action: A groupoid action relative to a category $\mathcal C$ would be a groupoid $\mathcal G$ and a functor $\mathcal G\to \mathcal C$. In analogy to this, one could interpret a monoid as a category with a single object, a monoid action as a single object category $\mathcal M$ and a functor $\mathcal M\to \mathcal C$. A semigroup action would then be defined as a subsemigroup of a corresponding monoid action.

One problem I have is that if there were such a thing as a semigroupoid (there is: it's called a category...), it would be easy to interpret a small semigroupoid (and hence also a small groupoid) as a semigroup. (Add a new absorbing element and use it to define the result of any undefined composition from the semigroupoid.) But can one define a semigroup action in such a way that also the semigroupoid action can be interpreted appropriately in terms of semigroup action? This doesn't mean that the above definition won't work, maybe one just has to switch to a corresponding category of categories for being able to interpret it appropriately.


Side note One general issue for me related to the proposed "solution" is that I'm not too familiar with the treatment of partial homomorphisms within category theory. The category of pointed sets "hinted at" by Qiaochu Yuan makes it "crystal clear" how partial homomorphisms work in the case of sets. But is the situation for other (concrete) categories really as "straightforward" as this? Andrej Bauer suggested some references, and the topic also seems to be discussed in some category theory texts in connection with "limits and colimits", where a construction based on subobjects, equivalence classes and pullbacks is described. I will have to read and understand these.

$\endgroup$
  • 2
    $\begingroup$ The action of a semigroup $G$ in a category $\mathcal{C}$ is given by a functor $G \to \mathcal{C}$, where we view $G$ as a category with a single object, and the morphisms are the elements of $G$. This comes down to: an action is given by an object $X$ in $\mathcal{C}$ and a semigroup homomorphism $G \to \mathrm{Hom}(X,X)$. It's all completely analogous to group actions, so I don't really understand what you'd like. $\endgroup$ – Andrej Bauer Aug 30 '14 at 8:46
  • 1
    $\begingroup$ Your question about getting a notion of partial morphism is separate from what makes a semigroup action. For that, I recommed reading: J. Robin B. Cockett, Stephen Lack: Restriction categories I: categories of partial maps. Theor. Comput. Sci. 270(1-2): 223-259 (2002), and also the second paper J. Robin B. Cockett, Stephen Lack: Restriction categories II: partial map classification. Theor. Comput. Sci. 294(1/2): 61-102 (2003) $\endgroup$ – Andrej Bauer Aug 30 '14 at 8:48
  • 1
    $\begingroup$ As @Andrej, I do not understand well what exactly you want to achieve but I have a vague feeling nonetheless that idempotent splitting may be used to unify everything in sight. It is always the case that the category of actions of a monoid $M$ on objects of an idempotent-split category $C$ is equivalent to the category of actions of the category of idempotents of $M$ on objects of $C$. I believe both semigroups and inverse semigroups are incorporated as particular cases of this. If I am not mistaken, inverse semigroups are precisely semigroups whose category of idempotents is a groupoid. $\endgroup$ – მამუკა ჯიბლაძე Aug 30 '14 at 10:24
  • 2
    $\begingroup$ I am in fact downvoting the question because it is unclear what it is asking. Let's continue the discussion. $\endgroup$ – Andrej Bauer Aug 30 '14 at 12:53
  • 1
    $\begingroup$ I summon Robin Cockett! $\endgroup$ – Andrej Bauer Sep 1 '14 at 7:53
3
$\begingroup$

Thanks to Andrej Bauer to drawing my attention to this question.

This is definitely related to restriction categories and I do recommend the articles by Steve Lack and myself ("Restriction categories I" TCS 2002). However, I though it may be useful to say a word or two about how the question relates to our development.

(1) There is, to start with, the issue of "units": being category theorists by training we (Steve and I) tended to assume units are present and preserved. An inverse semigroup (semicategory) of course can always be completed to an inverse monoid (category) or alternatively (and more interestingly) one can split the idempotents to get and inverse category. Both directions do allow one to keep (with some extra structure) all the information about one's start point. For example in the latter case one needs some information about what glues together into an object -- this leads one into a version of Ehresmann's "pseudo-groups" ... the multi-object version of all this, as far as I know, has not been systematically developed. Mark Lawson is the goto man on this!

(2) Given that one accepts one has units then restriction categories have a lot to say about representation theory:

Restriction categories give a very clean algebraic approach to partiality. There is a long (categorical and non-categorical) history behind this notion. For an appreciation of this see my paper with Ernie Manes (Boolean and classical restriction categories, MSCS 2009). However, the point is the categorical expression is very natural and is captured in just four identities.

An inverse category is a restriction category in which every map is a partial isomorphism. Thus an inverse category is to a restriction category what a groupoid is to an ordinary category. In particular, a one object inverse category is an inverse monoid ...

(3) There are two (main) representation theorems on restriction categories (see my paper with Steve).

(i) The first simply states that every restriction category is a full subcategory of a partial map category. This is a sanity check: it says the notion successfully completely captures "partiality".

(ii) The second -- and more relevant to this discussion -- says there is a full and faithful representation of a restriction category as a partial map category of a presheaf category. This is a genuine representation theorem and is a strengthening of the traditional Wagner-Preston theorem (as it gives a full and faithful embedding rather than just a faithful one). The theorem also gives a basic representation theorem for inverse categories as they are special restriction categories. The theorem is closely related to the Yoneda lemma (of course) but also requires the "right" notion of partiality on the presheaf category.

I hope this helps.

-robin

$\endgroup$
4
$\begingroup$

If you want to get inverse semigroup actions as by partial injections you need to remember more than its semigroup structure, I think.

One option is to view it as a 1-object restriction category (or semigroupoid). If you view sets and partial maps as a restriction category you will get the right notion.

Alternatively inverse semigroups are etale groupoids with their Alexandrov topology. Actions on sets by partial actions are the same thing as cts actions of the soberification of the etale groupoid on discrete sets.

You can also define partial maps and injections in any category as certain spans. This might let you then define actions of categories by partial injections.

$\endgroup$
1
$\begingroup$

The following answer is a long and convoluted way of saying that a semigroup action "is what it is", and that a semigroup is not a category. (A monoid may be a category with a single object, but a semigroup is not a monoid.) If we want to use the language of category theory, we better stay within the realm of established translation schemes (at least as a first step). The conclusion is that working in the category of sets and partial functions has wider implications than just allowing a more general notion of semigroup action, and doesn't even achieve the intended goal to treat inverse semigroup actions "well".


How does the definition of semigroup action in terms category theory look like?

Before we can define a semigroup action in terms of category theory, we have to define a semigroup in terms of category theory. A semigroup $S$ may be described as an object $S$ together with a morphism $\mu:S\times S \rightarrow S$ such that the following diagram in $\mu$ commutes: $$\begin{matrix} S\times S\times S & \xrightarrow{1\times\mu} & S\times S \\ \\ \downarrow^{\mu \times 1} & & \downarrow^\mu \\ \\ S\times S & \xrightarrow{\mu} & S \end{matrix}$$ This means that we have $\mu\circ(1\times\mu)=\mu\circ(\mu\times 1)$, but the commutative diagram is more understandable, because it also show the objects and not just the morphisms.

In this language, a semigroup action may be described as a semigroup $S$, an object $X$ and a morphism $\alpha:S\times X \rightarrow X$ such that the following diagram in $\mu$ and $\alpha$ commutes: $$\begin{matrix} S\times S\times X & \xrightarrow{1\times\alpha} & S\times X \\ \\ \downarrow^{\mu \times 1} & & \downarrow^\alpha \\ \\ S\times X & \xrightarrow{\alpha} & X \end{matrix}$$ This means that we have $\alpha\circ(1\times\alpha)=\alpha\circ(\mu\times 1)$.

Does this definition make sense when applied to an inverse semigroup?

The next step would be to define an inverse semigroup in terms of category theory. We have to express the identities $x=xx^{-1}x$ and $xx^{-1}yy^{-1}=yy^{-1}xx^{-1}$ in terms of commutative diagrams for this. Hence an inverse semigroup may be described as a semigroup $S$ together with a morphism $\zeta:S\rightarrow S$ such that the following diagrams in $\mu$ and $\zeta$ commute:$$\begin{matrix} S\times S\times S & \xrightarrow{1\times\zeta\times 1} & S\times S\times S \\ \\ \uparrow_{(\delta \times 1)\circ\delta} & & \downarrow^{\mu\circ(\mu\times 1)} \\ \\ S & =\!= & S \end{matrix}$$ $$\begin{matrix} S\times S\times S\times S& \xleftarrow{\delta\times\delta} & S\times S \overset{\text{swap}}{\leftrightarrow} S\times S &\xrightarrow{\delta\times\delta}&S\times S\times S\times S\\ \\ \downarrow^{1\times\zeta \times 1\times\zeta} & & & & \downarrow^{1\times\zeta \times 1\times\zeta}\\ \\ S\times S\times S\times S & \xrightarrow{\mu\circ(\mu\times\mu)} & S & \xleftarrow{\mu\circ(\mu\times\mu)} & S\times S\times S\times S \end{matrix}$$ We could just apply the definition of semigroup action to this scenario, and we would have a definition. But should we add additional conditions that must be satisfied by an inverse semigroup action? Maybe, but I don't know which conditions these would be.

Does it lead to the intended representation theorem if used with the category of sets and partial function?

As long as we don't add additional conditions to be satisfied by an inverse semigroup action, there is no reason why this actionshould lead to the intended representation theorem. And even before that, in a category where partial functions are allowed, we have to allow that $\mu$ and $\zeta$ are partial function, as long as all stipulated diagrams in $\mu$ and $\zeta$ are commutative. So we are already patently outside the domain of inverse semigroup theory, and not even close to the intended representation theorem.

Is there an analogous definition of groupoid action?

One potential definition is already given in the question.

Are the various connections between semigroups and groupoids compatible with these definitions of an action?

They are incompatible in a similar way as the connection between monoid action and semigroup action.

$\endgroup$
  • $\begingroup$ You should look at the restriction category stuff. It axiomatizes the domain and range idempotents. $\endgroup$ – Benjamin Steinberg Aug 31 '14 at 15:04
  • $\begingroup$ @BenjaminSteinberg I will read the three papers by Cockett and Lack on restriction categories. But I started by trying to make sense of the comments closer to my comfort zone. For example: "The idempotent splitting of an inverse semigroup is not a groupoid." now makes more sense for me, because the idempotents of an inverse semigroup form a semilattice, but a semilattice is not a groupoid. Or I verified that "define partial maps ... as certain spans" is essentially the "... construction based on subobjects, equivalence classes and pullbacks ..." found in some category theory texts. $\endgroup$ – Thomas Klimpel Aug 31 '14 at 23:28
  • $\begingroup$ Your semigroup and the object live in the same category. Another option is to let semigroup live in the category of sets (or wherever your hom-sets live) and then you can define what it means for such a semigroup to act on an object in a category. $\endgroup$ – Andrej Bauer Sep 1 '14 at 7:44
  • $\begingroup$ @AndrejBauer Your initial suggestion to take an inverse semigroup and a semigroup homomorphism into $\operatorname{Hom(X,X)}$ (for an object $X$ from a suitable category $\mathcal C$) still seems the most promising route to me now. If I take a category of partial injections for this, then I get at least the intended representation theorem. But what I don't like about this is that the inverse semigroup itself can't live inside a category of partial injections. $\endgroup$ – Thomas Klimpel Sep 1 '14 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.