1.2-关系(简).ppt

1、第二节 关 系(relations),的基本概念及其性质 1.2.2等价关系 1.2.3部分序关系,1.2.1 关系的基本概念及其性质,定义1.2.1 设A1,A2,An是n个集合， 集合A1A2 An的一个子集F称为A1,A2,An上的一个n元关系。特别地，集合AB中的一个子集R，称为集合A与B上的一个二元关系(binary relation)，简称为关系。 对于xA，yB，若(x,y)R则称x，y有关系R，记为xRy；若(x,y)R，则称x，y没有关系R，记为xRy。 若B=A，则R称为A上的二元关系。,关系的特点,AA上的任一子集都是A上的一个关系； 若A=n，则A上的关系有 个。 A上

2、的三个特殊关系，即空关系；全域关系EA=AA；相等关系IA=(x,x)xA。 有序偶(a,b)=(c,d)的充要条件是a=c，b=d。,关系的补充说明,为了便于关系定义的理解并且与我们头脑中不够清晰严密的关系相区分，我们首先给出下列问题描述。 例假设目前中国乒乓球对男子队员集合是A=马琳，王励勤，马龙，王皓，郝帅，陈杞，闫森，女队员集合B=张怡宁，郭跃，郭炎，李晓霞，丁宁，牛剑锋，刘诗雯。现在要出征乒乓球世界杯赛，如果按照上面关系的定义，对男子双打，女子双打和混合双打分别可以构造出249个关系，但实际上这里的很多关系是没有实际意义的。假设教练组根据个人状态和实际情况确定双打和混双组合如下：男子

3、双打关系R1=(马琳,陈杞)，(王励勤,马龙)，(王皓，郝帅)，(陈杞, 马琳)，(马龙,王励勤)，(郝帅，王皓) ； 女子双打关系R2=(张怡宁,丁宁)，(郭跃,李晓霞)，(郭炎,牛剑锋)，（丁宁, 张怡宁)，(李晓霞, 郭跃)，(牛剑锋,郭炎)； 男女混双关系R3=(马龙, 张怡宁)，(王皓, 郭跃)，(郝帅, 刘诗雯)，(张怡宁, 马龙)，(郭跃,王皓)，(刘诗雯, 郝帅)。,从上述三个关系我们可以清晰地看出那些队员之间构成所需确切关系，并且把人们头脑中模糊的对称关系也显示地表达出来，而不是人们头脑中仅需要前三个二元有序对的关系能够确切表达的,这也是人与计算机理解问题的差异。这也是我们书

4、中的关系与我们日常所说关系的区别。 实际上关系还可以用坐标系来描述，例如二元关系可以用平面上的离散点坐标系来描述，两个坐标上的离散点集对应我们讨论的两个集合，这两个集合可以不同也可以相同，不如用坐标描述男子双打组合关系时这两个集合相同，而男女混双时不同，对于三元及以上关系可以用三维及以上坐标系表示。坐标系中不同点的组合就构成了不同的关系。,关系的补充说明,例,设A=a,b,c,d,e,f为学生集合，B=,为选修课程集合，C=2,3,4,5为学习成绩集合，学生与课程之间存在着一种关系即“选修关系”；学生、课程和成绩之间也存在着一种叫做“学习成绩关系”。设用R表示选修关系，S表示学习成绩关系，那么

5、R为A与B上的二元关系，S为A，B和C上的三元关系。,R=(a,),(a,),(b,),(b,),(c,),(c,),(e,),(f,) 表示学生a选修课程，；学生b选修课程，；学生c选修课程，；学生e 选修课程；学生f选修课程；而学生d没有选修任何课程。 S=(a,5), (a, ,5), (b, , 3), (c, ,4), (f, ,2) 表示学生a所选的两门课程成绩都是5分；学生b所选课程的成绩是3分；学生c所选课程的成绩是4分；学生f所选课程的成绩是2分。,关系是集合，因此集合的方法对关系都是有效的。因而有子关系，关系的并、交、差、余等运算。 例：R，S是集合A上的两个关系，若RS，

