离散数学第五章1

的二元运算*. 使得对于任意Π1,Π2∈p(s), Π1*Π2是由Π1的 每个元素(s的子集)与Π2 中的每个元素的交集所组成的集合,
其中去掉空集φ.
如: s={a,b,c,d,e,f} Π1={{a,b}{c}{d,e,f}}, Π2={{a,b,c}{d}{e,f}} Π1*Π2={{a,b,}{c}{d}{e,f}} 则< p(s),*>是一个独异点. 因为集合p(s)对运算*是封闭的,即< p(s),*>是一个代数系统.
<N, . >是独异点, <N,+ >不是独异点, 无单位元.
例5: G是n阶方阵集合, ×是矩阵的乘法,则<G,×>是独异点, 单位元e =I . 例6: 代数系统<2U,∪>, < 2U ,∩>分别是以φ和U为单位元 的独异点.
例7: s是非空集合, p(s)是s的所有的分划的集合,定义在p(s)
1 2 3 I 1 2 3 1 2 3 2 3 1
1 2 3 1 3 2 1 2 3 3 1 2
1 2 3 2 1 3 1 2 3 3 2 1
例3: 代数系统<I, +>, <R+ , . >是半群, 但代数系统<I, - >, <R+ , / >均不是半群, 无结合律.
二. 独异点的概念
定义2: 若半群<s, *>对于运算*有单位元, 则称该半群为 独异点. 定理1 独异点有唯一的单位元.(第四章的结果)
例4: v1=<z, . > 与v1=<z, + >均为独异点, + . 是通常的运算.
在独异点<Z,+>中,0是单位元: a0=0, a n+1=an+ a 可有
证明:设<s,*>生成元g,则任意 a,b ∈s,存在i,j ∈Z 使得 a=gi, b=gj a*b=gi * gj= gi + j = g j +i = g j* gi= b* a 证毕
<Z,+>是一个循环独异点,1是生成元,0是单位元.
且θl* θl= θl, 所以
θl-1* (θl*θl) = θl -1* θl=e 另一方面 θl-1* (θl*θl) = (θl -1* θl)* θl= e * θl= θl 与单位元e不等于任一个左零元相矛盾.
§5.2 群 的 定 义
定义 设<G,*>是一个代数系统,若G上的运算*满足下列 条件,则称<G,*>是一个群: 1). 任意a,b ∈ G, 有a* ( b * c)= (a* b ) * c; 2). 存在元素e ∈ G, 对 任意a∈ G, a* e = e * a =a;
事实上,对任意的Π1,Π2∈p(s)→ Π1 * Π2∈p(s)，即Π1 * Π2
仍是s的一个分划。 为此，设Π1 * Π2＝{A1,A2,A3,……, Ar} Ai均为集合.
设Π I={Lπ11, Lπ12, ……, Lπ1k }, Π 2={Lπ21, Lπ22, ……, Lπ2h }
任意x∈ s, x是Π1 , Π2 中的某元素Lπ1m , Lπ2n的元素,(因为 Π1 , Π2是分划)所以x∈ Lπ1m ∩Lπ2n 所以 s Π1 * Π2 ;
所以Π1 * Π2∈p(s),即< p(s),*>是一个代数系统.进一步:
*运算有结合律(由交的结合律);而Π={s}是p(s)在运算*下 的单位元,所以< p(s),*>是一个独异点. 定义3 若独异点< s,*>中运算*是可交换的 ,则称< s,*>是可
交换的独异点.
例8:<R,*>是一代数系统,*运算由a*b=a+b-ab 所定义,有结 合律,交换律,0是单位元, <R,*>是可交换的独异点. 例9: RA表A上所有关系的 集合,*表示复合运算,则< RA ,*> 是一个不可交换的 独异点.单位元是IA.
环独异点.
1是幂等元,a是幂等元,c3是幂等元, b3是幂等元, d3是幂等元.
证明: 任意a ∈s,考察二元代数<sα,*>,这里sα={e, a,a2, …… }是 S 的子集, 因为s有限,所以sα是有限循环独异点,生成元为a,由于
sα是有限集,必有这样的 n, 它使an是在序列中出现过的元素,
设n是一个这样的最小的正整数,使得am=an m <n, an 是am以后 第一次出现的相等的元素,于是序列可写成: e, a,a2, ……am,a m+1 , ……an-1,an=am, a m+1 , ……an-1,am, a m+1 , ……(1) 所以sα中恰有n个不的元素:即
sα={e, a,a2, …… ,an-1 }
e∈ T, T非空,设任意a,b ∈ T, 有a*a=a,
b*b=b
由可换性: (a*b)* (a*b)= (a* ( b* a ) *b)=(a* (a * b) *b) =(a* a) * (b*b)=a*b
所以a *b是幂等元. 即<T, * >是<s, *>一子代数, 所以
<T, * >是<s, *>一子独异点. 体会证明方法. 定理5.4 设 h是代数系统v1=<s1,*1>到v2=<s2,*2>的满同态,则 1. 若v1=<s1,*1>是半群,则v2=<s2,*2>也是半群;
设n-m=L,观察(1)可知,任意i≥m, ai=a i+hL (2) (L类似于周期). 为证明定理: 可 取i=kL, 这里kL是使kL ≥m的L的最小倍数. (如m=10,L=3, 则取k=4) h ∈Z
显然,另外可取h为k,即 h=k (2)仍成立,故有 ai=akL=a kL+kL=a kL*a kL 则akL是幂等元.证毕. 前例中:sc={c0,c1,c2,c3,c4, ……}={1,c,b,a,d,b,a, ……}
因为c5=c*d=b=c2 所以m=2,n=2 L=n-m=3, 观察证明
任意i≥2, ai=a i+3h h ≥0 L=3 , k=1,h=1, i=3. 所以c 3+3=c3=a是幂等元 即c 3*c3=a*a=a= c3. i≥2=m i=Lk ≥m=2
再考察sd={d0,d1,d2,d3,d4, ……}={1,d,b,a,d,b,a, ……} 其中无c
b b
a
b
b
d a a
d
a b b
d
a b b
c3=c2*c =b*c=a
c4=c3*c =a*c= d 所以c是<s,*>的生成元, <s,*>是一循 环独异点.
c c d d d d
四. 循环独异点的表示,有限独异点的幂等元
定理5.2 设<s,*>是一有限独异点,则对每一a ∈s,存在 j ∈N 使得aj是幂等元.
例11.
<Ne , . >是<N , . >的子半群.非子独异点.
例12. <N , + >与<I,+>均是<R,+>的子独异点. 注意0 ∈N. 例13 G2(R) 是二阶矩阵的集合,则< G2(R) ,*>是独异点;
a 0 1 s { a R } 则<s,*>是独异点, e ( 0 0 0 <s,*>不是< G2(R) ,*>的子独异点, 因为 S E
10=0, 任意n ∈Z+ n=1+1+1+ …… +1=1n 1n = 1n-1+1 例10 设<s,*>是一循环独异点,其中s={1,a,b,c,d} ,乘法表如下: * 1 1 1 a a b b c c d d 可验证*满足结合律,-是单位元,且 c0=1 c1=c c2=c*c =b
a a
* 例14:<s, *>=<{e,0,1},* >是独异点,*由表 给出,<{0,1}*>是<s, *> 的子代数,子半群 e {0.1} , <{0,1}*>不是 是独异点,但 <s, *>的子独异点. e 0 e e 0 0 0 0
0 ) 0
1 1 0
1
1
0 1
定理5.3 设<s, *>是一个可交换的独异点,则s 的所有幂等 元形成的集合在运算 *下是<s, *>一子独异点。 证明 设T是中所有幂等元的集合.因为e是幂等元,所以
说明sd并不是一定等于s的,但d 的某次幂一定是幂等元,类似
前面的讨论,这里仍有d3是幂等元.
五.子半群与子独异点
定义6 若<s,*>是个半群,且<T,*>是<s,*>的子代数,则称 <T,*>是<s,*>的子半群.
性质:
1.子半群也是半群; 2.作为例a∈s,则T={a,a2,a3, ……}时, <T,*>是<s,*>的子半群. 定义 7 若<s,*>是个独异点,且<T,*>是<s,*>的子代数,且 e∈T,则称<T,*>是<s,*>的子独异点.
第五章 群
群的概念与理论在实际中应用十分广泛,在数理化,计算机, 社会科学等方面均有广泛的用途.
§5.1 半群与独异点
一.半群概念
定义1: 设S是非空集合,*是S上的二元运算,若*是可结合的,则 称代数系统<S, *>是半群. 例1: 代数系统<N,+>,<N, . >均为半群.+, . 是通常的加乘运算. 例2: G是n阶方阵集合, ×是矩阵的乘法,则<G,×>是半群.