摘 要：domain理論是計(jì)算機(jī)程序語言的理論基礎(chǔ)，為計(jì)算機(jī)函數(shù)式程序提供了數(shù)學(xué)模型。擬連續(xù)domain是domain理論的重要推廣。本文以鏈為主要研究對(duì)象，對(duì)一般的擬連續(xù)domain進(jìn)行了推廣，定義了序列擬連續(xù)domain、序列擬基及其廣義有界理想，并證明了序列擬基可以嵌入到其廣義有界理想中。同時(shí)，本文指出廣義有界理想的集合是序列擬連續(xù)domain。這為理論計(jì)算機(jī)提供了更為簡(jiǎn)單的程序式語義和數(shù)學(xué)模型，有助于對(duì)domain理論的進(jìn)一步研究。

關(guān)鍵詞：鏈；序列擬連續(xù)；domain；嵌入

中圖分類號(hào)：O153.1；O189.1"" 文獻(xiàn)標(biāo)識(shí)碼：A"""""" 文章編號(hào)：2095-9699（2024）06-0001-04

20世紀(jì)70年代，Scott等^[1]人提出了domain理論，受到了數(shù)學(xué)、邏輯學(xué)、計(jì)算機(jī)等領(lǐng)域廣大學(xué)者的廣泛關(guān)注。2003年，Gierz等^[2]人合著的《Continuous Lattices and Domains》集中體現(xiàn)了偏序集理論與domain理論的重要成果。近年來，domain理論相關(guān)領(lǐng)域的研究成果也不斷涌現(xiàn)^[3-7]。domain理論既是計(jì)算機(jī)程序語言的理論基礎(chǔ)，又為計(jì)算機(jī)函數(shù)式程序提供了數(shù)學(xué)模型，并廣泛應(yīng)用于理論計(jì)算機(jī)、數(shù)學(xué)建模、模糊數(shù)學(xué)、形式驗(yàn)證等領(lǐng)域^[8-10]。將domain理論推廣到更一般的結(jié)構(gòu)上去是其重要的研究方向之一。1983年，Gierz等^[6]人提出了擬連續(xù)domain，將domain理論中點(diǎn)與點(diǎn)的逼近關(guān)系推廣到非空有限子集之間的逼近關(guān)系，并說明了連續(xù)domain都是擬連續(xù)的，反之不成立，這也說明了擬連續(xù)domain確實(shí)是domain理論的重要推廣。2009年，Bauer等^[7]人通過對(duì)偏序集上鏈的研究，在連續(xù)domain基的基礎(chǔ)上提出了序列連續(xù)的概念，并由其構(gòu)造了有界理想。他們證明了序列基的所有有界理想構(gòu)成的集合是序列連續(xù)的，同時(shí)也研究了函數(shù)擴(kuò)充、函數(shù)表示、完備化等多種性質(zhì)。基于以上研究，自然會(huì)產(chǎn)生一個(gè)問題：擬連續(xù)domain是否有類似的結(jié)構(gòu)呢？本文根據(jù)擬連續(xù)domain擬基的特點(diǎn)，給出了序列擬連續(xù)domain、序列擬基等概念，并研究了其廣義有界理想。

1 基本概念

首先，介紹domain理論中的連續(xù)性與擬連續(xù)性^[11]。設(shè)L是偏序集，如果其任意的定向子集D有上確界，記為supD或∨D，則稱L是有界完備偏序集，簡(jiǎn)稱dcpo。任意的x，y∈L，如果對(duì)任意的定向集D?L，y≤supD意味著D∩↑x≠?，則稱元素x逼近元素y，記為x＜＜y。設(shè)L是dcpo，若對(duì)任意的x∈L，如果{y：y＜＜x}是定向集且其上確界為x，則稱L是連續(xù)domain。

設(shè)L是dcpo，G和H?L是非空有限集，D?L是定向集，定義如下關(guān)系：

