序列擬連續domain的廣義有界理想

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

關鍵詞：鏈；序列擬連續；domain；嵌入

中圖分類號：O153.1；O189.1"" 文獻標識碼：A"""""" 文章編號：2095-9699（2024）06-0001-04

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

1 基本概念

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

設L是dcpo，G和H?L是非空有限集，D?L是定向集，定義如下關系：

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

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

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

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

擬連續domain是連續domain的推廣，其有著許多與連續domain類似的性質。

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

2 序列擬連續與廣義有界理想

設L是偏序集，L中的鏈是一個保序序列（an）n∈N，簡記為（an）n。如果任意的鏈都存在上確界，記為∨n（an）n，則稱L是ω-完備偏序集，簡稱ωcpo。任意的x，y∈L，如果對任意的鏈（an）?L，y＜＜∨n（an）n，意味著存在n∈瘙綃使得x≤an，則稱元素x序列逼近元素y，記為x＜＜ny^[12]。

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

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

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

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

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

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

結合定義1.1，若L是dcpo，則所有的鏈都是定向集族，從而擬連續domain都是序列擬連續domain。上述定義說明了序列擬連續結構是定義在更簡單的ωcpo上的。

一般情況下，序列擬連續domain可能是比較復雜的結構。于是，自然產生一個問題：由一個較簡單的序列擬連續domain能否生成一個比較復雜的序列擬連續domain？為此，我們單獨定義序列擬基。

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

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

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

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

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

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

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

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

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

下面說明nb是由（Bn）n生成的廣義有界理想。如果F∈〈Bn〉n，則Bn?↑F對某個n成立，則F≤Bn＜＜b，即F∈nb。反之，如果F∈nb，若對任意的n，FBn，則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，則由元素之間的序列逼近關系定義，可知存在n使得f≤bn，這與bn↑F矛盾，則存在n使得F≤Bn，F∈〈Bn〉n。

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

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

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

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

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

反之，如果na?nb，設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 設偏序集B是一個序列擬基，嵌入e：B→GRIdI（B）是單射。

證明：如果a，b∈B且a≠b，且na=nb，即na有兩個不同的原像，則↑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）是單射。

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

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

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

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

顯然，對任意的m≤n，對任意的i有Bm，i＜＜nBn，j對某一個j成立。對所有的1≤i≤m，1≤j≤n存在k使得Bi，j＜＜nBm+1，k，把k看成關于i，j的函數，記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鏈滿足對任意的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說明了鏈中所有廣義有界理想構成的鏈的并仍然是廣義有界理想。

定理2.2 設偏序集B是一個序列擬基，則GRIdI（B）是以B為序列擬基序列擬連續domain。

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

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

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

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

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

3 結束語

在傳統domain理論中，由于定向集的不確定性，很難從一個簡單的擬連續domain定義一個更大的擬連續domain。本文以偏序集中的鏈為研究對象，定義了序列擬基，其本質也是序列擬連續domain，并將其擴充為一個更大的序列擬連續domain。

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

（1）序列擬連續domain與擬連續domain之間具有怎樣的聯系，是否存在類似于第一可數拓撲空間是序列空間的性質。

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

參考文獻：

[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-超連續偏序集的性質及等價刻畫[J].計算機工程與應用，2015，51（1）：9-12.

[4]路玲霞.定向完備偏序集上的模糊Scott拓撲[J].計算機工程與應用，2012，48（25）：57-60.

[5]何超琴.一種基于L包含度的語義蘊涵程度化方法[J].計算機工程與應用，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]何俊，張彩慶，李小珍，等.基于偏序集的數據清洗規則鏈自動生成方法[J].計算機應用研究，2021，38（1）：83-87.

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

[10]孟華，原雅燕，儲節磊，等.AGM信念算子的拓撲式刻畫[J].計算機科學，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.

責任編輯：肖祖銘

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

基金項目：天津市教委科研計劃項目（2023KJ281）

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