Z-連通極小集及其應(yīng)用

趙 娜

（1.長治醫(yī)學(xué)院數(shù)學(xué)教研室，山西長治046000； 2.陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，陜西西安710119）

Domain理論自20世紀(jì)70年代創(chuàng)建以來備受關(guān)注，其中研究的一個重要分支是盡可能將Domain理論推廣到更一般的格序結(jié)構(gòu)［1-3］.1977年，Hutton［4］在完全分配格上引入了極小族概念，證明了完全分配格的每個元都有極小族.自此，極小集（更一般地，φ-極小集）理論得到了廣泛的應(yīng)用，并產(chǎn)生了一系列較深刻的結(jié)果［5-13］.文獻(xiàn)［5］引入并討論了完備格上的極大族與極小族理論，給出完全分配格的一個構(gòu)造定理.文獻(xiàn)［6］證明了φ-極小集存在與完全分配律等價.文獻(xiàn)［7］以擬極小集為基礎(chǔ)，證明了擬極小集存在與連續(xù)偏序集等價，并對Lawson和Hoffmann所確立的完全分配格與連續(xù)偏序集間的對應(yīng)關(guān)系給出了一種新處理.文獻(xiàn)［8-13］分別論述了一些具體序結(jié)構(gòu)的極小集刻畫.本文在文獻(xiàn)［5-13］的基礎(chǔ)上引入Zc-極小集的概念，給出Zc-連續(xù)偏序集及保Zc-集的并且保?Zc的映射的Zc-極小集刻畫，得到了保Zc-集的并且保?Zc的映射的擴(kuò)張定理.

1 預(yù)備知識

定義 1.1［14］設(shè) P 是偏序集，?≠S?P.若?x，y∈S，?xi∈S，i＝1，2，...，n，使得 x＝x1，xn＝y(tǒng)，且?i＝1，2，...，n-1，xi，xi＋1可比較，則稱 S 是連通的，x與y在S中連通.

定義 1.2［14］設(shè) POS 是以偏序集為對象，保序映射為態(tài)射的范疇，設(shè)C是POS的一個子范疇，C上的一個連通集系統(tǒng)Zc是一個映射，其中對C的每一個對象 P，Zc（P）是 P的連通子集構(gòu)成的子族，且滿足下列條件：

1）?x∈P，↓x∈Zc（P）；

2）若 f：P→Q 是 C 中的態(tài)射，則?D∈Zc（P），↓f（D）∈Zc（Q）；

3）對C的每一個對象 P，Zc（P）還是 C的對象，其中Zc（P）的序是通常的包含關(guān)系.

設(shè)P是偏序集.稱Zc（P）中元素為Zc-子集.若?D∈Zc（P），∨D存在，則稱P是Zc-完備的.記↓IZc（P）＝｛↓D｜D∈Zc（P）｝，IZc（P）中的元素稱為Zc-理想.易證P是Zc-完備的當(dāng)且僅當(dāng)P的每個Zc-理想在P中上確界存在.

本文僅考慮POS上的連通集系統(tǒng).

注 1.3Z-連通集系統(tǒng)和Z-子集系統(tǒng)［2］是POS上的2個不同的子集系統(tǒng).對于偏序集P，根據(jù)Z-連通集系統(tǒng)和Z-子集系統(tǒng)的定義可以驗證：

1）Zc（P）＝｛↓x｜x∈P｝是 Z-連通集系統(tǒng)，不是Z-子集系統(tǒng)；

2）Z（P）＝｛F｜F是 P的有限子集｝是 Z-子集系統(tǒng)，不是Z-連通集系統(tǒng)；

3）Zc（P）＝｛D｜D 是 P 的定向子集｝既是Z-連通集系統(tǒng)，也是Z-子集系統(tǒng).

定 義 1.4［14］設(shè) P 是 偏 序 集.若 對Zc（IZc（P））中任意 Zc- 集 D，都有∪D∈IZc（P），∪D＝∨D，則稱連通集系統(tǒng)Zc是并完備的.

定義 1.5［14］設(shè) P 是 Zc-完備偏序集，x，y∈P.若?D∈Zc（P），y≤∨D，?d∈D，使得 x≤d，則稱 x?Zcy.記?Zcx＝｛y∈P｜y?Zcx｝.

