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:
. .
/ \ / \
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::= 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).
- |-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::= See 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=>*)}
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
[ answer1 ]
below.
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.
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 ]
Any set of homogeneous relationships(HREL) that is closed under composition
forms a semigroup. If the Identity relation is included we have
a monoid.
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, (;)).
(End of 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
[ Relational Semigroups ]
[ Cannonical Forms ]
below
- A0::=
Net{
- Set::={0,1}.
- op::Set><Set->Set= (1,1)+>1 |-> 0.
- (above)|-SEMIGROUP(Set, op).
- (above)|-1 in units(op).
- (above)|-0 in zeroes(op).
}=::
A0.
. . . . . . . . . ( end of section Examples) <<Contents | End>>
A
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).
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).
- (defs)|- (trivial_unit_zero): for z:zeroes(S), u:units(S), if z=u then for all s:S(s=u=z).
- For SEMIGROUP(Set=>X, op=>*), Ideals::={I: @Set || I * Set ==> I and Set * I ==> I}
- 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.
[ poset in math_21_Order ]
- 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}.
- (above)|-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}.
- (above)|-For SEMIGROUP(S,*), N: normal_sub_semigroup(S), SEMIGROUP( S/N, (o) ).
- (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.
- (above)|-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)).
- (above)|-(Set=>A/f, op=>*/f) in semigroup.
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.
- (above)|-For SEMIGROUP(S,*), SEMIGROUP(@S, op) where op:=map[A,B:@S]({s:S || for some a:A, b:B( s=a*b) }).
- 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)},
- (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.
- 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) )).
- (above)|-For S1,S2, f:(semigroup)S1->S2, semigroup(S1.Set/f S1.op/f).
- (above)|-For S1,S2, f:(semigroup)S1->S2, map [x](x/f) in (semigroup)S1>==S1/f.
- (above)|-For S1,S2, f:(semigroup)S1->S2, (semigroup)S1/f --- (img(f),S2.op).
- (above)|-For S1,S2, f:(semigroup)S1->S2, (semigroup)(img(f),S2.op)==>S2.
- (above)|-For S1,S2, a, f, z:zeroes(S1), f(z) in zeroes(S2).
- (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.
- 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),
- (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}.
- (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).
- (above)|-for all R in congruence(S1), S1=(S,o), (_)/R:(semigroup)S>==S/R.
- (above)|-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_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_SEMIGROUP::=SEMIGROUP and Net{for some x,y:Set(x op y<>y op x).}.
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.
- (above)|-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).
- (above)|- (m2): for all x:S (x^n=(x^n)^n)
- (above)|- (m3): for all a,b:S(a b=b a)
}.
Let
- |-x:S.
- (above)|-if n=1 then x^1^1=x^1.
- Let{
- |-n>1.
- (above)|-x^n= x x^(n-1)=(x^(n-1))^n x^n=(x^n)^n
- }.
(Close Let )
Let
- |-a,b:S.
- (above)|-a b = b^n a^n = (a^n)^n (b^n)^n = (a^n) (b^n) = b a.
(Close Let )
- (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.
- (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.
Any semigroup is homomorphic (??isomorphic?) to a functional semigroup.
Let
- |-SEMIGROUP(S, *).
- (above)|-For all s:S, (_*s) in S->S.
- F:= { (_*s) | s:S }.
- (above)|-For all f,g, f;g in F.
Let
- |-f,g:F.
- (above)|-for some s, f=(_*s),
- (s:=a)|-f=(_*a).
- (above)|-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 )
- (above)|-F is a functional_semigroup.
- (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 ]
- 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.
}
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 )
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 )
. . . . . . . . . ( end of section Semigroups) <<Contents | End>>
- 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.
[ 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 }.
- INFIX::= See http://cse.csusb.edu/dick/maths/math_11_STANDARD.html#INFIX.
- STANDARD::= See http://cse.csusb.edu/dick/maths/math_11_STANDARD.html#Overloadings.
- category::= See http://cse.csusb.edu/dick/maths/math_25_Categories.html
- monoid::= See http://cse.csusb.edu/dick/maths/math_33_Monoids.html
- strings::=
[ intro_strings.html ]
[ logic_6_Numbers..Strings.html ]
[ math_61_String_Theories.html ]
[ math_62_Strings.html ]
[ math_66_SuperStrings.html ]
- HREL::= See http://cse.csusb.edu/dick/maths/logic_41_HomogenRelations.html
- unit::= See 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::= See 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}.
(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....
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 ]
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
- STANDARD::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html
- 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).
- given::reason="I've been told that...", used to describe a problem.
- given::variable="I'll be given a value or object like this...", used to describe a problem.
- goal::theorem="The result I'm trying to prove right now".
- goal::variable="The value or object I'm trying to find or construct".
- 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.
- hyp::reason="I assumed this in my last Let/Case/Po/...".
- QED::conclusion="Quite Easily Done" or "Quod Erat Demonstrandum", indicates that you have proved what you wanted to prove.
- QEF::conclusion="Quite Easily Faked", -- indicate that you have proved that the object you constructed fitted the goal you were given.
- RAA::conclusion="Reducto Ad Absurdum". This allows you to discard the last
assumption (let) that you introduced.