相對連續偏序集及其應用

劉東明，姜廣浩，李 輝

（淮北師范大學數學科學學院，安徽淮北235000）

1 引言與預備知識

由于計算機程序語言邏輯的迫切需要，著名數學家Scott于1972年首次引入連續格的概念，并由此創建了比較完整的連續格理論[1].隨后相關學者將連續格理論推廣到使用更廣泛的連續Domain[2]上.Domain理論的一個重要的研究方向是將其推廣到一般的偏序集中去，如，連續偏序集[3-5]、擬連續偏序集[6-7]、C-連續偏序集[8-9]等.本文在以往文獻的基礎上，將定向集和一致集進行推廣.首先引入相對定向集和相對定向完備集的概念，并在相對定向完備集上引入相對雙小于的概念，研究其在給定的集合T中的一些性質；然后利用相對way below關系引入相對連續偏序集的概念，探討了它的一些等價條件；最后引入相對遺傳性的概念，證明了相對連續偏序集在給定的集合T下具有相對T的遺傳性.

設P為偏序集，?X?P，記↓X={y∈P：?x∈X，y≤x}，對偶地，記↑X={y∈P：?x∈X，x≤y}，并記↓x=↓{x}，↑x=↑{x}.設P為偏序集，X?P，則X是下集當且僅當X=↓X，X為上集當且僅當X=↑X.若?x、y∈X，?z∈X，使得 x、y≤z，則稱 X是P的定向集.對偶地，可以定義余定向集.

定義1[2]設P為偏序集，X?P，稱X為理想，當且僅當X既是下集又是定向集.對偶地，可以定義濾子.記P的所有理想構成的集合為Idl（P），P的所有濾子構成的集合為Filt（P）.

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

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

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

定義5[4]設P為偏序集，定義P上的waybelow＜＜u關系如下：?x、y∈P，若對于任意一致集S，當y≤sup S時，存在s∈S，使得x≤s，則稱x一致小于 y，記作x＜＜uy.記?ux={v：v＜＜ux}.

定義6[4]設P為一致完備偏序集，若對于任意x∈P，x=sup?ux，則稱P是一致連續偏序集.

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

例1設P為偏序集，T?P，T≠，?x∈T，則單點集{x}是P中相對于T的定向集.

定義8設P為偏序集，T?P，T≠，若任意相對于T的定向集都存在最小上界，則稱P為相對于T的定向完備集.當T明了時，簡稱P為相對定向完備集，簡記為 RDCPO（T）.

設P為偏序集，且P具有性質Q，若P的任意非空子集也具有性質Q，則稱Q在P中具有遺傳性.

2 相對way below關系

定義9設P為相對于T的定向完備集，定義P上的相對 way below＜＜T關系如下：?x、y∈P，若對于任意相對于T的定向集S，當y≤sup S時，存在s∈S，使得x≤s，則稱x在P上相對于T小于y，當T明了時，簡稱 x相對小于 y，記為 x＜＜Ty.若 x＜＜Tx成立，則稱x為P上相對于T的緊元，當T明了時，簡稱x為相對緊元.記?Tx={u：x＜＜Tu}，?Tx={v：v＜＜Tx}.

命題設P為偏序集，T?P，T≠，若P為相對于T的定向完備集，則對于任意u、x、y、z∈T，有如下結論成立.

（1）x＜＜Ty?x≤y.

（2）u≤x＜＜Ty≤z?u＜＜Tz.

（3）?Tx∈U（T）.

（4）當P有最小元0時，0＜＜Tx.

（5）x＜＜Tz，y＜＜Tz，若 x∨y存在，則 x∨y＜＜Tz.

證明（1）?D∈U（T），由于P為相對于T的定向完備集，則sup D存在，若y≤sup D，則存在d∈D，使得 x≤d，取 D={y}∈U（T），則 x≤sup D=y.

（2）?D∈U（T），sup D存在，若 z≤sup D，由條件得y≤sup D，又 x＜＜Ty，從而存在 d∈D，使得 x≤d，又因為 u≤x，所以u≤d，由相對way below的定義得u＜＜Tz.

（3）?a、b∈?Tx，有 a＜＜Tx 且 b＜＜Tx，則 a≤x，b≤x，而 x∈T，所以?Tx∈U（T）.

（4）?D∈U（T），若 x≤sup D，則存在 d∈D，使得x≤d，又由于0是P的最小元，故0≤d，所以0＜＜Tx.

（5）?D∈U（T），則 sup D 存在且 sup D∈D，若z≤sup D，因為 x＜＜Tz，y＜＜Tz，故存在 d1、d2∈D，使得x≤d1≤sup D 且 y≤d2≤sup D，進而 x∨y≤sup D，所以x∨y＜＜Tz.

由命題易得推論1和推論2.

推論1設P為偏序集，T?P，T≠，若P為相對于T的定向完備集，則?x∈T，有?Tx?↓x，?Tx?↑x.

推論2設P為偏序集，T?P，T≠，若P為相對于T的定向完備集，則?x、y∈T且x≤y，有?Tx??Ty.

