43
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, I realise that it's subjective what counts as 'interesting' but hopefully potentially answerers can cope with this. $\endgroup$ – bryn Jul 22 '10 at 8:55
  • $\begingroup$ Yes, but it's a very arcane subject that most people don't understand/care about. Might I suggest that you ask on meta.mathoverflow.net if this question is appropriate for mathoverflow? I am not confident that you will receive a decent answer here. $\endgroup$ – user126 Jul 22 '10 at 9:00
  • 2
    $\begingroup$ I'll try my luck. If the community decides to close the question on grounds of arcaneness then so be it. $\endgroup$ – bryn Jul 22 '10 at 9:31
  • 1
    $\begingroup$ @Harry: you have a very funny way of complimenting, I will give you that much! Arcane = compliment haha! $\endgroup$ – Vivi Jul 22 '10 at 10:50
  • 2
    $\begingroup$ I think that subsemigroups of monoids are probably more important than semigroups proper. Like the even numbers $\{2,4,6,8\}$ are a multiplicative subsemigroup of $\mathbb{N}.$ But to make them a monoid, we'd have to include $1$, which would be odd (pun intended!). $\endgroup$ – goblin May 19 '13 at 15:46

15 Answers 15

31
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ This is a very good answer. Note, however, that in the discrete analog of convolution (say for summable sequences over $Z$), there is an identity: the discrete analog of the delta function! $\endgroup$ – Akhil Mathew Jul 22 '10 at 11:39
  • 6
    $\begingroup$ For reference, the function @Akhil mentions is the Kronecker Delta, specifically the one at 0. $\endgroup$ – Larry Wang Jul 22 '10 at 11:46
19
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ I am a bit surprised to see that this answer received such a high grade. I do not agree with the sentence "We could just study monoids and the effect would be the same" (see my answer), but more importantly, the sentence starting with "Note that" is wrong. In the bicyclic monoid, which is the monoid $M$ presented by $< a, b \mid ab = 1 >$, no element apart from $1$ has an inverse. However $M - 1$ is not a semigroup. $\endgroup$ – J.-E. Pin Aug 10 '15 at 15:04
5
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Your definition of a group seems wrong to me. You need to require that $e$ is a two-sided identity and that $a^{-1}$ is a two-sided inverse, don't you? $\endgroup$ – Qiaochu Yuan Jan 24 '12 at 23:32
  • 2
    $\begingroup$ @QiaochuYuan: actually, the usual definition is equivalent to this one. $\endgroup$ – Dejan Govc Mar 14 '12 at 13:35
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where did you find this example? (Or more precisely, where could I read more about such examples?) It reminds me of learnyouahaskell.com/a-fistful-of-monads#the-list-monad (or book.realworldhaskell.org/read/monads.html#id641620), and other "monadic" constructions. However, I wasn't aware that such "monadic" constructions could actually yield semigroups. $\endgroup$ – Thomas Klimpel Jan 7 '12 at 11:13
  • 1
    $\begingroup$ @Thomas: I wouldn't say monads are the inspiration, but categories are, because of the restriction on composition. I though finite sets of matrices under pairwaise multiplication was a slightly easier intuition than finite sets of morphisms over a category under pairwise composition. $\endgroup$ – Charles Stewart Jan 8 '12 at 19:22
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for this list. It seems to be a list of properties/results on semigroups rather than any examples of particular semigroups that cannot be extended in an obvious way. So it is an answer to the question "Is there any reason to study semigroups rather than monoids?" but possibly not an answer to my original question. $\endgroup$ – bryn Aug 21 '15 at 19:57
  • 1
    $\begingroup$ The unique nilpotent (resp. locally trivial) semigroup which is a monoid is the trivial monoid. The locally idempotent and commutative monoids are idempotent and commutative (i.e. semilattices). Apart from these, all the semigroups cannot be extended to a monoid of the same family. The smallest example is the the two-element nilpotent semigroup $\{s, 0\}$, where $s^2 = 0$. $\endgroup$ – J.-E. Pin Aug 22 '15 at 6:22
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ I like the analogy, but I think one should attempt to provide a clean definition of the semigroup elements and the binary operation in this case... $\endgroup$ – Alexander Konovalov May 3 '15 at 14:57
  • $\begingroup$ @AlexanderKonovalov Well, the usual thing would be a finite-state automaton, but really you can treat a semigroup called $\mathrm{Time}$ as an index set and use that to parameterise any $X$ you’re interested in. $\endgroup$ – isomorphismes May 3 '15 at 16:00
  • 1
    $\begingroup$ @AlexanderKonovalov BTW, this is not my idea; it's the prologue of books.google.com/books?id=0ukzw5VszNwC. $\endgroup$ – isomorphismes May 3 '15 at 16:03
  • $\begingroup$ Great, thanks for the reference! $\endgroup$ – Alexander Konovalov May 3 '15 at 17:08
0
$\begingroup$

Let G be the set of (continuous) functions f: R -> 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: R->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: R->R} is not a group. Therefore the following correction is needed: consider only functions such that $f(x) \neq 0$ everywhere.

$\endgroup$
  • $\begingroup$ -1: {f:R->R} is only a group under addition, not multiplication. $\endgroup$ – user126 Jul 22 '10 at 10:34
  • $\begingroup$ What, pray tell, is the inverse of f(x)=x? Note that g(x)=1/x is not defined on the entire real line. It is defined as a function R\{0}->R. $\endgroup$ – user126 Jul 22 '10 at 10:52
  • $\begingroup$ To quote the question, if the domain can be extended in an obvious way to include an identity element then that's not what I'm after. $\endgroup$ – Charles Stewart Jul 22 '10 at 11:55
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Although this answers the question in the title, it seems to ignore the second paragraph where I try to tighten what is meant by the question. $\endgroup$ – bryn Dec 12 '13 at 9:13
0
$\begingroup$

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.

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.