Are there any interesting semigroups that aren't monoids?

Question

Are there any interesting and natural examples of semigroups that are not monoids (that is, they don't have an identity element)?

To be a bit more precise, I guess I should ask if there are any interesting examples of semigroups $(X, \ast)$ for which there is not a monoid $(X, \ast, e)$ where $e$ is in $X$. I don't consider an example like the set of real numbers greater than $10$ (considered under addition) to be a sufficiently 'natural' semigroup for my purposes; if the domain can be extended in an obvious way to include an identity element then that's not what I'm after.

Answer 1

Convolution of functions/distributions is useful in a variety of fields, and the identity element, the dirac delta, is not strictly a function.

Answer 2

One source of monoids is given by taking rings with identity, and forgetting about addition. So similarly, one source of semigroups that are not monoids is taking rings without identity, and forgetting about addition. With this in mind, let me explain one basic source of rings without identity.

A basic source of rings is given by taking functions satisfying some reasonable condition on a space, e.g. continuous real or complex valued functions on a space, with pointwise addition and multiplication. Of course, the constant function 1 is continuous, and so this gives a ring with identity.

But suppose now that we impose some condition, such as "all functions that are continuous, and which furthermore vanish at some specified point". This throws out the constant function 1, and so gives a ring without identity. Now you could naturally object that this is artificial (as per the requirement in the question that there not be an obvious extension to a monoid), so let me add more explanation as to why it need not be.

One example of a point to consider is "the point at infinity", i.e. we could look at all functions which vanish at infinity, i.e. which on the complement of larger and larger compact sets, grow smaller and smaller. This is a natural condition to impose in many analytic contexts, and so gives a natural example. (The reason that this kind of growth condition is natural in analysis is that, on a non-compact space, e.g. the real line, a random continuous function may not be integrable (just as an example), and imposing some decay at infinity (perhaps of the kind I specified, or perhaps something more quantitive) becomes a way to rescue the situation.) (Note also that the example that Tomer Vromen gives is exactly of this form.)

Finally, note that if your semigroup doesn't have an identity, then you can always formally adjoin one, just by throwing in an extra element $e$ and declaring that $ex = x$ for all $x$.

One can do a similar thing for rings without identity. If $A$ is a $C$-algebra (say) without an identity, then one can form $A \oplus C e$ (the direct sum), and declare that $e$ acts as a multiplicative identity. This is a frequently-used technique in the theory of rings-without-identity.

P.S. I don't know much literature about semigroups without identity, but for rings without identity, the best literature I know of is in functional analysis books; e.g. Naimark's classic Normed Rings often treats the case of Banach algebras (and the like) without identity in addition to the case when they do have identity, exactly so as to be able to handle examples such as the ring of continuous functions on a locally compact space that vanish at infinity.

Answer 3

Here is a cheap answer which takes the stance that semigroups are inherently interesting :) Consider the following definition of a group:

$\textbf{Definition}$ A semigroup $S$ is said to be a group if the following hold:

1. There is an $e \in S$ such that $ea=a$ for all $a\in S$
2. For each $a \in S$ there is an element $a^{-1} \in S$ with $a^{-1}a=e$

At one point in my life, it seemed natural to ask what happens if we replace axiom 2 with the very similar axiom

2$^\prime$. For each $a \in S$ there is an element $a^{-1} \in S$ with $aa^{-1} = e$.

It is a fun exercise to work out some of the consequences that result from this. Here are a few facts about a semigroup $S$ which satisfies $1$ and $2^\prime$:

• If $e$ is the unique element of $S$ satisfying axiom 1, then $S$ is a group
• If $S$ has an identity (in the usual sense) then $S$ is a group
• The principal left ideal $Sa = \{sa \mid s \in S\}$ is a group for all $a \in S$, and in fact all principal left ideals of $S$ are isomorphic as groups.

It is not difficult to find examples of such semigroups that are not groups. For example, consider the following set of $2\times 2$ matrices (with matrix multiplication as the operation): $$\left\{\begin{pmatrix} a & b \\ 0 & 0\end{pmatrix} \mid a,b \in \mathbb{R}, a \neq 0\right\}$$ Or, an example that appears as exercise 30 in section 4 of Fraleigh's abstract algebra text: the nonzero real numbers under the operation $\ast$ defined by $a\ast b = |a|b$.

Certainly it is debatable whether or not semigroups satisfying axioms 1 and 2$^\prime$ are "interesting" or "natural". But I guess I think they are. And, I am not the only one (or the first one, by a long shot!) to think this. See Mann, On certain systems which are almost groups (MR). (A bit of googling will turn up more results if you are interested.)

Answer 4