（1）如果↑H?↑G，則稱G小于等于H，記為G≤H；

（2）如果supD∈↑H蘊(yùn)含D∩↑G≠?，則稱G逼近H，記為G＜＜H。若H={x}，則簡(jiǎn)記為G＜＜x^[11]。

用P^（w）（L）表示L的所有非空有限子集，Γ為非空有限集族。如果對(duì)任意的F1，F(xiàn)2∈Γ存在F∈Γ使得F?↑F1∩↑F2，則稱Γ是定向的非空有限集族。令fin（x）={F：F∈P^（w）（L），F(xiàn)＜＜x}，其中P^（w）（L）表示偏序集L的所有非空有限子集的集合。

定義1.1^[11] 設(shè)L是dcpo，若對(duì)任意的x∈L，集合fin（x）={F：F∈P^（w）（L），F(xiàn)＜＜x}是定向集族并且有↑x=∩F∈fin（x）↑F，則稱L是擬連續(xù)domain。

擬連續(xù)domain是連續(xù)domain的推廣，其有著許多與連續(xù)domain類似的性質(zhì)。

定義1.2^[11] 設(shè)L是dcpo，B?L。如果對(duì)任意的x∈L，bin（x）={F：F∈P^（w）（B），F(xiàn)＜＜x}是非空有限集的定向集族并且有↑x=∩F∈bin（x）↑F，則稱B是L的擬基。

2 序列擬連續(xù)與廣義有界理想

設(shè)L是偏序集，L中的鏈?zhǔn)且粋€(gè)保序序列（an）n∈N，簡(jiǎn)記為（an）n。如果任意的鏈都存在上確界，記為∨n（an）n，則稱L是ω-完備偏序集，簡(jiǎn)稱ωcpo。任意的x，y∈L，如果對(duì)任意的鏈（an）?L，y＜＜∨n（an）n，意味著存在n∈瘙綃使得x≤an，則稱元素x序列逼近元素y，記為x＜＜ny^[12]。

設(shè)L是ωcpo，G和H?L是非空有限集，（an）?L是一個(gè)鏈，如果a∈G，b∈H，a＜＜nb，則稱G序列逼近H，記為G＜＜nH。若H={x}，則簡(jiǎn)記為G＜＜nx，記nx={F：F∈P^（w）（B），F(xiàn)＜＜nx}。已知上述定義的關(guān)系滿足：

（1）如果G＜＜nH，則G＜＜H；

（2）如果F≤G＜＜nH或F＜＜nG≤H，則F＜＜nH。

如果非空有限集序列（Bn）n滿足Bi＜＜Bi+1，則稱序列（Bn）n是＜＜n鏈，＜＜n鏈將是本文研究的重要對(duì)象，如未特殊說明，＜＜n鏈總是指上述定義的形式。

定義2.1 設(shè)L是ωcpo，若對(duì)任意的x∈L，存在鏈（Bn）n使得↑x=∩↑Bn，Bn∈fin（x），則稱L是序列擬連續(xù)domain。

序列擬連續(xù)domain L的序列擬基D是滿足如下條件的子集：任意的x∈L，存在鏈（Bn）n，Bn∈bin（x）使得↑x=∩↑Bn。

結(jié)合定義1.1，若L是dcpo，則所有的鏈都是定向集族，從而擬連續(xù)domain都是序列擬連續(xù)domain。上述定義說明了序列擬連續(xù)結(jié)構(gòu)是定義在更簡(jiǎn)單的ωcpo上的。

一般情況下，序列擬連續(xù)domain可能是比較復(fù)雜的結(jié)構(gòu)。于是，自然產(chǎn)生一個(gè)問題：由一個(gè)較簡(jiǎn)單的序列擬連續(xù)domain能否生成一個(gè)比較復(fù)雜的序列擬連續(xù)domain？為此，我們單獨(dú)定義序列擬基。

