Semigroups

If the semigroup also has a unit then it is actually a Monoid or even a Group. There is a richer theory of groups and monoids. Here I show that much of the structure normally presented as part of the theory of groups is part of the structure of semigroups and so can be inherited by both monoids and groups.

In a semigroup the operation that combines objects must be associative as well as total and closed. This means that three objects a,b, and c say, can be combined by pairing a with b and that with c, or we can combine a with the result of pairing b with c. As a counterexample the constructor function cons in LISP is not associative because it constructs trees rather than strings:

           .               .

          / \             / \

         a   .           .   c

            / \         / \

           b   c       a   b

A semigroup that has a unit is called a monoid. Monoids however have all the properties of semigroups. In fact many semigroups are also monoids.

A semigroup that has a commutative operation (so that a combined with b is the same as b combined with a) is said to be Abelian.

Basis

The above statements take the basis and asserts it as part of this document. Since we may not wish to click the links here is a summary of the relevant definitions found in BASIS:

Examples

The Natural Numbers

The set of so-called natural numbers:
1. Nat::= { 1,2,3,4,...}, forms a semigroup with either addition or multiplication as the operator.
2. (Nat, (+)) in semigroup.
3. (Nat, (*)) in semigroup. However under multiplication the number 1 is a unit (for all x( x * 1 = 1 * x = 1) ) and so we can say that (Nat, (*), 1) is a monoid.

   Notice that it is better to state the operator when we talk about a semigroup. There are at least two semigroups with Set=Nat.
   (exercise1): Can you find two more operators that give semigroups for the Natural numbers Nat? If you can't see [ answer1 ] below.

   The Free Semigroup

   A common example of a semigroup is the free semigroup generated by a set of atomic elements A by concatenating them. The free semigroup consists of all strings of one or more atoms with the concatenation operator (!):
   
4. (SEMIGROUP)|-SEMIGROUP( #A, !) where
5. #A = Nat->A
6. and (!)=map[x,y]( (x1,x2,x3,...,y1,y2,y3,...)).

   See strings below for more.

   Notice that the set of all list structures -- %A -- with the LISP like 'cons' operation is not a semigroup, because cons is not associative.

   Set Theoretic Semigroups

   Union and Intersection on a set of subsets of a set give a semigroup if and only if the operations are closed. A set of sets closed under union forms a monoid with the null set as unit. A set of sets closed under intersection which includes the set itself forms another monoid. These systems have special names and are used in many different parts of mathematics. [ logic_31_Families_of_Sets.html ]

   Relational Semigroups

   Any set of homogeneous relationships(HREL) that is closed under composition forms a semigroup. If the Identity relation is included we have a monoid.

   Functional Semigroups

   A set of mapping from a set S into itself that is closed under composition forms a semigroup.
7. FS::=following
   Net
   1. S:Sets.
   2. F::@(S->S).
      
   3. |-For all f,g:F, f;g in F.
      
   4. (maps)|-SEMIGROUP( F, (;)).

   
   (End of Net)
   
   

   
   

8. (INFIX)|-For (X,*):$ SEMIGROUP, x:X, (x*_)= map y:X(x * y), (_*x)= map y:X(y * x). proof by blatant definition - see INFIX

   
   

9. (INFIX)|-For (X,*):$ SEMIGROUP, x:X, SEMIGROUP ( {x*_ ||x:S}, o ) and SEMIGROUP ( {_*x ||x:S}, o ). Functional semigroups are also [ Relational Semigroups ]

   [ Cannonical Forms ] below

   Simplest Anihilator Semigroup

10. A0::=
    Net{

    1. Set::={0,1}.
    2. op::Set><Set->Set= (1,1)+>1 |-> 0.
       
    3. (above)|-SEMIGROUP(Set, op).
       
    4. (above)|-1 in units(op).
       
    5. (above)|-0 in zeroes(op).

    
    }=::A0.

. . . . . . . . . ( end of section Examples) <<Contents | End>>

Zeroes

If element z is in zeroes with respect to a set X and operator * when for all x:X,

Zeroes are also known as anihilators.

There is classic simple proof that a semigroup can have at most one zero. Informally if allow each anihilator to annihilate the other one then we get the same answer.

A zero is one kind of idempotent element:

Given a semigroup S1 with operation op1 that has no zero we can generate a new semigroup S2 with operation op2 and a zero z that contains a copy of S1 (and op1) within in it:

There can only be one unit in a semigroup.

If (S,*) is a semigroup and it has a unit u then (S,*,u) is a monoid.

Sub-semigroups

The word normal, as used here, does not indicate average or typical. A normal sub-semigroup is in a sense 'normal' - at right angles - to the blocks of the generated partition. A normal sub-algebra is a sub-algebra that generates a partition of the elements in the algebra. Typically the partition is itself another algebra of the same type.

Induced Semigroups

Maps from set into a semigroup induce a semigroup on a partition of the set.

Power Semigroups

Semigroup Morphisms

All semigroup morphisms define a partition of the codomain and induce on the collection of sets in the partition another semigroup. If f is a morphism from the semigroup S1 to S2 then it is a map and so define a partition of S1.Set into a collection of sets which themselves form a semigroup with an operation defined by the inverses image of the operation in the second semigroup S2.op.

Congruences

o/R ::= map X,Y:S1.Set/R((x o y)/R where x:X and y:Y)). S1/R ::=(Set=>S1.Set/R, op=>S1.op/R).

Congruences and morphisms

These are also called Abelian_semigroups:

1. |-MULTIPLICATIVE_SEMIGROUP.
   
