偏序集上的相對定向集及其應用

劉東明，姜廣浩，李 輝

(淮北師范大學數學科學學院，安徽淮北 235000)

1 預備知識

自20世紀70年代著名數學家和邏輯學家Scott創立連續格理論[1]以來，經過多年的發展，連續格的大部分研究成果被推廣到連續Domain上，并在范疇學、格論、格上拓撲以及計算機程序理論上得到廣泛應用[2-4].白仲林[5]提出了“一致集”的概念，這一概念是“定向集”的自然推廣，有關于一致集的格論研究是程序展開理論的基礎.近年來，阮小軍[6-8]對一致連續偏序集做了深入研究并得到十分豐富的成果.受“一致集”概念的啟發，本文首先在偏序集上引入并考察相對集的概念，討論其性質，并證明當T定向時，偏序集上所有相對T的定向集可以構成一個完備格.其次，在相對定向集基礎上引入相對定向完備集的概念，得到的一致完備集是相對定向完備集，并研究定向完備集、一致完備集與相對定向完備集三者之間的關系.本文中大部分采用文獻[2]的符號.

定義1.1[2]設P為偏序集，D?P，D≠?，對于任意x，y∈D,sup{x,y}存在且sup{x,y}∈D，則稱D為偏序集P上的定向集.

定義1.2[5]設P是偏序集，S?P，若?x,y∈S，存在z∈P，使得x≤z,y≤z，則稱S為P的一致集.

定義1.3[2]設P為偏序集，若對于任意定向子集D,supD存在且supD∈D，則稱偏序集P是定向完備的.簡記為DCPO.

定義1.4[5]設P為偏序集，若對于任意一致集S，supS存在且supS∈S，則稱偏序集P是一致完備的.簡記為UCPO.

2 相對定向集

定義2.1 設P是偏序集，S,T?P，S≠?，T≠?，若?x,y∈S，存在t∈T，使得x≤t,y≤t，則稱S為偏序集P相對于T的定向集.當T明了時，簡稱S為相對定向集.

設P為偏序集，集合T?P，T≠?，記Ir(T)={↓S:S為相對于T的定向集}，U(T)={S:S為相對于T的定向集}.

注2.1 相對定向集不一定為下集，下集也未必是相對定向集.

注2.2 定向集不一定為相對定向集，相對定向集也未必為定向集.

例2.1 設P={a,b,c,d,e,f,g}，若取T={b,e,f,g}，令S={c,d,f}，則S為相對T的定向集，但是S不是定向集也不是下集；令M={a,b,c,f,g}，則可見M本身為定向集且為下集，但M不為相對T的定向集.

定理2.1 設P為偏序集，集合T?P，T≠?，S為相對T的定向集，則S為偏序集P上的一致集.

證明 設S為相對T的定向集，根據定義有?x,y∈S，存在t∈T，使得x≤t且y≤t，又T?P，故t∈T，由一致集的定義可得，S為偏序集P上的一致集.

注2.3 若S為偏序集P上的一致集，S未必是偏序集P相對T的定向集.

例2.2 如圖1所示，設P={a,b,c,d,e,f,g}，取T={e,f,g}，S={c,d,f,g}，則S為偏序集P的一致集，但S不為P相對T的定向集，且S本身不為定向集.

下面定理揭示了定向集、相對定向集和一致集合的內在聯系.

命題2.1 設P為偏序集，T,S?P；T,S≠?，則有如下結論成立：

(1)若T=S，則S相對T定向?T本身定向；

(2)若T=P，則S相對T定向?S為P中的一致集.

命題2.2 設P為偏序集，T?P，T≠?，則以下結論成立：(1)?x∈T，則{x}∈U(T)；(2)?x,y∈T，若x≤y，則{x,y}∈U(T).

證明 (1)?a,b∈{x}，有a,b=x∈{x}?T，{x}為相對T的定向集，即{x}∈U(T).

(2)?a,b∈{x,y}，有a,b取值只可能為x或y，又x≤y∈T，有a≤y,b≤y，從而{x,y}為相對T的定向集，即{x,y}∈U(T).

定理2.2 設P為偏序集，T?P，T≠?，則Ir(T)?U(T).

證明 任意取M∈Ir(T)，則存在S∈U(T)，使得M=↓S.?x,y∈M，則x,y∈↓S，從而存在s1,s2∈S，使得x≤s1,y≤s2，又S為相對于T的定向集，故存在t∈T，使得s1≤t,s2≤t，進而有x≤t,y≤t，所以M為相對T的定向集.

引理2.1 設P為偏序集，T?P，T≠?，S1?S2，若S2∈U(T)，則S1∈U(T).

證明 ?x,y∈S1，因S1?S2,故x,y∈S2,又S2∈U(T),所以存在t∈T,使得x≤t,y≤t，進而S1∈U(T).

定理2.3 設P為偏序集，T?P，T≠?，S1,S2∈U(T)，則S1∩S2∈U(T).

