11
$\begingroup$

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

  • 0
    Nobody has used the word "monomorphism" as far as I can see. Why not? Isn't that what ^ is?2013-11-24

3 Answers 3

0

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.

1

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.

  • 0
    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.2012-12-11
1

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.

  • 0
    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.2012-12-11