性質(zhì) 1.6［14］設(shè) P 是 Zc-完備偏序集.若x?Zcy≤z（x≤y?Zcz），則 x?Zcz.

定義 1.7［14］設(shè) P 是 Zc-完備偏序集.若?x∈P，有：

1）?Zcx∈Zc（P）；

2）x＝∨?Zcx，則稱P是Z-連通連續(xù)偏序集，簡記為Zc-連續(xù)偏序集.

定義 1.8［14］設(shè) P 是 Zc-完備偏序集，F(xiàn)?P.若F滿足：

1）F＝↓F；

2）?D∈Zc（P），D?F，則∨D∈F.

則稱F是 Zc-閉集.記 P的 Zc-閉集全體為ΓZc（P）.Zc-閉集的補(bǔ)集稱為 Zc-Scott開集.全體Zc-Scott開集構(gòu)成一個拓?fù)洌Q為Zc-Scott拓?fù)洌涀?σZc（P）.

命題 1.9［15］設(shè) P 是 Zc-完備偏序集，U?P.U是Zc-Scott開集當(dāng)且僅當(dāng)U滿足：

1）U＝↑U；

2）?S∈Zc（P），∨S∈U，則 S?U≠?.

2 Z c-極小集及Z c-連續(xù)偏序集的Z c-極小集刻畫

定義 2.1設(shè) P是 Zc-完備偏序集，x∈P，D∈Zc（P），若 D 滿足如下條件：

1）x＝∨D；

2）若?S∈Zc（P），x≤∨S，則?d∈D，?s∈S，使得d≤s，則稱D是x的一個Zc-極小集.

注2.21）Zc-極小集的并未必是Zc-極小集.故若x有Zc-極小集，則未必有最大的.

2）定義2.1中若將條件 D∈Zc（P）改為 D?P，則稱D是x的一個廣義Zc-極小集.廣義Zc-極小集的并是廣義Zc-極小集.故若x有廣義Zc-極小集，則必有最大的.

3）Zc-極小集是廣義Zc-極小集.當(dāng)Zc（P）是P中所有定向集之族，則此時的廣義Zc-極小集是文獻(xiàn)［8］中定向極小集的推廣.

命題2.3設(shè)P是Zc-連續(xù)偏序集，x∈P，則?Zcx是x的最大Zc-極小集.

證明由Zc-連續(xù)偏序集及?Zc的定義可知?Zcx是x的Zc-極小集.設(shè)D是x的任一Zc-極小集，取S＝?Zcx，由Zc-極小集的定義知?d∈D，?s∈?Zcx，使得 d≤s.從而 d?Zcx，即 D??Zcx，?Zcx是x的最大Zc-極小集.

定理2.4設(shè) P是 Zc-完備偏序集，x∈P，?Zcx∈Zc（P）.則下列條件等價：

1）P是Zc-連續(xù)偏序集；

2）?D∈Zc（P），D??Zcx，∨D＝x；

3）?D∈Zc（P），∨D＝x，↑x＝∩｛?Zcd｜d∈D｝；

4）x有Zc-極小集.

證明1）?2）取D＝?Zcx即可.

2）?3）?d∈D，d?Zcx，從而當(dāng) x≤y時，有d?Zcy，即↑x?∩｛?Zcd｜d∈D｝.反之，若 a∈∩｛?Zcd｜d∈D｝，則?d∈D，d?Zca.由此可知x＝∨D≤a，即∩｛?Zcd｜d∈D｝?↑x.

3）?4）?S∈Zc（P），x≤∨S，則∨S∈↑x＝∩｛?Zcd｜d∈D｝，從而?d∈D，d?Zc∨S.由?Zc的定義知?s∈S，使得 d≤s，即 D是 x的 Zc-極小集.

4）?1）設(shè)D是x的一個Zc-極小集，則D??Zcx，x＝∨D≤∨?Zcx≤x.從而 x＝∨?Zcx，即 P是Zc-連續(xù)偏序集.

推論2.5設(shè)P是Zc-連續(xù)偏序集，x∈P.則下列條件等價：