定義2.2 如果偏序集L中的任意元x存在B中＜＜n鏈（Bn）n使得↑x=∩n∈瘙綃↑Bn，則B是一個(gè)序列擬基。

如果＜＜n鏈（Bn）n滿足↑x=∩n∈瘙綃↑Bn，則稱其為逼近序列。

定義2.2單獨(dú)對(duì)一個(gè)集合定義了序列擬基。如果B是一個(gè)序列擬基，則其也是序列擬連續(xù)domain。那么，自然的研究方向就是序列擬基的性質(zhì)，以及如何建立起序列擬基與序列擬連續(xù)domain之間的關(guān)系。為此，給出廣義有界理想的概念，并研究廣義有界理想的序列擬連續(xù)性。

定義2.3 設(shè)偏序集B是一個(gè)序列擬基，Γ為B的非空有限集族，如果存在＜＜n鏈（Bn）n使得下式成立F∈Γn∈Ν，Bn?↑F，即F≤Bn，則稱Γ是B的由＜＜n鏈（Bn）n生成的廣義有界理想，簡(jiǎn)稱廣義有界理想，記為Γ=〈Bn〉n。

命題2.1 設(shè)偏序集B是一個(gè)序列擬基，Γ為B的廣義有界理想，則Γ是下集。

證明：設(shè)H∈Γ，G≤H，即H?↑G。由廣義有界理想的定義，不妨設(shè)Γ=〈Bn〉n且Bn?↑H，則顯然Bn?↑H?↑G，從而G∈Γ，Γ是下集。

記序列擬基B的所有廣義有界理想的集合為GRIdI（B），賦予集合之間的包含序。

命題2.2 設(shè)偏序集B是一個(gè)序列擬基，b∈B。則nb為B的廣義有界理想。

證明：由于B是一個(gè)序列擬基，b∈B，則存在逼近序列（Bn）n使得↑b=∩n∈瘙綃↑Bn。則對(duì)任意的n∈N，b∈↑Bn，即Bn≤b，從而易知Bn－1＜＜b，n=1，2，…。

下面說明nb是由（Bn）n生成的廣義有界理想。如果F∈〈Bn〉n，則Bn?↑F對(duì)某個(gè)n成立，則F≤Bn＜＜b，即F∈nb。反之，如果F∈nb，若對(duì)任意的n，F(xiàn)Bn，則Bn↑F，即存在bn∈Bn，bn↑F。則由集合與集合子集的＜＜n的定義知（bn）n為保序序列，顯然bn≤b，b是（bn）n的上界。

如果a也是（bn）n的上界，則a∈∩n∈瘙綃↑Bn=↑b，即ab，從而b=∨n（bn）n。由F＜＜nb知f∈F，f＜＜nb，則由元素之間的序列逼近關(guān)系定義，可知存在n使得f≤bn，這與bn↑F矛盾，則存在n使得F≤Bn，F(xiàn)∈〈Bn〉n。

綜上可知，nb為B的廣義有界理想。

設(shè)偏序集B是一個(gè)序列擬基，則可以定義嵌入e：B→GRIdI（B）如下：b∈B，e（b）=nb。

命題2.3 設(shè)偏序集B是一個(gè)序列擬基，嵌入e：B→GRIdI（B）是保序映射。

第6期""""""""""""" 王 武：序列擬連續(xù)domain的廣義有界理想

證明：如果a，b∈B且a≤b，顯然na?nb。

反之，如果na?nb，設(shè)na，nb分別由a，b的逼近序列（An）n，（Bn）n生成，即na=〈An〉n，nb=〈Bn〉n。〈An〉n?〈Bn〉n意味著任意的An∈〈Bn〉n，則存在n使得An≤Bn＜＜Bn+1，從而↑b=∩n∈瘙綃↑Bn?∩n∈瘙綃↑An=↑a，則a≤b。

命題2.4 設(shè)偏序集B是一個(gè)序列擬基，嵌入e：B→GRIdI（B）是單射。

