曾佳泓,趙 浩

(華南師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,廣東廣州 510631)

§1 引言

布爾巴基學(xué)派學(xué)者以結(jié)構(gòu)主義觀點(diǎn)從事數(shù)學(xué)分析,他們認(rèn)為數(shù)學(xué)包含三大結(jié)構(gòu):序結(jié)構(gòu),拓?fù)浣Y(jié)構(gòu)和代數(shù)結(jié)構(gòu),稱為母結(jié)構(gòu).由母結(jié)構(gòu)的相互交叉可以派生,演變出更多的數(shù)學(xué)結(jié)構(gòu).20世紀(jì)60年代,Dana Scott為λ演算找尋指稱語義而提出Domain理論[1-2].

作為研究域的特定種類偏序集合的數(shù)學(xué)分支,Domain理論亦被看作序理論的分支,在計(jì)算機(jī)科學(xué)和數(shù)學(xué)領(lǐng)域中廣泛應(yīng)用.Domain理論體現(xiàn)了序與拓?fù)涞南嗷ソY(jié)合,相互作用.其中一個(gè)重要的結(jié)論是:一個(gè)偏序集是連續(xù)的當(dāng)且僅當(dāng)其上的Scott拓?fù)涫峭耆峙涓馵3-4].因此,可以利用內(nèi)蘊(yùn)拓?fù)溲芯科蚪Y(jié)構(gòu),亦可以利用偏序結(jié)構(gòu)研究相關(guān)的拓?fù)浣Y(jié)構(gòu).[3-5]

拓?fù)鋵W(xué)致力于研究幾何圖形或空間在連續(xù)改變形狀后還能保持一些不變的性質(zhì).拓?fù)鋵W(xué)中一個(gè)基本問題是:n元素集上拓?fù)淇倲?shù)的計(jì)算.在現(xiàn)有研究中,大部分學(xué)者利用計(jì)算機(jī)編程以窮舉運(yùn)算求解拓?fù)淇倲?shù).若不借助計(jì)算機(jī)求解,亦可考慮有限集上T0拓?fù)淇倲?shù)和非T0拓?fù)淇倲?shù),但其中T0拓?fù)淇倲?shù)的計(jì)算難度較大.

文獻(xiàn)[6-7]從Domain理論在拓?fù)漕I(lǐng)域的應(yīng)用出發(fā),利用序與拓?fù)涞慕徊?得到n=1,2,3,4,5時(shí)的T0拓?fù)淇倲?shù)分別為1,3,19,219和4231,相應(yīng)的拓?fù)淇倲?shù)為1,4,29,355和6942.本文在其研究的基礎(chǔ)上利用序與拓?fù)浣徊娴姆椒?結(jié)合Hasse圖和層級配比數(shù)輔助分類,進(jìn)一步給出6元素集合上的T0拓?fù)淇倲?shù)的計(jì)算,得到本文主要結(jié)論.

定理1.1設(shè)X為6元素集合,則X上的T0拓?fù)鋫€(gè)數(shù)為130023.

§2 相關(guān)概念及引理

首先介紹本文涉及的相關(guān)定義,它們大多采自于文獻(xiàn)[6-8].

定義2.1[8]設(shè)X為集合,記≤是X上的二元關(guān)系.若≤滿足:(1)x ∈X,x ≤x;(2) 對任意x,y,z ∈X,x ≤y,y ≤z ?x ≤z;則稱≤是X上的預(yù)序,稱(X,≤)為一個(gè)預(yù)序集.

定義2.2[8]設(shè)X為集合,若≤滿足:對任意x,y ∈X,x ≤y,y ≤x ?x=y;則稱≤是X上的偏序,稱(X,≤)為一個(gè)偏序集.其中,用x

定義2.3[6-7]設(shè)X為預(yù)序集,稱m ∈X為一個(gè)極小元,如果對任意x ∈X,x ≤m ?m ≤x.

定義2.4[6-7]設(shè)X為預(yù)序集,稱其非空子集D為定向集,若對任意x,y ∈D,存在z ∈d,使x ≤z,y ≤z.

