《集合论与图论》第8讲1 第8讲等价关系与序关系 内容提要 ?等价关系,等价类,商集 ?划分, 第二类Stirling数 ?偏序,线序,拟序,良序 ?哈斯图 ?特殊元素: 最?元,极?元,?界,?确界 ?(反)链 《集合论与图论》第8讲2 等价(equivalence)关系 ?定义 ?同余关系 ?等价类 ?商集 ?划分 ?划分的加细 ?Stirling子集数 《集合论与图论》第8讲3 等价(equivalence)关系定义 ?等价关系: 设R?A×A 且A≠?, 若R是自 反的, 对称的, 传递的,则称R为等价关系 ?例9: 判断是否等价关系(A是某班学生): R 1 ={<x,y>|x,y∈A∧x与y同年生} R 2 ={<x,y>|x,y∈A∧x与y同姓} R 3 ={<x,y>|x,y∈A∧x的年龄不比y小} R 4 ={<x,y>|x,y∈A∧x与y选修同门课程} R 5 ={<x,y>|x,y∈A∧x的体重比y重} 《集合论与图论》第8讲4 例9(续) × × × √ √ 等价关系 ×√√x与y选修同 门课程 R 4 √√√x与y同姓R 2 √××x的体重比y 重 R 5 √×√x的年龄不比 y小 R 3 √√√x与y同年生R 1 传递对称自反定义 《集合论与图论》第8讲5 例10 ?例10: 设R?A×A 且A≠?, 对R依次求三 种闭包共有6种不同顺序, 其中哪些顺序 一定导致等价关系? rst( R ), rts( R ), str( R ), srt( R ), trs( R ), tsr( R )=t(s(r( R ))) ?解: st( R )?ts( R ), sr( R )=rs( R ),… tsr( R )=trs( R )=rts( R ) str( R )=srt( R )=rst( R ) 《集合论与图论》第8讲6 例10(续) √ √ √ √(等价闭包) × 传递 √ 对称 × √ str(R)=srt(R) =rst( R ) 等价关系 自反 tsr(R)=trs(R) =rts( R ) 《集合论与图论》第8讲7 等价类(equivalence class) ?等价类: 设R是A≠?上等价关系,?x∈A,令 [x] R ={ y | y∈A ∧ xRy }, 称[x] R 为x关于R的等价类, 简称x的等价类, 简记为[x]. ?等价类性质: [x] R ≠? ; xRy ? [x] R =[y] R ; ?xRy ? [x] R ∩[y] R =? ; U{ [x] R | x∈A } =A. 《集合论与图论》第8讲8 定理27 ?定理27:设R是A≠?上等价关系,?x,y∈A, (1) [x] R ≠? (2) xRy ? [x] R =[y] R ; (3) ?xRy ? [x] R ∩[y] R =? ; (4) U{ [x] R | x∈A } =A. ?证明: (1) R自反?xRx?x∈[x] R ?[x] R ≠?. x 《集合论与图论》第8讲9 定理27(证明(2)) ? (2) xRy ? [x] R =[y] R ; ?证明: (2) 只需证明[x] R ?[y] R 和[x] R ?[y] R. (?) ?z, z∈[x] R ∧xRy? zRx∧xRy ? zRy ? z∈[y] R . ∴ [x] R ?[y] R . (?) 同理可证. x y z 《集合论与图论》第8讲10 定理27(证明(3)) ?(3) ?xRy ? [x] R ∩[y] R =? ; ?证明: (3) (反证) 假设?z, z∈[x] R ∩[y] R , 则 z∈[x] R ∩[y] R ? zRx∧zRy ? xRz∧zRy ? xRy, 这与?xRy矛盾! ∴ [x] R ∩[y] R =?. x y z 《集合论与图论》第8讲11 定理27(证明(4)) ? (4) U{ [x] R | x∈A } = A. ?证明: (4) A=U{ {x} | x∈A } ? U{ [x] R | x∈A } ? U{ A | x∈A }=A. ∴ U{ [x] R | x∈A } = A. # x y 《集合论与图论》第8讲12 ?同余关系: 设n∈{2,3,4,…}, x,y∈Z,则 x与y模n同余(be congruent modulo n) ? x≡y(mod n) ? n|(x-y) ? x-y=kn (k∈Z) ?同余关系是等价关系 ?[0] ={ kn|k∈Z}, [1] ={ 1+kn|k∈Z}, [2] ={ 2+kn|k∈Z},…, [n-1]={(n-1)+kn|k∈Z}. 同余(congruence)关系 6 39 8 75 4 2 1 10 11 0 《集合论与图论》第8讲13 例11 ?例11: 设A={1,2,3,4,5,8}, 求 R 3 = { <x,y> | x,y∈A ∧ x≡y(mod 3) } 的等价类, 画出R 3 的关系图. ?解: [1]=[4]={1,4}, [2]=[5]=[8]={2,5,8}, [3]={3}. # 1 4 25 8 3 《集合论与图论》第8讲14 商集(quotient set) ?商集: 设R是A≠?上等价关系, A/R = { [x] R | x∈A } 称为A关于R的商集, 简称A的商集. ?显然U A/R = A. ?例11(续): A/R 3 ={ {1,4}, {2,5,8}, {3} }. 《集合论与图论》第8讲15 例12(1) ?例12(1): 设A={a 1 ,a 2 ,…,a n }, I A , E A , R ij =I A ∪{<a i ,a j >,<a j ,a i >} 都是A上等价关系, 求对应的商集, 其中 a i ,a j ∈A, i≠j. ?是A上等价关系吗? 解: A/I A ={ {a 1 }, {a 2 },…, {a n } } A/E A ={ {a 1 ,a 2 ,…,a n } } A/R ij = A/I A ∪{{a i ,a j }} - {{a i },{a j }}. ?不是A上等价关系(非自反). # 《集合论与图论》第8讲16 划分(partition) ?划分: 设A≠?, A?P(A),若A满足 (1) ??A ; (2) ?x,y( x,y∈A ∧ x≠y ? x∩y=? ) (3) UA = A 则称A为A的一个划分, A中元素称为划分 块(block). 《集合论与图论》第8讲17 划分(举例) ?设?≠A 1 ,A 2 ,…,A n ?E, 则以下都是划分: A i = {A i ,~A i }, ( i=1,2,…,n ) A ij = {A i ∩A j ,~A i ∩A j , A i ∩~A j ,~A i ∩~A j }-{?} ( i,j =1,2,…,n ∧ i≠j ) …… A 12…n = {~A 1 ∩~A 2 ∩… ∩~A n ,…, ~A 1 ∩~A 2 ∩… ∩~A n-1 ∩A n ,… A 1 ∩A 2 ∩… ∩A n }-{?}. # 《集合论与图论》第8讲18 划分(举例,续) A i ~A i 《集合论与图论》第8讲19 等价关系与划分是一一对应的 ?定理28: 设A≠?, 则 (1) R是A上等价关系? A/R是A的划分 (2) A是A的划分? R A 是A上等价关系,其中 xR A y ??z(z∈A ∧ x∈z ∧ y∈z) R A 称为由划分A所定义的等价关系(同块关系). # 《集合论与图论》第8讲20 例12(2) ?例12(2): A={a,b,c}, 求A上全体等价关系. ?解: A上不同划分共有5种: a b c a b c a b c a b c a b c R 1 = E A , R 2 =I A ∪{<b,c><c,b>}, R 3 =I A ∪{<a,c><c,a>}, R 4 =I A ∪{<a,b><b,a>}, R 5 =I A . # 《集合论与图论》第8讲21 Bell数(Bell number) ?问题: 给n个对象分类, 共有多少种分法? ?答案: Bell数B n = (Eric Temple Bell, 1883~1960) ?Stirling子集数(Stirling subset number) : 把n个对象分成k个非空子集的分法个数. ? ?递推公式: . 21 1 ? ? ? ? ? ? ++ ? ? ? ? ? ? + ? ? ? ? ? ? = ? ? ? ? ? ? ∑ = n nnn k n n k L ? ? ? ? ? ? k n .1, 1 ,12 2 ,1 1 ,0 0 21 = ? ? ? ? ? ? = ? ? ? ? ? ? ? ?= ? ? ? ? ? ? = ? ? ? ? ? ? = ? ? ? ? ? ? ? n n C n nnnn n n . 1 11 ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? = ? ? ? ? ? ? k n k n k k n 《集合论与图论》第8讲22 Stirling子集数 ?递推公式: . 1 11 ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? = ? ? ? ? ? ? k n k n k k n 剔除一个 其余分k类 加入一类 其余分k-1类 自成一类 《集合论与图论》第8讲23 第一、二类Stirling数 ?第一类Stirling数(Stirling number of the first kind): s(n,k) ?第二类Stirling数(Stirling number of the second kind): S(n,k)= ? ? ? ? ? ? k n .)1()2)(1(),( 0 kk n k xkxxxxxkns =+???= ∑ = L .),()1()2)(1(),( 00 k n k n k n xknSkxxxxknSx ∑∑ == =+???= L 《集合论与图论》第8讲24 Bell数表 190,899,322148777 13 12 11 10 9 8 n 27,644,4372036 678,570154 21,14722 4,213,597525 115,97553 4,14011 B n B n n 《集合论与图论》第8讲25 第二类Stirling数表 9 1 45 8 1 36 750 1 28 462 5,880 7 1 21 266 2,646 22,827 6 42,525 6,951 1,050 140 15 1 5 34,501 7,770 1,170 350 65 10 1 4 101 9,3305111010 3,035255109 966127108 1 1 1 1 1 1 1 3016307 31 15 7 3 1 2 9006 604 02 2505 103 10 30n\k 《集合论与图论》第8讲26 例13 ?例13: 问A={a,b,c,d}上有多少种等价关系? ?解: # .1516711)12(1 4 4 3 4 2 4 1 4 2 4 3 4 =+++=++?+= ? ? ? ? ? ? + ? ? ? ? ? ? + ? ? ? ? ? ? + ? ? ? ? ? ? = CB 《集合论与图论》第8讲27 划分的加细(refinement) ?划分的加细: 设A和B都是集合A的划分, 若A的每个划分块都包含于B的某个划分 块中, 则称A为B的加细. ? A为B的加细? R A ?R B 《集合论与图论》第8讲28 例14 ?例14: 考虑A={a,b,c}上的划分之间的加细. ?解: a b c a b c a b c a b c a b c 加细加细 加细 加细 加细 加细 # 《集合论与图论》第8讲29 序关系 ?偏序,线序,拟序,良序 ?哈斯图 ?特殊元素: 最?元, 极?元, ?界, ?确界 ?(反)链 《集合论与图论》第8讲30 偏序(partial order)关系 ?偏序关系: 设R?A×A 且A≠?, 若R是自 反的, 反对称的, 传递的, 则称R为偏序关 系 ?通常用?表示偏序关系,读作“小于等于” <x,y>∈R ? xRy ? x?y ?“严格小于”: x?y ? x?y ∧ x≠y ?偏序集(poset): <A,?>, ?是A上偏序关系 ?例子: <A,≤>, <A,|>, <A,?>, <π,? 加细 > 《集合论与图论》第8讲31 偏序集<A,≤>, <A,≥>, <A,|> ??≠A?R ≤ = { <x,y> | x,y∈A ∧ x≤y }, ≥ = { <x,y> | x,y∈A ∧ x≥y }, ??≠A?Z + ={ x | x∈Z ∧ x>0 } | = { <x,y> | x,y∈A ∧ x|y } 《集合论与图论》第8讲32 偏序集<A,?> ?A?P(A), ? = { <x,y> | x,y∈A ∧ x?y } ?设A={a,b}, A 1 ={?,{a},{b}}, A 2 ={{a},{a,b}}, A 3 =P(A)={?,{a},{b},{a,b}},则 ? 1 = I A1 ∪ { <?,{a}>,<?,{b}> } ? 2 = I A2 ∪ { <{a},{a,b}> } ? 3 = I A3 ∪ { <?,{a}>,<?,{b}>, <?,{a,b}>, <{a},{a,b}>, <{b},{a,b}> } 《集合论与图论》第8讲33 偏序集<π,? 加细 > ?A≠?, π是由A的一些划分组成的集合 ? 加细 = { <x,y> | x,y∈π ∧ x是y的加细} ?设A={a,b,c}, A 1 ={{a,b,c}},A 2 ={{a},{b,c}}, A 3 ={{b},{a,c}},A 4 ={{c},{a,b}},A 5 ={{a},{b},{c}} 取π 1 ={A 1 ,A 2 },π 2 ={A 2 ,A 3 },π 3 ={A 1 ,A 2 ,A 3 ,A 4 ,A 5 } ? 1 = I π1 ∪ { <A 2 ,A 1 > }, ? 2 = I π2 , ? 3 = I π3 ∪ { <A 2 ,A 1 >,<A 3 ,A 1 >, <A 4 ,A 1 >, <A 5 ,A 1 >,<A 5 ,A 2 >,<A 5 ,A 3 >,<A 5 ,A 4 >}. # 《集合论与图论》第8讲34 哈斯图(Hasse diagram) ?设<A,?>是偏序集, x,y∈A ?可比(comparable): x与y可比? x?y ∨ y?x ?覆盖(cover): y覆盖x ? x?y ∧??z( z∈A ∧ x?z?y ) ?哈斯图: 当且仅当y覆盖x时,在x与y之间 画无向边, 并且x画在y下方 《集合论与图论》第8讲35 例16(1)(2) ?例16: 画出下列偏序关系的哈斯图. (1) <A,|>, A={1,2,3,4,5,6,9,10,15} (2) <A,?>, A={a,b,c}, A?P(A), A={?,{a},{b},{c},{a,b},{b,c},{a,c}} ?解: 1 2 4 3 6 9 15 5 10 ? {a} {b} {c} {a,b} {a,c} {b,c} 《集合论与图论》第8讲36 例16(3) ?例16: 画出下列偏序关系的哈斯图. (3) <π,? 加细 >, π={A 1 ,A 2 ,A 3 ,A 4 ,A 5 ,A 6 }, A={a,b,c,d} A 1 = { {a}, {b}, {c}, {d} }, A 2 = { {a,b}, {c,d} }, A 3 = { {a,c}, {b,d} }, A 4 = { {a}, {b,c,d} }, A 5 = { {a}, {b}, {c,d} }, A 6 = { {a,b,c,d} } ?解: A 1 A 2 A 5 A 3 A 4 A 6 # 《集合论与图论》第8讲37 偏序关系中的特殊元素 ?最大元, 最小元 ?极大元, 极小元 ?上界, 下界 ?最小上界(上确界), 最大下界(下确界) 《集合论与图论》第8讲38 最大元, 最小元 ?设<A,?>为偏序集, B?A, y∈B ?最大元(maximum/greatest element): y是B的最大元? ?x( x∈B → x?y ) ?最小元(minimum/least element): y是B的最小元? ?x( x∈B → y?x ) 《集合论与图论》第8讲39 最大元, 最小元举例(例16(1)) ?例16(1): <A,|>, A={1,2,3,4,5,6,9,10,15} B 1 ={1,2,3}, B 2 ={3,5,15}, B 3 =A. B 1 的最大元是{}, B 1 的最小元是{1} B 2 的最大元是{15}, B 2 的最小元是{} B 3 的最大元是{}, B 3 的最小元是{1} 1 2 4 3 6 9 15 5 10 1 2 4 3 6 9 15 5 10 《集合论与图论》第8讲40 极大元,极小元 ?设<A,?>为偏序集, B?A, y∈B ?极大元(maximal element): y是B的极大元? ?x( x∈B ∧ y?x → x=y ) ?极小元(minimal element): y是B的极小元? ?x( x∈B ∧ x?y → x=y ) 《集合论与图论》第8讲41 极大元,极小元举例(例16(1)) ?例16(1): <A,|>, A={1,2,3,4,5,6,9,10,15} B 1 ={1,2,3}, B 2 ={3,5,15}, B 3 =A. B 1 的极大元是{2,3}, B 1 的极小元是{1} B 2 的极大元是{15}, B 2 的极小元是{3,5} B 3 的极大元是{4,6,9,15,10}, B 3 的极小元是{1} 1 2 4 3 6 9 15 5 10 1 2 4 3 6 9 15 5 10 《集合论与图论》第8讲42 上界, 下界 ?设<A,?>为偏序集, B?A, y∈A ?上界(upper bound): y是B的上界? ?x( x∈B → x?y ) ?下界(lower bound): y是B的下界? ?x( x∈B → y?x ) 《集合论与图论》第8讲43 上界, 下界举例(例16(1)) ?例16(1): <A,|>, A={1,2,3,4,5,6,9,10,15} B 1 ={1,2,3}, B 2 ={3,5,15}, B 3 =A. B 1 的上界是{6}, B 1 的下界是{1} B 2 的上界是{15}, B 2 的下界是{1} B 3 的上界是{}, B 3 的下界是{1} 1 2 4 3 6 9 15 5 10 1 2 4 3 6 9 15 5 10 《集合论与图论》第8讲44 最小上界, 最大下界 ?设<A,?>为偏序集, B?A ?最小上界(least upper bound): 设C = { y | y是B的上界}, C的最小元称 为B的最小上界, 或上确界. ?最大下界(greatest lower bound): 设C = { y | y是B的下界}, C的最大元称 为B的最大下界, 或下确界. 《集合论与图论》第8讲45 最小上界,最大下界举例(例16(1)) ?例16(1): <A,|>, A={1,2,3,4,5,6,9,10,15} B 1 ={1,2,3}, B 2 ={3,5,15}, B 3 =A. B 1 的最小上界是{6}, B 1 的最大下界是{1} B 2 的最小上界是{15}, B 2 的最大下界是{1} B 3 的最小上界是{}, B 3 的最大下界是{1} 1 2 4 3 6 9 15 5 10 1 2 4 3 6 9 15 5 10 《集合论与图论》第8讲46 特殊元素比较 √√××(表示不一定) 最大元 ×××× 上界 ×√×× 下确界 ×××× 下界 √××<Z,≤>,B=Z√ (表示一定) 极大元 ×√×× 上确界 √××√ 极小元 √√×× 最小元 ∈B 唯一 存在(B无穷)存在(B非空有穷) 《集合论与图论》第8讲47 链(chain), 反链(antichain) ?设<A,?>为偏序集, B?A, ?链(chain): B是A中的链? ?x?y(x∈B∧y∈B → x与y可比) |B|称为链的长度 ?反链(antichain): B是A中的反链? ?x?y(x∈B∧y∈B∧x≠y → x与y不可比) |B|称为反链的长度 《集合论与图论》第8讲48 链, 反链(举例) ?设偏序集<A,?>如图所示, A={a,b,…,k}. a b c d e f g h i j k B 1 ={a,c,d,e}是长为4的链 上界{e,f,g,h}, 上确界{e} 下界{a}, 下确界{a} B 2 ={a,e,h}是长为3的链 B 3 ={b,g}是长为2的链 B 4 ={g,h,k}是长为3的反链 上界,下界,上确界,下确界: 无 B 5 ={a}是长为1的链和反链 B 6 ={a,b,g,h}既非链,亦非反链 《集合论与图论》第8讲49 定理31 ?定理31: 设<A,?>为偏序集, A中最长链的 长度为n, 则 (1) A中存在极大元 (2) A存在n个划分块的划分, 每个划分块 都是反链(即A划分成n个互不相交的反链) ?推论: 设<A,?>为偏序集, 若|A|=mn+1,则 A中要么存在长度为m+1的反链, 要么存 在长度为n+1的链. 《集合论与图论》第8讲50 定理31(举例) a b c d e f g h i j k 最长链长度为6, 如 B 1 ={a,c,d,e,f,h}, B 2 ={a,c,d,e,f,g}, A={a,b,…,k}可以划分为 A 1 = { {a,b,i}, {c,j}, {d}, {e}, {f}, {g,h,k} }, A 2 = { {a,b}, {c,i}, {d,j}, {e,k}, {f}, {g,h} } |A|=11=2×5+1, A中既有长度为2+1=3的反链, 也有长度为5+1=6的链 《集合论与图论》第8讲51 定理31(证明(1)) ?定理31: 设<A,?>为偏序集, A中最长链的 长度为n, 则(1) A中存在极大元 ?证明: (1) 设B是A中长度为n的最长链, B 有极大元(也是最大元)y, 则y也是A的极 大元, 否则A中还有比y“大”的元素z, B就 不是最长链. 《集合论与图论》第8讲52 定理31(证明(2)) ?定理31: 设<A,?>为偏序集, A中最长链的 长度为n, 则(2) A存在n个划分块的划分, 每个划分块都是反链(即A划分成n个互不 相交的反链) ?证明: (2) A 1 = { x | x是A中的极大元}, A 2 = { x | x是(A-A 1 )中的极大元},… A n = { x | x是(A-A 1 -…-A n-1 )中的极大元}, 则A = { A 1 , A 2 ,…, A n }是满足要求的划分. 《集合论与图论》第8讲53 定理31(证明(2):举例) a b c d e f g h i j k 最长链长度为6, A 1 = { g, h, k }, A 2 = { f, j }, A 3 = { e, i }, A 4 = { d }, A 5 = { c }, A 6 = { a, b }, A = { {a,b}, {c}, {d}, {e,i}, {f,j}, {g,h,k} } 《集合论与图论》第8讲54 定理31(证明(2)续) ?证明(续): [1] A 1 = { x | x是A中的极大元}, 极大 元互相之间不可比, 所以A 1 是反链, 同理 A 2 ,…,A n 都是反链. [2]显然A 1 ,A 2 ,…,A n 互不相交. [3]最长链上的元素分属A 1 ,A 2 ,…,A n , 所以 A 1 ,A 2 ,…,A n 都非空. [4]假设z∈A-A 1 -…-A n ,则最长链上的元素加上z 就是长度为n+1的链, 矛盾! 所以 A=A 1 ∪A 2 ∪…∪A n . 综上所述, A={ A 1 ,A 2 ,…,A n }确是所求划分. # 《集合论与图论》第8讲55 定理31推论(证明) ?推论: 设<A,?>为偏序集, 若|A|=mn+1,则 A中要么存在长度为m+1的反链, 要么存 在长度为n+1的链. ?证明: (反证)假设A中既没有长度为m+1 的反链, 也没有长度为n+1的链, 则按照定 理31(2)中要求来划分A, A至多划分成n块, 每块至多m个元素, 于是A中至多有mn个 元素, 这与|A|=mn+1矛盾! # 《集合论与图论》第8讲56 全序(total order)关系 ?全序关系: 若偏序集<A,?>满足 ?x?y( x∈A∧y∈A → x与y可比) 则称?为全序关系, 称<A,?>为全序集 ?全序关系亦称线序(linear order)关系 ?例: <A,≤>, <A,≥> 《集合论与图论》第8讲57 拟序(quasi-order)关系 ?拟序关系: 设R?A×A 且A≠?, 若R是反 自反的, 传递的, 则称R为拟序关系 ?通常用?表示拟序关系(对比:“严格小于”) ?反自反性与传递性蕴涵反对称性 ?拟序集: <A,?>, ?是A上拟序关系 ?例子: 设?≠A?R, ?≠B?Z + <A,<>,<A,>>,<B,|’>,<A,?> |’ = { <x,y> | x,y∈B ∧ x|y ∧ x≠y} 《集合论与图论》第8讲58 定理29 ?定理29:设?是非空集合A上偏序关系,?是 A上拟序关系,则 (1) ?是反对称的; (2) ?-I A 是A上拟序关系; (3) ?∪I A 是A上偏序关系. ?证明: (1) x?y ∧ y?x ? x?x , 矛盾! (2)(3) 显然. 《集合论与图论》第8讲59 定理30 ?定理30:设?是非空集合A上拟序关系,则 (1) x?y,x=y,y?x中至多有一式成立; (2) (x?y ∨ x=y) ∧ (y?x ∨ x=y) ? x=y. ?证明: (1) 两式以上成立导致x?x , 矛盾! (2) x≠y ? (x?y ) ∧ (y?x ), (由已知条件) 与(1)矛盾! # 《集合论与图论》第8讲60 三歧性(trichotomy) ?三歧性: 设?是非空集合A上拟序关系, 若 x?y,x=y,y?x中有且仅有一式成立,则称? 具有三歧性. ?拟全序关系:设?是非空集合A上拟序关系, 若?具有三歧性, 则称?为拟全序关系, 或 拟线序关系,称<A,?>为拟线序集. 《集合论与图论》第8讲61 良序(well-order) ?良序关系: 设<A,?>为拟全序集, 若A的任 何非空子集B均有最小元, 则称?为良序关 系, <A,?>为良序集 ?例: <N,<>是良序集, <Z,<>不是良序集 ?良序原理(well-ordering principle): 每一 个集合都可以良序化(建立良序关系) ?良序原理等价于选择公理 ?良序集可做超限(transfinite)归纳证明 《集合论与图论》第8讲62 总结 ?等价关系, ?等价类,商集, ?划分 ?偏序,线序,拟序,良序 ?哈斯图, ?特殊元素, ?(反)链 《集合论与图论》第8讲63 作业(#6) ?p84, 习题二, 35,39,47,50,52