6元素集合上T0拓撲總數(shù)的計算

曾佳泓,趙 浩

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

§1 引言

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

作為研究域的特定種類偏序集合的數(shù)學分支,Domain理論亦被看作序理論的分支,在計算機科學和數(shù)學領域中廣泛應用.Domain理論體現(xiàn)了序與拓撲的相互結合,相互作用.其中一個重要的結論是:一個偏序集是連續(xù)的當且僅當其上的Scott拓撲是完全分配格[3-4].因此,可以利用內(nèi)蘊拓撲研究偏序結構,亦可以利用偏序結構研究相關的拓撲結構.[3-5]

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

文獻[6-7]從Domain理論在拓撲領域的應用出發(fā),利用序與拓撲的交叉,得到n=1,2,3,4,5時的T0拓撲總數(shù)分別為1,3,19,219和4231,相應的拓撲總數(shù)為1,4,29,355和6942.本文在其研究的基礎上利用序與拓撲交叉的方法,結合Hasse圖和層級配比數(shù)輔助分類,進一步給出6元素集合上的T0拓撲總數(shù)的計算,得到本文主要結論.

定理1.1設X為6元素集合,則X上的T0拓撲個數(shù)為130023.

§2 相關概念及引理

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

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

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

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

定義2.4[6-7]設X為預序集,稱其非空子集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設X為預序集,A ?X.A稱為X的Scott-閉集[1,9],如果滿足:(1)↓A=A;(2) 對任意定向集D ?X,若存在D的上確界supD,則有supD ∈A.

記X上的全體Scott-閉集為σ?(X).X上Scott-閉集的補集全體形成X上的拓撲,稱為Scott拓撲,記作σ(X).

定義2.7[1,9]設X為拓撲空間.X上的特殊化序≤定義為:x ≤y當且僅當x ∈{y}?,其中{y}?為獨立點{y}的閉包.

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

命題2.1[6-7]預序集X的序和其上的Scott拓撲的特殊化序是一致的.若X為T0拓撲空間,則X上的特殊化序為偏序.若X為非T0拓撲空間,則X上的特殊化序為預序,這樣的預序稱為真預序.

引理2.1[6-7]設X為有限集,τ和η為其上的兩個拓撲,則τ=η當且僅當其誘導的特殊化序相等.對于X上的兩個預序≤1及≤2,則兩個預序相同當且僅當其誘導的Scott拓撲相同.

以上引理說明,有限集上的拓撲與其上的預序形成一一對應,且T0拓撲對應于偏序,非T0拓撲對應于真預序.

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

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

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

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

§3 若干情形討論

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

3.1 含有6個極小元

引理3.1當有限集X含有6個極小元時,可形成1個偏序.

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

3.2 含有5個極小元

引理3.2當有限集X含有5個極小元時,可形成186個偏序.

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

3.3 含有4個極小元

引理3.3當有限集X含有4個極小元時,可形成5325個偏序.

證對剩下的2個元分以下情況.

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

圖3.3.1

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

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

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

圖3.3.2

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

因此,當有限集X含有4個極小元時,一共可形成3375+1950=5325個偏序.

3.4 含有3個極小元

引理3.4當有限集X含有3個極小元時,可形成35660個偏序.

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

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

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

圖3.4.1

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

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

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

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

圖3.4.2

①當該2個元只大于同一個極小元時,極大元可大于另外的1或2個極小元.

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

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

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

圖3.4.3

對小元與極小元的關系分以下情況.

①當小元大于1個極小元時,有以下情況.

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

因此,當有限集X含有3個極小元時,一共可形成35660個偏序.

3.5 含有2個極小元

引理3.5當有限集X含有2個極小元時,可形成63465個偏序.

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

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

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

圖3.5.1

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

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

圖3.5.2

圖3.5.3

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

④當2個極大元均大于2個中間元時,2個中間元與極小元均形成=3種選擇.值得注意,當2個中間元只大于同一個極小元時,2個極大元均可單獨大于另外的極小元.

圖3.5.4

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

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

圖3.5.5

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

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

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

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

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

圖3.5.6

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

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

圖3.5.7

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

圖3.5.8

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

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

圖3.5.9

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

圖3.5.10

①當小元大于1個極小元時,極大元,大元和中元至多有1個可以單獨大于另外的極小元,有=8種選擇;

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

因此,當有限集X含有2個極小元時,一共可形成63465個偏序.

3.6 含有1個極小元

引理3.6當有限集X含有1個極小元時,可形成25386個偏序.

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

因此,當有限集X含有1個極小元時,一共可形成25386個偏序.

§4 主要定理的證明

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

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

注本文從序與拓撲的交叉出發(fā),基于預序集X的序和其上的Scott拓撲的特殊化序的一致性,結合Hasse圖和層級配比數(shù),給出了6 元素集合上的T0拓撲總數(shù)的計算,其結果為130023.該方法還有望向n的更大情形推廣,但計算難度會越來越大.