A semigroup \((S, \cdot)\) consists of a nonempty base set \(S\) and an associative binary operation \(\cdot\) on \(S\). That is, \(x (y z) = (x y) z\) for all \(x, \, y, \, z \in S\).
As in the definition, we often use simple justaposition instead of writing the operator \(\cdot \) explicitly. By the associative property, we can write \(x y z\) without ambiguity for \(x, \, y, \, z \in S\), and of course, this extends to longer finite products. Often \(\cdot\) is used generically as the operator even when there are several semigroups under discussion. Usually the base set is clear from context.
Suppose that \((S, \cdot)\) is a semigroup.
Suppose that \((S, \cdot)\) and \((T, \cdot)\) are semigroups.
A homomorphims preserves the semigroup operation. An isomorphism preserves all semigroup properties, so isomorphic semigroups are essentially the same, except for superficial matters of appearance. The semigroup operation will allow us to shift right
, analogous to shifting forward in time in the standard reliability settings. In turn, this leads to a study of how a shifted probability distribution compares to the original distribution. For this to work properly, we need the following assumption:
We assume that the semigroups \((S, \cdot)\) in this text satisfies the left cancelation law. That is, \(x y = x z\) implies \(y = z\) for \(x, \, y, \, z \in S\).
As we will see, the right cancellation law does not necessary hold for the semigroups we will study. That is, it's possible to have \(x, \, y, \, z \in S\) with \(y x = z x\) but \(y \ne z\). If a semigroup does not have a left identity (so in particular the semigroup does not have an identity), then an identity can be added:
Suppose that \((S, \cdot)\) is a semigroup without a left identity. Let \(e\) be an element not in \(S\) and define \(S_e = S \cup \{e\}\). Extend \(\cdot\) to \(S_e\) by the rule that \(x e = e x = x\) for all \(x \in S_e\). Then \((S_e, \cdot)\) is a semigroup with identity \(e\).
Suppose that \(x, \, y, \, z \in S_e\). The associative property \(x (y z) = (x y) z\) still holds since it holds if \(x, \, y, \, z \in S\) and trivially holds if one (or more) of the elements is \(e\). Suppose next that \(x y = x z\). If \(x, \, y, \, z \in S\) then \(y = z\) by the left cancellation property in \((S, \cdot)\). If \(x = e\) or if \(y = z = e\) then trivially \(y = z\). If \(x, \, y \in S\) and \(z = e\) then \(x y = x\). Hence \(x y u = x u\) for every \(u \in S\) and so by left cancellation \(y u = u\) for every \(u \in S\). But then \(y\) is a left identity in \((S, \cdot)\) in contradiction to our assumption. The case \(y = e\) and \(x, \, z \in S\) leads to the same contradiction.
If \((S, \cdot)\) has a left identity then this procedure would not work because the left cancellation property would be disrupted.
A semigroup \((S, \cdot)\) is commutative or Abelian if \(x y = y x\) for all \(x, \, y \in S\).
Often \(+\) is the generic operator used for commutative semigroups.
Suppose that \((S, \cdot)\) is a semigroup. For \(A, \, B \subseteq S\) define
The following definition is an important special case.
Suppose that \((S, \cdot)\) is a semigroup. For \(x \in S\) and \(A \subseteq S\) define
So for \(x \in S\) and \(A \subseteq S\), the set \(x A\) is an abbreviation for \(\{x\} A\) and \(x^{-1} A\) is an abbreviation for \(\{x\}^{-1} A\). In the latter case, note that we are not defining \(x^{-1}\) individually, but just in combination with a set \(A \subseteq S\), and that \(x^{-1} A\) may be empty, even when \(A\) is nonempty. In particular by the left cancelation law, if \(y \in x S\) then \(x^{-1} \{y\}\) consists of the unique element \(t \in S\) such that \(x t = y\). We denote this element by \(x^{-1} y\), but note again that we are not defining \(x^{-1}\) individually.
Suppose that \((S, \cdot)\) is a semigroup and let \(x \in S\). The mappings \(A \mapsto x^{-1} A\) and \(A \mapsto x A\) preserve all of the set operations. Moreover, for \(x \in S\) and \(A \in \ms S\),
For \(x \in S\), let \(\varphi_x(y) = xy\) for \(y \in S\). By the left cancelation property, \(\varphi_x\) maps \(S\) one-to-one onto \(x S\) for each \(x \in S\). For \(A \in \ms S\) and \(x \in S\), note that \(x^{-1} A = \varphi_x^{-1}(A)\) and \(x A = \varphi_x(A)\). Of course, inverse images preserve the set operations, and since \(\varphi_x\) is one-to-one, so do forward images.
In particulr, \(x (x^{-1} A) = A\) if \(x \in S\) and \(A \subseteq x S\).
For a semigroup, every subset of the base set gives rise to a binary relation and hence a graph.
For \(A \subseteq S\), the graph \((S, \rta_A)\) associated with \((S, \cdot)\) and \(A\) is defined by \(x \rta_A y\) if and only if \(y \in x A\), so that \(y = x a\) for some \(a \in A\). When \(A = S\) we drop the reference to \(A\), so that \((S, \rta)\) is the graph associated with \((S, \cdot)\).
The case \(A = S\) is by far the most important case. Of course, all of the definitions and results for graphs in Chapter 1 hold for the graphs associated with \((S, \cdot)\).
Suppose again that \((S, \cdot)\) is a semigroup and let \(\rta_A\) denote the relation associated with \(A \subseteq S\). Then \(u \rta_A v\) if and only if \(x u \rta_A x v\) for \(x, \, u, \, v \in S\).
Suppose that \(x, \, u, \, v \in S\) and that \(u \rta_A v\). Then there exists \(a \in A\) such that \(u a = v\). But then \(x (u a) = (x u) a = x v\) so \(x u \rta_A x v\). Conversely, suppose that \(x, \, u, \, v \in S\) and that \(x u \rta_A x v\). Then there exists \(a \in A\) such that \((x u) a = x (u a) = x v\). By the left cancelation law, \(u a = v\) so \(u \rta_A v\).
Suppose that \((S, \cdot)\) is a semigroup. For \(x \in S\) and \(A \subseteq S\), the mapping \(u \mapsto x u\) is an isomorphism from the graph \((S, \rta_A)\) to the graph \((x S, \rta_A)\).
By definition, \(u \mapsto x u\) maps \(S\) onto \(x S\). The mapping is one-to-one by the left cancelation property: if \(x u = x v\) for \(u, \, v \in S\) then \(u = v\). Finally, by Proposition , if \(u, \, v \in S\) then \(u \rta_A b\) if and only if \(xu \rta_A x v\).
In particular, for \(x \in S\), the mapping \(u \mapsto x u\) is an isomorphism from the graph \((S, \rta)\) to the graph \((x S, \rta)\).
The \(\sigma\)-algebra associated with the semigroup \((S, \cdot)\) is the \(\sigma\)-algebra associated with the graph \((S, \rta)\), that is, \(\sigma\{x S: x \in S\}\).
Recall that the \(\sigma\)-algebra associated with a graph \((S, \rta)\) is the \(\sigma\)-algebra generated by the collection of (right) neighbor sets. For the semigroup \((S, \cdot)\), the neighbor set of \(x \in S\) is \(x S\).
Suppose that \((S, \cdot)\) is a semigroup and that \(R \subseteq S\). Then \(R\) is closed under \(\cdot\) if \(x, \, y \in R\) implies \(x y \in R\) or equivalently, \(R R \subseteq R\). In this case, \((R, \cdot)\) is a sub-semigroup of \((S, \cdot)\).
So \((R, \cdot)\) is a semigroup under the same operation that makes \(S\) a semigroup. Note that the associative and left cancellation laws hold for \((R, \cdot)\) since they hold for the larger semigroup \((S, \cdot)\).
Suppose again that \((S, \cdot)\) is a semigroup and that \(R \subseteq S\). Then \(R\) is a right ideal of \((S, \cdot)\) if \(R S \subseteq R\).
Of course \(R\) is a left ideal of \((S, \cdot)\) if \(S R \subseteq R\) and \(R\) is a (two-sided) ideal if it is both a left and right ideal.
Trivially a right ideal \(R\) is also a sub-semigroup since \(R R \subseteq R S \subseteq R\). A homomorphism from one semigroup into another defines two natural sub-semigroups, one for the co-domain and one for the domain.
Suppose that \(\varphi\) is a homormphims from a semigroup \((S, \cdot)\) to a semigroup \((T, \cdot)\). Then \((\varphi(S), \cdot)\) is a sub-semigroup of \((T, \cdot)\).
Of course, \(\varphi(S)\) is the range of \(\varphi\). Suppose that \(u, \, v \in \varphi(S)\). Then \(u = \varphi(x)\) and \(v = \varphi(y)\) for some \(x, \, y \in S\). (Of course, \(x\) and \(y\) are not necessarily unique.) Then \(\varphi(x y) = \varphi(x) \varphi(y) = u v\) so \(u v \in \varphi(S)\).
Suppose that \(\varphi\) is a homormphims from a semigroup \((S, \cdot)\) to a semigroup \((T, \cdot)\) that has an identity \(e\). Then \((\ker(\varphi), \cdot)\) is a sub-semigroup of \((S, \cdot)\) where \(\ker(\varphi) = \{x \in S: \varphi(x) = e\}\) is the kernel of \(\varphi\).
Suppose that \(x, \, y \in \ker(S)\). Then \(\varphi(x) = \varphi(y) = e\). Hence \(\varphi(x y) = \varphi(x) \varphi(y) = e e = e\) so \(x y \in \ker(S)\).
The following sub-semigroups will be particularly important in the study of exponential distributions in Section 5.
Suppose that \((S, \cdot)\) is a semigroup. Then \(x S\) is a right ideal (and hence a sub-semigroup) for each \(x \in S\).
For \(x \in S\) note that \((x S) S = x (S S) \subseteq x S\).
Suppose that \((S, \cdot)\) is a semigroup and that \(A \subseteq S\). The sub-semigroup \((\langle A \rangle, \cdot)\) generated by \(A\) is the smallest sub-semigroup of \((S, \cdot)\) containing \(A\). That is, \[\langle A \rangle = \bigcap\{T: (T, \cdot) \text{ is a sub-semigroup of } (S, \cdot) \text{ and } A \subseteq T\} \]
As defined, \(\langle A \rangle\) is closed under the semigroup operation: If \(x, \, y \in \langle A \rangle\) then \(x, \, y \in T\) for every sub-semigroup \((T, \cdot)\) of \((S, \cdot)\) that contains \(A\). Hence \(x y \in T\) for every such sub-semigroup and so \(x y \in \langle A \rangle\). Moreover, \(A \subseteq \langle A \rangle\) and if \((T, \cdot)\) is a sub-semigroup with \(A \subseteq T\) then \(\langle A \rangle \subseteq T\).
Suppose again that \((S, \cdot)\) is a semigroup and that \(A\) is a nonempty subset of \(S\). Then \(\langle A \rangle\) is the set of all finite products of elements in \(A\). That is, \[\langle A \rangle = \{a_1 a_2 \cdots a_n: n \in \N_+ \text{ and } a_i \in A \text{ for } i \in \{1, 2, \ldots n\}\}\]
Let \(R\) denote the set of finite products of elements of \(A\) as defined. Then clearly \(R\) is closed under the semigroup operation and \(A \subseteq R\). Hence \(\langle A \rangle \subseteq R\). On the other hand, since \(\langle A \rangle\) is closed under the semigroup operation, \(R \subseteq \langle A \rangle\).
A finite product \(a_1 a_2 \cdots a_n\) where \(n \in \N_+\) and \(a_i \in A\) for \(i \in \{1, 2, \ldots n\}\) is called a word on \(A\). So \(\langle A \rangle\) consists of all words on \(A\). Of course, the representation of an element \(x \in \langle A \rangle\) as a word on \(A\) is not necessarily unique, as shown in .
Suppose that \((S, \cdot)\) is a semigroup and that \(x \in S\). The semigroup generated by \(\{x\}\) is abbreviated \((\langle x \rangle, \cdot)\) where \(\langle x \rangle = \{x^n: n \in \N_+\}\).
If \((S, \cdot)\) does not have an identity then it's possible that \(x^n = x^m\) for distinct \(m, \, n \in \N_+\). However, if \((S, \cdot)\) has an identity \(e\) and \(x \ne e\) then \(x^m \ne x^n\) for distinct \(m, \, n \in \N_+\).
Suppose that \((S, \cdot)\) is a semigroup and that \(R \subseteq S\). The graph \((S, \rta_R)\) associated with \((S, \cdot)\) and \(R\) is transitive if and only if \((R, \cdot)\) is s sub-semigroup.
Suppose that \(R\) is closed under \(\cdot\), and that \(x, \, y, \, z \in S\) with \(x \rta_R y\) and \(y \rta_R z\). Then there exists \(s, t \in R\) such that \(y = x s\) and \(z = y t\). Hence \(z = (x s) t = x (s t)\). But \(s t \in R\) so \(x \rta_R z\). Conversely, suppose that \(\rta_R\) is transitive and that \(x, \, y \in R\). Then \(x \rta_R x^2\) and \(x^2 \rta_R x^2 y\). Hence \(x \rta_R x^2 y\), so there exists \(t \in R\) with \(x t = x^2 y = x (x y)\). By left cancelation, \(t = x y\) so \(x y \in R\).
In particular, the graph \((S, \rta)\) associated with \((S, \cdot)\) (that is, \(R = S\)) is transitive, and so graphs associated with semigroups are somewhat special compared with the more general graphs studied in Chapter 1.
Suppose that \((S, \cdot)\) is a semigroup and that \(\rta\) is the associated relation. A sub-semigroup \((T, \cdot)\) of \((S, \cdot)\) is (algebraically) complete if \(x, \, y \in T\) and \(x \rta y\) implies \(x^{-1} y \in T\).
Equivalently, if \((T, \cdot)\) is complete and \(\rta_T\) denotes the relation associated with \((T, \cdot)\), then as sets of ordered pairs, \(\rta_T\) is the intersection of \(\rta\) with \(T \times T\). We have emphasized that the definition of complete, like the definition of closed earlier, are in an algebraic sense, not a topological sense.
Semigroups, as the name implies, often come from a richer algebraic structure known as a group.
A Group \((S, \cdot)\) consists of a base set \(S\) and a binary operation \(\cdot\) on \(S\) satisfying the following properties.
A group \((S, \cdot)\) satisfies the left and right cancellation laws. That is, for \(x, \, y, \, z \in S\),
This follows from the basic properties: If \(x y = x z\) then \(x^{-1} (x y) = x^{-1} (x z)\). By the associative and identity properties, the left side is \((x^{-1} x) y = e y = y\) and the right side is \((x^{1} x) z = e z = z\). The proof for the right cancellation law is similar.
Hence a group is also a semigroup, as we have defined the term, and so all of the definitions and properties in the subsections above apply to groups.
Supposse that \((S, \cdot)\) is a group. Then \(x^{-1} A = \{x^{-1} a: a \in A\}\) for \(x \in S\) and \(A \subseteq S\).
So the notation introduced in Definition is consistent. In particular, \(x^{-1} y\) is the product of \(x^{-1}\) and \(y\) for \(x, \, y \in S\) and this is the unique element \(u \in S\) with \(x u = y\). More generally, for \(A \subseteq S\) define \(A^{-1} = \{a^{-1}: a \in A\}\). Then \(A^{-1} B\) is the product of \(A^{-1}\) with \(B\) as defined in , so again the notation is consistent.
If \((S, \cdot)\) is a group then the associated graph is the complete reflexive graph \((S, \equiv)\) so that \(x \equiv y\) for every \(x, \, y \in S\).
For \(x, \, y \in S\) note that \(x (x^{-1} y) = y\).
The complete graph is generally not interesting for the reliability concepts that we have in mind, and this is why our interest is primarily in semigroups that are not groups. However, many of the semigroups that we will study (but certainly not all) are sub-semigroups of an underlying group. By , the left and right cancellation laws are clearly necessary for a semigroup to be embedded in a group, but are not sufficient. Here are a couple of classical results from group theory:
Suppose that \((S, \cdot)\) is a finite semigroup that satisfies both cancellation laws. Then \((S, \cdot)\) is a group.
Suppose that \((S, \cdot)\) is a communtative semigroup that satsifies the cancellation laws. Then \((S, \cdot)\) is a sub-semigroup of a group \((G, \cdot)\).
Suppose now that \((S, \ms S)\) is a measurable space. Recall that \(S^n\) is given the product \(\sigma\)-algebra \(\ms S^n\) for \(n \in \N_+\). Recall also that in the discrete case, \(S\) is countable and \(\ms S\) is the collection of all subsets of \(S\).
A semigroup \((S, \cdot)\) is a measurable semigroup if the graph \((S, =)\) is measurable and the mapping \((x, y) \mapsto x y\) is measurable.
So a measurable semigroup must be on a space with a measurable diagonal, as discussed in the Preface. The reason for this extra condition is given in the following important result: we want the graphs associated with a measurable semigroup to be measurable.
Suppose that \((S, \cdot)\) is a measurable semigroup. Then the graph \((S, \rta_A)\) is measurable for each \(A \in \ms S\).
For \(A \in \ms S\) define \(\varphi_A(x, y) = x y\) for \(x \in S\) and \(y \in A\) so that \(\varphi_A: S \times A \to S\). Since \(S\) has a measurable diagonal, the graph of \(\varphi_A\) is measurable. That is, \[\{(x, y, x y): x \in S, y \in A\} \in \ms S^3\] Hence \(\{(x, x y): x \in S, y \in A\} \in \ms S^2\), and this is the graph \((S, \rta_A)\).
In particular, the graph \((S, \rta)\) associated with \((S, \cdot)\) (corresponding to \(A = S\)) is measurable. Of course, all of the results in the Chapter 1 on measurable graphs apply to \((S, \rta_A)\) for \(A \in \ms S\) and in particular to \((S, \rta)\). As a further corollary of , it follows that if \(x \in S\) and \(A \in \ms S\) then \(x A \in \ms S\) and \(x^{-1} A \in \ms S\). Suppose now that \(\lambda\) is a \(\sigma\)-finite reference measure on \((S, \ms S)\). Recall that in the discrete case, \(\lambda = \#\) is counting measure, and in the Euclidean case, \(\lambda\) is Lebesgue measure.
Suppose again that \((S, \cdot)\) is a semigroup and that \(A \in \ms S\). The following functions from \(S\) to \([0, \infty)\) are measurable:
These results are a direct consequence of .
Groups require two natural conditions for measurability and the consequences help explain further the need for the measurable diagonal condition for semigroups.
A group \((S, \cdot)\) is a measurable group if the mapping \((x, y) \mapsto x y\) from \(S^2\) to \(S\) and the mapping \(x \mapsto x^{-1}\) from \(S\) to \(S\) are measurable. A measurable group is a measurable semigroup.
The function \(g: S^2 \to S\) defined by \(g(x, y) = x y^{-1}\) is measurable. If \(e\) denotes the identity then \[g^{-1}\{e\} = \{(x, y) \in S^2: x y^{-1} = e\} = \{(x, y) \in S^2: x = y\} \in \ms S^2\] and hence \((S, =)\) is measurable.
Assume now that \(S\) has an LCCB topology and that \(\ms S\) is the corresponding Borel \(\sigma\)-algebra (that is, the \(\sigma\)-algebra generated by the topology). The product set \(S^n\) is given the product topology and corresponding Borel \(\sigma\)-algebra for \(n \in \N_+\), which as noted in the Preface is the product \(\sigma\)-algebra \(\ms S^n\). Also of course, the topological properties automatically apply in the discrete case, corresponding to the discrete topology.
A semigroup \((S, \cdot)\) is a topological semigroup if the mapping \((x, y) \mapsto x y\) from \(S^2\) to \(S\) is continuous. A topological semigroup is measurable.
Since mapping \((x, y) \mapsto x y\) is continuous, it is measurable. Also, since the space is Hausdorff, the diagonal \(\{(x, x): x \in S\}\) is closed and hence measurable.
So all of the results in the previous subsection apply. In a topological semigroup, the semigroup operation preserves many basic topological properties.
Suppose that \((S, \cdot)\) is a topological semigroup.
We denote the topological closure of \(A \subseteq S\) by \(\cl(A)\). There exists a metric that generates the topology on \(S\) and so \(x \in \cl(A)\) if and only if there exists \(x_n \in A\) for \(n \in \N_+\) with \(x_n \to x\) as \(n \to \infty\).
Suppose again that \((S, \cdot)\) is a topological semigroup. If \((T, \cdot)\) is a sub-semigroup of \((S, \cdot)\) then \((\cl(T), \cdot)\) is also a sub-semigroup.
Suppose that \(x, \, y \in \cl(T)\). Then there exists \(x_n, \, y_n \in T\) for \(n \in \N_+\) such that \(x_n \to x\) and \(y_n \to y\) as \(n \to \infty\). But then \(x_n y_n \in T\) for \(n \in \N_+\) and by continuity, \(x_n y_n \to x y\) as \(n \to \infty\). Hence \(x y \in \cl(T)\)
The following definitions are from Székely:
Suppose again that \((S, \cdot)\) is a topological semigroup.
In particular, \((S, \cdot)\) has dimension 0 if there are no non-trivial continuous homomorphisms from \((S, \cdot)\) to \((\R, +)\) and \((S, \cdot)\) has dimension \(\infty\) if for every finite subset of \(S\) there exists a nontrivial continuous homomorphism from \((S, \cdot)\) into \((\R,\,+)\) which maps the finite subset onto 0. For groups, we need to add another natural condition, just as we did for measurability.
A group \((S, \cdot)\) is a topological group if the mapping \((x, y) \mapsto x y\) from \(S^2\) to \(S\) and the mapping \(x \mapsto x^{-1}\) from \(S\) to \(S\) are continuous.
Suppose that \((S, \cdot)\) is a topological group and that \((T, \cdot)\) is a sub-semigroup of \((S, \cdot)\) with \(T \subseteq S\) closed. Then the graph \((T, \rta)\) associated with \((T, \cdot)\) is closed.
Recall that \(T\) is given the relative topology and \(T^2\) the corresponding product topology. The statement that \((T, \rta)\) is closed means that \(\rta\) as a subset of \(T^2\) is closed. So suppose that \(x_n, \, y_n \in T\) with \(x_n \rta y_n\) for \(n \in \N_+\) and that \(\lim_{n \to \infty} x_n = x \in T\) and \(\lim_{n \to \infty} y_n = y \in T\). We need to show that \(x \rta y\). By assumption, there exists \(t_n \in T\) with \(x_n t_n = y_n\) for \(n \in \N_+\). Since we are in a group, \(t_n = x_n^{-1} y_n\) for \(n \in \N_+\) and by continuity, \(\lim_{n \to \infty} t_n = x^{-1} y\). Since \(T\) is closed, \(x^{-1} y \in T\). So then \(y = x (x^{-1} y\) so \(x \rta y\).
All of the groups and semigroups in this subsection are topological, with the Euclidean topology for the continuous spaces and the discrete topology for the discrete spaces.
The space \((\R, +)\) is a commutative group where \(+\) is ordinary addition. The identity element is 0 and the inverse of \(x \in \R\) is \(-x\).
The space \(((0, \infty), \cdot)\) is a commutative group where \(\cdot\) is ordinary multiplication. The identity element is 1 and the inverse of \(x \in (0, \infty)\) is \(1 / x\).
The group and semigroups in are isomorphic to the group and semigroups in with isomorphism \(x \mapsto e^x\) from \(\R\) onto \((0, \infty)\). These semigroups and other related spaces are studied in Chapter 3.
The space \((\Z, +)\) is a subgroup of of the group \((\R, +)\). The space \((\N, +)\) is a sub-semigroup with associated graph \((\N, \le)\).
The semigroup \((\N, +)\) and other related spaces are studied in Chapter 4.
The space \((\N_+, \cdot)\) is a sub-semigroup of the group \(((0, \infty), \cdot)\) where \(\cdot\) is ordinary multiplication. The associated graph is \((\N_+, \preceq)\) where \(\preceq\) is the division relation.
That is, \(x \preceq y\) if and only if \(x\) divides \(y\) so that \(y / x = z\) for some \(z \in \N_+\).
The semigroup \((\N_+, \cdot)\) and other related spaces are studied in Chapter 6.
For \(m, \, n \in \N_+\), recall that \(\R^{m \times n}\) denotes the set of \(m \times n\) matrices with elements in \(\R\).
For \(m, \, n \in \N_+\), the space \((\R^{m \times n}, +)\) is a commutative group where \(+\) is ordinary matrix addition. The identity element is \(\bs{0}\) and the inverse of \(\bs{x} \in \R^{m \times n}\) is \(- \bs{x}\). The space \(([0, \infty)^{m \times n}, +)\) is a sub-semigroup with associated graph \(([0, \infty)^{m \times n}, \le)\).
Recall that \(+\) is component-wise addition and \(-\bs x\) is also component-wise. The identity element \(\bs{0}\) is the \(m \times n\) matrix each of whose components is 0. Finally, the partial order \(\le\) is component-wise.
For \(n \in \N_+\), the determinant of \(\bs{x} \in \R^{n \times n}\) is denoted \(\det(\bs{x})\).
For \(n \in \N_+\), let \(M_n = \{ \bs{x} \in \R^{n \times n}: \det(\bs{x}) \gt 0\}\). The space \((M_n, \cdot)\) is a group, where \(\cdot\) is ordinary matrix multiplication.
Recall that \(\det(\bs x \bs y) = \det(\bs x) \det(\bs y)\) for \(\bs x, \, \bs y \in M_n\). The identity element \(e\) is the diagonal matrix with 1 for each diagonal entry. Note that the group \((M_n, \cdot)\) is non-commutative for \(n \ge 2\).
For \(n \in \N_+\), the following are sub-semigroups of \((M_n, \cdot)\):
Recall that \(\det(\bs x^{-1}) = 1 / \det(\bs x)\) for \(x \in M_n\).
The larger group \((G_n, \cdot)\) where \(G_n = \{\bs x \in \R^{n \times n}: \det(\bs x) \ne 0\}\) (and again \(\cdot\) is matrix multiplication) is the general linear group of order \(n\). We use the group in Proposition and semigroups in Proposition because they are more analogous to the group and semigroups in Proposition .
For \(n \in \N_+\), the following are subgroups of the group \((M_n, \cdot)\):
Recall that \(\bs x \in R^{n \times n}\) is upper triangular if all of the entries below the main diagonal are 0, and similarly \(\bs x\) is lower triangular if all of the entries above the main diagonal are 0. In both cases, \(\det(\bs x)\) is the product of the diagonal entries. A matrix \(\bs x \in \R^{n \times n}\) is orthogonal if \(\bs x^{-1} = \bs x^T\) where \(\bs x^T\) is the transpose of \(\bs x\). Equivalently, the columns and rows of \(\bs x\) are orthonormal vectors in \(\R^n\). If \(\bs x \in M_n\) is orthogonal then \(\det(\bs x) = 1\).
Let \(A\) be a nonempty countable set of letters and let \(S = A^*\) denote the set of finite words over \(A\) (that is, finite strings of letters from \(A\)). Then \((S, \cdot)\) is a semigroup where \(\cdot\) is concatenation. It is known as the free semigroup over \(A\). The associated graph is \((S, \preceq)\) where \(x \preceq y\) if and only if \(x\) is a prefix of \(y\).
So two words (elements of \(S\)) are the same if and only if they have the same letters in the same order. The empty word \(e\) with no letters is the identity.
The free semigroup over \(A\) satisfies both cancellation laws. If \(A\) has at least two elements then the semigroup is noncommutative. In particular, the free semigroup over \(\{0, 1\}\) consists of finite bit strings. The term free is used becaue there are no algebra rules
imposed on the strings of letters.
Suppose that \((S, \cdot)\) is the free semigroup over the alphabet \(A\) as above. For \(x \in S\) let \(l(x)\) denote the length of \(x\), that is, the number of letters in \(x\). Then \(l\) is a homomorphism from \((S, \cdot)\) into \((\N, +)\).
Trivially, \(l(x y) = l(x) + l(y)\) for \(x, \, y \in S\).
The free semigroup and other related spaces are studied in Chapter 5. A free semigroup can be embedded in a free group by adding an inverse
\(a^{-1}\) for every \(a \in A\) and extending \(\cdot\) by the rule that \(a a^{-1} = a^{-1} a = e\) for every \(a \in A\).
The following example describes a trivial semigroup, but one that is nonetheless useful for certain constructions and counterexamples.
Define the binary operation \(\cdot\) on \(S\) by \(x y = y\) for all \(x, \, y \in S\). Then \((S, \cdot)\) is a semigroup, called the right zero semigroup. The associated relation \(\equiv\) is the complete reflexive relation on \(S\): \(x \equiv y\) for all \(x, \, y \in S\).
As the name suggests, every element of \(S\) is a right zero. The associative rule holds: \(x (y z) = x z = z\) and \((x y) z = y z = z\) for \(x, \, y, \, z \in S\). The left cancellation rule holds: if \(x y = x z\) for \(x, \, y, \, z \in S\) then by definition, \(y = z\).
If \(S\) has at least two elements then the right zero semigroup does not satisfy the right cancellation law, and hence is not a sub-semigroup of a group.
Suppose that \((S, \cdot)\) is a right zero semigroup. Then \((A, \cdot)\) is a sub-semigroup every \(A \in \ms{S}\) and is also a right zero semigroup.
If \(x, \, y \in A\) then \(x y = y \in A\).
So in the context of this example, \((A, \cdot)\) is the sub-semigroup generated by \(A\) for every \(A \in \ms{S}\). If \(x \in A\) then \(x = x_1 x_2 \cdots x_{n - 1} x\) for every choice of \(n \in \N_+\) and \(x_i \in A\) for \(i \in \{1, 2, \ldots n - 1\}\). In particular, \(x^n = x\) for every \(n \in \N_+\).
Suppose that \(A\) is a nonempty set. Let \(\ms T_A\) denote the set of all one-to-one functions from \(A\) into \(A\), and as usual, let \(\circ\) denote composition of functions. Then \((\ms T_A, \circ)\) is a semigroup, known as the transformation semigroup on \(A\). The identity function \(e\) on \(A\) is the identity element.
Suppose that \(f, \, g \in \ms T_A\). Then of course \(f \circ g: A \to A\). Moreover, if \((f \circ g)(x) = (f \circ g)(y) \) for \(x, \, y \in A\). Then \(f(g(x)) = f(g(y))\). Since \(f\) is one-to-one, \(g(x) = g(y)\). Since \(g\) is one-to-one, \(x = y\). Hence \(f \circ g\) is one-to-one so \(f \circ g \in \ms T_A\). As every student knows, composition of functions is associative. That is, if \(f, \, g, \, h \in \ms T_A\) then \(f \circ (g \circ h) = (f \circ g) \circ h\) and the common value at \(x \in A\) is \(f(g(h(x)))\). Next, suppose that \(f, \, g, \, h \in \ms T_A\) and \(f \circ g = f \circ h\). Then \((f(g(x)) = f(h(x))\) for \(x \in A\). Since \(f\) is one-to-one, \(g(x) = h(x)\) for \(x \in A\) and hence the left cancellation law holds. The identity function \(e: A \to A\) is defined by \(e(x) = x\) for \(x \in A\). Clearly \(e \in \ms T_A\) and \(e \circ f = f \circ e = f\) for \(f \in \ms T_A\).
The full transformation semigroup on \(A\) consists of all functions from \(A\) to \(A\) (again with composition as the operator). However, this semigroup does not satisfy the left cancellation law, which as we have stated, is essential for the reliability concepts that we have in mind. A transformation semigroup has a natural subgroup.
Suppose again that \(A\) is a nonempty set and let \(\ms T^\prime_A\) denote the set of all one-to-one functions from \(A\) onto \(A\). Then \((\ms T^\prime_A, \circ)\) is a subgroup of \((\ms T_A, \circ)\). The inverse of \(f \in \ms T^\prime_A\) is the ordinary inverse function \(f^{-1}\).
If \(f\) maps \(A\) one-to-one onto \(A\) then the inverse function \(f^{-1}\) is well defined and also maps \(A\) one-to-one onto \(A\). Moreover, \(f \circ f^{-1} = f^{-1} \circ f = e\), the identity function on \(A\).
Transformation semigroups are universal:
If \((S, \cdot)\) is a semigroup with an identity element then \((S, \cdot)\) isomorphic to a sub-semigroup of \((\ms T_S, \circ)\).
For \(x \in S\) define \(f_x: S \to S\) by \(f_x(y) = x y\) for \(y \in S\). So \(f_x: S \to x S\) for \(x \in S\). If \(f_x(y) = f_x(z)\) for \(y, \, z \in S\) then \(x y = x z\) and hence \(y = z\) by the left cancellation law. Hence \(f_x\) is one-to-one for \(x \in S\) and so the set \(\ms T = \{f_x: x \in S\}\) is a subset of \(\ms T_S\). Moreover, \((f_x \circ f_y)(u) = f_x(f_y(u)) = f_x(y u) = x (y u) = (x y) u\) for \(x, \, y, \, u \in S\) and so \(f_x \circ f_y = f_{x y}\). Therefore \(\ms T_S\) is closed under \(\circ\) so \((\ms T, \circ)\) is a sub-semigroup of \((\ms T_S, \circ)\). Finally, suppose that \(f_x = f_y\) for \(x, \, y \in S\). Then \(f_x(u) = x u = f_y(u) = y u\) for \(u \in S\). Letting \(u = e\) gives \(x = y\). Hence the mapping \(x \mapsto f_x\) from \(S\) onto \(\ms T\) is one-to-one and so is an isomorphism from \((S, \cdot)\) to \((\ms T, \circ)\).