What are some (simple/elementary) examples of noncommutative monoids with no additional structure? I'm having a hard time thinking of examples of "pure" monoids that aren't monoids simply because they are groups...
I've read this and this and some of this, but would like more examples that presuppose little to no algebra.
$\endgroup$ 33 Answers
$\begingroup$Free monoids are pretty intuitive at heart: strings of letters under a concatenation operation.
Also, the set of functions $X\to X$ on a set (no stipulation of being bijective). More generally the set of endomorphisms of an arbitrary object of an arbitrary category caries a monoid structure under composition, so in particular functions on a set and linear maps on a vector space (categories in general constitute an abstract algebra background, but sets and vector spaces not as much).
If $G$ is an arbitrary group (which is admittedly an essentially algebraic concept), in your case noncommutative, one can adjoin a zero element (in the literature's lingo, an absorption element) and easily make the set $G\cup\{0\}$ into a monoid that is not a group. (For fun, this process can be continued indefinitely to create bigger and bigger monoids.) This idea is pretty straightforward.
$\endgroup$ 2 $\begingroup$Let $\mathfrak{M}_n(\mathbb{R})$ be the set of real square matrices of order $n$ and $\circ$ the operation of matrix product, then $(\mathfrak{M}_n(\mathbb{R}),\circ)$ is a monoid for all $n\ge 2$.
It is not commutative: for $n=2$ it is$$\begin{bmatrix} 0 & 1\\0 & 0 \end{bmatrix}\circ\begin{bmatrix} 1 & 0\\0 & 0 \end{bmatrix}\ne\begin{bmatrix} 1 & 0\\0 & 0 \end{bmatrix}\circ\begin{bmatrix} 0 & 1\\0 & 0 \end{bmatrix}.$$
It is not a group, since all matrices with determinant $0$ have no inverse. For example, for $n=2$, the identity element is$$\begin{bmatrix} 1 & 0\\0 & 1 \end{bmatrix}$$and there's no $A\in\mathfrak{M}_2(\mathbb{R})$ such that$$A\circ\begin{bmatrix} 1 & 0\\0 & 0 \end{bmatrix}=\begin{bmatrix} 1 & 0\\0 & 1 \end{bmatrix}$$(SLM, pp. 37-38).
Let $A$ be a non empty set, $A^A$ denote the set of all functions $f\colon A\to A$ and $\circ$ denote the composition of functions defined, for all $f,g\in A^A$, as$$(f\circ g)(x)=f(g(x)),\ \forall x\in A.$$Then $(A^A,\circ)$ is a monoid with identity element $Id$, defined$$Id(x)=x,\ \forall x\in A$$(SVTL, pp. 164-165). Again, such monoid is not commutative and is not a group: can you prove it?
$\endgroup$ 2 $\begingroup$A generic answer is the monoid of all functions from a set $E$ into itself under the composition of functions. This example is generic since every monoid is isomorphic to a submonoid of such a monoid. In particular, take any set of functions from $E$ to $E$ and close under composition: you will get a monoid. See this link. This type of example occurs frequently in automata theory.
You could also consider partial functions or relations on $E$, still under composition. The monoid of $n \times n$ matrices over a ring under the usual multiplication of matrices is also a quite natural example. If you have a monoid $M$, the set $\mathcal{P}(M)$ of all subsets of $M$ is also a monoid under multiplication defined by$XY = \{ xy \mid x \in X, y \in Y \}$ (where $X, Y \in \mathcal{P}(M)$).
$\endgroup$