證明 因為S1∩S2?S1，由引理2.1可得S1∩S2∈U(T).

定理2.4 設P為偏序集，T?P，T≠?，S1,S2∈U(T)，若T定向，則S1∪S2∈U(T).

證明 ?a,b∈S1∪S2，則a屬于S1或者S2，b屬于S1或者S2，如果a,b同時屬于S1或者a,b同時屬于S2，則結論成立；下證a,b不同時屬于一個集合時，結論也成立，不妨令a∈S1且b∈S2，因S1,S2都為相對T的定向集，故分別存在ta,tb∈T使得a≤ta,b≤tb，因為T定向，所以存在t∈T使得a≤t,b≤t故S1∪S2為相對T的定向集，即S1∪S2∈U(T).

上述定理2.3和定理2.4可以推廣到任意多個情形.

由定理2.5和定理2.6可以得到定理2.7.

定理2.7 設P為偏序集，T?P，T≠?，T定向，則U(T)為完備格.

3 相對定向完備集

定義3.1 設P是偏序集，T?P，T≠?，若任意相對T的定向集都存在最小上界，則稱P為相對T的定向完備集；當T明了時，簡稱P為相對定向完備集.簡單記為RDCPO(T).

引理3.1[5]設P為偏序集，?D?P，若D為定向集，則D為一致集.

定理3.1 設P為一致完備集，則P即為定向完備集也為相對定向完備集.

證明 一方面，?D∈P，D≠?，若D定向，則D為一致集，又P為一致完備集，故supD存在且supD∈D，進而P為定向完備集.

另一方面，?D∈P，D≠?，若D相對T定向，則由引理3.1知，D為一致集，因為P為一致完備集，所以supD存在且supD∈D，進而P相對定向完備集.

定理3.2 設P是偏序集，T?P，T≠?，若T=P則P為相對T的定向完備集當且僅當P為一致完備集.

證明(必要性)?D?P，D為一致集，因T=P，由命題2.1可知，此時的D相對T定向，又P為相對T定向完備，故D存在最小上界，從而P為一致完備集.

(充分性)?S?P，S相對T定向，由定理2.1可知，S為一致集，此時P為一致完備集，故supS存在且supS∈S，進而P為相對T定向完備集.

定理3.3 設P為一致完備偏序集，?D?P，則D為一致集當且僅當D為定向集.

證明(必要性)?D?P，設D為一致集，因P為一致完備偏序集，故supD存在且supD∈D，從而對于?x,y,y∈D，有x≤supD,y≤supD，即D為定向集.

(充分性)?D?P，設D為定向集，由定理2.1可得，D為一致集.

注3.1 一致完備集的子集未必是一致集.

例3.1 圖2為一致完備集，但它本身不是一致集.

命題3.1 設P為一致完備偏序集，T?P，T≠?，若?D?T，則D為相對T的定向集當且僅當D本身為定向集.

證明(必要性)?D?T?P，設D相對T定向，由定理2.2可得，D為一致集，又P為一致完備偏序集，故supD存在且supD∈D，從而對于?x,y∈D，有x≤supD,y≤supD，故D為定向集.

(充分性)?D?T?P，設D為定向集，由定理2.1可得，D為一致集，又P為一致完備偏序集，故supD存在且supD∈D?T，從而?x,y∈D，存在t=supD∈T，使得x≤t,y≤t，所以D為相對T的定向集.

結合定理3.3和命題3.1得到定理3.4.

定理3.4 設P為一致完備偏序集，T?P，T≠?，若?D?T，則下列結論等價：(1)D為相對T的定向集；(2)D為定向集；(3)D為一致集.

注3.2 若P為定向完備集，P未必為一致完備集.

例3.2 如圖3所示，設P=N∪M,其中N=[a,b],M={c,d,e,f}，規定P中的序：若?x,y∈N，則x≤y?x=y；若x∈M，y∈N,則x≤y；若x,y∈M則按通常的序.易證P為定向完備集，M?P為一致集，但supM?M，故P不是一致完備集.

注3.3 若P是相對定向完備集，P也未必為定向完備集.

例3.3 如圖4所示，設P=[b,a)∪{d,c,e}，取T={d,c,b,e}，則?D∈P，若D相對T定向則D存在最小上界，從而P為相對T的定向完備集，但是P不是一個定向完備集.

注3.4 若P為相對定向完備集，P未必是一致完備集.

例3.4 如圖3所示，當T={b,e,f}時，此時的P為相對定向完備集，但由例3.2知，P不是一致完備集.

注3.5 若P為定向完備集，P未必為相對定向完備集.

例3.5 在圖1中，P={a,b,c,d,e,f,g}，令T={b,e,f,g}，易知P為定向完備集，但是當取D={c,d,f,g}時sup{D}={b}不屬于D，故P不是相對定向完備集.

綜上所述可以得到，DCPO、UCPO、RDCPO(T)三者關系如圖5所示.