Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section14.1Monoids

Recall the definition of a monoid from Chapter 11.

Definition14.1.1Monoid

A monoid is a set \(M\) together with a binary operation \(*\) with the properties

  • \(*\) is associative: \((a*b)*c=a*(b*c) \forall a,b,c \in M\), and

  • \(*\) has an identity in \(M\): \(\exists e\in M\) such that \(a*e=e*a=a \forall a \in M\)

Note14.1.2

Since the requirements for a group contain the requirements for a monoid, every group is a monoid.

Example14.1.3Some Monoids

  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}\), 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})\), \(n\geq 2\), with matrix multiplication, is a monoid. This follows from the fact that matrix multiplication is associative and has an identity, \(I_n\). This is an example of a noncommutative monoid since there are matrices, \(A\) and \(B\), for which \(A B \neq B A\).

  4. \(\left[\mathbb{Z}_n,\times_n\right],n\geqslant 2\), is a monoid with identity 1.

  5. Let \(X\) be a nonempty set. The set of all functions from \(X\) into \(X\), often denoted \(X^X\) , 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. This is another example of a noncommutative monoid, provided \(\lvert X\rvert\) is greater than 1. 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\). 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\).

The functions on \(B_2\)
Figure14.1.4The 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\); that is, it is a monoid with the operation of \(M\). 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\). This submonoid can be defined recursively by the following definition.

Definition14.1.6Submonoid Generated by a Set

If \(S\) is a subset of monoid \([M;*]\), the submonoid generated by \(S\), \(\langle S\rangle\), is defined by:.

  1. (Basis) The identity of \(M\) belongs to \(\langle S\rangle\); and \(a\in S \Rightarrow a\in \langle S \rangle\).

  2. (Recursion) \(a,b\in \langle S\rangle \Rightarrow a*b\in \langle S\rangle\).

Note14.1.7

If \(S=\left\{a_1,a_2,\ldots ,a_n\right\}\), 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\).

Example14.1.8Some Submonoids

  1. One example of a submonoid of \([\mathbb{Z};+]\) is \(\langle 2\rangle =\{0,2,4,6,8,\ldots \}\)

  2. The power set of \(\mathbb{Z},\mathcal{P}(\mathbb{Z}),\) over union is a monoid with identity \(\emptyset\). If \(S=\{\{1\},\{2\},\{3\}\}\),then \(\langle S \rangle\) is the power set of \(\{1,2,3\}\). 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.

Example14.1.9

\(M=[\mathcal{P}\{1,2,3\},\cap ]\) is isomorphic to \(M_2=\left[\mathbb{Z}_2^3;\cdot \right]\), where the operation in \(M_2\) is componentwise mod 2 multiplication. A translation rule is that if \(A\subseteq \{1,2,3\}\), 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} \end{equation*}

A more precise definition of a monoid isomorphism is identical to the definition of a group isomorphism, 11.7.9.

Subsection14.1.1Exercises for Section 14.1

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

  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
2

For each subset, describe the submonoid that it generates.

  1. \(\{3\}\) in \([\mathbb{Z}_{12};\times_{12}]\)

  2. \(\{5\} \textrm{ in } [\mathbb{Z}_{25};\times_{25}]\)

  3. the set of prime numbers in \([\mathbb{P}; \cdot ]\)

  4. \(\{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
4

A semigroup is an algebraic system \([S; *]\) with the only axiom that \(*\) be associative on \(S\). 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\).

5

Let \(B\) be a Boolean algebra and \(M\) the set of all Boolean functions on \(B\). Let \(*\) be defined on \(M\) by \((f * g)(a) = f(a) \land g(a)\). Prove that \([M,*]\) is a monoid. Construct the operation table of \([M,*]\) for the case of \(B = B_2\).

Answer