6、则称R为S的子关系； 对任意x，yA，有 x(RS)y当且仅当xRy或者xSy x(R S)y当且仅当xRy并且xSy x(R-S)y当且仅当xRy并且xSy x y当且仅当xR y,定义1.2.2 逆关系(inverse relation),设R是集合A上的一个关系。令R-1 =(y, x)xA, yA, 并且有xRy，则称关系R-1为关系R的逆。 例如，小于关系的逆关系是大于关系，大于关系的逆关系是小于关系，相等关系的逆关系仍是相等关系。 例：R=(a,b),(b,c),(a,c),(b,d),则R-1 = (b,a),(c,b),(c,a),(d,b),定义1.2.3 自反关系(refl

7、exive),集合A 上的关系R称为是自反的(反身的)，如果对每一个xA，都有xRx。 例：A=a, b, c, A 上的关系R1=(a,b),(b,b),(b,c) R2=(a,a),(a,b),(b,b),(b,c),(c,c) R是自反的当且仅当IAR，R是自反的当且仅当R-1是自反的 。,定义1.2.4 反自反关系(irreflexive),集合A上的关系R称为反自反的，如果对任意的xA，xRx均不成立。或者说对任意的xA，都有xRx。 例：A=a, b, c, A上的关系R1=(a,b),(b,b),(b,c) R2=(a,b),(b,c),(a,c) 显然，R是反自反的当且仅当 I

8、AR=。,讨论：,是否存在既具有自反性，又具有反自反性的关系？ 是否存在既不具有自反性，又不具有反自反性的关系？ 空关系 、全域关系EA、相等关系IA是否具有自反性，或反自反性？,定义1.2.4 对称关系(symmetric),集合A上的关系R称为对称的，如果xRy，则yRx。其中xA，yA。 例：A=a, b, c, A上的关系R1=(a,a),(a,b),(b,a),(b,c) R2=(a,a),(b,b),(c,b),(b,c),(a,c),(c,a) R是对称的当且仅当R-1=R 。,定义1.2.4反对称关系(antisymmetric),集合A上的关系R称为反对称的,如果xRy,则y

9、 Rx,除非x=y时成立。 其中xA,yA。 。 例：A=a, b, c, A上的关系R1=(a,a),(a,b),(b,c) R2=(a,a),(b,b),(c,b),(b,c),(c,a) R是反对称的当且仅当RR-1IA 。,讨论：,是否存在既具有对称性，又具有反对称性的关系？ 是否存在既不具有对称性，又不具有反对称性的关系？ 空关系 、全域关系EA、相等关系IA是否具有对称性，或反对称性？,定义1.2.4 传递关系(transitive),集合A上的关系R称为是传递的，如果xRy，yRz，则xRz。 其中xA，yA，zA。 例：A=a, b, c, A上的关系R1=(a,a),(a,b

10、),(b,c),(a,c) ， R2=(a,b),(a,c), R3=(a,a),(c,b),(b,c),(c,a)数的相等关系、大于关系、小于关系都具有传递性。,定义1.2.4 关系的乘积(composite),设R，S是集合A上的两个关系，令RS=(x, y)xA, yA且存在一个zA使得xRz，zSy。称关系RS为关系R和S的乘积或合成(composite) 。 例：兄弟关系和父子关系的乘积是叔侄关系，而姐妹关系和母子关系的乘积是姨与外甥关系。,例：,A=a, b, c, d, A上的关系 R和S ，R=(a, a),(b,a),(c,d)，S= (a,c),(a,d),(b,c),(c

11、,b)，则RS = (a,c),(a,d),(b,c),(b,d)SR = (a,d), (b,d),(c,a) 显然，RSSR，关系的乘法不满足交换率。,关系的乘法满足结合率,设R，S和T是集合A上的三个关系，证明： (RS)T= R(ST)。 分析：因为关系的乘积仍是集合，要证明集合相等，就要证明集合互为包含，我们首先证明(RS)TR(ST)，再证明R(ST) ( RS)T 。,证明(RS)TR(ST),任取(x, y)(RS)T，即x(RS)Ty，由关 系乘积的定义知，存在zA使得x(RS)z， zTy，同样对x(RS)z，必存在zA使得 xRz，zSz。故由zSz 和zTy知z(ST)

12、y， 再有xRz得xR(ST)y，即(x, y) R(ST), 从而证得了(RS)TR(ST),证明R(ST) (RS)T,任取(x, y)R(ST), 即xR(ST)y，由关 系乘积的定义知，存在zA使得xRz， z(ST)y，同样对z(ST)y，必存在zA使得 zSz，zTy 。故由xRz和zSz知x(RS)z， 再有zTy，得x(RS)Ty ，即(x,y)(RS)T， 从而证得了R(ST) (RS)T。 因此， (RS)T=R(ST)得证。,对A上任意的关系R，有RIA= IA R= R,由于关系的乘法运算满足结合律，因此我们可以用“幂”表示集合A上同一个关系的乘积，即 规定，R0=IA

