Apologies if this is is not very well-defined or exposes my ignorance; I know comparatively little about abstract algebra.

The structure of certain programming languages can be described with the algebraic structure $(S,\cdot,\verb|^|)$ where

  • $\cdot:S\times S\rightarrow S$ is associative and unital, and

  • $\verb|^| : S \rightarrow S$

i.e., a monoid with an extra unary operation. Unfortunately, nothing much can be said about $\verb|^|$ except that:

  • $\verb|^|$ distributes over $\cdot$, i.e., $\verb|^|(a\cdot b) = \verb|^|a\cdot \verb|^|b$.

  • $\verb|^|$ is cancellative: $\verb|^|a = \verb|^|$b implies $a = b$.

In particular, $\verb|^|$ is not an inverse operation, nor idempotent; in general, $\verb|^|(\verb|^|a) \neq a$, and in particular, $\verb|^|1\neq1$.

My question is:

Has this structure been studied, or at least been given a name, in abstract algebra?

I'm not optimistic, because adding $\verb|^|$ doesn't appear to make the structure much more interesting than a monoid. But if anyone can even point me towards similar structures, I'd be grateful. (Although clearly groups are not a good fit because of the lack of invertibility.)

(Edited to include the cancellative property of $\verb|^|$ and to explicitly mention its non-idempotency.)

  • 3
    $\begingroup$ So basically what you're describing is a monoid with an endomorphism on it, right?! $\endgroup$ – Giorgio Mossa Dec 10 '12 at 14:22
  • $\begingroup$ Does $\land a=\land b$ imply $a=b$? $\endgroup$ – Thomas Andrews Dec 10 '12 at 14:26
  • $\begingroup$ Also, is it known at least that ^1=1? If not, then @ineff is wrong that ^ is an endomorphism. $\endgroup$ – Thomas Andrews Dec 10 '12 at 14:34
  • 2
    $\begingroup$ It would be worthwhile to see specific examples that you are trying to formalize, so that we might have some idea whether there are additional commonalities other than the ones you have listed. $\endgroup$ – Thomas Andrews Dec 10 '12 at 15:58
  • $\begingroup$ @Thomas: Yes, ^a=^b implies a=b. But no, ^1≠1. I take it that, if ^1=1 held, it would be an endomorphism? Thanks to you and ineff for pointing this out -- it may be possible to reformulate things (in a contrived way) to get a special restricted case where ^1=1 and see where that leads me. $\endgroup$ – Chris Pressey Dec 10 '12 at 16:04

Given that it is not necessarily true that $\verb|^|1\neq 1$, we can't even say that $\verb|^|$ is an endomorphism of the monoid (only an endomorphism of the semigroup.)

The cancellation rule for $\verb|^|$ makes this hard to study in category theory. Without the cancellation rule, this would be some sort of "universal algebra." With the cancellation rule, we have a harder problem. (We don't talk about the category of integral domains, but really only the category of rings in general. The same is true here.)

By the way, it is not at all obvious that the "quote" operator of Joy distributes as you say. It seems like the description of "quote" in that article does not make $[ab]=[a][b]$. It depends on what it means, I guess, to "push onto the stack," but as I take it, $[a][b]$ pushes two things onto the stack, while $[ab]$ pushes only one.

  • $\begingroup$ True, Joy's quote does not work like that, but it's fairly easy to make a variation which does, and I was hoping that adding another property (however slight) might bring it closer to something algebraically conventional. Joy's quote is also intensional, whereas what I'm working with is extensional. I just realized that that means, in Joy, a=b does not imply [a]=[b]; but [a]=[b] still does imply a=b, and at any rate, extensionality is pretty important for my current purposes. $\endgroup$ – Chris Pressey Dec 11 '12 at 17:42

I don't know if this one can meet you requirement:

Let $(S,+,\centerdot)$ be a semiring, and treat your $\centerdot$ as $+$, treat your ^a as $a\centerdot c$ for a fixed $c$.

Even though it has more properties than your structure, it's the best one I can think of.

  • $\begingroup$ The commutativity of + is not a good fit, but the idea of fixing a c like that is intriguing. Do you happen to know if there's a good example of using that technique in some other context? $\endgroup$ – Chris Pressey Dec 10 '12 at 16:37
  • $\begingroup$ How about this one: near-semiring, which does not require the commutativity, see en.wikipedia.org/wiki/Near-semiring. For example the addition and multiplication of ordinals form a near-semiring, if you define your ^a as $c\centerdot a$ (it only has right distributive law), then the structure has all the properties you list, without invertibility,idempotency and commutativity $\endgroup$ – Chao Chen Dec 11 '12 at 3:27
  • $\begingroup$ That would work better, assuming I can find a suitable $c$. It is possible to transform programs in these languages in a way that removes brackets and adds a symbol which basically says "bracket this other thing"; that operator is a good candidate for this $c$. But there are issues with associativity that I don't know if I can get around, with that approach; it'll take some time for me to look into it. $\endgroup$ – Chris Pressey Dec 11 '12 at 10:29

It seems to me that the structure is a pair of a monoid (though not a unital) and a monomorphism $(S,\verb|^|)$. A morphism $S\overset{\alpha}{\longrightarrow} S^\prime$ should be a (non unital) monoid morphism $\alpha$ such that the diagram commutes: $\require{AMScd}$ \begin{CD} S @>\alpha>> S^\prime\\ @V \verb|^| V V{\#} @VV \verb|^| V\\ S @>>\alpha> S^\prime \end{CD}

But I don't know anything about that structure, not its name or history.


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.