定義2.5[6-7]若A ?X,記↑A={y ∈X:?x ∈A,x ≤y}及↓A={y ∈X:?x ∈A,y ≤x}.將↑{y}及↓{y}簡記為↑y和↓y.

定義2.6設(shè)X為預(yù)序集,A ?X.A稱為X的Scott-閉集[1,9],如果滿足:(1)↓A=A;(2) 對任意定向集D ?X,若存在D的上確界supD,則有supD ∈A.

記X上的全體Scott-閉集為σ?(X).X上Scott-閉集的補(bǔ)集全體形成X上的拓?fù)?稱為Scott拓?fù)?記作σ(X).

定義2.7[1,9]設(shè)X為拓?fù)淇臻g.X上的特殊化序≤定義為:x ≤y當(dāng)且僅當(dāng)x ∈{y}?,其中{y}?為獨(dú)立點(diǎn){y}的閉包.

本文所用計(jì)算理論基于以下的命題和引理,大多采自于文獻(xiàn)[1-2].

命題2.1[6-7]預(yù)序集X的序和其上的Scott拓?fù)涞奶厥饣蚴且恢碌?若X為T0拓?fù)淇臻g,則X上的特殊化序?yàn)槠?若X為非T0拓?fù)淇臻g,則X上的特殊化序?yàn)轭A(yù)序,這樣的預(yù)序稱為真預(yù)序.

引理2.1[6-7]設(shè)X為有限集,τ和η為其上的兩個(gè)拓?fù)?則τ=η當(dāng)且僅當(dāng)其誘導(dǎo)的特殊化序相等.對于X上的兩個(gè)預(yù)序≤1及≤2,則兩個(gè)預(yù)序相同當(dāng)且僅當(dāng)其誘導(dǎo)的Scott拓?fù)湎嗤?

以上引理說明,有限集上的拓?fù)渑c其上的預(yù)序形成一一對應(yīng),且T0拓?fù)鋵?yīng)于偏序,非T0拓?fù)鋵?yīng)于真預(yù)序.

引理2.2[6-7](Zorn引理) 對任意的非空偏序集,若任意全序子集都有上界,則該偏序集必然存在極大元.對偶地,對任意的非空偏序集,若任意全序子集都有下界,該偏序集必然存在極小元.

引理2.3[6-7]設(shè)X為有限偏序集,記其極小元集合為min(X).若x ∈Xmin(X),則存在x0∈X,使得x0≤x.

引理2.4[6-7]設(shè)X為有限偏序集,對任意y ∈X,↓y∩min(X)/=?.

定理2.5[6-7]設(shè)X為有限偏序集,若x ∈Xmin(X),則存在m0∈min(X),使得m0≤x.

§3 若干情形討論

隨著集合中元素個(gè)數(shù)的增加,層級分類趨于復(fù)雜,因此用每個(gè)層級所含的元素個(gè)數(shù)按序組成一個(gè)n位數(shù)序列,稱之為層級配比數(shù).例如,當(dāng)6元素集分為3個(gè)極大元,1 個(gè)中間元和2個(gè)極小元時(shí),層級配比數(shù)記為000312.

3.1 含有6個(gè)極小元

引理3.1當(dāng)有限集X含有6個(gè)極小元時(shí),可形成1個(gè)偏序.

證這時(shí)為離散偏序,其層級配比數(shù)為000006,共1個(gè).

3.2 含有5個(gè)極小元

引理3.2當(dāng)有限集X含有5個(gè)極小元時(shí),可形成186個(gè)偏序.

證剩下的元至少大于1個(gè)極小元,其層級配比數(shù)為000015.此時(shí)共有偏序數(shù)為

3.3 含有4個(gè)極小元

引理3.3當(dāng)有限集X含有4個(gè)極小元時(shí),可形成5325個(gè)偏序.

證對剩下的2個(gè)元分以下情況.

情形1若剩下的2個(gè)元不可相互比較,則其與極小元形成的偏序數(shù)均為=15.如圖3.3.1,層級配比數(shù)為000024.

圖3.3.1

此時(shí)共有偏序數(shù)為