1）D是x的Zc-極小集；

2）D∈Zc（P），D??Zcx，∨D＝x；

3）D∈Zc（P），∨D＝x，↑x＝∩｛?Zcd｜d∈D｝；

4）D∈Zc（P），?Zcx＝↓D.

證明由定理2.4的證明過程及Zc-連續(xù)偏序集的定義可得.

引理 2.6［14］設(shè) Zc是并完備的連通集系統(tǒng).若P是Zc-完備偏序集，則P上的?Zc關(guān)系滿足插入性質(zhì)，即 x?Zcy??z∈P，x?Zcz?Zcy.

定理2.7設(shè)Zc是并完備的連通集系統(tǒng)，P是Zc-完備偏序集.則P是Zc-連續(xù)偏序集當(dāng)且僅當(dāng)P滿足如下性質(zhì)：

1）?x∈P，?Zcx∈Zc（P）；

2）插入性質(zhì)：?x，y∈P，x?Zcy??z∈P，x?Zcz?Zcy；

3）｛?Zcx｜x∈P｝是 σZc（P）的基；

4）?x∈P，↑x＝∩｛U∈σZc（P）｜x∈U｝.

證明必要性 1）和2）分別由Zc-連續(xù)偏序集的定義及引理2.6直接可得.

3）顯然?Zcx 是上集.?S∈Zc（P），∨S∈?Zcx，即 x?Zc∨S.由?Zc滿足插入性質(zhì)知?p∈P，使得x?Zcp?Zc∨S.故?s∈S，使得 x?Zcp≤s，則x?Zcs，即?Zcx∩S≠?，因此?Zcx∈σZc（P）.

下證?U∈σZc（P），U＝∪｛?Zcx｜x∈U｝.顯然有∪｛?Zcx｜x∈U｝?U.反之，?x∈U，?Zcx∈Zc（P），∨?Zcx＝x，則?Zcx∩U≠?.從而?u∈U，使得 u?Zcx，即 x∈?Zcu，U?∪｛?Zcx｜x∈U｝.

4）由3）及定理2.4知

反之，由Zc-Scott開集是上集知↑a?U，即↑x?∩｛U∈σZc（P）｜x∈U｝.

充分性 由3）和4）知↑x＝∩｛?Zca｜a∈?Zcx｝.下證 x＝∨?Zcx.顯然有∨?Zcx≤x.反之，?a∈?Zcx，由2）知?p∈P，使得 a?Zcp?Zcx，即 p∈?Zcx.則a?Zcp≤∨?Zcx.從而a?Zc∨?Zcx.故∨?Zcx∈∩｛?Zca｜a∈?Zcx｝＝↑x，即∨?Zcx≥x.

3 保Z c-集并和?Z c的映射的Z c-極小集刻畫及擴(kuò)張定理

定義 3.1［14］設(shè) P、Q 是 Zc-完備的偏序集，f：P→Q 是映射.若?S∈Zc（P），f（∨S）＝∨f（S），則稱f保Zc-集的并.

注3.2設(shè)映射 f：P→Q保 Zc-集的并，則 f是保序的，即 x≤y?f（x）≤f（y）.

定義 3.3設(shè) P、Q是 Zc-完備的偏序集，f：P→ Q 是 映 射.若 ?x，y∈ P，x ?Zcy?f（x）?Zcf（y），則稱 f保?Zc.

定義 3.4設(shè)P、Q是Zc-完備的偏序集，f：P→Q是映射.若?x∈P，D是x的Zc-極小集，則↓f（D）是f（x）的Zc-極小集.則稱f保Zc-極小集.

定理3.5設(shè)f：P→Q是Zc-連續(xù)偏序集間的映射.則下列條件等價：

1）f保Zc-集的并且保?Zc；

2）f保 Zc- 集 的 并 且 ?x∈P，f（?Zcx）??Zcf（y）；

3）f保 Zc- 集 的 并 且 ?x∈P，f（?Zcx）??Zcf（y）；

4）f保序且f保Zc-極小集；

5）f保 Zc- 集 的 并 且 ?x∈P，↑f（x）?∩｛?Zcf（y）｜y∈?Zcx｝.

證明1）?2），2）?3）顯然.

