On the notion of partial semigroup

Question

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...).

Answer 1

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 .]

Answer 2

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).

Answer 3

I realize that this is a question is nearly a decade old, but hopefully someone will find this helpful. One thing that is notable about using (4) as our definition for a partial semigroup is that it makes partial semigroups a universal first order relational theory (as far as I understand---take it with a grain of salt, as I'm not really a model theorist!) What I mean is that with definition (4) we can write out the axioms of a semigroup using only universal quantifiers and one 3-ary relation symbol (together with a symbol for (in)equality).

Let's denote our 3-ary relation symbol by $m$. For $a,b,c \in X$, we want to think of $m(a,b,c)$ as expressing that $a*b=c$. (If $m(a,b,c)$ is not true, then perhaps $a*b$ is not defined, or perhaps it is and is just not equal to $c$). We want $a*b$ to have at most one value, and we want some sort of associativity to hold. These can be expressed using axioms using only universal quantifiers, if associativity is in the sense of (4):

1. (uniqueness) $\forall a,b,c,d \in X, m(a,b,c) \land m(a,b,d) \Rightarrow c=d$.
2. (pre-associativity) $\forall a,b,c,x,y,z \in X, [m(a,b,x) \land m(b,c,y) ] \Rightarrow [ m(x,c,z) \Leftrightarrow m(a,y,z) ].$

It's not hard to see that I could similarly axiomatize left- or right-pre-associativity using only universal quantifiers. On the other hand, I think you might not be able to phrase the other definitions stated without introducing an existential quantifier. The subtle thing I suppose is that with these restrictions, you can't actually express "$x*y$ is defined" ($\exists z : m(x,y,z)$), you can only express $x*y=z$ ($m(x,y,z)$).

Now, you might ask why I want this to be a universal first order relational theory anyway. Well, for me personally, I had just watched a lecture of Leonardo Nagami Coregliano on the IAS YouTube channel, where he was discussing technology which (to put it crudely) creates analogues of graphons for any finite universal first order relational theory, thus giving "continuous" limits for various different combinatorial objects. Someone in the lecture asked about groups, and he pointed out that there were many points in the definition of groups where you really need an existential quantifier (as well as a constant symbol for the identity). So after watching the lecture I thought a bit and it seemed that the closest one could get to a group with these restrictions was a partial semigroup as I defined above (actually you can encode cancellation as well, if you like).

Aside from applying that specific technology, one nice property of such theories (as pointed out in the lecture also) is that any subset of a model of the theory induces a model of the theory. That is, if we define a partial semigroup to be a pre-associative partial magma, then every subset of a partial semigroup also gives a partial semigroup. Depending on one's taste, that might suggest that we've given partial semigroups too little structure, but in my opinion, sort of the whole reason that we consider these partially defined objects is precisely so that fairly general subsets of our objects are subobjects. For instance, in my mind, one of the main motivating examples of a partial semigroup should be an arbitrary subset of a group. For this reason (5) is a bit too strong of a definition for my taste.

As for dissociativity, it seems relatively natural to me, and even though I don't think it's a universal first order relational theory, it might actually also have the property that every subset of a dissociative partial magma is a dissociative partial magma [I haven't checked this really]---so maybe I haven't done anything to convince you of (4) over (8). But hopefully I've given some indication of why pre-associativity might give a natural definition, at least for some purposes.

Answer 4

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.

Gerhard "Ask Me About System Design" Paseman, 2013.03.05

Answer 5

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.