|
2 Comonads的基本范畴论性质 由于monads和comonads互为范畴对偶概念,因此comonads的许多范畴论性质都可以直145 接由monads的对偶所得.J.M.Beck和M.Barr等人在其研究[2-5]中对comonads的纯范畴论性质有比较详细的介绍. P.Huber于1961年提出并证明了由遗忘函子U:及其左伴随F:所构成的伴随函子F-|U:和伴随射:IdUF,:FUId可以自然地确定一个monad (UF,,UF)[7].随后,S.Eilenberg和J.Moore、H.Kleisli分别从不同的角度证明了范畴上的每一个monad都可150 由一对伴随函子“自然地”确定.S.Eilenberg和J.Moore是根据由monad (T,,)所确定的T-代数范畴T及其忘却函子UT:T来构造伴随函子,并证明该伴随函子所确定的monad就是(T,,),而H.Kleisli则利用Kleisli范畴给出伴随函子的构造方式. M.Barr[5]证明了以下定理成立: 定理1. 任意一对伴随函子F|G:可以“自然地”确定范畴上的一个comonad 155 (D,,),其中自函子D= FG:,共单位元:DId,共乘=FG:D=FGFGFG=D2. 定理1表明任意一对伴随F|G:都可以确定范畴上的一个comonad D=(FG,,FG),因此伴随函子构成comonads的一个来源.由于范畴中的每一个comonad (D,,)同时也是其反射范畴op中的一个monad.因此,任意两个范畴间的每一个经典构造都可以定义一个伴随,而每一个伴随反过来又可以定义一个monad和一个comonad.换句话说,每一个经典构造都160 可以自然地产生一个monad和一个comonad. 相反地,任意一个comonad都可以由一对伴随函子“自然地”确定.对范畴上的每一个comonad,存在许多范畴,使得该comonad可以分解为一个从到的伴随.典型地,利用后面的共自由共代数可以确定一个comonad.假设D是由D-共代数所构成的范畴,函子BD:D将任意的变量X映射为X的共自由共代数(DX,X:DXD2X),而遗忘函子UD:D165 将每一个D-共代数(X,X:XDX)映射为其载体X,将每一个D-共代数同态射f :(X,X)(Y,Y) 映射为载体上的函数f :XY.由伴随BD|UD:D可以自然地确定一个comonad,并且该伴随是一个初始对象.即对于产生comonads的任意伴随B|U:,都存在一个唯一的比较函子K:D,使得以下的图表交换: DUUDBDBK 170 图2. 伴随与比较函子 Figure 2. Adjunction and comparison functor 即比较函子K在所有确定comonads的伴随对范畴中是一个初始对象.若该比较函子K是一个同构射,那么称U:称为是comonadic函子.例如,UD:D就是一个典型的comonadic函子.B.Mesablishvili在文献[8]中介绍了部分范畴上的comonadic函子的判定条件. 175 Comonads与伴随之间的关系一方面有助于从更抽象的角度探讨comonads的构造以及与monads的对偶性.例如,利用伴随构造comonads可以将基于终结共代数的共归纳原则替换成更加抽象的伴随原则,或者将comonadic程序与monadic程序关联起来.另一方面便于将一些简单范畴上的comonads研究扩展到其他更复杂的范畴中. Comonadic函子的判定及其系统所具有的性质对于共等式、共簇(covarieties)及模态逻辑180 等领域的研究具有重要的意义.例如,J.Adamek[9]证明了若共代数遗忘函子U:B是comonadic函子,则函子B为一个共簇子(covarietor),且共簇恰好是B的一个完全子范畴.利用comonadic函子和比较函子还可以进一步比较和分析一般共代数和comonads共代数之间的对应关系.J.Huges[10]和D.Turi[11]等人在其博士论文均对这方面进行了比较详细的分析. 值得注意的是,虽然comonads的许多性质都可以由monads的对偶所得,而且范畴中的185 一个comonad同时也是其反射范畴op中的一个monad,但有些时候范畴中的许多性质在其反射范畴op中并不存在,例如拓扑空间.因此,我们认为研究这些范畴上的comonads有助于更好地理解comonads的特性及与monads间的关系. 3 Comonads与共代数 正如泛代数中的许多核心概念,如基调、变量、项、替换、等式及簇等,都可利用集合范190 畴Set上的monads理论给出相应的解释,泛共代数中的许多核心概念,如共基调、全局行为、观察、共等式及共簇等,也都可以利用集合范畴Set上comonads理论给出相应的解释.事实上,comonads(或monads)可以看成是对满足某种性质的共代数(或代数)结构的一种抽象. 下面给出共自由共代数、共自由comonads及comonads共代数的定义. 定义4. 给定具有积的范畴及其上的共代数(X,X:XBX).对于每一个对象X,D在X195 的值DX是自函子Id×B:所对应的终结共代数上的载体,并且满足DX X×BDX.称(DX,εX,DX)是共代数函子B在X上的一个共自由共代数,其中εX:DXX,DX:DXBDX. 共自由共代数具有泛性质:对于任意的B-共代数(Y,Y)及相应的共评价(coevaluation)函数f :YX,都存在一个唯一的态射f B,使得f B是从(Y,Y)到(DX,DX)的共代数同态射,即(DX,DX)为一个终结共代数,而f B是从(Y,Y)到(DX,DX)的共归纳扩展射或共迭代函数. 200 特殊地,对于单元素集1={*}(即集合中的终结对象),由于D11×BD1BD1,因此D在1上的值D1实际上就是共代数函子B所对应的终结共代数上的载体,即D1为共代数函子B的抽象全局行为集合. 由共自由共代数及其泛性质可确定一个comonad (D,,),其中共单位元=X,共乘 :DD2在X上的值可看成是由DX:DXBDX沿DX的标识函子IdDX的共归纳扩展而成.容205 易证明和均为自然转换,且满足comonads上的一致性条件.称该comonad (D,,)是由共代数函子B通过共自由构造所产生的共自由comonad.显然,共自由共代数和共自由comonads分别是泛代数理论中的自由代数和自由monads的范畴对偶概念. 定义5. 给定范畴上的一个comonad (D,,),称(X,X:XDX)为一个D-共代数当且仅当满足以下的图表交换: 210 XXDXXXIdX X2DXDXDXXXDXX 图3. D-共代数的一致性性质 Figure 3. Coherence properties of D-coalgebras D-共代数实际上就是自函子D:上的共代数,且同时保持comonads上的共单位元及共乘定律.D-共代数也经常称为Eilenberg-Moore-共代数[12]或comonads共代数.给定某个由共215 代数函子B所共自由产生的共自由comonad (D,,),则由所有的D-共代数及其同态射可构成一个范畴,记为D,并称之为comonad (D,,)的co-Eilenberg-Moore范畴. 可以说,comonads与共代数之间的有机结合是该理论能够在计算机科学中得到广泛应用的一个非常重要的原因.一方面可以充分利用共代数在系统理论方面的研究成果,另一方面可以利用comonads与monads间的对偶性及分配律将代数中各种重要的研究成果与共代数研220 究有机的融合在一起. 由于comonads共代数在comonads理论及共代数研究中的重要性,许多学者均对comonads共代数与一般共代数间的关系及其性质进行了广泛而深入的研究.例如,其中一个重要的成果是由共代数函子B所确定的co-Eilenberg-Moore范畴D与由所有B-共代数及其同态射所构成的范畴B之间是同构的,即每一个B-共代数(DX,DX:DXBDX)与一个D-共代225 数(DX,X:DXD2X)存在一一对应关系.利用该同构性可以在一般共代数与comonads共代数之间互相转换.在很多情况下,利用comonads共代数研究状态系统的行为语义要比一般的共代数更合适,例如可借助共单位元和共乘操作对状态空间上的行为进行遍历.D.Turi在研究程序语言的函子化指称语义和操作语义时就是利用comonads共代数来代替一般的共代数[11-12].类似地,在模态逻辑研究中也经常采用comonads共代数研究共等式和共簇的范畴论语义.另230 外,在描述状态系统时,一般共代数只给了系统的单步行为结构,而comonads共代数可以给出系统的多步行为结构,这有助于人们更好地理解和研究状态系统的行为语义关系,如互模拟、模拟和迹等价等. 从现有的相关研究文献来看,大部分的研究集中在由共代数函子所生成的共自由comonads共代数与原函子的共代数之间的关系.但在有些情况下,comonads并不一定能够通235 过共代数函子所共自由生成,因此需要研究这些类型的comonads共代数 (如非共自由生成、自由生成或一般的comonads共代数)及其范畴本身的性质,如完备co-Eilenberg-Moore范畴的条件和性质,以及它们与一般的共代数之间的关系,如存在一一对应关系的前提条件等. 另一方面,泛共代数中的许多核心概念(如共代数的构造、互模拟、终结共代数的存在性和共归纳原理等)的comonads解释或者与comonads之间的关系也需要更深入的研究.例如,M.Kick240 在其研究[6]中指出进化comonads共代数上的互模拟关系就是时间互模拟,但comonads与共代数互模拟、模拟和迹等价等理论之间的关系仍存在许多问题有待解决.另外,将集合范畴Set上的comonads与共代数之间的关系扩展到其他范畴上也是很值得研究的一个方向.例如,在 范畴SetA上研究基于comonads的多类别共代数理论,或者在拓扑空间上利用comonads共代数研究程序的行为语义,或者在代数范畴上利用comonads研究线性逻辑的范畴论模245 型.B.Jacobs在文献[13]中证明了由完全格上的幂集comonads的共代数所构成的范畴同构于集合范畴. 4 结论 与monads理论相比,comonads理论具有自己独特的优势.一方面,comonads的高度抽象性、良好的扩展性和适应性使得它为形式语义、程序语言设计、类型理论、计算模型、模态250 逻辑、共代数和双代数等众多领域的研究提供了更为高级和抽象的方法,带来新的研究思路,并促进范畴论和共代数在计算机科学中的应用;另一方面,利用comonads和函子间的各种分配律可以将计算机科学中许多长期以来被广泛研究和应用的数学基础理论有机地融合起来,特别是代数和共代数中的各种重要研究成果. 学术论文网Tag：代写硕士论文 代写论文 代写MBA论文 代写博士论文 |
