# On the notion of partial semigroup

A partial binary operation on a set $X$ is just a (partial) function $\varphi: X \times X \rightharpoonup X$ (I'm using \rightharpoonup for partial maps), and a partial magma is a pair $\mathbb M = (M, \star)$ such that $M$ is a set and $\star$ is a partial binary operation on $M$ (I say that $\mathbb M$ is a magma if $\star$ is total). But what about partial semigroups? At least in principle, many alternative definitions are possible: The only thing I would take for certain is that a partial semigroup must be a partial magma $\mathbb M = (M, \star)$ for which $\star$ satisfies some kind of associativity, and of course I've my personal list. Specifically, I say that $\mathbb M$ is

1. (properly) associative if for all $x,y,z \in M$ such that $(x \star y) \star z$ and $x \star (y \star z)$ are defined, it holds $(x \star y) \star z = x \star (y \star z)$.
2. left pre-associative if for all $x,y,z \in M$ such that $x \star y$ and $y \star z$ is defined, it holds that "$(x \star y) \star z$ is defined" implies "$x \star (y \star z)$ is defined and $(x \star y) \star z = x \star (y \star z)$".
3. right pre-associative if the dual of $\mathbb M$ is left pre-associative.
4. pre-associative if it is both left and right pre-associative.
5. strongly associative if for all $x,y,z \in M$ it holds that "$x \star y$ and $y \star z$ are defined" implies "$(x \star y) \star z$ and $x \star (y \star z)$ are defined, and also $(x \star y) \star z = x \star (y \star z)$".
6. left dissociative if for all $x,y,z \in M$ it holds that "$(x \star y) \star z$ is defined" implies "$x \star (y \star z)$ is defined and $(x \star y) \star z = x \star (y \star z)$".
7. right dissociative if the dual of $\mathbb M$ is left dissociative.
8. dissociative if it is both left and right dissociative.

In this taxonomy (which doesn't aim to be complete by any means), "being (propertly) associative" corresponds to the weakest possible form of associativity, in the sense that it is implied by all the others. Moreover, all of the above properties collapse into each other if $\mathbb M$ is a magma. So, the (somewhat philosophical) question is:

What should a partial semigroup be? Do you envisage any "higher logic" advocating for one instead of another choice?

My own answer is that a partial semigroup should be a strongly associative partial magma, in the sense of the above condition 5. But, on the one hand this doesn't seem to be the "standard" definition in the literature (see, e.g., R.H. Schelp, A partial semigroup approach to partially ordered sets, Proc. London Math. Soc. (1972), s3-24 (1), 46-58, where partial semigroups are pre-associative partial magmas, in the sense of the above condition 4), and on the other hand I can't give myself a reason why this should be better or worse than something different (which bothers me much...).

The "right" definition of "partial semigroup" probably depends on the use one wants to make of these structures. Vitaly Bergelson, Neil Hindman, and I needed partial semigroups in our paper "Partition Theorems for Spaces of Variable Words", and we used the definition that says if either of $(x*y)*z$ and $x*(y*z)$ is defined then so is the other and they are equal. That seems quite a natural definition, and it worked well for our purposes. I don't know (though I may have known when working on the paper) whether some other definition would have worked as well. [The paper is in Proc. London Math Soc. (3) 68 (1994) pp. 449-476, and a version of it is on my web site at http://www.math.lsa.umich.edu/~ablass/bbh.pdf .]

• Yours is precisely my notion of dissociativity, which I've not included in the list in the OP since I myself don't find it particularly "natural". And although we agree that one "right" definition, of course, does not exist, I'd be quite surprised if a "categorial" perspective on the question cannot provide a conceptual motivation, going beyond the scope of a mere "principle of local utility", for favoring one choice over another (which is really what I'm looking for). In any case, thank you much for your answer and the reference. – Salvo Tringali Mar 5 '13 at 14:54
• @Salvo: Yes, it depends on what you like. There is probably no final choice, it depends. That is why we have also groups, groupoids etc. - A stronger reason for the above partial semigroup definition by @Andreas is that you do not need brackets any more in word expressions. I think that's the point for that definition. - On the other hand it is also somewhat limiting. For example, most (arbitrary) subsets of groups are not partial semigroups in this sense. Think about it in Z. – Hans Mar 5 '13 at 19:33
• @Salvo: mhm, does this also hold if we take condition 2) in your list and (x y) z is defined, but y z is not defined? - ED: ok, you mean that we know that we must interpret xyz as (xy)z because the other possibility makes no sense. Ok, I see. Good argument. It will be hard to work with such expressions practically, but it's interesting. Maybe they should indeed also be considered. – Hans Mar 5 '13 at 21:37
• Yes, but now that I read myself, I must say that it's expressed in a wrong way. What I mean is that either (xy)z and x(yz) are both defined (and then they're equal to each other), one, and only one, of them is defined, or none of them is defined. In the first two cases, we have a unique unambiguous way to interpret the expression xyz. I'll delete my previous comment to avoid confusion. – Salvo Tringali Mar 6 '13 at 9:09

