1. Reliability
  2. 2. Semigroups
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 6
  9. 7
  10. 8

2. Positive Semigroups

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,S). Semigroups are assumed to be measurable and satisfy the left cancellation property, as discussed in Section 1.

Definitions and Properties

Suppose that (S,) is a semigroup.

  1. (S,) is a strict positive semigroup if xyx for every x,yS.
  2. (S,) is a positive semigroup if (S,) has an identity element e and (S+,) is a strict positive semigroup where S+=S{e}.
Details:

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+,) is a strict positive semigroup. Let e be an element not in S and define S=S+{e}. Extend to S by the rule that xe=ex=x for all xS. Then (S,) is a positive semigroup.

Details:

This follows from the more general result in Section 1 since (S+,) does not have a left identity. In terms of the measure theory, suppose that (S+,S+) is the underlying measure space. We define S by adding to S+ all sets of the form A{e} where AS+.

Note that the algebraic assumptions of a positive semigroup do not rule out the possibility that xy=y for some x,yS with xe. A positive semigroup has no nontrivial inverses.

Suppose that (S,) is a positive semigroup with identity e. Then xy=e if and only if x=y=e

Details:

Trivially if x=y=e then xy=e since e is an identity. If xe and ye then xye since S+ is algebraically closed. If x=e and ye then xy=ye. Finally if xe and y=e then xy=xe.

If (S,) is a positive semigroup then a product over an empty index set is interpreted as the identity e. In particular, x0=e for xS.

Suppose that (S,) is a positive semigroup. The positive sub-semigroup generated by xS+ has base set x={xn:nN}. This semigroup is isomorphic to the standard discrete semigroup (N,+), with isomorphism nxn.

Details:

Suppose that m,nN with m<n and that xm=xn. Then xme=xmxnm and so by left cancelation, e=xnm. But then x=e by repeated applications of [3], a contradiction. Hence the mapping nxn is one-to-one and onto. Of course also (m+n)xm+n=xmxn for m,nN.

Graphs

The following result is the reason that positive semigroups have special importance.

Suppose that (S,) is a positive semigroup with identity e, and that (T,) is a sub-semigroup.

  1. If eT then the relation T associated with (S,) and T is a partial order.
  2. If eT then the relation T associated with (S,) and T is a strict partial order.
Details:

Since T is algebraically closed, the relation associated with (S,) and T is transitive from Section 1.

  1. Suppose that eT. Then xTx since x=xe for xS. Hence T is reflexive. If xTy and yTx for some x,yS then there exists a,bT with y=xa and x=yb. Hence x=yb=(xa)b=x(ab)=xe. By the left cancellation property, ab=e and so from [3], a=b=e. Thus x=y and so T is anti-symmetric.
  2. Suppose that eT. If xTx for some xS then there exists aT with xa=x=xe. By left cancellation again, a=eT, a contradiction. Hence T is anti-reflexive, and since it's transitive, also asymmetric.

The most important case is when T=S and as usual, we drop the subscript so that the relation associated with (S,) is a partial order. In the case that T=S+, the associated relation is the corresponding strict partial order , 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,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,) since ex for every xS.

Suppose again that (S,) is a positive semigroup and that AS. Then relative to the graph (S,),

  1. A is increasing if and only if xA and yxS imply yA, or equivalently xA implies xSA.
  2. A is decreasing if and only if yA and yxS imply xA.
  3. A is convex if and only if xA, yxS and zAyS imply yA.
Details:

All three results follow form the definitions, since uv if and only if vuS for u,vS.

Suppose that (S,) is a positive semigroup with associated partial order S and that (T,T) is another partial order graph. Suppose also that f:ST. Then relative to the partial orders,

  1. f is increasing if f(x)Tf(xy) for x,yS.
  2. f is decreasing if f(xy)Tf(x) for x,yS.
Details:

Again, the results follow from the definitions since xSxy for x,yS.

Suppose that (S,) is a positive semigroup with associated partial order . By the result in Section 1, for fixed xS, the mapping yxy is an isomorphism from the graph (S,) to the graph (xS,).

Irreducible Elements

In this subsection, we assume that (S,) is a discrete positive semigroup with associated partial order .

An element iS is irreducible if i cannot be factored i=xy for x,yS, except for the trivial factoring i=ei=ie.

The covering graph of (S,) can be characterized in terms of the irreducible elements.

If x,yS then y covers x if and only if y=xi for some irreducible element i. That is, the covering relation is the relation associated with I, the set of irreducible elements of (S,).

Details:

Suppose that y covers x. Then xy so there exists iS+ with y=xi. If i=ab for some a,bS+ then xxaxab=y which would be a contradiction. Thus, i has no non-trivial factorings and hence is irreducible. Conversely, suppose that y=xi for some irreducible element i. Then xy. Suppose there exists uS with xuy. Then u=xs and y=ut for some s,tS+. Thus y=xst=xi so by left cancellation, i=st. But this is a contradiction since i is irreducible, and so y covers x.

