Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

Section 14.1 Monoids

Recall that in Section 11.2 we introduced systems called monoids. Here is the formal definition.

Definition 14.1.1. Monoid.

A monoid is a set \(M\) together with a binary operation \(*\) with the properties
  • \(*\) is associative: \(\forall a,b,c \in M\text{,}\) \((a*b)*c=a*(b*c)\) and
  • \(*\) has an identity in \(M\text{:}\) \(\exists e\in M\) such that \(\forall a \in M\text{,}\) \(a*e=e*a=a\)

Note 14.1.2.

Since the requirements for a group contain the requirements for a monoid, every group is a monoid.
  1. The power set of any set together with any one of the operations intersection, union, or symmetric difference is a monoid.
  2. The set of integers, \(\mathbb{Z}\text{,}\) with multiplication, is a monoid. With addition, \(\mathbb{Z}\) is also a monoid.
  3. The set of \(n\times n\) matrices over the integers, \(M_n(\mathbb{Z})\text{,}\) \(n\geq 2\text{,}\) with matrix multiplication, is a monoid. This follows from the fact that matrix multiplication is associative and has an identity, \(I_n\text{.}\) This is an example of a noncommutative monoid since there are matrices, \(A\) and \(B\text{,}\) for which \(A B \neq B A\text{.}\)
  4. \(\left[\mathbb{Z}_n;\times_n\right],n\geqslant 2\text{,}\) is a monoid with identity 1.
  5. Let \(X\) be a nonempty set. The set of all functions from \(X\) into \(X\text{,}\) often denoted \(X^X\text{,}\) is a monoid over function composition. In Chapter 7, we saw that function composition is associative. The function \(i:X\to X\) defined by \(i(a)=a\) is the identity element for this system. If \(\lvert X\rvert\) is greater than 1 then it is a noncommutative monoid. If \(X\) is finite, \(\left\lvert X^X\right\rvert =\lvert X\rvert ^{\lvert X\rvert }\) . For example, if \(B=\{0,1\}, \left\lvert B^B\right\rvert=4\text{.}\) The functions \(z,u,i,\textrm{ and } t,\) defined by the graphs in Figure 14.1.4, are the elements of \(B^B\) . This monoid is not a group. Do you know why?
    One reason why \(B^B\) is noncommutative is that \(t \circ z \neq z \circ t\) because \((t\circ z)(0)=t(z(0))=t(0)=1\) while \((z\circ t)(0)=z(t(0))=z(1)=0\text{.}\)
The functions on \(B_2\)
Figure 14.1.4. The functions on \(B_2\)
Virtually all of the group concepts that were discussed in Chapter 11 are applicable to monoids. When we introduced subsystems, we saw that a submonoid of monoid \(M\) is a subset of \(M\text{;}\) that is, it is a monoid with the operation of \(M\text{.}\) To prove that a subset is a submonoid, you can apply the following theorem.
Often we will want to discuss the smallest submonoid that includes a certain subset \(S\) of a monoid \(M\text{.}\) This submonoid can be defined recursively by the following definition.

Definition 14.1.6. Submonoid Generated by a Set.

If \(S\) is a subset of monoid \([M;*]\text{,}\) the submonoid generated by \(S\text{,}\) \(\langle S\rangle\text{,}\) is defined by:.
  1. (Basis) The identity of \(M\) belongs to \(\langle S\rangle\text{;}\) and \(a\in S \Rightarrow a\in \langle S \rangle\text{.}\)
  2. (Recursion) \(a,b\in \langle S\rangle \Rightarrow a*b\in \langle S\rangle\text{.}\)

Note 14.1.7.

If \(S=\left\{a_1,a_2,\ldots ,a_n\right\}\text{,}\) we write \(\left\langle a_1,a_2,\ldots ,a_n\right\rangle\) in place of \(\left\langle \left\{a_1,a_2,\ldots ,a_n\right\}\right\rangle\text{.}\)
  1. One example of a submonoid of \([\mathbb{Z};+]\) is \(\langle 2\rangle =\{0,2,4,6,8,\ldots \}\text{.}\)
  2. The power set of \(\mathbb{Z}\text{,}\) \(\mathcal{P}(\mathbb{Z})\text{,}\) over union is a monoid with identity \(\emptyset\text{.}\) If \(S=\{\{1\},\{2\},\{3\}\}\text{,}\) then \(\langle S \rangle\) is the power set of \(\{1,2,3\}\text{.}\) If \(S=\{\{n\}:n\in \mathbb{Z}\},\) then \(\langle S\rangle\) is the set of finite subsets of the integers.
