半群和群semigroup and group
- 格式:doc
- 大小:109.00 KB
- 文档页数:17
9.半群和群semigroup and group
§9.1 二元运算复习binary operation revisited
A上二元运算
f:A×A→A
f处处有定义的函数。
Dom(f)=A×A,
对任意a,b∈A,f(a,b)∈A,唯一确定。
二元运算常记做+,-,×,*,◦,等等
对任意a,b∈A,a◦b∈A
说成A对◦封闭。
A={a1,a2,……,an}时,二元运算可以用运算表给出。
二元运算的性质
1可换commutative a*b=b*a
2 结合associative a*(b*c)=(a*b)*c
3 幂等idempotent a*a=a
§9.2 半群semigroup
半群定义:
(S,*) *是S上乘法,满足结合律。
半群的例
(Z,+),(Z,×),
(N,×),(N,+),
(Q,+),(R,×),
(Zn,+),(Zn,×)
(P(S),∪),(P(S), ∩),
(Mn,+),(Mn,×),
(F[x], +), (F[x], ×),
S上全体映射,对于复合,
(L,∧),(L,∨),L是格 (A*, ),
A* 是A中字符组成的字符串,
是连接运算,
(A*,)也叫作A生成的自由半群 free semigroup。
由结合律
定理1. 半群中,n个元素的乘积与乘法的次序无关。
恒等元identity:e∈(S,*), 对任意a∈S,e*a=a*e=a. 恒等元也叫单位元unit。
独异点monoid:有恒等元的半群叫独异点.
例
是(N,+),(Z,+),(Q,+),(R,+)的恒等元。
(Z+,+)中无恒等元,
是(N,×),(Z,×),(Q,×),(R,×)的恒等元。
(P(S),∪)的恒等元是,(P(S),∩)的恒等元是。
(Mn,+),(Mn,×),(F(x), +), (F(x),×)的恒等元分别是。
S上全体映射,对于复合组成的半群的恒等元是 。
自由半群(A*, ◦)的恒等元是 。
子半群subsemigroup 子独异点submonoid
设(S,*)是半群,TS,T对*封闭,则(T,*)也是半群,称为(S,*)的子半群。
设(S,*)是独异点,TS,T对*封闭,且e∈T,则(T,*)也是独异点,称为(S,*)的子独异点。
(N,+),(Z,+),(Q,+),(R,+)前一个是后一个的子半群,也是子独异点。
(N,×),(Z,×),(Q,×),(R,×)前一个是后一个的子半群,也是子独异点。
设(S,*)是半群,(S,*)是(S,*)的子半群。
设(S,*)是独异点,(S,*)是(S,*)的子独异点。
设(S,*)是独异点, ({e},*)是(S,*)的子独异点。
一个独异点(S,*)中只有一个恒等元。
设e和e’都是S的恒等元,
e’=e*e’=e.
幂power:
设(S,*)是半群,a∈S,定义a的幂power:
a1=a, an=an-1*a.
设(S,*)是独异点,令
a0=e
幂的运算:
am*an=am+n
(am)n=amn.
(1)设(S,*)是半群,a∈S,令
T={ai | i∈Z+}
则(T,*)是(S,*)的子半群。
(2)设(S,*)是独异点,a∈S,令
T={ai | i∈N}
则(T,*)是(S,*)的子独异点。
同构isomorphism和同态 homomorphism
同构
设(S,*)和(T,*’)是两个半群,函数f:S→T是一一对应,a,b∈S,
f(a*b)=f(a)*’f(b).
称(S,*)和(T,*’)同构,记做(S,*)(T,*’).
验证两个半群(S,*)和(T,*’)同构的方法:
定义一个映射f:S→T,证明
(1) f 处处有定义,即Dom(f)=S.
(2) f 单,f(a)=f(b)a=b.
(3) f 满,Ran(f)=T.
(4) f保持运算f(a*b)=f(a)*’f(b).
例. 令T={2n | n∈Z},则(T,×)是(N,+)的子半群,
且(N,+)(T,×)。
证明.
令f:N→T,
对任意n∈N,f(n)= 2n.
(1) f处处有定义.
(2) f单:f(m)=f(n), 即
2m=2nm=n。
(3) f满.
(4) f保持运算:
f(m+n)= 2m+n
=2m×2n =f(m)×f(n)
定理2. 恒等元的同构像是恒等元
设(S,*),(T,*)是独异点,恒等元分别是e和e’,同构f:(S,*)(T,*’), 则f(e)=e’.
证明. 我们证明f(e)是T的恒等元。对任意b∈T,要证明b*’f(e)=f(e)*’b=b.
f(e)是恒等元,恒等元唯一,f(e)=e’.
同态Homomorphisim
设(S,*)和(T,*’)是两个半群,
函数f:S→T处处有定义,a,b∈S,
f(a*b)=f(a)*’f(b).
称f是(S,*)到(T,*’)内的同态映射,
如果f还是满射,称(S,*)和(T,*’)同态,T是S的同态像,记做
(S,*)(T,*’).
例20. 设A={0,1},则自由半群(A*, )与(A,+)同态,(A,+)的二元运算+由运算表给出:
+ 0
1
0 0
1
1 1 0
例. (Z,+) (Zn,+),
(Z,×) (Zn,×).
定理3. 恒等元的同态像是恒等元
设(S,*),(T,*)是独异点,恒等元分别是e和e’,同态f:(S,*)(T,*’), 则f(e)=e’.
定理4.子半群的同态像是子半群。
设f:(S,*) (T,*’)是半群同态,S’是(S,*)的子半群,
则f(S’)是(T,*’)的子半群。
证明.只要证f(S’)对运算封闭。
设t1,t2∈f(S’),要证t1*’t2∈f(S’).
存在s1,s2∈S’,
f(s1)=t1,f(s2)=t2, t1*’t2= f(s1)*’f(s2)
= f(s1*s2)∈f(S’).
定理5.交换半群的同态像是交换半群。
设f:(S,*) (T,*’)是到上半群同态,(S,*)是交换半群,
则(T,*’)的交换半群。
证明. 任意t1,t2∈T,
要证t1*’t2=t2*’t1.
存在s1,s2∈S,
f(s1)=t1,f(s2)=t2,
t1*’t2= f(s1)*’f(s2)= f(s1*s2)
=f(s2*s1)=f(s2)*’f(s1)=t2*’t1.
§9.3 乘积半群和商半群
Products and Quotiens Semigroup
定理1. 设(S,*)和(T,*’)是两个半群,则(S×T,*”)也是半群。
(s1, t1)*” (s2, t2)=( s1*s2, t1*’t2 ).
设(S,*)和(T,*’)是两个独异点,则(S×T,*”)也是独异点,恒等元是(e,e’)。
同余关系 congruence relation
设(S,*)是半群,R是S上等价关系。R称为S上同余关系:
aRa’, bRb’(a*b)R(a’*b’).
例1. Z上剩余关系是(Z,+)上同余关系:
ab(mod 2) 2 | a-b。
证明. ab(mod 2)是等价关系。
ab(mod 2), 2 | a-b, a-b=2k.
cd(mod 2), 2 | c-d, c-d=2t.
(a+c)-(b+d)=(a-b)+(c-d)=2(k+t)
a+c b+d(mod 2) ab(mod 2)是(Z,+)上同余关系。
Z上剩余关系是(Z,×)上同余关系.
例2.令A={0,1},自由半群(A*,)上关系R:
αRβα,β含有同样多个1。
则R是(A*,)上同余关系。
例3.设f(x)=x2-x-2, 令(Z,+)上关系R:aRb f(a)=f(b).
R是Z上等价关系,但不是同余关系。
-1R2,f(-1)=f(2)=0
-2R3,f(-2)=f(3)=4
-1+-2=-3, 2+3=5
f(-3)=10, f(5)=18
-1+-2 与 2+3 不满足R。
定理2. 设R是半群(S,*)上同余关系。定义商集S/R上二元运算*:
[a]*[b]=[a*b]。则(S/R,*)是半群。
证明. 设[a]=[a’], [b]=[b’],
要证[a*b]=[ a’*b’]
aRa’, bRb’,由*是同余关系
a*bRa’*b’,因此[a*b]=[ a’*b’],*是映射,二元运算。
还要证*满足结合律:
[a]*([b]*[c])=[a]*[b*c]
=[a*(b*c)]=[(a*b)*c]
=[a*b]*[c]=([a]*[b])*[c]
因此(S/R,*)是半群。
称S/R为商半群。
推论1. 设R是独异点(S,*)上同余关系,则(S/R,*)是独异点。
证明.恒等元e∈S,只要证明[e]是S/R,的恒等元。任何a∈S,
[a]*[e]=[a*e]=[a]
[e]*[a]=[e*a]=[a].