[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [ MATHS ] / math_32_Semigroups
[Contents] [Source Text] || [Notation] || [Copyright] || [Contact] [Search ]
Thu Nov 10 13:13:07 PST 2011



      A semigroup is a set of things that can be combined together in pairs to make more things. The result of combining two things must always be a new thing of the same type - the operation must be closed. It most also always work -- the operation must be total. In other words it must be a mapping from any pair of objects into an object in the same set.

      If it is not possible to combine any pair then we don't have a semigroup - it may be a category instead. It may also be the newer and less well known serial_calculus.

      Further in a semigroup the operation is associative:

    1. 1 + (2 + 3) = (1+2) +3

      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.


    2. BASIS::= See http://www.csci.csusb.edu/dick/maths/math_31_One_Associative_Op.html This satement links this document to a set of shared definitions of all the simple assoicative algebrase (BASIS).

    3. |-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:

    4. (BASIS)|-
    5. SEMIGROUP::= See http://www.csci.csusb.edu/dick/maths/math_31_One_Associative_Op.html#SEMIGROUP
    6. (SEMIGROUP) |- semigroup::={ Set:Sets || (Set,op) in $ SEMIGROUP},
    7. (SEMIGROUP) |- Semigroup::=$ SEMIGROUP, (SEMIGROUP) |-For o, semigroup(o) ::={ Set:Sets || (Set,o) in $ SEMIGROUP}, (SEMIGROUP) |-For *:infix(T1), semigroup(*) ::={S:@T1||SEMIGROUP(Set=>S,op=>*)}


        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
        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::=
        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).


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


      A zero is defined in STANDARD by
    8. (STANDARD) |- zeroes(X,*)::={z:X||for all x:X( z * x = x * z = z}.

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

    9. z * x = z = x * z.

      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.

    10. (zeroes)|- (unique_zero): For all SEMIGROUP, 0..1 zeroes(S.Set, S.op).

      A zero is one kind of idempotent element:

    11. (STANDARD) |- idempotents(X,*)::={i:X||i * i = i}.

    12. (zeroes, idempotents)|-zeroes(Set,op) ==> idempotents(Set, op).

      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:

    13. S2 = S1|{z}.
    14. op2 = (z,z)+>z | |[s:S1](s,z)+>z | |[s:S1](z,s)+>z | [s,t:S1](s,t)+>(s op1 t).


      A unit is an element in a semigroup which does not change the elements it is combined with. Again units is a set defined in STANDARD:
    15. (STANDARD) |- units(X,*)::={u:X||x * u = u * x = x}.

      There can only be one unit in a semigroup.

    16. (SEMIGROUP)|- (unique_unit): For all SEMIGROUP(S,o), 0..1 units( o ).

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

    17. (defs)|-units(Set,op) ==> idempotents(Set, op).

      Units and Zeroes

    18. (defs)|- (trivial_unit_zero): for z:zeroes(S), u:units(S), if z=u then for all s:S(s=u=z).


    19. For SEMIGROUP(Set=>X, op=>*), Ideals::={I: @Set || I * Set ==> I and Set * I ==> I}


    20. For X:Sets,*:infix(X), Y:@X, Y sub_semigroup X::@= (Y,*) in semigroup(*).
    21. (sub_semigroup)|-for all X,Y, if Y sub_semigroup X then all y1,y2:Y(y1 * y2 in Y).
    22. (def)|-(S=>semigroup, R=>sub_semigroup) in poset. [ poset in math_21_Order ]

      Normal Subsemigroups

    23. N normal_sub_semigroup X::= N sub_semigroup X and for all a:X(a * N= N * a} and for all a,b:X(if a * N & b * N<>{} then a * N = b * N}.

      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.

    24. For SEMIGROUP(S,*), N: normal_sub_semigroup(S), S/N::= { a * N || a in S}.
    25. (above)|-For SEMIGROUP(S,*), N: normal_sub_semigroup(S), S>== S/N
    26. For SEMIGROUP(S,*), N: normal_sub_semigroup(S), A,B: S/N, A o B::={(a * b)* N}||for some a:A, b:B}.
    27. (above)|-For SEMIGROUP(S,*), N: normal_sub_semigroup(S), SEMIGROUP( S/N, (o) ).

      Induced Semigroups

    28. (funpart)|-For Sets A, S, f:S^A, A/f==>@A and A>==A/f---S. [ funpart in logic_5_Maps ]

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

    29. (above)|-For SEMIGROUP(S,*), A:Set, f:S^A, for all s, one X:A/f(f(X)=s),
    30. For SEMIGROUP(S,*), A:Set, f:S^A, X,Y:A/f, X */f Y::=the Z:A/f(f(Z)=f(X) * f(Y)).
    31. (above)|-(Set=>A/f, op=>*/f) in semigroup.

      Power Semigroups

      This is an often used construction but has no common name. In STANDARD MATHS any infix operator on a set S is overloaded to operate like this on subsets of S.
    32. (above)|-For SEMIGROUP(S,*), SEMIGROUP(@S, op) where op:=map[A,B:@S]({s:S || for some a:A, b:B( s=a*b) }).

      Semigroup Morphisms

    33. For S1:semigroup(+), S2:semigroup(*), a:{>==,==>,>--,->,-->}, (semigroup) S1 a S2 ::={f:S1 a S2||for x,y:X(f(x + y)=f(x) * f(y)},
    34. (above)|-S1 sub_semigroup S2 iff (semigroup)S1==>S2.

      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.

    35. For S1,S2, a, f:(semigroup)S1 a S2, S1.op/f::=map[X,Y:S1.Set/f](/f(f(X) S2.op f(Y) )).

    36. (above)|-For S1,S2, f:(semigroup)S1->S2, semigroup(S1.Set/f S1.op/f).
    37. (above)|-For S1,S2, f:(semigroup)S1->S2, map [x](x/f) in (semigroup)S1>==S1/f.
    38. (above)|-For S1,S2, f:(semigroup)S1->S2, (semigroup)S1/f --- (img(f),S2.op).
    39. (above)|-For S1,S2, f:(semigroup)S1->S2, (semigroup)(img(f),S2.op)==>S2.

    40. (above)|-For S1,S2, a, f, z:zeroes(S1), f(z) in zeroes(S2).
    41. (above)|-For S1,S2, a, f, z:units(S1), f(z) in units(S2).


      Congruences are equivalence relation which allows substitution of expressions in the algebra being studied.
    42. congruence(S1)::={R:equivalence_relation(S)|| for all x1,y1,x2,y2,if x1 R y1 and x2 R y2 then (x1 o x2 R y1 o y2),

    43. (above)|-for R: equivalence_relation(S), R in congruence(S,o) iff for all x,y:S(if x R y then (x o b)/R=(y o b)/R}.

    44. (above)|-for all R in congruence(S1), S1=(Set,o), for all x,y,z in S(if x R y then u o x R u o y and x o u R y o u).

      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

    45. (above)|-for all R in congruence(S1), S1=(S,o), (_)/R:(semigroup)S>==S/R.
    46. (above)|-For f:(semigroup)S1->S2, (=(f)) in congruence(S1), S1/f ::=(S1.set/=(f), S1.op/=(f)),
    47. (semigroup)S1>==S1/f, (semigroup)S1/f---(img(f),S2.op), (semigroup)img(f)==>S2.

      Commutative Semigroups

    48. COMMUTATIVE_SEMIGROUP::=SEMIGROUP and Net{for all x,y:Set(x op y=y op x).}.

      These are also called Abelian_semigroups:


      Non_Commutative Semigroups

    50. NON_COMMUTATIVE_SEMIGROUP::=SEMIGROUP and Net{for some x,y:Set(x op y<>y op x).}.

      Multiplicative Semigroups

      THese use the algebraic notation for multiplication and have a power operator(^) defined.
      1. SEMIGROUP(Set, op=>()). (^) ::infix(Set, Nat, Set).
      2. |-For x:Set, x^1=x.
      3. |-For n:Nat, x:Set, x^n=x x^(n-1).


      Source: Solutions to problem 1400, Math Mag V66n3(June 93)p198

    52. Let{

      2. (above)|-if for some n:Nat all x,y:S( x y = y^n x^n)then ABELIAN_SEMIGROUP(S,()).
      3. Let{
        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


        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


        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,()).

        Source: 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,()).

        Source: Quicky Q805, Math Mag V66n3(June 93)pp193 and201.

        Cannonical Forms

        Any semigroup is homomorphic (??isomorphic?) to a functional semigroup.

        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.

          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 ]


          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.

          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


          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

            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>>


    53. closed::=an operation on a set is closed if applying to elements in the set generates a new element in the same set.

    54. euclid::=Things that are equal to the same thing are equal to each other. [ logic_11_Equality_etc.html ]

    55. free::=an algebra is free if has no added axioms - no extra structure.

    56. total::=an operation is total if it can be applied to any possible set of arguments. Otherwise it is partial.

    57. idempotents(S,o)::=setof{s:S. s o s = s }.


    58. INFIX::= See http://cse.csusb.edu/dick/maths/math_11_STANDARD.html#INFIX.
    59. STANDARD::= See http://cse.csusb.edu/dick/maths/math_11_STANDARD.html#Overloadings.

    60. category::= See http://cse.csusb.edu/dick/maths/math_25_Categories.html

    61. monoid::= See http://cse.csusb.edu/dick/maths/math_33_Monoids.html

    62. strings::= [ intro_strings.html ] [ logic_6_Numbers..Strings.html ] [ math_61_String_Theories.html ] [ math_62_Strings.html ] [ math_66_SuperStrings.html ]

    63. HREL::= See http://cse.csusb.edu/dick/maths/logic_41_HomogenRelations.html

    64. unit::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html#units
    65. |- units(X,*)::={u:X||for all x:X( u * x = x * u = x}.

    66. zeroes::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html#zeroes
    67. |- zeroes(X,*)::={z:X||for all x:X( z * x = x * z = z}.


      (serial_calculus): Burghard von Karger & C A R Hoare, Sequential Calculus, Info Proc Letters V53n3(Feb 95)pp123-130.


      (answer1): (Nat, min) and (Nat,max) are also semigroups. There are many others....

      Notes on MATHS Notation

      Special characters are defined in [ intro_characters.html ] that also outlines the syntax of expressions and a document.

      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 might be described by Net{radius:Positive Real, center:Point, area:=π*radius^2, ...}.

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

      Notes on the Underlying Logic of MATHS

      The notation used here is a formal language with syntax and a semantics described using traditional formal logic [ logic_0_Intro.html ] plus sets, functions, relations, and other mathematical extensions.

      For a more rigorous description of the standard notations see

    68. STANDARD::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html


    69. above::reason="I'm too lazy to work out which of the above statements I need here", often the last 3 or 4 statements. The previous and previous but one statments are shown as (-1) and (-2).
    70. given::reason="I've been told that...", used to describe a problem.
    71. given::variable="I'll be given a value or object like this...", used to describe a problem.
    72. goal::theorem="The result I'm trying to prove right now".
    73. goal::variable="The value or object I'm trying to find or construct".
    74. let::reason="For the sake of argument let...", introduces a temporary hypothesis that survives until the end of the surrounding "Let...Close.Let" block or Case.
    75. hyp::reason="I assumed this in my last Let/Case/Po/...".
    76. QED::conclusion="Quite Easily Done" or "Quod Erat Demonstrandum", indicates that you have proved what you wanted to prove.
    77. QEF::conclusion="Quite Easily Faked", -- indicate that you have proved that the object you constructed fitted the goal you were given.
    78. RAA::conclusion="Reducto Ad Absurdum". This allows you to discard the last assumption (let) that you introduced.