As you might expect, two monoids are isomorphic if and only if there exists a translation rule between them so that any true proposition in one monoid is translated to a true proposition in the other.
\(M=[\mathcal{P}\{1,2,3\};\cap ]\) is isomorphic to \(M_2=\left[\mathbb{Z}_2^3;\cdot \right]\text{,}\) where the operation in \(M_2\) is componentwise mod 2 multiplication. A translation rule is that if \(A\subseteq \{1,2,3\}\text{,}\) then it is translated to \(\left(d_1,d_2,d_3\right)\) where
\begin{equation*} d_i=\left\{ \begin{array}{cc} 1 & \textrm{ if } i\in A \\ 0 & \textrm{ if } i\notin A \\ \end{array} \right. \end{equation*}
Two cases of how this translation rule works are:
\begin{equation*} \begin{array}{lr} \begin{array}{c} \{1, 2, 3\}\quad\textrm{ is the identity for } M_1\\ \updownarrow \\ (1,1,1) \quad\textrm{ is the identity for }M_2\\ \end{array} & \begin{array}{c} \{1, 2\}\cap \{ 2, 3\}=\{2\}\\ \updownarrow \\ (1, 1, 0) \cdot (0, 1, 1) = (0, 1, 0)\\ \end{array}\\ \quad \end{array}\text{.} \end{equation*}
A more precise definition of a monoid isomorphism is identical to the definition of a group isomorphism, Definition 11.7.9.

Exercises Exercises

1.

For each of the subsets of the indicated monoid, determine whether the subset is a submonoid.
  1. \(S_1=\{0,2,4,6\}\) and \(S_2=\{1,3,5,7\}\) in \([\mathbb{Z}_8;\times_8].\)
  2. \(\{f\in \mathbb{N}^{\mathbb{N}}:f(n) \leqslant n, \forall n \in \mathbb{N}\}\) and \(\left\{f\in \mathbb{N}^{\mathbb{N}}:f(1)=2\right\}\) in the monoid \([\mathbb{N}^{\mathbb{N}};\circ]\text{.}\)
  3. \(\{A\subseteq \mathbb{Z} \mid A \textrm{ is finite}\} \textrm{ and} \left\{A\subseteq \mathbb{Z} \mid A^c\textrm{ is} \textrm{ finite}\right\}\) in \([\mathcal{P}(\mathbb{Z});\cup].\)
Answer.
  1. \(S_1\) is not a submonoid since the identity of \(\left[\mathbb{Z}_8; \times_8\right]\text{,}\) which is 1, is not in \(S_1\text{.}\) \(S_2\) is a submonoid since \(1 \in S_2\) and \(S_2\) is closed under multiplication; that is, for all \(a, b \in S_2\text{,}\) \(a \times_8 b\) is in \(S_2\text{.}\)
  2. The identity of \(\mathbb{N}^{\mathbb{N}}\) is the identity function \(i:\mathbb{N}\to \mathbb{N}\) defined by \(i(a) = a\text{,}\) \(\forall a\in \mathbb{N}\text{.}\) If \(a \in \mathbb{N}\text{,}\) \(i(a) = a \leq a\text{,}\) thus the identity of \(\mathbb{N}^{\mathbb{N}}\) is in \(S_1\text{.}\) However, the image of 1 under any function in \(S_2\) is 2, and thus the identity of \(\mathbb{N}^{\mathbb{N}}\) is not in \(S_2\text{,}\) so \(S_2\) is not a submonoid. The composition of any two functions in \(S_1\text{,}\) \(f\) and \(g\text{,}\) will be a function in \(S_1\text{:}\)
    \begin{equation*} \begin{split} (f\circ g)(n) & = f(g(n)) \leq g(n)\textrm{ since } f \textrm{ is in } S_1\\ & \leq n\textrm{ since } g \textrm{ is in } S_1 \Rightarrow f \circ g \in S_1 \end{split} \end{equation*}
    and the two conditions of a submonoid are satisfied and \(S_1\) is a submonoid of \(\mathbb{N}^{\mathbb{N}}\text{.}\)
  3. The first set is a submonoid, but the second is not since the null set has a non-finite complement.

2.

For each subset, describe the submonoid that it generates.
  1. \(\{3\}\) in \([\mathbb{Z}_{12};\times_{12}]\)
  2. \(\displaystyle \{5\} \textrm{ in } [\mathbb{Z}_{25};\times_{25}]\)
  3. the set of prime numbers in \([\mathbb{P}; \cdot ]\)
  4. \(\displaystyle \{3,5\} \textrm{ in } [\mathbb{N}; +]\)

3.

An \(n \times n\) matrix of real numbers is called stochastic if and only if each entry is nonnegative and the sum of entries in each column is 1. Prove that the set of stochastic matrices is a monoid over matrix multiplication.
Answer.
The set of \(n \times n\) real matrices is a monoid under matrix multiplication. This follows from the laws of matrix algebra in Chapter 5. To prove that the set of stochastic matrices is a monoid over matrix multiplication, we need only show that the identity matrix is stochastic (this is obvious) and that the set of stochastic matrices is closed under matrix multiplication. Let \(A\) and \(B\) be \(n \times n\) stochastic matrices.
\begin{equation*} (AB)_{i j}= \sum _{k=1}^n a_{i k} b_{k j} \end{equation*}
The sum of the \(j^{\textrm{th}}\) column is
\begin{equation*} \begin{split} \sum_{j=1}^n (AB)_{i j} & =\sum_{k=1}^n a_{1 k} b_{k j}+\sum_{k=1}^n a_{1k} b_{k j}+\cdots +\sum_{k=1}^n a_{n k} b_{k j}\\ &=\sum_{k=1}^n \left(a_{1 k} b_{k j}+a_{1k} b_{k j}+\cdots +a_{n k} b_{k j}\right)\\ &=\sum _{k=1}^n b_{k j}\left(a_{1 k} +a_{1k}+\cdots +a_{n k} \right)\\ &= \sum _{k=1}^n b_{k j} \quad\textrm{ since } A \textrm{ is stochastic}\\ & = 1 \quad\textrm{ since } B \textrm{ is stochastic}\\ \end{split} \end{equation*}

4.

A semigroup is an algebraic system \([S; *]\) with the only axiom that \(*\) be associative on \(S\text{.}\) Prove that if \(S\) is a finite set, then there must exist an idempotent element, that is, an \(a \in S\) such that \(a * a = a\text{.}\)

5.

Let \(B\) be a Boolean algebra and \(M\) the set of all Boolean functions on \(B\text{.}\) Let \(*\) be defined on \(M\) by \((f * g)(a) = f(a) \land g(a)\text{.}\) Prove that \([M;*]\) is a monoid. Construct the operation table of \([M;*]\) for the case of \(B = B_2\text{.}\)
Answer.
Let \(f, g, h \in M\text{,}\) and \(a \in B\text{.}\)
\begin{equation*} \begin{split} ((f*g)*h)(a) & = (f*g)(a) \land h(a)\\ & = (f(a)\land g(a))\land h(a)\\ & = f(a) \land ( g(a) \land h(a))\\ & = f(a) \land (g * h)(a)\\ & = (f * (g * h))(a)\\ \end{split} \end{equation*}
Therefore \((f * g) * h =f * (g * h)\) and \(*\) is associative.
The identity for \(*\) is the function \(u \in M\) where \(u(a) = 1\) = the “one” of \(B\text{.}\) If \(a \in B\text{,}\) \((f*u)(a) =f(a)\land u(a) = f(a)\land 1 = f(a)\text{.}\) Therefore \(f * u = f\text{.}\) Similarly, \(u * f =f\text{.}\)
There are \(2^2= 4\) functions in \(M\) for \(B = B _2\text{.}\) These four functions are named in the text. See Figure 14.1.4. The table for \(*\) is
\begin{equation*} \begin{array}{c|cccc} * & z & i & t & u\\ \hline z &z & z & z & z \\ i &z & i & z & i \\ t &z & z & t & t \\ u &z & i & t & u \\ \end{array} \end{equation*}
<Prev^TopNext>