人才梯隊(duì)是根據(jù)企業(yè)的增長來匹配的，只能提前一點(diǎn)點(diǎn)，不能提前很多，提前很多會造成浪費(fèi)。但一定要有梯隊(duì)，因?yàn)闆]有梯隊(duì)，后面的機(jī)制是會失靈的。沒有梯隊(duì)，機(jī)制會失靈；沒有評價(jià)，機(jī)制會死機(jī)；沒有選擇，組織會板結(jié)。這三點(diǎn)非常重要。

情形2若剩下的2個(gè)元可以相互比較,則較小元至少大于一個(gè)極小元.如圖3.3.2,層級配比數(shù)為000114.

圖3.3.2

故此時(shí)共有偏序數(shù)為

因此,當(dāng)有限集X含有4個(gè)極小元時(shí),一共可形成3375+1950=5325個(gè)偏序.

3.4 含有3個(gè)極小元

引理3.4當(dāng)有限集X含有3個(gè)極小元時(shí),可形成35660個(gè)偏序.

證對剩下的3個(gè)元,按極大元的個(gè)數(shù)分以下情形.

情形1含有3個(gè)極大元,層級配比數(shù)為000033,即剩下的3個(gè)元不可相互比較.則每個(gè)元與極小元形成的偏序數(shù)均為=7.此時(shí)共有偏序數(shù)為

情形2含有2個(gè)極大元,層級配比數(shù)為000213.根據(jù)第3元與2個(gè)極大元的關(guān)系分以下情況.

圖3.4.1

(1) 第3元小于2個(gè)極大元,且至少大于1個(gè)極小元.

而對可與第三元比較的極大元分以下情況.

情形3含有1個(gè)極大元,根據(jù)另外的2個(gè)元的關(guān)系分以下情況.

(1) 若該2個(gè)元不可比較,稱為較小元,層級配比數(shù)為000123,如圖3.4.2.則該2個(gè)元分別與極小元形成=7種選擇.值得注意的是以下兩種特殊情況:

圖3.4.2

①當(dāng)該2個(gè)元只大于同一個(gè)極小元時(shí),極大元可大于另外的1或2個(gè)極小元.

②當(dāng)該2個(gè)元一共大于2個(gè)極小元時(shí)(2個(gè)元各大于1個(gè)極小元(不相等) ;其中1個(gè)元大于2個(gè)極小元,1個(gè)元大于其中1個(gè)極小元;每個(gè)中間元都大于2個(gè)極小元;),極大元可大于剩余的1個(gè)極小元.

此時(shí)共有偏序數(shù)為

(2) 若2個(gè)元可比較,層級配比數(shù)為001113,如圖3.4.3.即除極小元外的3個(gè)元可相互比較,則首先有=6種選擇.將該3個(gè)元分別稱為“大元”,“中元”,“小元”.

圖3.4.3

對小元與極小元的關(guān)系分以下情況.

①當(dāng)小元大于1個(gè)極小元時(shí),有以下情況.

此時(shí)共有偏序數(shù)為

因此,當(dāng)有限集X含有3個(gè)極小元時(shí),一共可形成35660個(gè)偏序.

3.5 含有2個(gè)極小元

引理3.5當(dāng)有限集X含有2個(gè)極小元時(shí),可形成63465個(gè)偏序.

證對剩下的4個(gè)元,按極大元的個(gè)數(shù)分以下情形.

情形1含有4個(gè)極大元,層級配比數(shù)為000042.即剩下的4個(gè)元相互不可比較.則每個(gè)元與極小元形成的偏序數(shù)均為=3.此時(shí)共有偏序數(shù)為

情形2含有3個(gè)極大元,層級配比數(shù)為000312,如圖3.5.1.根據(jù)第4元與極大元的關(guān)系分以下情況.

圖3.5.1

(1) 第4元小于3個(gè)極大元,且至少大于1個(gè)極小元.

情形3含有2個(gè)極大元.稱極大元和極小元以外的2個(gè)元為“中間元”.根據(jù)2個(gè)中間元的關(guān)系分以下情況.(1) 2個(gè)中間元不可相互比較,層級配比數(shù)為000222,如圖3.5.2.根據(jù)極大元和中間元的關(guān)系分以下情況.

圖3.5.2

圖3.5.3

此時(shí)共有偏序數(shù)為