I don't know if this counts as interesting, but a simple example is what C programmers know as the comma operator: Ignore the first argument and return the second. Or written as multiplication rule: $ab=b$ for all $a,b\in S$. This is easily shown to be a semigroup, but as long as there are at least two elements in $S$, this is not a monoid, as with neutral element $e$ you'd have for all $a\in S$ the identity $a=ae=e$.

Answer 5

Finite sets of matrices of varying dimensions, where the product A*B={PQ|P in A & Q in B & dim(Q)=codim(P)}, and dim & codim are the dimensions of the source & target spaces of a matrix.

The infinite case has an obvious unit.

Answer 6

Let $(M,\cdot,e)$ be a monoid and let $M^\circ$ be the set of finite words constructed from $M$. For two words let's define operation $*$ as point-wise application of $\cdot$, truncating according to the shorter word: $$(u_1,\ldots,u_m)*(v_1,\ldots,v_n)=(u_1\cdot v_1,\ldots, u_{\min(m,n)}\cdot v_{\min(m,n)})$$ Then $(M^\circ,*)$ is a semigroup, but it's not a monoid. Any candidate $y$ for the unit element would have only a finite length, so for any $x$ that is longer we'd have $y*x\neq x$. The unit element would have to be an infinite sequence $(e,e,\ldots)$, but $M^\circ$ contains only finite ones.

This example is not arbitrary, it is closely related to zipping lists and convolution.

--

Update: A very simple example of a semigroup that is not a monoid is $(\mathbb{Z},\min)$. While $\min$ is clearly associative, there is no single element in $\mathbb{Z}$ that would serve as the identity. (It is actually a homomorphic image of the previous example, mapping words to their length.)

Answer 7

The problem with this question is that any semigroup can be very easily made into a monoid. If your semigroup is not a monoid, then add a new element $1$ and define the lacking multiplication in the only possible way. In a sense, there is no need to study semigroups. We could just study monoids and the effect would be the same. Note that it is easy to distinguish a monoid that was build by adding a unity. It's enough to check whether any element of the monoid apart from $1$ has an inverse. If none has, the unity "has been added" in the sense that it can be removed.

Answer 8

There are many examples related to automata theory. I just mention three of them.

(1) A semigroup $S$ with $0$ is nilpotent if there exist $n > 0$ such that, for all $s_1, \dotsm, s_n \in S$, $s_1 \dotsm s_n = 0$.

A regular language is finite or cofinite if and only if its syntactic semigroup is nilpotent.

This is really a result on semigroup and not on monoids since the syntactic monoid of a nonempty finite language is not nilpotent.

(2) A finite semigroup $S$ is locally trivial if, for each idempotent $e \in S$, the semigroup $eSe = \{ese \mid s \in S\} = \{e\}$. Again, this notion is uninteresting for monoids since a finite locally trivial monoid is trivial. A language of $A^+$ is generalized definite if it is of the form $F \cup GA^*H$ for some finite languages of $A^+$.

A regular language is generalized definite if and only if its syntactic semigroup is nilpotent.

(3) A much deeper result. A finite semigroup $S$ is locally idempotent and commutative if, for each idempotent $e \in S$, the semigroup $eSe$ is idempotent and commutative.

A language of $A^+$ is locally testable if it is a Boolean combination of languages of the form $uA^*$, $A^*v$ and $A^*wA^*$, where $u, v, w \in A^+$. The following statement is difficult theorem proved independently in [1] and [2].

A regular language is locally testable if and only if its syntactic semigroup is locally idempotent and commutative.

Again, this is a result on semigroups and not on monoids.

[1] Brzozowski, J. A.; Simon, Imre. Characterizations of locally testable events. Discrete Math. 4 (1973), 243--271.

[2] McNaughton, Robert. Algebraic decision procedures for local testability. Math. Systems Theory 8 (1974), no. 1, 60--76.

Answer 9

Here are a few examples:

• Natural numbers (ordered by $\leq$) under minimum.
• Sets (ordered by $\subseteq$) under intersection.
• Strings (ordered by $\sqsubseteq$) under longest common prefix.
• Positive integers (ordered by divisibility $\mid$) under greatest common divisor.

What these examples have in common is that they are meet-semilattices without a greatest element. That is, they have no element $g$ such that $x \leq g$ and thus $x \land g = x$ for all $x$.

Another simple example is the semigroup where $a b = a$ or $a b = b$.

Answer 10

One family of examples comes from the so-called "semigroup variant" construction, which goes back to early work of Lyapin, Magill and others.