There were many articles of Soviet semigroupists (Vagner, Lyapin and their pupils). E.g., see

Evseev, A.E. A survey of partial groupoids. Transl., II. Ser., Am. Math. Soc. 139, 43-67 (1988); translation from Properties of semigroups, Interuniv. Collect. Sci. Works, Leningrad 1984, 39-76 (1984).

Lyapin, E.S. The possibility of a semigroup continuation of a partial groupoid. (English) Sov. Math. 33, No.12, 82-85 (1989); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 1989, No.12(331), 68-70 (1989).

Lyapin, E.S.; Evseev, A.E. The theory of partial algebraic operations. Transl. from the Russian by J. M. Cole. Mathematics and its Applications (Dordrecht). 414. Dordrecht: Kluwer Academic Press. x, 235 p. (1997).

• Boris, can you do homological stuff on partial grupoids? – Victor Mar 5 '13 at 14:36
• Many thanks for the references. I will look at the papers tomorrow, but I don't think that the authors give any conceptual motivation to support their own definitions, right? – Salvo Tringali Mar 5 '13 at 14:44
• @Victor :Sorry, I do not quite understand your question :-( – Boris Novikov Mar 5 '13 at 15:31
• @Salvo Tringali: Maybe. As I knew Lyapin, he was a great "conceptualist" in Semigroups. – Boris Novikov Mar 5 '13 at 15:35
• @Boris. Thanks, but I may have problems in finding a copy of the book that you mention as a last entry in your list. Yet, I see from the 1988 English translation of Evseev's survey that he's using the term groupoid in the sense of Bourbaki's magma. That's fine, but I find the definition of a subgroupoid provided in the paper unconceivable from any conceptual point of view: Evseev lets a submagma of a magma $\mathbb M=(M,\star)$ be a subset $N$ of $M$ s.t. $a\star b\in N$ for all $a,b\in N$ s.t. $a\star b$ is defined in $\mathbb M$. In my view, this is "wrong", for it doesn't agree with [...] – Salvo Tringali Mar 5 '13 at 16:08

I agree with Andreas Blass: the best notion depends on what you need to do. If you are going to do many general algebraic constructions, you might benefit from George Graetzer's classic textbook "Universal Algebra", which develops much theory starting from partial algebras. My hunch is he uses your 1) to build varieties of partial semigroups, but you should check it out for yourself.

• Then I will repeat that, on the practical level, I agree with you and him, but my question is slightly different. I know you know this very well, but let me stress the obvious: Even if some questions are not formal, it can still make sense to look for answers which, in presence of many possible alternatives, are better motivated than others by some sort of abstract rationale, and hence canonical in a suitable sense, especially when you're working on foundational aspects and have to decide your basic definitions. On a similar note, if I'm given a set and asked to put a partial order (...) – Salvo Tringali Mar 5 '13 at 17:23
• (...) on it, and if the questioner is not expressing an interest in any particular application, then I have no doubt as to the answer which I should provide. – Salvo Tringali Mar 5 '13 at 17:30
• @Gerhard. I followed your suggestion, and checked it out for myself, but there's no occurrence of the strings "sociativ" or "semigroup" in the 2nd chapter of the 2008 edition of Grätzer's book (which is apparently the only chapter in the whole text devoted to partial algebras). – Salvo Tringali Mar 5 '13 at 18:22
• You can pick your foundations and then build what you can; you can also pick your constructs and find what foundations work best to extend those constructs or explain them more thoroughly. Your question likely warrants more of a philosophical discussion than this Q&A forum is meant to provide. Alternately, you could say "I give up. I will become a general algebraist, use George's book, and follow his rationale and definitions; I accept his as the right definition of partial semigroup." . Gerhard "It's Really Up To You" Paseman, 2013.03.05 – Gerhard Paseman Mar 5 '13 at 18:28
• I am glad you followed my suggestion. However, I think that you need to look not just at substrings, but to consider his definition of variety, and possibly pseudo or quasi variety. Your definitions may turn out to have equational or Horn sentence equivalents, or require a certain set of all but finitely satisfiable sentences. I am unsure which would fit your needs best, and you may need to spend half an hour or more reading it to find what you need. For more on partial algebras, I think Burmeister has some material. Gerhard "Relying On Decade Old Memories" Paseman, 2013.03.05 – Gerhard Paseman Mar 5 '13 at 18:35

There is the notion of semigroupoid (see for example chapter 2 of Groupoid Metrization Theory by Mitrea, Mitrea, Mitrea and Monniaux or this paper by R.Exel) for the exact definition and some motivation for it) which generalizes semigroups in the same way that groupoids generalize groups. The associativity condition in semigroupoids doesn´t seem to be in your list, as far as I can tell.