證明：如果a，b∈B且a≠b，且na=nb，即na有兩個(gè)不同的原像，則↑a=∩naF=∩nbF=↑b，分兩種情況說明：

（1）如果alt;b，則a↑a但a↑b，與↑a=↑b矛盾；

（2）如果a與b不能比較，則也有則a↑a但a↑b，與↑a=↑b矛盾。故a=b，e：B→GRIdI（B）是單射。

由上述命題可知，在同構(gòu)意義下可以把B看成GRIdI（B）的子集。

定理2.1 設(shè)偏序集B是一個(gè)序列擬基，則GRIdI（B）是ωcpo且GRIdI（B）個(gè)中鏈（Γm）m的上確界就是∪mΓm，進(jìn)而所有廣義有界理想構(gòu)成的鏈的并仍然是廣義有界理想。

證明：設(shè)（Γm）m是GRIdI（B）中的鏈。將（Γm）m的生成序列表示為：

Γ1：B1，1…B1，n…Γ2：B2，1…B2，n…Γm：Bm，1…Bm，n…

顯然，對(duì)任意的m≤n，對(duì)任意的i有Bm，i＜＜nBn，j對(duì)某一個(gè)j成立。對(duì)所有的1≤i≤m，1≤j≤n存在k使得Bi，j＜＜nBm+1，k，把k看成關(guān)于i，j的函數(shù)，記k1=c（1，1），ki+1=c（i，max（i，ki））。令Bi=Bi，ki，則

Bi=Bi，ki＜＜nBi+1，c（i，max（i，ki））=Bi+1，ki+1=Bi+1。

易知上述選擇的＜＜n鏈滿足對(duì)任意的Bmn存在i使得Bmn＜＜nBi。顯然，Bi?∪mΓm，從而〈Bi〉i?∪mΓm。反之，若Λ∈∪mΓm，則存在m，n使得Λ＜＜nBm，n＜＜Bi，故Λ∈〈Bi〉i。

綜上可知，〈Bi〉i=∪mΓm是鏈（Γm）m的上確界，GRIdI（B）是ωcpo，且證明了GRIdI（B）中鏈的上確界就是∪mΓm。

定理2.1說明了鏈中所有廣義有界理想構(gòu)成的鏈的并仍然是廣義有界理想。

定理2.2 設(shè)偏序集B是一個(gè)序列擬基，則GRIdI（B）是以B為序列擬基序列擬連續(xù)domain。

證明：由定理2.1知GRIdI（B）是ωcpo，下面說明廣義有界理想的集合GRIdI（B）是序列擬連續(xù)的。

設(shè)Γ∈GRIdI（B），其生成序列是（Bn）n。

令e（Bn）={e（b）：b∈Bn}，由于（Bn）n是＜＜n鏈，則由e：B→GRIdI（B）的保序性知e（Bn）≤e（Bn+1），則{e（Bn）}是鏈。

對(duì)任意的F＜＜nbm，有F＜＜nbm＜＜nBm+1，則F∈Γ，則e（bm）?Γ，故?！省黣（Bm），↑Γ?∩m↑e（Bm）。反之，如果對(duì)任意的m都有Σ∈↑e（Bm），則存在bmk使得e（bmk）?Σ。對(duì)任意的F∈Γ有F＜＜nBn對(duì)某個(gè)n成立，則F＜＜nbn對(duì)任意的bbk∈Bn成立，故F∈e（bmk），從而Γ?e（bmk）?Σ，Σ∈↑Γ，即↑?！蒻↑e（Bm）。

綜上可知，↑Γ=∩m↑e（Bm），故GRIdI（B）是擬連續(xù)的且{nb：b∈B}是GRIdI（B）的擬基。

3 結(jié)束語

