复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）21/32

§2自由代数 定义197:设X是集合,G是一个T代数, σ为X到G的函数若对每个T代数A和X到 A的函数τ,都存在唯一的G到A的同态映 射φ,使得q=τ,则称G(更严格的说是 (G,o)是生成集X上的自由T-代数。X中 的元素称为生成元。 A变,φ变 τ变,φ也变 对给定的和A,φ是唯一的

§2 自由代数  定义19.7:设X是集合，G是一个T-代数， 为X到G的函数,若对每个T-代数A和X到 A的函数，都存在唯一的G到A的同态映 射,使得=，则称G(更严格的说是 (G,))是生成集X上的自由T-代数。X中 的元素称为生成元。  A变， 变  变， 也变  对给定的 和A，是唯一的

A

  X G  A   

引理191:若(G,o)是X上的自由T代数, 则o是内射

 引理19.1:若(G,)是X上的自由T-代数， 则是内射

定理191:对任何集合X和类型T,存在X 上的自由T代数,并且这种T代数在同 构意义下是唯一的。 ■证明:1唯一性 P1 G

 定理19.1:对任何集合X和类型T，存在X 上的自由T-代数，并且这种T-代数在同 构意义下是唯一的。  证明:1.唯一性  X G 1  G1 1  1 G X G1

■存在性证明采用构造法,在证明之前,先看个 例子

 存在性证明采用构造法,在证明之前,先看个 例子   1º G X G

设X={x1…,xm},T={F,}其中 ar(F)=0ar(→→)=2, } P1={(,an川ana∈Po} ={(→,F,F)}∪{(,F,x川x∈X}U (一,x1F)x∈U{(一→,x)xX∈好 P2={(→,an4)a∈P0aeP1yU{(→)a1)a∈ P1a∈P0}

 设 X={x1 ,…,xn ,…}，T={F,→}， 其 中 ar(F)=0,ar(→)=2，  令： P0={F,x1 ,…,xn ,…} P1={(→,ai ,aj )|ai ,ajP0 } ={(→,F,F)}∪{(→,F,xi )|xiX}∪ {(→,xi ,F)|xiX}∪{(→,xi ,xj )|xi ,xjX} P2={(→,ai ,aj )|aiP0 ,ajP1 }∪{(→,ai ,aj )|ai P1 ,ajP0 }

随着n的增大P将更为复杂。 n令P(X)为:P(X)=U n∈N 按类型I=({F,→},ar)定义P(X上的运算: 把0元运算Fx规定为P(X中的特定元素 二元运算→Px定义为: pox(p, =(,P, q 构成了X上T代数P(X),F,→exl 并且是自由T代数 这个T代数就是以后要讨论的命题代数

 随着n的增大Pn将更为复杂。  令P(X)为：P(X)=  n N Pn  按类型T=({F,→},ar)定义P(X)上的运算: 把0元运算FP(X)规定为P(X)中的特定元素 F 二元运算→P(X)定义为: →P(X)(p,q)=(→,p,q)， 构成了X上T-代数[P(X),FP(X),→P(X)] 并且是自由T-代数 这个T-代数就是以后要讨论的命题代数

(2)存在性 n采用递归构造方法 iG。=T0UX 这里假定Tx=② i假设G(0rn已经确定,则: Gn=(ta1…ak)t∈Ta.-1 ∑ ⅲG=∪Gn n∈ N

 (2)存在性  采用递归构造方法  ⅰG0=T0∪X.  这里假定T0∩X=  ⅱ假设Gr (0r<n)已经确定，则： G {(t,a , ,a ) | t T , , 1} 1 n = 1 k  k   = − = a G r n k i i r i  i ⅲ  n N G Gn  =

ⅳ定义G中运算te;GarG v对任何x∈X,o(x)=x 构造φ 称X中的元素为生成元 Gn是T表达式集,其复杂程度随着n的增大而 增加。 推论191:设G是可列集X={x1…,xm}上的自 由T代数。则G中每个元素都是某个有限子集 Xn={1xn所生成的自由T代数中的元素。 下次讲余下部分和第二十章的202,20.3

 ⅳ定义G中运算tG:Gar(t)→G  ⅴ对任何xX,(x)=x  构造  称X中的元素为生成元  Gn是T-表达式集，其复杂程度随着n的增大而 增加。  推论19.1:设G是可列集X={x1 ,…,xn ,…}上的自 由T-代数。则G中每个元素都是某个有限子集 Xn={x1 ,…,xn }所生成的自由T-代数中的元素。  下次讲余下部分和第二十章的20.2，20.3

■作业:P380:3,5,7

作业: P380 :3,5,7