13、。,综合思考题,设A表示工人的集合,B表示工作的集合. R1 表示A到B的二元关系,R1=(a,b)aA,bB, a分配去做工作b.设R2表示A到A的二元关系,R2=(a1,a2)a1,a2A,a1和a2不能友好相处.请你用R1和R2表示关系 R,使得xRy表示 x,y分配去做同样工作且能友好相处.,因为R1是A到B的二元关系,故R1-1表示B到A的二元关系, 则R1R1-1表示从A到A的二元关系,即由分配做同一样工作的两个人构成的序偶的全体.因此R=R1R1-1-R2,定理1.2.1,设R是A上的关系，m，n为任意的自然数，那么，(1) RmRn=Rm+n；(2) (Rm)n=Rmn。 证明

14、：(1)任给m，对n作归纳法。n=0时，Rm R0=Rm IA= Rm = Rm+0。假设Rm Rn=Rm+n，那么RmRn+1=Rm(RnR1)= (RmRn )R1= Rm+nR1= Rm+n+1= Rm+(n+1) 。,(2)任给m，对n作归纳法。n=0时，(Rm)0=IA= R0 = Rm0。假设(Rm)n=Rmn。那么(Rm)n+1= (Rm)n Rm = Rmn Rm= Rmn+m= Rm(n+1) 。,定理1.2.2,设集合A的元素数为n，R是A上二元关系，那么存在自然数i，j(0ij )使得Ri=Rj。 证明：由关系的特点知道，若A=n，则A上的关系有 个，因此，在 R0，R1

15、，R2，这 +1个关系中，至少有两个是相同的（鸽巢原理），即有i,j(0ij )使得Ri=Rj。,定理1.2.3,设R是集合A上的关系，若存在自然数i，j(ij)，使得Ri=Rj，则有 (1)Ri+k=Rj+k，kN；(2)Ri+kp+m=Ri+m，其中k，mN，p=j-i。 证明： (1) Ri+k= Ri Rk =Rj Rk =Rj+k；,证明,(2),根据(1),根据(1),根据(1),定理1.2.4,集合A上的关系R具有传递性的充要条件是R2 R。 证明：必要性。若R具有传递性，任取 (x,y)R2，于是存在zA，使得xRz，zRy， 因为R是传递的，所以有xRy，即(x,y) R,故

16、R2 R。 充分性。如果xRy，yRz，则xR2z。 因为R2 R，故xRz。所以具有传递性的。,二元关系的表示方法,1列举法:列出关系R中的所有序偶; 2关系矩阵;给定两个有限 集合A=a1,a2,B=b1,b2,R为A到B的一个二元关系,则可以用下列关系矩阵MR=rijmn来表示R: r11 r12 r1n MR= r21 r22 r2n ： ： ： rm1 rm2 rmn 其中rij=1,若(ai,bj)R;否则rij=0,若(ai,bj)R 关系的矩阵表示与矩阵的行列对应的集合A和B上的元素顺序是相关的,不同的排序会得到不同的关系矩阵.,二元关系的表示方法,3关系图:给定两个有限集合A

17、=a1,a2, am,B=b1,b2,bn,R为A到B的一个二元关系. 首先在平面上作m个结点代表a1,a2, am,然后作另外n结点代表b1,b2,bn.如果aiRbj,则画一条从ai到 bj的有向弧,这样的图称为R的关系图.,关系的性质总结,定义1.2.9 关系的闭包(closure),设A是非空集合，R是A上的二元关系。称R 是R的自反闭包(对称闭包，传递闭包)，如果R满足： （1）R是自反的(对称的，传递的)； （2）RR； （3）对A上任意关系R， 若R R，且R是自反的(对称的，传递的)，必有RR。,R 的自反闭包、对称闭包和传递闭包分别记为r(R)，s(R)，t(R) ，也称r，

