【正文】 y)| x, y∈ A而且 x, y同班 }； Rc’ = {(x, y)| x, y∈ A而且 x, y同年級(jí) }。 則： C={{0801班的學(xué)生 }， {0802班的學(xué)生 }， {0803班的學(xué)生 } , … , {0501 班的學(xué) 生 }, …} 。 C?={{大一的學(xué)生 }, {大二的學(xué)生 }, {大三的學(xué)生 }, {大四的學(xué)生 }}； 有， C是 C’的加細(xì)， Rc是 Rc’的子集。 例 ?設(shè) A={a， b， c}， 找出 A的全部劃分及對(duì)應(yīng)的等價(jià)關(guān)系 ， 以及劃分間的加細(xì)和等價(jià)關(guān)系間的包含關(guān)系 。 ?解 : 由第二類 Stirling數(shù)易知 ， A上共有 個(gè)劃分 。 31333 1 2 1 1 51 2 3?? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ??這些 劃分 分別為： C1={{a,b,c}}， C2={{a},{b,c}}，C3={,{a,c}}， C4={{c},{a,b}}， C5={{a},,{c}}。 ?它們對(duì)應(yīng)的 等價(jià)關(guān)系 分別為 : 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的加細(xì)， RC2，RC3， RC4， RC5都是 RC1的子集。 (partial ordering) 設(shè) R是集合 A上的一個(gè)關(guān)系。如果 R具有 自反性 ， 反對(duì)稱性 ， 傳遞性 ，則稱 R為一個(gè)部分序關(guān)系 (半序關(guān)系、偏序關(guān)系 )。集合 A在部分序關(guān)系 R下做成一個(gè) 部分序集 (半序集、偏序集 )。 記作 (A， R) 。 ?通常，將部分序關(guān)系 R寫做 “ ≤ ” ，讀做“ 小于或等于 ” 。 ? 顯然，一個(gè)部分序集的子集仍為部分序集。 (A, R) = (B, R∩ (B B)), 其中 B ? A 例 ?設(shè) A是整數(shù)集合， R是小于等于 關(guān)系 (或大于等于關(guān)系 )，則 (A, R)是一個(gè)部分序集 ； ?設(shè) A是正整數(shù)集合， R是整除關(guān)系，則 (A, R )是一個(gè)部分序集 ； ?設(shè) A是一個(gè)集合族， R是“ ?”關(guān)系。則(A,R)是一個(gè)部分序集。 設(shè)（ A,R）是部分序集，則 (B, R∩ (B B))是部分序集 , 其中 B ? A 證明： 1. R∩ (B B)是自反的 ， 任取 x∈ B，則 (x, x) ∈ B B， 由 x∈ B， B ? A，知 x∈ A．因 R是 A上的自反關(guān)系，故(x, x) ∈ R． 因此， (x, x) ∈ R∩ (B B)，即 R∩ (B B)是自反的。 2. R∩ (B B)是反對(duì)稱的 ， 若 (x, y) ∈ R∩ (B B)， (y, x) ∈ R∩ (B B)， 則 (x, y) ∈ R而且 (y, x) ∈ R ，因?yàn)?R是反對(duì)稱 的，所以x=y。 因此， R∩ (B B)是反對(duì)稱的。 (B, R∩ (B B))是部分序集 , 其中 B ? A 3. R∩ (B B)是傳遞的 ， 若 (x, y) ∈ R∩ (B B), (y, z) ∈ R∩ (B B), 則 (x, y) ∈ R, (y, z) ∈ R, 由 R有傳遞性知， (x, z) ∈ R。 另外， (x, y) ∈ B B， (y, z) ∈ B B，顯然B B是 B的全域關(guān)系 EB，則 (x, z) ∈ B B。這樣就有 ： (x, z) ∈ R∩ (B B)，即 R∩ (B B)是傳遞的。 哈斯 圖 (Hasse diagram) ?以平面上的點(diǎn)代表部分序集中的元素 。 1） 若 x≤y， 且 x≠y， 則將 x畫在 y的下面 。 2） 若 x≤y， x≠y，并且 沒有 不同于 x， y的 z， 使得 x≤z≤y(稱 y蓋住 x)，則在 x， y之間用直線連結(jié)。 例 : ?設(shè) A＝ ??a?, ?b?, ?a,b?, ?a,b, c?, ?a,b, c,d?, ? a,b,c,e??， 則 (A, ?) 是一個(gè)部分序集。 ?a? ?b? ?a,b? ?a,b,c? ?a,b,c,d? ?a,b,c,e? 例 : ?設(shè) A＝ ?1,2,3, 4,5,6,8,10,12,24?， R是整除關(guān)系，則 (A, R) 是一個(gè)部分序集。 3 1 5 2 6 4 12 10 8 24 鏈 (chain) ?設(shè) (A, ≤)是一個(gè)部分序集，對(duì)任意 x, y?A，如果 x≤y，或 y≤x，稱 x與 y可比(parable) ；否則，稱 x與 y不可比 。 ?一個(gè)部分序集的子集，其中任意兩個(gè)元素都可比，稱該子集為一條 鏈 (chain)。 例 : ?設(shè) A＝ ?1,2,3, 4,5,6,8,10,12,24?， R是整除關(guān)系，則 (A, R) 是一個(gè)部分序集。 3 1 5 2 6 4 12 10 8 24 全序集 (totally ordered set) ?一個(gè)部分序集 (A, ≤)說是一個(gè)全序集 ，如果 (A, ≤)本身是一條鏈 。 ?結(jié)論 : 若 （ A,R） 是全序集 ， 則 (B, R∩ (B B))是全序集 , 其中 B ? A 例 : ?設(shè) A＝ ?1,2,4, 8,16,32,64?， R是整除關(guān)系，則 (A, R) 是一個(gè)全序集。 1 2 4 8 32 16 64 例 : ?設(shè) A整數(shù)集合 ，R是“小于等于”關(guān)系，則 (A, R) 是一個(gè)全序集。 …… 2 1 0 2 1 3 … 擬序關(guān)系 ?設(shè) R是集合 A上的一個(gè)關(guān)系 。 如果 R具有 反自反性 ， 傳遞性 ， 則稱 R為一個(gè)擬序關(guān)系 。 記為 ＜ ， 讀做 “ 小于 ” 。 ?注意 ， 擬序關(guān)系的定義中隱含了其具有 反對(duì)稱性 。 ?例：數(shù)間的小于 （ “ ＜ ” ） 關(guān)系；集合間的真包含 （ “ ?” ） 關(guān)系 。 擬序關(guān)系是反對(duì)稱的 證明： 若 R= ? ，則 R是反自反的、傳遞的，而且是反對(duì)稱的； 若 R不是空集，任取 (x,y) ∈ R， 即 xRy, 斷言 x≠y，否則與 R是反自反的矛盾，往證一定有 yRx。若不然，則由 xRy,yRx，以及 R具有傳遞性知 xRx，與 R具有反自反性矛盾。因此，對(duì) 任意 xRy都沒有 yRx，即 R是反對(duì)稱的。 最大 (最小 )元 極大 (極小 )元 ?設(shè) (A, ≤)是一個(gè)部分序集 (poset)， (1)如果 A中有一個(gè)元素 a，對(duì)于所有的x?A，都有 x≤a(a≤x)，則稱 a為集合 A的 最大(最小 )元。 （ 2） A中元素 a說是一個(gè) 極大 (極小 )元，如果除 a之外， A中 沒有 元素 x，使得a≤ x(x≤ a)。 Note :集合 A的 (最小 )元、極大 (極小 )元必是該集合中的元素。 例 : ?a? ?b? ?a,b? ?a,b,c? ?a,b,c,d? ?a,b,c,e? 極大元 極小元 上 (下 )界，上 (下 )確界 (3) 對(duì)于 A中的子集 M， A中 元素 a稱為子集 M的一個(gè) 上界 (下界 )，如果對(duì) M中任意元素 m，都有 m≤a(a≤m)。 (4) 對(duì)于 A中的子集 M， A中 元素 a稱為M的一個(gè) 最小上界 (或稱 上確界 )，如果 a是 M的一個(gè)上界，并且對(duì) M的任意一個(gè)上界 x，都有 a≤x。 上 (下 )界，上 (下 )確界 (5) 對(duì)于 A中的子集 M， A中 元素 a稱為M的一個(gè) 最大下界 (或稱 下確界 ) ，如果 a是 M的一個(gè) 下 界，并且對(duì) M的任意一個(gè) 下 界 x，都有 x≤a 。 Note： M的上界 (下界 )、上確界（下確界）未必是 M中的元素． 例 : 求上 (下 )界，上 (下 )確界 ?a? ?b? ?a,b? ?a,b,c? ?a,b,c,d? ?a,b,c,e? 例 : ?a? ?b? ?a,b? ?a,b,c? ?a,b,c,d? ?a,b,c,e? ? ?a,b,c,d,e? ?設(shè) A={1,2,3,…,12}, ?是 A上的整除關(guān)系 ,(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 1 極小元 極大元 最小元 最大元 上界 下界 上確界 下確界 B 2 4,6 2 ? 12 1,2 12 2 C 4,6,9 4,6,9 ? ? ? 1 ? 1 D 1 10 1 10 10 1 10 1 討論 最大元，最小元未必存在，如果存在必唯一。 ?a? ?b? ?a,b? ?a,b,c? ?a,b,c,d? ?a,b,c,e? 討論 極大元，極小元對(duì)有限部分序集必存在，但未必唯一。 ?a? ?b? ?a,b? ?a,b,c? ?a,b,c,d? ?a,b,c,e? 討論 上下界未必存在，存在時(shí)又未必唯一。 ?a? ?b? ?a,b? ?a,b,c? ?a,b,c,d? ?a,b,c,e? 討論 即使有上下界時(shí)，最小上界和最大下界也未必存在。 {a, b, c, d} {a, b, c, e} {a}  定理 ?設(shè) (A,≤)是一個(gè)部分序集， B?A。 （ 1）若 b∈ B，而且 b是 B的最大元 (最小元 )，則 b必為 B的最小上界 (最大下界 )； （ 2）若 b為 B的上 (下 )界，且 b?B，則 b必為B的最大 (最小 )元； （ 3）若 B有最大下界 (最小上界 )，則最大下界 (最小上界 )唯一。 定理 (1)若 b∈ B，而且 b是 B的最大元(最小元 )，則 b必為 B的最小上界(最大下界 )； 證明：任意 B的上界 (下界 )x ∈ A，顯然有 b ≤x (b ≥x) ，則 b是 B的最小上界（最大下界）。 定理 (2)若 b為 B的上 (下 )界，且 b?B，則 b必為 B的最大 (最小 )元； 證明：因?yàn)?b是 B的上 (下 )界，則任意 B中的元素 x，都有 x≤b(x≥b)，又由 b?B，從而 b是 B的最大 (最小 )元。 定理 (3)若 B有最大下界 (最小上界 )，則最大下界 (最小上界 )唯一。 證明：設(shè) b1, b2分別是 B的最大下界 (最小上界 )，則按照最大下界(最小上界 )的定義有： b1≤b2, b2 ≤b1，從而有： b1=b2。 補(bǔ)充作業(yè)： 1. 設(shè) A = {a, b, c}，畫出部分序集 (2A, ?)以及 (2A, ?)的 Hasse圖，并分別指出最大、最小元和極大、極小元。 A = {a, b, c}，對(duì)于 2A的子集 B = {{a}, , {c}}，部分序關(guān)系 ?、 ?， 指出 B的所有上界、下界和上確界、下確界。