• Exel's notion of associativity (for what it's worth, I know that paper quite well) is just a disjunctive combination of "my" notions of strong associativity and left/right dissociativity, and you're right that I've not included the last two in the OP (basically, for the reason that I mention in the first comment to Andreas Blass' answer). On another hand, I don't agree that sgrpds, as they're defined in Exel's work, generalize sgrps in the same way as grpds do with grps, but this may depend on our relative definitions: For me, a grpd is a cat all of whose arrows are iso. I'm editing the OP. – Salvo Tringali Mar 5 '13 at 16:46
• You mean "conjunctive combination"? Also, the algebraic definition of groupoid (which is equivalent to the cat definition according to en.wikipedia.org/wiki/Groupoid#Algebraic) has the same associativity notion as Exel´s notion. – Ramiro de la Vega Mar 5 '13 at 18:28
• But I've never meant that the two definitions of grpd given by Wiki.en are not equivalent to each other. Instead, I said that I don't know which definition (of grpd) you are thinking of when you claim that Exel's sgrpds generalize sgrps in the same way as grpds do with grps: Some people, for instance, use the term "grpd" to refer to Bourbaki's magmas (e.g., J. Howie). Secondly, I'd rather say that grps are to grpds as monoids are to cats, and monoids are to cats as sgrps are to (Mitchell's) semicats, and not to Exel's sgrpds. As for the rest, Definition 2.1 in Exel's paper expresses (...) – Salvo Tringali Mar 5 '13 at 20:17
• (...) associativity as the (inclusive) disjunction of three conditions: He says that a partial map $\cdot:\Lambda\times\Lambda\rightharpoonup\Lambda$ is associative if "[...] either of (i) ..., or (ii) ..., or (iii) ... [...]" holds. Now, if my English is not worse than I want to admit to myself, "if either of (i) ..., or (ii) ..., or (iii) ... holds" should mean "if at least one among (i) ..., (ii) ..., or (iii) ... holds". Right?! – Salvo Tringali Mar 5 '13 at 20:17
• The assertion $\forall x [p(x) \lor q(x) \implies r(x)]$ is equivalent to the conjunction of $\forall x [p(x) \implies r(x)]$ and $\forall x [q(x) \implies r(x)]$ not to their disjunction. – Ramiro de la Vega Mar 5 '13 at 23:38