.Open Semigroups
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 + (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:
.As_is           .               .
.As_is          / \             / \
.As_is         a   .           .   c
.As_is            / \         / \
.As_is           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
BASIS::=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).

|-$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:
(BASIS)|-
SEMIGROUP::=http://www.csci.csusb.edu/dick/maths/math_31_One_Associative_Op.html#SEMIGROUP
(SEMIGROUP)|- semigroup::={ Set:Sets || (Set,op) in $ $SEMIGROUP}, 
(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=>*)}

.Open Examples
. The Natural Numbers
The set of so-called natural numbers:
Nat::= { 1,2,3,4,...},
forms a semigroup with either addition or multiplication as
the operator.  
	(Nat, (+)) in semigroup.
	(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
.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 (!):
	(SEMIGROUP)|- SEMIGROUP( #A, !) where 
		#A = $Nat->A
	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.
.See http://www/dick/maths/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.
FS::=following
.Net
	S:Sets.
	F::@(S->S).
	|-For all f,g:F, f;g in F.
	(maps)|-SEMIGROUP( F, (;)).
.Close.Net

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

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

.See Cannonical Forms
below

. Simplest Anihilator Semigroup
A0::=Net{
	Set::={0,1}.
	op::Set><Set->Set= (1,1)+>1 |-> 0.
	()|- SEMIGROUP(Set, op).
	()|- 1 in units(op).
	()|- 0 in zeroes(op).
}=::A0.
.Close Examples
. Zeroes
A 
.Key zero
is defined in $STANDARD by
(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,
	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.
(zeroes)|-(unique_zero): For all $SEMIGROUP, 0..1 zeroes(S.Set, S.op).

A $zero is one kind of `idempotent` element:
(STANDARD)|- idempotents(X,*)::={i:X||i * i = i}. 

(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:
	S2 = S1|{z}.
	op2 = (z,z)+>z | |[s:S1](s,z)+>z | |[s:S1](z,s)+>z | [s,t:S1](s,t)+>(s op1 t).
. Units
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:
(STANDARD)|- units(X,*)::={u:X||x * u = u * x = x}.

There can only be one unit in a semigroup.
(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.

(defs)|- $units(Set,op) ==> $idempotents(Set, op).
. Units and Zeroes
(defs)|- (trivial_unit_zero): for z:zeroes(S), u:units(S), if z=u then for all s:S(s=u=z).
. Ideals
 For SEMIGROUP(Set=>X, op=>*), Ideals ::={I: @Set || I * Set ==> I and Set * I ==> I}

. Sub-semigroups
 For X:Sets,*:infix(X), Y:@X, Y sub_semigroup X ::@= (Y,*) in semigroup(*). 
        (sub_semigroup)|-for all X,Y, if Y sub_semigroup X then all y1,y2:Y(y1 * y2 in Y).
        (def)|- (S=>semigroup, R=>sub_semigroup) in poset.
.See http://www/dick/maths/math_21_Order.html#poset
. Normal Subsemigroups
        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.

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

. Induced Semigroups
(funpart)|-For Sets A, S, f:S^A,  A/f==>@A  and A>==A/f---S.
.See http://www/dick/maths/logic_5_Maps.html#funpart

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

()|- For SEMIGROUP(S,*), A:Set, f:S^A, for all s, one X:A/f(f(X)=s),
 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)).
()|- (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.
()|- 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
 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)},
	()|-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.
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) )).

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

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

. Congruences
Congruences are equivalence relation which allows substitution of expressions in the algebra being studied.
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),

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

   ()|-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
   ()|-for all R in congruence(S1), S1=(S,o), (_)/R:(semigroup)S>==S/R.
  ()|- For f:(semigroup)S1->S2, (=(f)) in congruence(S1),
          S1/f ::=(S1.set/=(f), S1.op/=(f)),
          (semigroup)S1>==S1/f, (semigroup)S1/f---(img(f),S2.op), (semigroup)img(f)==>S2.
. Commutative Semigroups
COMMUTATIVE_SEMIGROUP::=SEMIGROUP and Net{for all x,y:Set(x op y=y op x).}.

These are also called Abelian_semigroups:
  ABELIAN_SEMIGROUP::=COMMUTATIVE_SEMIGROUP.