18、s，t为闭包运算，它们作用于关系R后，产生包含R的最小的自反、对称、传递的关系。,定理1.2.5,设R是集合A上的关系，那么， (1) r(R)=IAR； (2) s(R)=RR-1； (3) t(R)=,（1）证明 r(R)=IAR,因为IA IAR，所以IAR具有自反性； 显然，R IAR 对A上任意关系R， 若R R，且R是自反的，往证IAR R。因为R是自反的，所以IA R ，又R R，所以IAR R。,（2）证明 s(R)=RR-1, 任取(x,y) RR-1 ，则(x,y) R或 (x,y)R-1 ，若(x,y)R，则有(y,x)R-1， 所以(y,x)RR-1；若(x,y)R-1

19、 ，则有 (y,x)R，所以(y,x)RR-1 ， RR-1具有对称性； 显然，R RR-1,对A上任意关系R， 若R R，且R是对称的，往证RR-1 R。 任取(x,y)RR-1 ，则(x,y)R或(x,y)R-1 ， 若(x,y)R，因为R R，则(x,y)R ； 若(x,y)R-1 ，则有(y,x)R，则(y,x)R， 因为R是对称的，所以(x,y)R ， 因此，RR-1 R。,（3）证明 t(R)=,对于任意x,y,zA，若(x,y) ， (y,z) , 则存在自然数j, k，使得(x,y) Rj，(y,z) Rk ，故(x,z) Rj Rk = Rj+k，从而(x，z) ，所以， 具

20、有传递性； 显然，R ,对A上任意关系R， 若R R，且R是传递的，往证 R。为此只要证对任意正整数n，Rn R 。对n采用归纳法，n=1时，显然有R1 R 。假设n=k时有Rk R ，任取(x, y)Rk+1，那么有z使(x,z)Rk，(z,y)R。根据归纳假设及题设，有(x,z)R ，(z,y)R。又R是传递的，故(x,y)R ，所以Rk+1 R；因此， R。证毕。,设R是有穷集合A上的关系，|A|=n，则 t(R)=,推论,1.2.2等价关系(equivalence relation),定义1.2.10设A是一个非空集合，R是A上二元关系。如果R具有自反性，对称性，传递性，则称R是一个等

21、价关系。 通常，用“ ”表示等价关系。 例：整数的同余关系，几何图形的面积相等关系，人群中的同姓关系、同龄关系等。,定义1.2.11 等价类(equivalence class),设A是一个非空集合，R是A上的等价关系。A的一个非空子集M叫做A关于R的一个等价类，如果,通常，用aR表示包含元素a的等价类，则 aR=x|(x,a)R ,a称为该等价类代表元。,例：,设集合A=1,2,3,10，R是模3同余关系，则3R=6R=9R=3,6,9, 1R= 4R= 7R= 10R=1,4,7,10 , 2R= 5R= 8R= 2, 5, 8都是等价类。 设A是本教室中的所有人集合，在同姓关系下，则本教

22、室中所有姓“张”的人构成的集合是一个等价类,所有姓“王”的人构成的集合是一个等价类, 。,定理1.2.6,设是集合A上的等价关系，于是等价类是存在的。 证明: (1)任取aA，令Mx|xA并且xa，显然，M非空。 (2)任取x1M，x2M，根据M的定义，则有x1a，x2a，而具有对称性，传递性，所以x1x2。 (3)任取x1M，若x1y，则x1a，而具有对称性，传递性，所以ya，故yM。 因此，M是一个等价类。,定理1.2.7,设是集合A上的等价关系，M1, M2 , ，是A中关于的所有等价类。于是AM1 M2 并且MiMj=(ij)，亦即，集合A上的等价关系把A分成了互不相交的等价类。,证明

23、：,任取Mi，Mj，ij。假设MiMj ，则必存在xMiMj，则任取aMi，b Mj，都有ax，bx，所以ab, 故MiMj，矛盾。 任取aA， 令MxxA并且xa，由定理1.2.6知，M是等价类，故有k，使得MMk，因为aM，所以，aM1M2Mk。显然有M1 M2 A。故AM1 M2 。,定义1.2.12 划分(partition),称集合A的子集族C为A的划分，如果：（1）若BC，则B；（2） ；（3）对任意的B，BC，若BB，则BB=。称C中元素为划分的单元，或划分块。 规定，A=时只有划分，,例：,设A=1,2,3,4,5,6,7,8,9,10， C1=1,2,3,4,5,6,7,8,

