一种新的定量域理论方法结合了多领域思想，构建X-范畴实现建设性分析与模糊数学

77理论计算机科学电子笔记45（2001）网址：http://www.elsevier.nl/locate/entcs/volume45.html11页一种新的定量域理论范磊1，2首都师范大学数学系北京100037摘要本文介绍了一种新的研究框架充实的范畴理论的方法 该方法结合了来自各个领域的思想，如广义超度量域，类，建设性分析和模糊数学。 作为基本框架，我们使用Wagner的带框架的X-范畴[18，19]代替带单位的Quantale。范畴中的对象和态射分别称为L-Fuzzy偏序集和L-Fuzzy单调映射。此外，我们引入了伴随的概念和一种收敛的L-Fuzzy偏序集，使理论的“建设性”或“可计算”。1介绍数量域理论引起了广泛的关注[4]，[15]，[17]和[18]。 在这些发展中，K.Wagner的超范畴理论是最一般的，而J.J.M.M.Rutten的广义超度量Domain理论最接近标准Domain理论。因此，人们很自然地认为，关于后者的某些性质，特别是与单位区间[0，1]的运算性质和拓扑性质密切相关的性质，在没有对值Quantale的限制条件的情况下，可能不能推广到N-范畴理论当然，这在一般情况下是正确的，但它并不总是正确的K瓦格纳在本文中，我们提供了更多的例子，以进一步支持这一观察。在第二节中，我们回顾了本文所需的一些材料。作为基础，我们使用Wagner然而，本文中使用的方法适用于1本工作得到国家自然科学基金2电子邮件地址：fanlei63@hotmail.com2000年1月，出版社dbyElsevierScienceB。 V. 在CC BY-NC-ND许可下开放访问。雷范78--∧ ∨→∈⇒∈≤×−→∈ ∧≤--一般情况下。为了强调本文所持的模糊观点，我们将范畴中的对象和态射分别称为L-Fuzzy偏序集和L-Fuzzy单调映射然后，我们证明了一个表示定理，它表明，每一个L-Fuzzy预序集可以表示为一个家庭的预序，该集正确地粘在一起。最后，我们给出了L-Fuzzy单调映射的伴随对理论，它是Rutten度量伴随对理论的推广。在第三节中，我们引入了L-Fuzzy偏序集的收敛性理论该理论是基于一个简单的想法，从建设性的分析，即取代武断的n>0，具有适当的 因此，我们的工作可以被看作是一个建设性的版本瓦格纳在最后一节中，我们按照J. J. M. M. Rutten[15]的方法，在L-Fuzzy偏序集和L-Fuzzy伴随对范畴中建立了递归域方程的理论。2LF-偏序集与LF-单调映射首先，我们以稍微不同的形式回顾了一些基本概念，详见[19]。 请注意，我们使用框架代替一个可交换的Quantale与单位。在下文中，（L，）将表示一个固定的非平凡框架（或完备海廷代数），其最大元素为1，最小元素为0。对于a，b L，L中的交，并和蕴涵分别用ab，ab和ab定义2.1设X是一个非空集，e：XXL是一个映射。e称为X上的L-Fuzzy前序，如果它满足以下条件：1. 对所有x∈X，e（x，x）= 1，2. 对于所有的x，y，zX，e（x，z）e（x，y）e（y，z）。对（X，e）或X称为L-Fuzzy预序集。如果满足附加条件，3. 对于所有x，y X，e（x，y）=e（y，x）= 1x =y，则称它为X上的L-Fuzzy偏序，（X，e）称为L-Fuzzy偏序集（简称L-Fuzzy偏序集或LF-偏序集）。4. 设（X，eX）和（Y，eY）是L-Fuzzy预序集，f：X−→Y是映射.称f是L-Fuzzy单调映射，如果对任意x，y∈X，e Y（f（x），f（y））≥ e X（x，y）.LF-预序集（LF-偏序集）和LF-单调映射的范畴用LF-Pre（LF-POS）表示.备注2.2（1）若L= 0， 1，则范畴LF-Pre（LF-POS）可与普通预序集范畴Pre（POS）等同雷范79≤X±（偏序集）和单调映射。(2)如果L= [0， 1]，则范畴LF-Pre（LF-POS）可以通过下面定义的关系与Rutten的广义超度量空间（拟超度量空间）和非扩张映射的范畴Gums（Qumse（x，y）= 1 −d（x，y），x，y∈X.直觉上，e（x，y）被解释为xy的次数。这部分地证明了L-Fuzzy这个术语。当然，还有其他原因。参见下面的示例2.3（2）、[10]、[11]和[13]以了解更多信息。例2.3（1）设（X，≤）是一个预序集。对于x，y∈X，令e≤（x，y）= 1 x ≤ y。则（X，e≤）是L-Fuzzy预序集。当≤是X上的偏序时，（X，e≤）是L-Fuzzy偏序集.(2)设A：X−→L是X上的L-Fuzzy集。 对于x，y∈X，令e A（x，y）= A（x）→ A（y）。则（X，eA）是L-Fuzzy预序集。特别地，每个帧L可以看作是一个L-Fuzzy预序集，令X=L和A=idL。设（X，eX）和（Y，eY）是L-Fuzzy预序集，YX=[X → Y]={f |f：X −→ Y是L-单调}。我们可以使YX作为L-Fuzzy预序集，通过定义E YX（f，g）={e Y（f（x），g（x））|x ∈X}，f，g ∈ Y.此外，我们将f和g之间的噪声定义为δf，g= E XX（id X，g f）<$E YY（f g，id Y）.设（X，e）是L-Fuzzy预序集，x，y∈X，a∈L.在X上定义一个关系±a如下：x±ay≠e（x，y）≥a。然后很容易检验±a是X上的一个预序，对所有a∈L。事实上，我们有：定理2.4（分解定理）设（X，e）是L-Fuzzy预序集。然后(1) 如果a ≤ b，则±b<$±a。(2) 对于所有SL，如果a=S，则a={≤ s|s ∈ S}。雷范80(3) 对所有x，y ∈ X，e（x，y）= {a ∈ L|x ± ay}。雷范81F{|∈}≈此外，如果f：X −→ Y是L-Fuzzy预序集之间的映射，则f是L-单调的当且仅当对所有a∈L，f：（X，±a）−→（Y，±a）是单调的，即x ±ay =<$f（x）±af（y）。✷定理2.5（表现定理）设X是一个集合，F ={R a|a∈ L}是X上的一个预序族，具有以下性质：(1) 若a≤b，则Rb<$Ra;(2) 对于所有SL，Ra={R s|s ∈ S}，当a =S.则（X，eF）是L-Fuzzy预序集，其中eF（x，y）={a∈L|（x，y）∈Ra}，x，y ∈X.此外，假设X，Y是集合，F={R a|a∈L}，G={T a|a ∈ L}满足上述性质（1）和（2），f：X −→ Y是一个映射，使得对所有a∈L，f：（X，Ra）−→（Y，Ta）是单调的. 则f：（X，eF）−→（Y，eG）是L-单调映射。✷上述定理的证明是常规的。值得注意的是，定理2.4和定理2.5可以用（前）层的语言改写如下。回想一下，L上的一个预层是一个逆变函子F：L−→SetfromL（视为一个范畴）to the catorySet of sets and mapping。如果用一个更一般的具有适当结构的范畴C来替换Set，则得到一个C设PO（X）表示集合X上所有以子集包含为序的预序的偏序集（所以是一个范畴）。那么很容易看出定理2.5中的条件（1）等价于说=Ra a L是L上的PO（X）-预层，而条件（2）恰好是层条件。众 所 周 知 ， 伴 随 对 理 论 在 整 环 理 论 中 起 着 重 要 的 作 用 。J.J.M.M.Rutten [15]和F.Alesi et al. [2]建立了伴随的经典理论的真正定量版本。我们现在将建立一个LF-单调映射的伴随理论，它是Rutten的一个推广。对a，b，η∈L，设a<$b=（a→b）<$（b→a）且a<$ηb惠a<$b≥η.在非正式的模糊逻辑术语中，a/b是命题a和b的等价“程度”，而aηb意味着a和b等价于“直到次数η“ 至少.定义2.6设（X，eX）和（Y，eY）是LF-预序集，f：X−→Y和g：Y−→X LF-单调映射且η∈L.如果对所有x∈X，y∈Y，eY（f（x），y）∈eX（x，g（y）），则f，g称为η-伴随对，记为fEηg。定理2.7设（X，eX）和（Y，eY）是LF-预序集，f：X−→Y和g：Y−→XLF-单调映射且η∈L.那么下面的雷范82∈--{}∈∈−{}∈条件等同：(1)fEηg;(2)δαf，gαη1;(3) 对所有x∈X，y ∈Y，n≤η，f（x）≤ny惠x≤ng（y）;(4) idX± ηg f，f g ± ηidY。✷证明的基本部分是框架理论的一个简单结果，如下所示。引理2.8设L是框架，a，b，η L。以下条件是等效的：(1) aaab;(2) an=bn;(3) a→η=b →η;(4) 对任意的ε ∈ L，ε ≤ η，ε ≤ a惠ε ≤ b。3LF-偏序集的收敛定理在这一节中，我们介绍了LF-偏序集的收敛理论。它是基于一个非常简单和直观的想法，从建设性的分析，即我们取代任意的n>0与一个可计算的序列减少到0（如1/n），为所有的实际目的，见[3]的例子。 我们将这一思想推广到LF-偏序集.事实上，由此产生的理论是瓦格纳的收敛liminf理论的一个特例定义3.1设η=（ηn）n∈ω是L中的增序列，n∈ω}=1. 则η称为测试序列。{η n|实施例3.2（1）设L =0、 1个对所有n ω，ηn= 1。则η=（ηn）是L中的检验序列.这对应于基于预序集的经典理论(2) 设L = [0，1]，对所有n ω，ηn= 1（1/n）。则η =（ηn）是L中的测试序列。这对应于Rutten(3) 设L = ω ω，对所有n ω，ηn= n. 则η =（ηn）是L中的检验序列.这对应于蒙泰罗的sfe理论（具有等价族的集合），详见[14]。定义3.3设（X，e）是一个非空LF-偏序集，（xn）n∈ωa序列在X.(1) 称（xn）关于η收敛于x（η-收敛于x，brie y），记为x=η-limxn，如果存在x∈X使得雷范83{|∈}对于每个N∈ω和a∈X，n≥Ne（x n，a）nN e（x，a）。(2) 称（xn）是关于η的（正向）柯西序列（η-柯西序列，简记），如果对任意N∈ω且m≥n≥N，e（ xn， xn）≥ηN，或等价地，对任意n ≥ N，e（xn，xn+1）≥ηN.(3) 称（X，e）是η-完备的，如果X中的每个η-柯西序列都收敛.用η-CPO表示η-完备LF-偏序集和LF-单调映射范畴.注3.4一位匿名的评论者向作者指出，关于tη的收敛是来自丰富范畴论的加权（余）极限概念的一个特例，参见[5]。关于度量空间的情况，参见[16]。例3.5设L ={0，1}，η是例3.2（1）中的检验序列。则X中的序列（xn）有极限xw.r.tη当且仅当x是集合xn n ω的最小上界。此外，（xn）是η-Cauchy当且仅当它是X中的增序列.所以我们有：定理3.6设X为例2.3（1）中定义的LF-偏序集，η为例3.2（1）中定义的检验序列. 则X是η-完全的当且仅当它是ω-dcpo。✷定理3.7设（X，e）是LF-偏序集，（xn）是X中的序列，x∈X.则x = η-lim xn当且仅当以下条件成立：（一）（二）n≥Ne（xn，x）≥ηN，N∈ω;n≥Ne（xn，a）≤e（x，a），N∈ω，a ∈ X.✷推论3.8设（xn）是X中的序列，且x ∈ X. 如果x = η-lim x n，则：(1) n≥N，e（xn，x） ≥ηN，N ∈ω;(2) 如果XJ∈ X使得条件（1）成立则e（x，XJ）= 1.✷推论3.8中的条件（1）和（2）可以用序论的术语解释如下：（（换句话说，x是集合{ x n}的最小上界|n∈ω，n≥N}在水平η N对所有N∈ω.定理3.9设L是一个LF-偏序集框架，如例2.3（2）所示，η是L中的一个检验序列。 若（xn）是L中的η-Cauchy序列，然后η-limxn ={x n|N ∈ ω，n≥N}。特别地，L作为LF-偏序集是η -完备的.✷雷范84∈定义3.10设（X，eX），（Y，eY）是LF-偏序集且f：（X，eX）−→（Y，eY）是LF-单调映射.(1) f称为η-连续的，如果对X中的每个收敛序列（xn），（f（xn））是Y中的收敛序列，并且f（η-lim xn）= η-lim f（xn）.从X到Y的所有η-连续映射的集合C（X，Y），当它被看作Y的子集X= [X→Y]时，也是LF(2) f称为η-近似的，如果对所有x，y∈X，N∈ω，e（x，y）≥η N= εe（f（x），f（y））≥η N+1.“近似”一词是由L.Monteiro在[14]中创造的。它是度量空间理论中压缩映射的一种构造形式注3.11众所周知，在标准度量空间中，每个压缩映射都是连续的。但在目前的情况下，情况并非如此。实际上，η-连续映射和η-近似映射是不可比较的.定理3.12设X，Y是LF-偏序集，Y是η-完备集. 然后C（X，Y）也是η-完全的。✷定理3.13（不动点定理）设（X，e）是η-完备LF-偏序集，f：X-→X是LF-单调映射.(1) 若f是η-连续的且存在xX使得e（x，f（x））=1，则f有不动点。(2) 如果f是η-连续的，η-逼近的，且存在x ∈ X使得e（x，f（x））≥ η0，则f有不动点.✷定理3.13的证明类似于广义超度量空间的相应结果，见[15]中的定理6.3。4η-CPO范畴中的区域方程在这一节中，我们按照J.M.Rutten [15]的方法，在η-完备LF-偏序集和LF-伴随对范畴中建立了求解域方程的理论。本节结果的证明类似于广义超度量空间的情形，详见[6]。作为基本框架，我们使用了由η-完备LF-偏序集和η-连续LF-伴随对构成的范畴η -CPOP（P表示对），即η-CPOP中的对象是η-完备LF-偏序集，η -CPOP中的态射是对<$f，g<$：X−→Y，其中f：X−→Y和g：Y−→X是η-连续映射.态射的合成像往常一样定义：如果n-CPO P中的态射是n-CPO P中的态射，则n-CPO P中的态射是n-CPO P中的态射，n-CPO P中的态射是n-CPOP雷范85⟨⟩00⟨⟩11⟨⟩00⟨⟩11⟨⟩00⟨⟩11定义4.1（1）序列x0的f、g−→X1f、g−→ · ··在η-CPO中，P称为η-Cauchy链，如果对任意N∈ω且n≥N，fnEηNgn，或等价地，δηN1。(2) 让f、gX0−→ X1f、g−→ · ··是η-CPOP中的η-Cauchy链。链的锥是一个序列{<$αk，βk<$：Xk→X}是η-CPOP中的态射，使得<$αk，βk<$=<$αk+1，βk+1 <$$><$fk，gk<$对于每个k∈ω。(3) 一个锥{<$αk，βk<$：Xk→X}是一个余极限，如果它是初始锥，即对每一个锥{<$αkJ，βkJ<$：Xk→XJ}，都存在唯一态射f，g，f：X−→XJ，使得<$αkJ，βkJ<$=<$αk，βk<$$>f，g<$对于每个k∈ω。我们将使用以下约定。 对所有的k，l ∈ ω，k k（gkl<$fkl），其中k ∈ ω.(2) η-lim（αk<$βk）= idX.✷定理4.3 η-CPOP中的每一个η-Cauchy链都有唯一的上极限锥. ✷定义4.4假设F：LF−POS−→LF−POS是一个函子，FXY：YX−→F（Y）F（X）表示LF-偏序集X，Y的映射f<$→F（f）.(1) 称F是局部LF-单调的，如果对任意LF-偏序集X，Y，FXY是LF-单调的.(2) 称F是局部η-连续的，如果FXY对任意LF-偏序集X，Y是η-连续的.雷范86−→⟨ ⟩ ⟨ ⟩ ⟨⟩−→−→- −→ −0(3) 称F是局部η-逼近的，如果FXY对任意LF-偏序集X，Y都是η-逼近的.每个函子F：LFPOSLFPOS可以扩展到一个功能-torFP：η-CPOPη-CPOPP如下：对于每个对象，FP（X）=F（XX在η-CPOP中的任意态射f，g都有FP（f，g）=F（f），F（g）.称函子FP：η-CPOPη-CPOP是局部LF-单调的（分别是局部η-连续的，局部 η-近似的），如果相应的函子F是.定理4.5设F P：η-CPOPη-CPOP是如上定义的函子. 然后又道：(1) 如果F是局部LF-单调的，则δ（FP（f，g））=δ<$F（f），F（g）<$≥δ<$f，g<$对于η -CPOP中的每个态射<$f，g<$f.(2) 如果F是局部η-近似的，则δ<$f，g<$≥ηN=<$δ<$F（f），F（g）<$≥ηN+1对η -CPOP中的每个态射δ<$f，g <$f，N ∈ ω.✷作为广义超度量空间的情形，我们现在可以给出定理3.13的范畴形式。定理4.6设F P：η-CPOP−→η-CPOP是函子.(1) 如果F是局部η-连续的，且存在一个对象X和一个态射n ∈f，g∈ f：X−→ η -CPOP的F（X），使得f∈g.则存在η -CP OP的对象Y满足F（Y）≠Y.(2) 如果F是局部η-连续的和η-逼近的，且存在一个对象X和η -CPOP的态射<$f，g<$：X−→F（X）使得fEηg.n存在n-CPOP的非目标Y满足F（Y）≠ Y. ✷确认作者感谢M教授。不爱，G.- Q.感谢张先生和裁判们的宝贵帮助，纠正了许多错误，改进了演示文稿，并提出了意见。引用[1] Abramsky ， S. ， A. Jung， Domain theory ， in S.Abramsky ， D.Gabbay ，T.Maibaum，editors，“Handbook of Logic in Computer Science”，vol. 3，pp.1-168，牛津大学出版社，1995年。雷范87[2] Alesi，F.，P. Baldan，G.贝尔和JJM吕明，函子与非函子度量域方程的解，电 子 笔 记 ， 理 论 计 算 机 科 学 1 （ 1995 ） 。 网 址 ：http://www.elsevier.nl/locate/entcs/volume1.html。[3] Bishop，E.，D. Bridges，[4] Bonsangue，M.M.，张文，张文生，张文生，等.超度量空间的完备化与幂域，计算机科学，1998，第1 -51页.[5] Borceux，F.，G. M. Kelly，A notion of limit for enriched categories，Bull.Austral.Math.Soc.12（1975），pp.49-72.[6] 凡湖，论域理论中的几个问题，首都师范大学博士论文，2001。(In中文版）[7] Flagg，B.，R. 张文，连续空间：连续域与度量空间，计算机科学，1997年，第111 -138页。[8] Flagg，B.，R. Kopperman，不动点与弹性区域方程连续空间的范畴，理论计算机科学电子笔记1（1995）。网址：http://www.elsevier.nl/locate/entcs/volume1.html。[9] 弗拉格湾，P. 南德豪和K。 瓦格纳量子论域理论的逻辑方法1996年提交给Elsevier的预印本[10] 格雷森河J.，Heyting-valued语义，在G.Lotti等人，编辑，逻辑学术讨论会[11] 霍勒，美国在A. 约翰是这样的。，编，[12] Lawvere，F.W.，度量空间，广义逻辑与闭范畴，Rend。Sem等Mat. e. Fisicodi Milano43（1973），pp.135-166.[13] 洛温河，Mathematics and Future，in A.Jones et al.，编者，“模糊集与应用”，第3-38页，D.Reidel出版公司1986年。[14] 蒙泰罗，L.，语义域基于对集与家庭电子笔记在理论计算机科学11（1996）。网址：http://www.elsevier.nl/locate/entcs/volume11.html。[15] Rutten，J.J.M.M.，《广义超度量域理论的基本原理》，《理论计算机科学》，170（1996），第349 -381页。[16] Rutten，J.J.M.M.，广义度量空间中的加权余极限和形式球，拓扑及其应用89（1998），pp.179-202。[17] 史密斯，M.B、准一致性：用度量空间表示域，程序设计语言语义学的数学基础，计算机科学讲义，Springer出版社，1987年。雷范88[18] Wagner，K.，张文龙，张文龙，张文龙，1994.[19] Wagner，K.， 极限收敛的范畴，理论计算机科学，出现。[20] Zheng，Chongyou，L.范，H.B. 崔，（中文）