9
$\begingroup$

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

$\endgroup$

5 Answers 5

5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2013 at 14:54
  • $\begingroup$ @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. $\endgroup$
    – Hans
    Mar 5, 2013 at 19:33
  • $\begingroup$ @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. $\endgroup$
    – Hans
    Mar 5, 2013 at 21:37
  • $\begingroup$ 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. $\endgroup$ Mar 6, 2013 at 9:09
2
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ Boris, can you do homological stuff on partial grupoids? $\endgroup$
    – Victor
    Mar 5, 2013 at 14:36
  • 1
    $\begingroup$ 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? $\endgroup$ Mar 5, 2013 at 14:44
  • $\begingroup$ @Victor :Sorry, I do not quite understand your question :-( $\endgroup$ Mar 5, 2013 at 15:31
  • $\begingroup$ @Salvo Tringali: Maybe. As I knew Lyapin, he was a great "conceptualist" in Semigroups. $\endgroup$ Mar 5, 2013 at 15:35
  • $\begingroup$ @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 [...] $\endgroup$ Mar 5, 2013 at 16:08
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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 (...) $\endgroup$ Mar 5, 2013 at 17:23
  • $\begingroup$ (...) 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. $\endgroup$ Mar 5, 2013 at 17:30
  • $\begingroup$ @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). $\endgroup$ Mar 5, 2013 at 18:22
  • $\begingroup$ 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 $\endgroup$ Mar 5, 2013 at 18:28
  • $\begingroup$ 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 $\endgroup$ Mar 5, 2013 at 18:35
0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2013 at 16:46
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2013 at 18:28
  • $\begingroup$ 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 (...) $\endgroup$ Mar 5, 2013 at 20:17
  • $\begingroup$ (...) 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?! $\endgroup$ Mar 5, 2013 at 20:17
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2013 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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