Let $S$ be a semigroup (a monoid if you want), and fix some element $a\in S$. Define the operation $\star$ on $S$ by $x\star y=xay$ for all $x,y\in S$. Then $\star$ is associative, so $(S,\star)$ is a semigroup, denoted $S^a$ and called the "variant of $S$ with respect to $a$". It is easily shown that $S^a$ is a monoid if and only if $S$ is a monoid and $a$ is a unit of $S$. (See for example Prop 3.4 of this paper.)

So in general, variants are semigroups without identities. However, variants often have what are called "mid-identities". A mid-identity of a semigroup $S$ is an element $u$ such that $xuy=xy$ for all $x,y\in S$. (Roughly speaking, if identity elements "do nothing" when they are used in products, then mid-identities "do nothing" when they are used in the middle of products). Now suppose $a$ is a regular element of $S$; this means that there exists $b\in S$ such that $a=aba$, and in general, there may be many such elements $b$. Then it is easy to check that any such $b$ is a mid-identity of the variant $S^a$. Having no identity but several mid-identities seems "interesting" to me (but the above article hopefully shows that variants are interesting for many other reasons as well - as are the more general "sandwich semigroups" studied in a few papers following on from that one).

For a concrete example, let $S$ be the semigroup of all functions from the set $\{1,2,3,4\}$ to itself: i.e., the full transformation monoid of degree $4$. And let $a\in S$ be the transformation with $a(1)=a(2)=1$ and $a(3)=a(4)=3$. Then $S^a$ is not a monoid (since $a$ is not a permutation), but $S^a$ has $64$ mid-identities! (It is easy to use GAP to show that there are $64$ elements $b\in S$ satisfying $a=aba$, and since $a$ is an idempotent, it is easy to show that any mid-identity of $S^a$ must be such an element $b$.) For a more extreme example with the same $S$, if $a$ was instead taken to be a constant map, then every element of $S$ (of which there are $4^4=256$) would be a mid-identity of $S^a$.

Answer 11

If you consider finite monoids, the only ones with no non-trivial homomorphic images are the finite simple groups and the two element multiplicative monoid of $\mathbb Z/2\mathbb Z$. But if you consider semigroups, there are the two-element semigroups and an infinite family associated to combinatorial incidence structures.

Take any $m\times n$ matrix $A$ of zeroes and ones with no repeated rows or columns. Define a semigroup $S_A$ to consist of all $n\times m$ matrices of zeroes and ones with the product $B\ast C=BAC$. Then this is a finite semigroup with no non-trivial homomorphic image.

Two such $S_A$ and $S_B$ are isomorphic iff there are permutation matrices $P,Q$ with $PAQ=B$, that is the incidence structures determined by $A,B$ are isomorphic.

Answer 12

Excerpts from Grillet’s Semigroups Chapter 1, Page 1,

“There are 1160 distinct … semigroups of order 5; 15793 semigroups of order 6; 836,021 semigroups of order 7…”

Granted, many of those semigroups are not that interesting. However, transformation semigroups (not monoids unless you count the identity map in) are interesting because most transformations(functions) are not bijective. Thus, transformation semigroups are more natural than permutation groups.

Answer 13

A simple example: the natural numbers under addition, if they are taken to not include zero. Naturally closed and associative, but without 0 there is no identity element.

Answer 14

Time. You can't turn it back (no inverse) and you can't stop it (no identity).

Answer 15

Example 1:

Let $T$ be a set and $\mathcal D(T)$ denote the set of all injective functions from $T$ to itself that are not surjective. Then under composition of functions, $\mathcal D(T)$ is a semigroup without an identity.

Example 2:

Let $\mathcal M (\mathbb N)$ denote all injective functions on $\mathbb N$ having the property that for each $f \in \mathcal M (\mathbb N)$

$\tag 1 \{m \in \mathbb N \, | \, m \text{ is not in the range of } f\}$

is an infinite set.

$(\mathcal M (\mathbb N), \circ)$ is a semigroup without identity.

Answer 16

Let $G$ be the set of (continuous) functions $f: \mathbb{R} \to \mathbb{R}$ where $f(x)$ tends to $0$ as $x$ tends to infinity: $lim_{x\to \infty}f(x) = 0$. The operator is the usual point-wise multiplication of functions.

$G$ is closed under $*$ since $\lim f(x) = 0$ and $\lim g(x) = 0$ imply $\lim f(x)*g(x) = 0$. $G$ is a subgroup of $\{ f: \mathbb{R} \to \mathbb{R} \}$, so the identity must be the same - the function which is constantly $1$. But this identity is not in $G$.

EDIT: As Harry correctly points out, $\{ f: \mathbb{R} \to \mathbb{R} \}$ is not a group. Therefore the following correction is needed: consider only functions such that $f(x) \neq 0$ everywhere.