离散数学第四讲半群和独异点

离散数学第四讲半群和独异点1第1页，共10页，2023年，2月20日，星期一定义2：若半群〈S,*〉对运算*有么元，则称该半群为含么半群,也称独异点。（3点）例2：判断下列给出的代数是不是独异点。①〈E,+〉和〈E,*〉,E为正偶数集{2,4,6,…}；②〈S,*〉，其中S是不同高度的人的集合，a*b表示a,b

中较高者；③〈R+,·〉〈R+,÷〉④〈{Rn|n∈N},合成运算，R0〉，其中R是S上的二元关系；

×√，么元为最矮的人√

×√

半群和独异点2第2页，共10页，2023年，2月20日，星期一定义3：如果〈S,*〉是半群,T⊆S且关于运算*封闭,那么〈T,*〉是〈S,*〉的子代数,称〈T,*〉为

〈S,*

〉的子半群。如〈[0，1],*

〉,〈N,*

〉都是〈R,*

〉的子半群.定理1：子半群是半群。证：

子半群是子代数,关于运算*封闭,结合律是继承的,

所以是半群。证毕。

半群和独异点3第3页，共10页，2023年，2月20日，星期一定义4：如果〈S,*,1〉是独异点。T⊆S,且关于运算*封闭,1∈T,那么〈T,*,1〉是〈S,*,1〉的子代数,称〈T,*,1〉是〈S,*,1〉的子独异点。如〈N,*,1

〉就是〈R,*,1

〉的子独异点.定理2：子独异点是独异点。证：子独异点是子代数,关于运算*封闭,含有么元,

结合律是继承的,所以是独异点。证毕。

半群和独异点4第4页，共10页，2023年，2月20日，星期一注：独异点一定是半群，但半群不一定是独异点。但可通过添加新元素将半群变为独异点，如半群〈[0，1),*

〉

添加么元1可变为独异点〈[0，1],*

,1〉。定理3：独异点〈S,*

〉中，运算*的运算表没有两行和两列是相同的。证：设S是有限集{e,a1,a2…an}，对任何ai,aj∈S，若ai≠aj

则e*ai≠e*aj,所以任意两列都不相同。又因为ai*e≠aj*e,所以任意两行都不相同。

半群和独异点5第5页，共10页，2023年，2月20日，星期一定义5：在半群(独异点)中,若运算是可交换的,则称此半群(独异点)为可交换半群(可交换独异点)。定理4:在任何可交换独异点〈S,*,e〉中,S的等幂元素集合T可构成子独异点。证:i)任取x,y∈T,

则x

*y=(x*x)*(y*y)=x*(x*y)*y=(x*y)*(x*y)

所以,x*y∈T,故运算封闭；

ii)T是S的子集，*在T上可结合；

iii)e*e=e,e是等幂元素,所以,e∈T。故〈T,*,e〉是子独异点。证毕。本定理对可交换半群也成立。

半群和独异点6第6页，共10页，2023年，2月20日，星期一下面我们定义独异点〈S,*,e〉中任意元素a的幂。用归纳定义:(1)(基础)a0=e(2)(归纳)an+1=an*a(n∈N)

由于独异点中,运算*是可结合的,容易证明如此定义的a的幂满足以下指数定律:

(1)(2)

半群和独异点7第7页，共10页，2023年，2月20日，星期一

定义6:

在独异点〈S,*,e〉中,如果存在一个元素g∈S,

使每一元素a∈S,都有一个相应的h∈N能把a写成

gh,

即a=gh

，则称此独异点为循环独异点。并称元素g

是此循环独异点的生成元,又可说此循环独异点是由

g生成的。例3：①〈N,+,0〉

是循环独异点，生成元是1，因为任取i∈N，当

i=0时，0=10；i≠0时，有

i=1i

。②是循环独异点，生成元为b,c1=b0,a=b2,b=b1,c=b3;1=c0,a=c2,b=c3,c=c1.

半群和独异点8第8页，共10页，2023年，2月20日，星期一定理5：每个循环独异点都是可交换的。

证：设〈S,*,e〉是循环独异点,其生成元是g,

对任意a、b∈S,存在m、n∈N,使a=gm和b=gn,