24、9,10 C2=1,3,2,4,5,6,7,8,9,10 C3=1,4,7,10,2,5,8,3,6,9,定义1.2.13 商集(quotient set),设R是非空集合A上的等价关系，以R的所有不同等价类为元素作成的集合称为A的商集，简称A的商集，记作A/R。 A/R恰是集合的一个划分。 设集合A=1,2,3,10，R是模3同余关系，则A/R 1R，2R ，3R，这里 1R=1,4,7,10, 2R= 2, 5, 8, 3R=3,6,9,例1.2.3,设A=a1,a2, , an，n1。 (1)验证EA，IA，Rij=IA(ai，aj)，(aj，ai)都是A上的等价关系，并求它们对应的商集

25、，其中ai，ajA，且ij。是A上的等价关系吗？ (2)A=a,b,c，试求出A上的全体等价关系及其对应的商集。,解,(1)EA，IA，Rij是等价关系(证明略)。A/IA=a1,a2,an；A/EA=a1,a2,an；A/Rij=ai,aj,ak1,ak2,akn-2，其中k1,k2,kn-2均不等于i或j，共有C2n个。因为无自反性，所以不是A上的等价关系。,(2)按(1)中n=3的情况，A=a,b,c上有5种不同的等价关系： EA，其商集为A/EA=a,b,c； IA，其商集为A/IA=a,b,c； R12=IA(a,b),(b,a)，A/R12=a,b,c； R13=IA(a,c),(

26、c,a)，A/R13=a,c,b； R23=IA(b,c),(c,b)，A/R23=b,c,a；,定理1.2.8,设A为一个非空集合。(1)设R为A上的任意一个等价关系，则对应R的商集A/R为A的一个划分。(2)设C为A的任一个划分，令RC=(x,y)|x,yA并且x, y属于C的同一划分块，则RC为A上的等价关系。,(1)证明：A/R是A的一个划分,设商集A/R M1, M2 , ，则i (i=1,2, )是A关于R的等价类，根据等价类的定义知，i (i=1,2,3, );又根据定理1.2.7知，AM1 M2 ，并且MiMj=(ij) ，所以，A/R是A的一个划分。,(2)证明：RC为A上的

27、等价关系,自反性；对任意的xA，有x和x属于C的同一划分块，所以(x,x) RC，则RC 具有自反性； 对称性；对任意的x,yA，若(x, y)RC，即x,y属于C的同一划分块，亦即y, x 属于C的同一划分块，所以(y,x) RC，则RC 具有对称性；,(2)证明：RC为A上的等价关系,传递性；对任意的x, y, zA，若(x, y)RC， (y, z)RC，即x与y属于同一划分块，y与z属于同一划分块，则x与z也属于同一划分块，所以(x,z) RC，则RC 具有传递性； 因此， RC为A上的等价关系。证毕。,第二类Stirling数,将n个不同的球放入r个相同的盒中去，并且要求无空盒，有多

28、少种不同的放法？这里要求nr。 不同的放球方法数即为n元集合A的不同的划分数，,设 表示将n个不同的球放入r个相同的盒中的方案数，称 为第二类Stirling数 。,第二类Stirling数的性质,(1),(2)满足如下的递推公式:,例1.2.4,集合A=a，b，c，d上有多少不同的等价关系？ 解：不同的划分个数为:不同的等价关系个数等于不同的划分个数，所以不同的等价关系个数为15。,定义1.2.14 加细,设C和C都是集合A的划分，若C的每个划分块都含于C的某个划分块中，则称C是C 的加细。 例：设A=1,2,3,4,5,6,7,8,9,10， C1=1,2,3,4,5,6,7,8,9,10

29、 C2=1,3,2,4,5,6,7,8,9,10 C3=1,4,7,10,2,5,8,3,6,9,C是C的加细当且仅当RCRC,例： 设A=x|x是吉大计算机学院的本科生， C=0901班的学生，0902班的学生，0903班的学生, C=大一的学生, 大二的学生,大三的学生, 大四的学生 C对应的等价关系RC是同班关系， C对应的等价关系RC是同年级关系。,例1.2.5,设A=a，b，c，找出A的全部划分及对应的等价关系，以及划分间的加细和关系中的包含关系。 解: 由第二类Stirling数易知，A上共有 个划分。,这些划分分别为：C1=a,b,c，C2=a,b,c，C3=b,a,c，C4=c