在傳統(tǒng)domain理論中，由于定向集的不確定性，很難從一個(gè)簡(jiǎn)單的擬連續(xù)domain定義一個(gè)更大的擬連續(xù)domain。本文以偏序集中的鏈為研究對(duì)象，定義了序列擬基，其本質(zhì)也是序列擬連續(xù)domain，并將其擴(kuò)充為一個(gè)更大的序列擬連續(xù)domain。

盡管本文的研究取得了一定進(jìn)展，但仍存在不完善之處，以下幾個(gè)方面仍需進(jìn)一步研究：

（1）序列擬連續(xù)domain與擬連續(xù)domain之間具有怎樣的聯(lián)系，是否存在類似于第一可數(shù)拓?fù)淇臻g是序列空間的性質(zhì)。

（2）序列擬連續(xù)domain之間的函數(shù)是怎樣的，函數(shù)f：B→D是否可以擴(kuò)充為GRIdI（B）到D的函數(shù)。

參考文獻(xiàn)：

[1]SCOTT D. Date types as lattices[J]. SIAM Journal on Computing，1976，55（5）：522-587.

[2]Gierz G， Hofmann K， Keimel K， et al. Continuous Lattices and Domains[M]. London： Combridge University Press， 2003.

[3]毛徐新，徐羅山.S-超連續(xù)偏序集的性質(zhì)及等價(jià)刻畫[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（1）：9-12.

[4]路玲霞.定向完備偏序集上的模糊Scott拓?fù)鋄J].計(jì)算機(jī)工程與應(yīng)用，2012，48（25）：57-60.

[5]何超琴.一種基于L包含度的語義蘊(yùn)涵程度化方法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（4）：45-46，49.

[6]YANG J B，LUO M K. Priestley spaces， quasi-hyperalgebraic lattices and Smyth powerdomains[J]. Acta mathematics Sinica， 2006，22（3）：951-958.

[7]Hamrin G. Two Categories of Effective Continuous Cpos[J].Theoretical Computer Science，2006，365（3） ：216-236.

[8]何俊，張彩慶，李小珍，等.基于偏序集的數(shù)據(jù)清洗規(guī)則鏈自動(dòng)生成方法[J].計(jì)算機(jī)應(yīng)用研究，2021，38（1）：83-87.

[9]榮宇音，徐羅山.邏輯系統(tǒng)L～*和BL～*的廣義演繹定理的逆定理[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（1）：47-49.

[10]孟華，原雅燕，儲(chǔ)節(jié)磊，等.AGM信念算子的拓?fù)涫娇坍媅J].計(jì)算機(jī)科學(xué)，2016，43（9）：87-90.

[11]LI Gaolin， XU Luoshan. QFS-Domains and their lawson compactness[J].Order，2013，30（1）：233-248.

[12]Bauer A， Kavkler I. A consteructive theory of continuous domains suitable for implementations[J]. Annals of Pure and Applied Logic，2009，159：251-267.

責(zé)任編輯：肖祖銘

Generalized Bounded Ideals of Sequential Quasi Continuous Domain

WANG Wu

（Basic Courses Department， Zhonghuan Information College Tianjin University of Technology， Tianjin 300380， China）

Abstract：Domain theory is the theoretical basis of computer programming language and provides a mathematical model for computer functional programming. Quasi continuous domain is an important generalization of domain theory. Taking the chain as the main research object， this paper generalizes the general quasi continuous domain， defines the sequence quasi continuous domain， the sequence quasi continuous base and its generalized bounded ideals， and proves that the sequence quasi continuous base can be embedded in its generalized bounded ideals. Meanwhile， it is pointed out that the set of generalized bounded ideals is a sequential quasi continuous domain. This provides a simpler procedural semantics and mathematical model for theoretical computer， which is conducive to the further study of domain theory.

Keywords： chain; sequence quasi continuity; domain; embed

基金項(xiàng)目：天津市教委科研計(jì)劃項(xiàng)目（2023KJ281）

作者簡(jiǎn)介：王 武（1985—），男，河北青龍人，副教授，主要從事domain理論及理論計(jì)算機(jī)研究。