Positive semigroups are a particularly important class of semigroups, since the underlying relation is a partial order, and so the structure more closely aligns with the standard reliability setting. As usual, our starting point is a measurable space \((S, \ms S)\). Semigroups are assumed to be measurable and satisfy the left cancellation property, as discussed in Section 1.
Suppose that \((S, \cdot)\) is a semigroup.
Recall that a semigroup is assumed to satisfy the left cancellation law. Note that a strict positive semigroup cannot have an idempotent element and hence cannot have an identity (left, right or two-sided) or a zero (left, right, or two-sided).
A strict positive semigroup can be made into a positive semigroup with the addition of an identity element.
Suppose that \((S_+, \cdot)\) is a strict positive semigroup. Let \(e\) be an element not in \(S\) and define \(S = S_+ \cup \{e\}\). Extend \(\cdot\) to \(S\) by the rule that \(x e = e x = x\) for all \(x \in S\). Then \((S, \cdot)\) is a positive semigroup.
This follows from the more general result in Section 1 since \((S_+, \cdot)\) does not have a left identity. In terms of the measure theory, suppose that \((S_+, \ms S_+)\) is the underlying measure space. We define \(\ms S\) by adding to \(\ms S_+\) all sets of the form \(A \cup \{e\}\) where \(A \in \ms S_+\).
Note that the algebraic assumptions of a positive semigroup do not rule out the possibility that \(x y = y\) for some \(x, \, y \in S\) with \(x \ne e\). A positive semigroup has no nontrivial inverses.
Suppose that \((S, \cdot)\) is a positive semigroup with identity \(e\). Then \(x y = e\) if and only if \(x = y = e\)
Trivially if \(x = y = e\) then \(x y = e\) since \(e\) is an identity. If \(x \ne e\) and \(y \ne e\) then \(x y \ne e\) since \(S_+\) is algebraically closed. If \(x = e\) and \(y \ne e\) then \(x y = y \ne e\). Finally if \(x \ne e\) and \(y = e\) then \(x y = x \ne e\).
If \((S, \cdot)\) is a positive semigroup then a product over an empty index set is interpreted as the identity \(e\). In particular, \(x^0 = e\) for \(x \in S\).
The positive sub-semigroup generated by \(x \in S_+\) has base set \(\langle x \rangle = \{x^n: n \in \N_+\}\). This semigroup is isomorphic to the standard discrete semigroup \((\N_+, +)\), with isomorphism \(n \mapsto x^n\).
Suppose that \(m, \, n \in \N\) with \(m \lt n\) and that \(x^m = x^n\). Then \(x^m e = x^m x^{n - m}\) and so by left cancelation, \(e = x^{b - n}\). But then \(x = e\) by repeated applications of , a contradiction. Hence the mapping \(n \mapsto x^n\) is one-to-one and onto. Of course also \((m + n) \mapsto x^{m + n} = x^m x^n\) for \(m, \, n \in \N\).
The following result is the reason that positive semigroups have special importance.
Suppose that \((S, \cdot)\) is a positive semigroup with identity \(e\), and that \((T, \cdot)\) is a sub-semigroup.
Since \(T\) is algebraically closed, the relation associated with \((S, \cdot)\) and \(T\) is transitive from Section 1.
The most important case is when \(T = S\) and as usual, we drop the subscript so that the relation \(\preceq\) associated with \((S, \cdot)\) is a partial order. In the case that \(T = S_+\), the associated relation is the corresponding strict partial order \(\prec\), so again we drop the subscript. At the other extreme, when \(T = \{e\}\), the associated relation is equality \(=\). Of course all of the definitions and results in Section 2.1 on partial order graphs apply to \((S, \preceq_T)\) but we will repeat some of these in terms of the semigroup operator. Note first that the identity \(e\) is the minimum element of \((S, \preceq)\) since \(e \preceq x\) for every \(x \in S\).
Suppose again that \((S, \cdot)\) is a positive semigroup and that \(A \subseteq S\). Then relative to the graph \((S, \preceq)\),
All three results follow form the definitions, since \(u \preceq v\) if and only if \(v \in u S\) for \(u, \, v \in S\).
Suppose that \((S, \cdot)\) is a positive semigroup with associated partial order \(\preceq_S\) and that \((T, \preceq_T)\) is another partial order graph. Suppose also that \(f: S \to T\). Then relative to the partial orders,
Again, the results follow from the definitions since \(x \preceq_S x y\) for \(x, \, y \in S\).
Suppose that \((S, \cdot)\) is a positive semigroup with associated partial order \(\preceq\). By the result in Section 1, for fixed \(x \in S\), the mapping \(y \mapsto x y\) is an isomorphism from the graph \((S, \preceq)\) to the graph \((x S, \preceq)\).
In this subsection, we assume that \((S, \cdot)\) is a discrete positive semigroup with associated partial order \(\preceq\).
An element \(i \in S\) is irreducible if \(i\) cannot be factored \(i = x y\) for \(x, \, y \in S\), except for the trivial factoring \(i = e i = i e\).
The covering graph of \((S, \preceq)\) can be characterized in terms of the irreducible elements.
If \(x, \, y \in S\) then \(y\) covers \(x\) if and only if \(y = x i\) for some irreducible element \(i\). That is, the covering relation is the relation associated with \(I\), the set of irreducible elements of \((S, \cdot)\).
Suppose that \(y\) covers \(x\). Then \(x \prec y\) so there exists \(i \in S_+\) with \(y = xi\). If \(i = a b\) for some \(a, \, b \in S_+\) then \(x \prec x a \prec x a b = y\) which would be a contradiction. Thus, \(i\) has no non-trivial factorings and hence is irreducible. Conversely, suppose that \(y = x i\) for some irreducible element \(i\). Then \(x \prec y\). Suppose there exists \(u \in S\) with \(x \prec u \prec y\). Then \(u = x s\) and \(y = u t\) for some \(s, \, t \in S_+\). Thus \(y = x s t = x i\) so by left cancellation, \(i = s t\). But this is a contradiction since \(i\) is irreducible, so \(y\) covers \(x\).
Suppose that \((S, \cdot)\) is left finite with \(I\) as the set of irreducible elements. Then \(x \in S\) can be factored finitely over \(I\) for every \(x \in S\). That is, \(x = i_1 i_2 \cdots i_n\) for some \(n \in \N\) where \(i_k \in I\) for \(k \in \{1, 2, \ldots, n\}\).
Recall that left finite means that the corresponding partial order graph is well founded, and hence does not have an infinite descending chain. Hence for \(x \in S\), there exists a finite walk in the covering graph from \(e\) to \(x\), say \((x_0, x_1, x_2, \ldots, x_n)\) where \(n \in \N\), \(x_0 = e\), \(x_n = x\), and \(x_{k + 1}\) covers \(x_k\) for each \(k \in \{0, 1, \ldots n - 1\}\). But then \(x_{k + 1} = x_k i_k\) for each \(k\) where \(i_k \in I\). Hence \(x = i_1 i_2 \cdots i_n\).
Of course, the factoring of \(x\) over \(I\) is not necessarily unique, and different factorings of \(x\) over \(I\) may have different lengths. If a partial order graph \((S, \preceq)\) is associated with a positive semigroup, then \((S, \preceq)\) is uniform if and only if, for each \(x\), all factorings of \(x\) over \(I\) (the set of irreducible elements) have the same length.
Suppose again that \((S, \cdot)\) is left finite. Then \(\dim(S, \cdot) \le \#(I)\).
Suppose that \(\varphi\) is a homomorphism from \((S, \cdot)\) into \((\R, +)\) and that \(\varphi(i) = 0\) for each \(i \in I\). If \(x \in S\), then from Proposition , \(x\) can be factored over \(I\) so that \(x = i_1 i_2 \cdots i_n\) where \(i_k \in I\) for each \(k\). But then \[\varphi(x) = \varphi(i_1) + \varphi(i_2) + \cdots + \varphi(i_n) = 0\] Hence \(I\) is a critical set and so \(\dim(S, \cdot) \le \#(I)\)
We can certainly have \(\dim(S, \cdot) \lt \#(I)\). The semigroup corresponding to the subset partial order on finite subsets of \(\N_+\) studied in Chapter 9 has infinitely many irreducible elements but the semigroup dimension is 1. For a positive semigroup, there are two definitions for dimension, one corresponding to the semigroup itself, and one corresponding to the corresponding graph. How are they related?
How are \(\dim(S, \cdot)\) and \(\dim(S, \preceq)\) related?
In this subsection we assume that \((S, \cdot)\) is a discrete, left-finite positive semigroup with identity \(e\). So the theory of Möbius inversion in Section 1.2 applies to the associated partial order graph \((S, \preceq)\).
Let \(M\) denote the Möbius kernel of \((S, \preceq)\). Then \(M(x, y) = M(t x, t y)\) for \(x, \, y, \, t \in S\).
The fact that \((S, \cdot)\) is left finite means that the Möbius kernel is well defined and that \((S, \preceq)\) is well founded so that we can use partial order induction. Let \(x, \, y, \, t \in S\). First, \(x \preceq y\) if and only if \(t x \preceq t y\) so it follows that if \(x \npreceq y\) then \(M(x, y) = 0 = M(t x, t y)\). Next, \(M(x, x) = 1 = M(t x, t x)\). Suppose now that \(x \prec y\). Recall that \(u \mapsto t u\) maps \([x, y)\) one to one and onto \([t x, t y)\). For the induction hypothesis, suppose that \(M(x, u) = M(t x, t u)\) for all \(u \prec y\). Then \[M(t x, t y) = -\sum_{z \in [t x, t y)} M(t x, z) = -\sum_{u \in [x, y)} M(t x, t u) = -\sum_{u \in [x, y)} M(x, u) = M(x, y)\]
The result is to be expected because of the self-similarity property of a positive semigroup. It follows that the general Möbius kernel \(M\) can be obtained from a simpler function.
The Möbius function \(\mu\) of \((S, \cdot)\) is defined by \(\mu(t) = M(e, t)\) for \(t \in S\), and is defined inductively as follows:
The Möbius kernel \(M\) is related to the Möbius function \(\mu\) by \[M(x, y) = \mu(x^{-1} y), \quad x \preceq y\]
Often (but not always) the positive semigroups that are of interest to us are embedded in groups. Suppose that \((G, \cdot)\) is a group and that \((S, \cdot)\) is a positive, sub-semigroup of \((G, \cdot)\). We can think of \(S\) as a set of positive elements of \(G\) and \(S_+ = S - \{e\}\) as the corresponding set of strictly positive elements of \(G\). Often we are interested in a maximal set of positive elements in a sense.
Suppose that \((G, \cdot)\) is a group. A positve, sub-semigroup \((S, \cdot)\) is maximal if \((S, \cdot)\) is not a sub-semigroup of a proper subgroup of \((G, \cdot)\).
In the case of a commutative group, a positive sub-semigroup is maximal if and only if we can write each element of the group as the difference between positive elements.
Suppose that \((G, +)\) is a commutative group and that \((S, +)\) is a positive sub-semigroup. Let \(H = \{u - v: u, \, v \in S\}\). Then
Many of the semigroup examples in Section 1 are positive semigroups.
The space \(([0, \infty), +)\) is a maximal positive sub-semigroup of the commutative group \((\R, +)\). The associated order is the total order \(\le\).
Trivially we can write \(x \in \R\) as \(x = u + v\) where \(u, \, v \in [0, \infty)\). In fact, either \(x \in [0, \infty)\) or \(-x \in [0, \infty)\).
The space \(([1, \infty), \cdot)\) is a maximal positive sub-semigroup of the commutative group \((0, \infty), \cdot)\). The associated order is the total order \(\le\).
Trivially we can write \(x \in (0, \infty)\) as \(x = u v\) where \(u, \, v \in [1, \infty)\). In fact, either \(x \in [1, \infty)\) or \(1 / x \in [1, \infty)\).
The group and semigroup in are isomorphic to the group and semigroup 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 \((\N, +)\) is a maximal positive sub-semigroup of the commutative group \((\Z, +)\). The associated order is the total order \(\le\).
Trivially we can write \(x \in \Z\) as \(x = u + v\) where \(u, \, v \in \N\). In fact, either \(x \in \N\) or \(-x \in \N\).
The semigroup \((\N, +)\) and other related spaces are studied in Chapter 4.
The space \((\N_+, \cdot)\) is a positive semigroup where \(\cdot\) is ordinary multiplication. The associated partial order \(\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.
The free semigroup \((S, \cdot)\) over a countable alphabet \(A\) is a positive semigroup. The associated partial order \(\preceq\) is defined by \(x \preceq y\) if and only if \(x\) is a prefix of \(y\).
Recall that \(S\) consists of finite words over \(A\) (strings of letters from \(A\)). The semigroup operation is concatenation. The empty word \(e\) with no letters is the identity. The free semigroup over \(A\) can be embedded in the free group \((G, \cdot)\) over \(A\) by adding the inverse letters
\(a^{-1}\) for \(a \in A\) and extending the operation in the obvious way so that \(a a^{-1} = a^{-1} a = e\) for \(a \in A\). Of course, does not apply since \((G, \cdot)\) is not commutative. Nonetheless, \((S, \cdot)\) is clearly maximal since any subgroup \((H, \cdot)\) of \((G, \cdot)\) that contains \(S\) would have to contain the set \(A^{-1}\) of inverse letters, which would then imply \(H = G\).
The free semigroup and other related spaces are studied in Chapter 5.