30、,a,b，C5=a,b,c。 它们对应的等价关系分别为:RC1=EA，RC2=IA(b, c), (c, b)，RC3= IA(a, c), (c, a)，RC4= IA(a, b), (b, a)，RC5=IA。 C2， C3， C4，C5都是C1的加细，RC2，RC3，RC4，RC5都是RC1的子集。,1.2.2部分序关系(partial ordering),定义1.2.15 设R是集合A上的一个关系。如果R具有自反性，反对称性，传递性，则称R为一个部分序关系(半序关系、偏序关系)。集合A在部分序关系R下做成一个部分序集(半序集、偏序集)。记作(A，R) 。 通常，将部分序关系R写做“”，

31、读做“小于或等于”。 显然，一个部分序集的子集仍为部分序集。,例,设A是整数集合， R是小于等于关系(或大于等于关系)。 设A是自然数集合，R是整除关系。 设A是一个集合族，R是“”关系。则(A,R)是一个部分序集；,哈斯图 (Hasse diagram),以平面上的点代表部分序集中的元素。 1）若xy，且xy，则将x画在y的下面。 2）若xy，xy，并且没有不同于x，y的z，使得xzy(称y盖住x)，则在x，y之间用直线连结。,例:,设Aa, b, a,b, a,b, c, a,b, c,d, a,b,c,e， 则(A, ) 是一个部分序集。,例:,设A1,2,3, 4,5,6,8,10,1

32、2,24，R是整除关系，则(A, R) 是一个部分序集。,定义 链(chain),设(A, )是一个部分序集，对任意x, yA，如果xy，或yx，称x与y可比(comparable) ；否则，称x与y不可比。 一个部分序集的子集，其中任意两个元素都可比，称该子集为一条链(chain)。,例:,设A1,2,3, 4,5,6,8,10,12,24，R是整除关系，则(A, R) 是一个部分序集。,定义1.2.16 全序集(totally ordered set),一个部分序集(A, )说是一个全序集，如果(A, )本身是一条链。 显然，全序集的子集仍为全序集。,例:,设A1,2,4, 8,16,32

33、,64，R是整除关系，则(A, R) 是一个全序集。,1,2,4,8,32,16,64,例:,设A整数集合，R是“小于等于”关系，则(A, R) 是一个全序集。,定义1.2.17拟序关系,设R是集合A上的一个关系。如果R具有反自反性，传递性，则称R为一个拟序关系。记为，读做“小于”。 例：数间的小于（“”）关系；集合间的真包含（“”）关系。,定义1.2.18,设(A, )是一个部分序集(poset)，(1)如果A中有一个元素a，对于所有的xA，都有xa(ax)，则称a为集合A的最大(最小)元。 （2）A中元素a说是一个极大(极小)元，如果除a之外，A中没有元素x，使得ax(xa)。,定义1.2

34、.18,(3) 对于A中的子集M，A中元素a称为子集M的一个上界(下界)，如果对M中任意元素m，都有ma(am)。 (4) 对于A中的子集M，A中元素a称为M的一个最小上界(或称上确界)，如果a是M的一个上界，并且对M的任意一个上界x，都有ax。,定义1.2.18,(5) 对于A中的子集M，A中元素a称为M的一个最大下界(或称下确界) ，如果a是M的一个下界，并且对M的任意一个下界x，都有xa 。,例:,例:,例题,设A=1,2,3,12,是A上的整除关系,(A,)和哈斯图如下,求B=2,4,6,C=4,6,9,D=1,2,5,10的特殊元素.,8,10,4,2,12,6,9,5,7,3,11

35、,1,定理1.2.9,设(A,)是一个部分序集，BA。 （1）若b是B的最大元(最小元)，则b必为B的最小上界(最大下界)； （2）若b为B的上(下)界，且bB，则b必为B的最大(最小)元； （3）若B有最大下界(最小上界)，则最大下界(最小上界)唯一。,定义1.2.19,设(A, )是一个部分序集。（1）称(A, )是良基的，如果A的任意非空子集都有关于的极小元；（2）称(A, )是良序集(well-ordered set)，如果(A, )是全序的、良基的。 例如：Ax|x是整数，0x100,在“”关系下，组成的部分序集是良基的，也是良序集。,引理,每一个非空有穷部分序集(A, )都有极小元素。 证明：选择A的一个元素a0，如