Suppose that (S,) is left finite with I as the set of irreducible elements. Then xS can be factored finitely over I for every xS. That is, x=i1i2in for some nN where ikI for k{1,2,,n}.

Details:

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 xS, there exists a finite path in the covering graph from e to x, say (x0,x1,x2,,xn) where nN, x0=e, xn=x, and xk+1 covers xk for each k{0,1,n1}. But then xk+1=xkik for each k where ikI. Hence x=i1i2in.

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,) is associated with a positive semigroup, then (S,) 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,) is left finite. Then dim(S,)#(I).

Details:

Suppose that φ is a homomorphism from (S,) into (R,+) and that φ(i)=0 for each iI. If xS, then from [10], x can be factored over I so that x=i1i2in where ikI for each k. But then φ(x)=φ(i1)+φ(i2)++φ(in)=0 Hence I is a critical set and so dim(S,)#(I)

We can certainly have dim(S,)<#(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, leading to an interesting problem:

How are dim(S,) and dim(S,) related?

Möbius Inverstion

In this subsection we assume that (S,) 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,).

Let M denote the Möbius kernel of (S,). Then M(x,y)=M(tx,ty) for x,y,tS.

Details:

The fact that (S,) is left finite means that the Möbius kernel is well defined and that (S,) is well founded so that we can use partial order induction. Let x,y,tS. First, xy if and only if txty so it follows that if xy then M(x,y)=0=M(tx,ty). Next, M(x,x)=1=M(tx,tx). Suppose now that xy. Recall that utu maps [x,y) one to one and onto [tx,ty). For the induction hypothesis, suppose that M(x,u)=M(tx,tu) for all uy. Then M(tx,ty)=z[tx,ty)M(tx,z)=u[x,y)M(tx,tu)=u[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 μ of (S,) is defined by μ(t)=M(e,t) for tS, and is defined inductively as follows:

  1. μ(e)=1
  2. μ(x)=t[e,x)μ(t) for xS+

The Möbius kernel M is related to the Möbius function μ by M(x,y)=μ(x1y),xy

Details:

Suppose that xy so that x1y makes sense. From [13], M(e,x1y)=M[x,x(x1y)]=M(x,y)

Groups

Often (but not always) the positive semigroups that are of interest to us are embedded in groups. Suppose that (G,) is a group and that (S,) is a positive, sub-semigroup of (G,). 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,) is a group. A positve, sub-semigroup (S,) is maximal if (S,) is not a sub-semigroup of a proper subgroup of (G,).

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={uv:u,vS}. Then

  1. (H,+) is a subgroup of (G,+) containing S.
  2. (S,+) is maximal if and only if H=G.
Details:
  1. If x,yH so that x=uv and y=zw where u,v,z,wS then x+y=(uv)+(zw)=(u+z)(v+w)H and x=(uv)=vuH. Hence (H,+) is a semigroup of (G,+). Moreover, H contains S since u=u0H for uS where 0 is the identity.
  2. If (S,+) is maximal then G=H by definition. Conversely, every subgroup of (G,+) containing S must also contain H. Hence if H=G then (S,+) is maixmal.

Examples

Many of the semigroup examples in Section 1 are positive semigroups.

The space ([0,),+) is a maximal positive sub-semigroup of the commutative group (R,+). The associated order is the total order .

Details:

Trivially we can write xR as x=uv where u,v[0,). In fact, either x[0,) or x[0,).

The space ([1,),) is a maximal positive sub-semigroup of the commutative group (0,),). The associated order is the total order .

Details:

Trivially we can write x(0,) as x=u/v where u,v[1,). In fact, either x[1,) or 1/x[1,).

The group and semigroup in [18] are isomorphic to the group and semigroup in [19] with isomorphism xex from R onto (0,). 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 .

Details:

Trivially we can write xZ as x=uv where u,vN. In fact, either xN or xN.

The semigroup (N,+) and other related spaces are studied in Chapter 4.

The space (N+,) is a positive semigroup where is ordinary multiplication. The associated partial order is the division relation.

Details:

That is, xy if and only if x divides y so that y/x=z for some zN+.

The semigroup (N+,) and other related spaces are studied in Chapter 6.

The free semigroup (S,) over a countable alphabet A is a positive semigroup. The associated partial order is defined by xy if and only if x is a prefix of y.

Details:

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,) over A by adding the inverse letters a1 for aA and extending the operation in the obvious way so that aa1=a1a=e for aA. Of course, [17] does not apply since (G,) is not commutative. Nonetheless, (S,) is clearly maximal since any subgroup (H,) of (G,) that contains S would have to contain the set A1 of inverse letters, which would then imply H=G.

The free semigroup and other related spaces are studied in Chapter 5.