推論3設P為偏序集，T?P，T≠，若P為相對于T的定向完備集，x∈T，則有?Tx∈RId（lT）.

證明由命題的（3）知?Tx∈U（T），下證?Tx為下集.任意取 a∈?Tx，則 a＜＜Tx，任意取 b∈P，若 b≤a，再由命題的（2）得 b＜＜Tx，因此?Tx為下集，故?Tx∈RId（lT）.

引理設P為偏序集，T?P，T≠，則I（rT）?U（T）.

證明?M∈I（rT），則存在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的定向集.

定理1設P為偏序集，T?P，T≠，P為相對于T的定向完備集.?x、y∈T，x＜＜Ty當且僅當?I∈I（rT），若 y≤sup I，則 x∈I.

證明必要性 ?I∈I（rT），由引理得I?U（T），故I相對于T定向且為下集，若x＜＜Ty且y≤sup I，則存在d∈I，使得x≤d，進而x∈I.

充分性 ?I∈I（rT），有I∈RId（lT），對于任意x∈I，則存在d∈I，使得x≤d，即對于任意相對于T定向的I，若y≤sup I，則存在d∈I，使得x≤d，故有x＜＜Ty.

定理2設P為一致完備集，T?P，T，?x∈T，則有?ux??Tx.

證明?a∈?ux，有 a＜＜ux，下證 a∈?Tx，任意取D?U（T），則D為P中的一致集，因為P為一致完備集，所以sup D存在，若x≤sup D，則存在d∈D，使得a≤d，由相對way below關系的定義得a＜＜Tx，從而a∈?Tx，故?ux??Tx.

3 相對連續偏序集

定義10設P為偏序集，T?P，T≠，且P為相對于T的定向完備集，若?x∈T，x=sup?Tx，則稱P為相對于T的連續偏序集.當T明了時，簡稱P為相對連續偏序集.

注1相對連續偏序集未必為一致連續偏序集.

例2設偏序集 P=M∪N，見圖 1.N={a，b，c，d}，規定P的序：若x、y∈M，則x≤y當且僅當x=y；若x∈N，y∈M,則 x≤y；若 x、y∈N，N 上的序如圖 1所示.令T={b，c，d}，則P為相對于T的連續偏序集.然而，對于一致集N，sup N?N，P不為一致完備集，從而P不是一致連續偏序集.

圖1 偏序集P=M∪NFig.1 Poset P=M∪N

注2相對連續偏序集未必為連續偏序集，連續偏序集也未必為相對連續偏序集.

例3設 P=[0，1），T=[0，1/2]，則 P 為相對于T的連續偏序集，但由sup P?P知P不為定向完備偏序集，故P不為連續偏序集.

定理3設P為一致連續偏序集，則?T?P，T≠，P為相對于T的連續偏序集.

證明若P為一致連續偏序集，則P為一致完備集，從而P為相對于T的定向完備集.?x∈T，由定理1知?Tx∈U（T）.下證x=sup?Tx.首先，易知x為?Tx的一個上界，從而sup?Tx≤x；其次，由定理2得?ux??Tx，又P為一致連續偏序集，故有x=sup?ux≤sup?Tx，進而x=sup?Tx.所以P為相對于T的連續偏序集.

定理4設P為偏序集，T1?T2?P，T1、T2≠，若P為相對于T2的連續偏序集，則P為相對于T1的連續偏序集.

證明設P為相對于T2的連續偏序集，則P為相對于T2的定向完備集.首先證P為相對于T1的定向完備集.?D∈U（T1），?a、b∈D，存在 t∈T1?T2，使得a≤t且b≤t，從而 D∈U（T2），又P為相對于 T2的定向完備集，故sup D存在且sup D∈D，進而P為相對于T1的定向完備集.?x∈T1，由定理1知.下面證易知的一個上界，從而下證，則有，，有，因P為相對于T1的定向完備集，故sup D存在且sup D∈D，若 x≤sup D，又，故存在 d∈D，使得y≤d，由相對way below的定義可知，進而，所以，又因P為相對于T2的連續偏序集，進而有，故綜上可知P為相對于T1的連續偏序集.

定義11設P為偏序集，T?P，T≠，若P具有性質Q，且T中的任意子集D都具有性質Q，則稱Q在P中具有相對于T的遺傳性.當T明了時，簡稱相對遺傳性.

注3若某種性質具有遺傳性，則必具有相對遺傳性.

注4若某種性質具有相對遺傳性，則未必具有遺傳性.

例4設偏序集 P={a，b，c，d，e，f}，見圖 2.設T={b，d，e}，易知P為定向的，且對于任意T中的非空子集D，D都是定向的，但顯然P中的子集不都是定向的.故定向性質具有相對于T的遺傳性，但不具有遺傳性.

圖2 偏序集 P={a，b，c，d，e，f}Fig.2 Poset P={a，b，c，d，e，f}

定理5設P為相對于T的連續偏序集，T?P，T≠，則對于T的任一非空子集D，P為相對于D的連續偏序集.