④當(dāng)2個(gè)極大元均大于2個(gè)中間元時(shí),2個(gè)中間元與極小元均形成=3種選擇.值得注意,當(dāng)2個(gè)中間元只大于同一個(gè)極小元時(shí),2個(gè)極大元均可單獨(dú)大于另外的極小元.

圖3.5.4

此時(shí)共有偏序數(shù)為

(2) 若2個(gè)中間元可比較,層級配比數(shù)為002112,則首先有=2種選擇.稱其中較大(小) 者為“較大(小) 元”.根據(jù)中間元與極大元的關(guān)系分以下情況.

圖3.5.5

②當(dāng)1個(gè)極大元大于較大元,而另一個(gè)極大元只大于較小元時(shí),有以下情形:若較小元大于1個(gè)極小元,則只大于較小元的極大元可單獨(dú)大于另外的極小元,并且另一極大元和較大元有至多1個(gè)可同時(shí)大于該極小元;若較小元大于2個(gè)極小元,則有=1種選擇.

此時(shí)共有偏序數(shù)為

此時(shí)共有偏序數(shù)為

情形4含有1個(gè)極大元.稱極大元和極小元以外的3個(gè)元為“中間元”.根據(jù)3個(gè)中間元的關(guān)系分以下情況.

(1) 若3個(gè)中間元不可相互比較,層級配比數(shù)為000132,如圖3.5.6.每個(gè)中間元與極小元均形成=3種選擇.值得注意的是,當(dāng)3個(gè)中間元只大于1個(gè)極小元時(shí),極大元可單獨(dú)大于另外的極小元.

圖3.5.6

此時(shí)共有偏序數(shù)為

(2) 若有2個(gè)中間元不可相互比較,且同時(shí)大于第3個(gè)中間元,層級配比數(shù)為001212,如圖3.5.7.則首先有=3種選擇.此時(shí)較小中間元與極小元形成=3種選擇.需要注意,當(dāng)較小中間元大于1個(gè)極小元時(shí),至多1個(gè)極大元或2 個(gè)較大中間元可大于另外的極小元.

圖3.5.7

此時(shí)共有偏序數(shù)為

圖3.5.8

此時(shí)共有偏序數(shù)為

(4) 若有1個(gè)中間元大于另外2個(gè)中間元且該2個(gè)中間元不可比較,則2個(gè)較小的中間元均與極小元形成=3種選擇.層級配比數(shù)為001122,如圖3.5.9.值得注意的是,當(dāng)較小中間元大于同一個(gè)極小元時(shí),較大中間元和極大元至多有1個(gè)可以單獨(dú)大于另外的極小元.

圖3.5.9

此時(shí)共有偏序數(shù)為

圖3.5.10

①當(dāng)小元大于1個(gè)極小元時(shí),極大元,大元和中元至多有1個(gè)可以單獨(dú)大于另外的極小元,有=8種選擇;

此時(shí)共有偏序數(shù)為

因此,當(dāng)有限集X含有2個(gè)極小元時(shí),一共可形成63465個(gè)偏序.

3.6 含有1個(gè)極小元

引理3.6當(dāng)有限集X含有1個(gè)極小元時(shí),可形成25386個(gè)偏序.

證該極小元也是最小元.其余5個(gè)元形成的5元偏序數(shù)為P5=4231,則此時(shí)共有偏序數(shù)為

因此,當(dāng)有限集X含有1個(gè)極小元時(shí),一共可形成25386個(gè)偏序.

§4 主要定理的證明

本節(jié)將利用§3的結(jié)論來證明本文的主要定理.

定理1.1的證明由引理3.1-3.6可知,6元素集合上一共可形成1+186+5325+35660+63465+25386=130023個(gè)偏序.因此,由引理2.1 可知,6元素集合上的T0拓?fù)鋫€(gè)數(shù)為130023.

注本文從序與拓?fù)涞慕徊娉霭l(fā),基于預(yù)序集X的序和其上的Scott拓?fù)涞奶厥饣虻囊恢滦?結(jié)合Hasse圖和層級配比數(shù),給出了6 元素集合上的T0拓?fù)淇倲?shù)的計(jì)算,其結(jié)果為130023.該方法還有望向n的更大情形推廣,但計(jì)算難度會越來越大.