2. (above)|-if for some n:Nat all x,y:S( x y = y^n x^n)then ABELIAN_SEMIGROUP(S,()).
3. Let{
   n:Nat,
   
   1. |- (m1): for all x,y:S( x y = y^n x^n).
      
   2. (above)|- (m2): for all x:S (x^n=(x^n)^n)
      
   3. (above)|- (m3): for all a,b:S(a b=b a)
      }.

   Proof of m2

   
   Let
   
   
   1. |-x:S.
      
   2. (above)|-if n=1 then x^1^1=x^1.
   3. Let{
      
   4. |-n>1.
      
   5. (above)|-x^n= x x^(n-1)=(x^(n-1))^n x^n=(x^n)^n
   6. }.
   
   (Close Let )
   

   Proof of m3

   
   Let
   
   
   1. |-a,b:S.
      
   2. (above)|-a b = b^n a^n = (a^n)^n (b^n)^n = (a^n) (b^n) = b a.
   
   (Close Let )
   

   
   

4. (above)|-some (S,()):$ MULTIPLICATIVE_SEMIGROUP ( for all r:2..., x,y(x^r y^r=y^r x^r)) and NON_COMMUTATIVE_SEMIGROUP(S,()). [Quicky Q805, Math Mag V66n3(June 93)pp193 and201].
   
5. (above)|-some (S,()):$ MULTIPLICATIVE_SEMIGROUP ( for all r,s:2..., x(x^r =x^s)) and NON_COMMUTATIVE_SEMIGROUP(S,()). [Quicky Q805, Math Mag V66n3(June 93)pp193 and201].

   Cannonical Forms

   Any semigroup is homomorphic (??isomorphic?) to a functional semigroup.
   Let
   
   
   1. |-SEMIGROUP(S, *).

      
      

   2. (above)|-For all s:S, (_*s) in S->S.
   3. F:= { (_*s) | s:S }.

      
      

   4. (above)|-For all f,g, f;g in F.
      Let
      
      
      1. |-f,g:F.
         
      2. (above)|-for some s, f=(_*s),
         
      3. (s:=a)|-f=(_*a).

         
         

      4. (above)|-for some s, g=(_*s)
         
      5. (s:=b)|-g=(_*b),
      6. f;g = map[s] (g(f(s))
      7. = map[s]((s*a)*b))
      8. =map[s](s*(a*b)),
         
      9. (c:=a*b)|-f;g = (_*c) in F.
      
      (Close Let )
      

      
      

   5. (above)|-F is a functional_semigroup.
      
   6. (above)|-map[a](_*a) in (SEMIGROUP)(S.*) -> (F, (;)).
   
   (Close Let )
   

   Also any finitely generated semigroup is a homomorphic image of a free semigroup [ The Free Semigroup ]

   Proofs

   Proof of unique_unit

   1. Let{
      
      
      1. |- (u1): (S,o):semigroup, u1,u2:units(S).

         
         

      2. (u1, unit)|- (u2): for x:S(x o u1=u1 o x=x),
         
      3. (u1, unit)|- (u3): for x:S(x o u2=u2 o x=x).

         
         

      4. (u2, x=>u2)|- (u4): u2 o u1=u1 o u2 = u2.
         
      5. (u3, x=>u1)|- (u5): u1 o u2=u2 o u1 = u1.
         
      6. ()|- (u6): u1=u2.
         }

      Proof of unique_zero

      We follow the standard for for proving 0..1 items: Assume there are two deriving the fact that they must be equal.
      Let
      
      
      1. |- (z1): (S,*):$ SEMIGROUP,
         
      2. |- (z2): z1:zeroes(S,*),
         
      3. |- (z3): z2:zeroes(S,*).

         
         

      4. (z2, zeroes)|- (z4): for all x:S( z1 * x = x * z1 = z1)
         
      5. (z3, zeroes)|- (z5): for all x:S( z2 * x = x * z2 = z2)

         
         

      6. (z4, x:=z2)|- (z6): z1 * z2 = z2 * z1 = z1.
         
      7. (z5, x:=z1)|- (z7): z2 * z1 = z1 * z2 = z2.

         
         

      8. (z6, z7, euclid)|- (z8): z1 = z2.
      
      (Close Let )
      

      Proof of trivial_unit_zero

      
      Let
      
      
      1. |-z:zeroes(S),
         
      2. |-u:units(S),
         
      3. (zeroes)|- (u0): z*u=z.
         
      4. (units)|- (z0): z*u = u
         
      5. (u0, z0)|- (uz0): z= u
         Let
         
         
         1. |-s:S.
            
         2. (units)|- (uz1): s = s * u.
            
         3. (uz0)|- (uz2): s * u = s * z.
            
         4. (zeroes)|- (uz3): x * z = z.

            
            

         5. (uz1, uz2, uz3, uz0)|- (QED): s=z=u.
         
         (Close Let )
         
         
      6. (QED)|-For all s:S( s=z=u ).
      
      (Close Let )
      

. . . . . . . . . ( end of section Semigroups) <<Contents | End>>

Glossary

Answers

Proofs follow a natural deduction style that start with assumptions ("Let") and continue to a consequence ("Close Let") and then discard the assumptions and deduce a conclusion. Look here [ Block Structure in logic_25_Proofs ] for more on the structure and rules.

The notation also allows you to create a new network of variables and constraints. A "Net" has a number of variables (including none) and a number of properties (including none) that connect variables. You can give them a name and then reuse them. The schema, formal system, or an elementary piece of documentation starts with "Net" and finishes "End of Net". For more, see [ notn_13_Docn_Syntax.html ] for these ways of defining and reusing pieces of logic and algebra in your documents. A quick example: a circle = Net{radius:Positive Real, center:Point}.

For a complete listing of pages in this part of my site by topic see [ home.html ]

Notes on the Underlying Logic of MATHS

For a more rigorous description of the standard notations see