. Non_Commutative Semigroups
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.
MULTIPLICATIVE_SEMIGROUP::=Net{ 
	SEMIGROUP(Set, op=>()).
	(^) ::infix(Set, Nat, Set).
	|-For x:Set, x^1=x.
	|-For n:Nat, x:Set, x^n=x x^(n-1).
}=::MULTIPLICATIVE_SEMIGROUP.
.Source [Solutions to problem 1400, Math Mag V66n3(June 93)p198]
Let{
	|-MULTIPLICATIVE_SEMIGROUP.
()|- if for some n:Nat all x,y:S( x y = y^n x^n)then ABELIAN_SEMIGROUP(S,()).
Let{ n:Nat, 
	|- (m1): for all x,y:S( x y = y^n x^n).
	()|-(m2): for all x:S (x^n=(x^n)^n)
	()|- (m3): for all a,b:S(a b=b a)
}.
. Proof of m2
.Let 
	|-x:S. 
	()|- if n=1 then x^1^1=x^1.
	Let{ 
		|- n>1. 
		()|- x^n= x x^(n-1)=(x^(n-1))^n x^n=(x^n)^n
	}.
.Close.Let
. Proof of m3
.Let
	|-a,b:S.
	()|-a b = b^n a^n =  (a^n)^n (b^n)^n = (a^n) (b^n) = b a.
.Close.Let

()|- 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].
()|- 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.
.Let
	|- SEMIGROUP(S, *).

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

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

	()|- for some s, g=(_*s)
	(s:=b)|- g=(_*b),
	f;g = map[s] (g(f(s))
		= map[s]((s*a)*b))
		=map[s](s*(a*b)),
	(c:=a*b)|- f;g = (_*c) in F.
.Close.Let

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

Also any finitely generated semigroup is a homomorphic image of
a free semigroup
.See The Free Semigroup

.Open Proofs
. Proof of unique_unit
Let{ 
	|-(u1): (S,o):semigroup, u1,u2:units(S).

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

	(u2, x=>u2)|-(u4): u2 o u1=u1 o u2 = u2.
	(u3, x=>u1)|-(u5): u1 o u2=u2 o u1 = u1.
	()	|-(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
	|-(z1): (S,*):$ $SEMIGROUP,
	|-(z2): z1:zeroes(S,*),
	|-(z3): z2:zeroes(S,*).

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

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

	(z6,z7, euclid)|-(z8): z1 = z2.
.Close.Let
. Proof of trivial_unit_zero
.Let
	|-z:zeroes(S),
	|-u:units(S),
	(zeroes)|-(u0): z*u=z. 
	(units)|-(z0): z*u = u
	(u0,z0)|-(uz0): z= u
.Let
	|- s:S.
	(units)|- (uz1): s = s * u.
	(uz0)|-(uz2): s * u = s * z.
	(zeroes)|-(uz3): x * z = z.

	(uz1, uz2,uz3,uz0)|- (QED): s=z=u.
.Close.Let
	(QED)|- For all s:S( s=z=u ).
.Close.Let
.Close.Proofs
.Close Semigroups
. Glossary
closed::=an operation on a set is closed if applying to elements in the set generates a new element in the same set.


euclid::=Things that are equal to the same thing are equal to each other.
.See http://www/dick/maths/logic_11_Equality_etc.html

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

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

idempotents(S,o) ::=setof{s:S. s o s = s }.
. Links
INFIX::=http://www/dick/maths/math_11_STANDARD.html#INFIX.
STANDARD::=http://www/dick/maths/math_11_STANDARD.html#Overloadings.

category::=http://www/dick/maths/math_25_Categories.html

monoid::=http://www/dick/maths/math_33_Monoids.html

strings::=
.See http://www/dick/maths/intro_strings.html
.See http://www/dick/maths/logic_6_Numbers..Strings.html
.See http://www/dick/maths/math_61_String_Theories.html
.See http://www/dick/maths/math_62_Strings.html
.See http://www/dick/maths/math_66_SuperStrings.html

HREL::=http://www/dick/maths/logic_41_HomogenRelations.html

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

zeroes::=http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html#zeroes
|- zeroes(X,*) ::={z:X||for all x:X( z * x = x * z = z}.
. References
(serial_calculus): Burghard von Karger & C A R Hoare, Sequential Calculus,
Info Proc Letters V53n3(Feb 95)pp123-130.

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