9

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

Salvo Tringali
  • 9,617
  • 2
  • 25
  • 56

5 Answers5

5

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

Andreas Blass
  • 72,290
  • 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 05 '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 05 '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 05 '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 06 '13 at 09:09
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).

Boris Novikov
  • 3,080
  • Boris, can you do homological stuff on partial grupoids? – Victor Mar 05 '13 at 14:36
  • 1
    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 05 '13 at 14:44
  • @Victor :Sorry, I do not quite understand your question :-( – Boris Novikov Mar 05 '13 at 15:31
  • @Salvo Tringali: Maybe. As I knew Lyapin, he was a great "conceptualist" in Semigroups. – Boris Novikov Mar 05 '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 05 '13 at 16:08
  • [...] the notion of subobject that is "naturally" implied by looking at the question from the "privileged" perspective of categories. Do you/anybody know if this has been "corrected" in the book? – Salvo Tringali Mar 05 '13 at 16:21
  • For the record, Evseev's notion of subgrpd is essentially an instance of the more general notion of (partial) subalgebra given by Grätzer at p. 80 of his Universal Algebra (2nd ed., 2008). The notion implied by the categorial point of view is, instead, the one of relative subalgebra, which Grätzer himself introduces a few lines after. To quote him, "In many papers, the authors select one of each [...] and give the reasons for their choice. In the author's opinion, all these concepts have their meirts and drawbacks, and each particular situation determines which one should be used." (...) – Salvo Tringali Mar 06 '13 at 09:23
  • (...) This is, of course, unquestionable, and it reflects Andreas & Gerhard's position. Yet, what I'm barely trying to say is that, if we put applications to the side for one moment, we face the fact that there's a higher rationale providing an abstract notion of subobject, which is telling us that, from a conceptual point of view, Grätzer's notion of relative subalg should be privileged, & I'd like to find, if possible, a similar motivation for the notion of partial sgrp. But again, this is just what it is, namely abstract nonsense, and it has little to do here with the everyday practice. – Salvo Tringali Mar 06 '13 at 09:51
  • I don't see how to accomplish A and B in the same context, where A is "putting aside any and all applications of the objects and definitions", and where B is answering your question, which I rephrase as "what is the most natural way, determined by higher principles, to apply the term partial semigroup? ". Whichever way you do B, you will have to consider how to use the result, which to me speaks of application. (Continued) Gerhard "What Is Math Without Application?" Paseman, 2013.03.05 – Gerhard Paseman Mar 06 '13 at 18:08
  • The only other take I have on your question I parody as "Universal Algebraists cross themselves from right to left, while Category Theorists do down to up; is there a higher rationale which indicates which is better or more natural?" . I intend no disrespect; it's just that without application, I see the question as worse than silly, I see it as pointless. With application, I see a point to the question,and I stand by my previous responses. Please consider this as explaining my shortcomings, not as criticizing your question or motives. Gerhard "Ask Me About System Design" Paseman, 2013.03.05 – Gerhard Paseman Mar 06 '13 at 18:17
  • By the way, for me a partial semigroup is equivalent to a fragment of its multiplication table, where it is possible to complete it to be the table of an associative operation. Gerhard "And What About Impartial Semigroups" Paseman, 2013.03.05 – Gerhard Paseman Mar 06 '13 at 18:24
  • @Gerhard. No worries! Instead, thank you for sharing your reflections on this. – Salvo Tringali Mar 06 '13 at 19:31
1

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.

Christian Gorski
  • 305
0

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.

Ramiro de la Vega
  • 11,463
  • 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 05 '13 at 16:46
  • You mean "conjunctive combination"? Also, the algebraic definition of groupoid (which is equivalent to the cat definition according to http://en.wikipedia.org/wiki/Groupoid#Algebraic) has the same associativity notion as Exel´s notion. – Ramiro de la Vega Mar 05 '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 05 '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 05 '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 05 '13 at 23:38
  • You're obviously right, I should have said "conjunctive combination". I insisted on using the adjective "disjunctive" disregarding the 2nd half of the logical implication (i.e., just looking at the 1st operand "Either of (i) ..., or (ii) ..., or (iii) ..."), which doesn't, however, make any sense. Sorry! – Salvo Tringali Mar 06 '13 at 09:07
  • I think that semigroup is to semigroupoid as group is to groupoid. The terms monoid and category are outliers. Monoid is a recent term. Semigroups preceded monoids and one had unital and nonunital. When categories were invented they were not seen as generalized monoids until maybe much later. So nobody will change the name to monoidoid. So if you think of a semigroupoid as a multiobject semigroup then I think semigroupoid is a better term than semicategory. Others can differ. – Benjamin Steinberg Mar 06 '13 at 16:16
  • @Benjamin. I clearly recall that you expressed this point of view in a previous discussion (see http://mathoverflow.net/questions/106898/references-for-semicategories). However, when I say that "grps are to grpds as monoids are to cats, and monoids are to cats as sgrps are to (Mitchell's) semicats", I'm not referring to the choice of terms, but to the meaning of these terms. – Salvo Tringali Mar 06 '13 at 19:34
0

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

Gerhard Paseman
  • 1,031
  • 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 05 '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 05 '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 05 '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 05 '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 05 '13 at 18:35
  • I see your point, and I respect it, although I continue to disagree: There's a dose of philosophy in my questions, there is a greater dose of philosophy in mathematics, and it seems that there's even some room for philosophical musings on MO (see, e.g., http://mathoverflow.net/questions/19644/what-is-the-definition-of-canonical or http://mathoverflow.net/questions/2748/what-is-the-right-definition-of-a-ring). Let it be as it may, the discussion so far suggests that my questions have a negative answer, which already counts as a positive answer. P.S.: thanks for the hints! – Salvo Tringali Mar 05 '13 at 22:53