2）?4）設(shè) D是 x的 Zc-極小集，則 D∈Zc（P），x＝∨D，D??Zcx.由連通集系統(tǒng) Zc的定義及 f保 Zc-集的并知↓f（D）∈Zc（P），∨↓f（D）＝∨f（D）＝f（∨D）＝f（x），且 f（D）?f（?Zcx）??Zcf（x），故↓f（D）??Zcf（x）.由推論2.5 知↓f（D）是 f（x）的 Zc-極小集.

4）?5）設(shè) D∈Zc（P），d＝∨D.由 f保序知∨f（D）≤f（d）.反之，?x∈?Zcd 即 x?Zcd，?a∈D，使得x≤a，從而 f（x）≤f（a）≤∨f（D），f（?Zcd）≤∨f（D）.由4）知↓f（?Zcd）是 f（d）的 Zc-極小集，則f（d）＝∨↓f（?Zcd）＝f（?Zcd），故 f（d）≤∨f（D），即f保 Zc-集的并.?x∈P，由推論2.5 及↓f（?Zcx）是f（x）的 Zc-極小集知

5）?1）設(shè) a?Zcb即 a∈?Zcb.由↑f（b）?∩｛?Zcf（y）｜y∈?Zcb｝知↑f（b）??Zcf（a），從而f（b）??Zcf（a），即 f（a）?Zcf（b）.

定義3.6設(shè)P是Zc-完備的偏序集，B?P.若?x∈P，?Zcx∩B∈Zc（B）且∨（?Zcx∩B）＝x，則稱B是P的一個Zc-基.

定理3.7（擴(kuò)張定理）設(shè)Zc是并完備的連通集系統(tǒng)，P，Q是Zc-連續(xù)偏序集，B是P的Zc-基.若g：B→Q是保Zc-集的并且保?Zc的映射，則g可擴(kuò)張為一個保Zc-集的并且保?Zc的映射f：P→Q，且擴(kuò)張是唯一的.

證明?x∈P，令 f（x）＝∨↓g（?Zcx∩B）＝∨g（?Zcx∩B），下證f是滿足條件的擴(kuò)張.

1）x∈B 時，f（x）＝∨g（?Zcx∩B）＝g（∨（?Zcx∩B））＝g（x）.

2）若 a≤b，則?Zca∩B??Zcb∩B.從而g（?Zca∩B）?g（?Zcb∩B），f（a）≤f（b）.即 f保序.

3）設(shè) D∈Zc（P），d＝∨D.由 f保序知∨f（D）≤f（d）.反之，?x∈?Zcd∩B，由 x?Zcd 知?a∈D，使得 x≤a.從而 g（x）＝f（x）≤f（a）≤∨f（D），故 f（d）＝∨g（?Zcx∩B）≤∨f（D）.即 f保Zc-集的并.

4）設(shè) a，b∈P，a?Zcb.由引理 2.6 知?c∈P，a?Zcc?Zcb.由于 B 是 P 的 Zc-基，則∨（?Zcb∩B）＝b.從而?u∈?Zcb∩B，使得 a?Zcc≤u?Zcb，故 a?Zcu?Zcb.同 理 可 得 ?v∈ B，使 得a?Zcu?Zcv?Zcb.由 f保序及 g 保?Zc知 f（a）≤f（u）＝g（u）?Zcg（v），故 f（a）?Zcg（v）.又由 f的定義知g（v）≤f（b），所以 f（a）?Zcf（b），即 f保?Zc.

5）設(shè)h：P→Q是g的另一個滿足條件的擴(kuò)張.則?x∈ P，h（x）＝h（∨ （↓ （?Zcx∩ B）））＝∨h（↓（?Zcx∩B））＝∨↓h（?Zcx∩B）＝∨h（?Zcx∩B）＝∨g（?Zcx∩B）＝f（x）.即擴(kuò)張是唯一的.

注3.8Zc-基B關(guān)于P上的序未必是Zc-完備偏序集.g：B→Q保Zc-集的并是指若?S∈Zc（B），∨S∈B，則 g（∨BS）＝∨Qg（S）.故在定義3.6 中要求?Zcx∩B∈Zc（B）.