（应用数学专业论文）余代数上的松弛不变量.pdf

余代数中的松弛不变量 摘要 在文献【1 】中，b a r t j a c o b s 和j e s s e h u g h e s 引进了集合范畴上带有偏序 关系的函子概念，定义并研究了模拟以及双向互模拟等概念本文在同 样的框架下，引入谓词不变量，定义了松弛不变量和双向松弛不变量等 概念，研究了其基本性质及相关结果，并比较了松弛不变量与模拟之间 的关系，给出了双向松弛不变量与不变量等价的充分条件；此外我们还 引进了最大松弛不变量的概念，并证明了在集合范畴上，最大松弛不变 量是关于一个特殊函子余代数的终结余代数 关键词：不变量，松弛谓词提升，松弛不变量，不动点，终结余代数 a b s t r a c t i n 【1 】b a r tj a c o b sa n dj a s s eh u g h e sh a v eb r o u g h ti na n e wk i n do ff u n c t o r t h e y t o o kt h eo r d e ro naf u n c t o ra san e wf u n c t o r b a s e do nt h a t ，t h e yd e f i n e da n d r e s e a r c h e ds o m en e wn o t i o n sa b o u tb i s i m u l a t i o n w et a k et h i sn e wf u n c t o ri n t ot h e r e s e a r c ho fi n v a r i a n ti nc o a l g e b r a ，g e tt h ed e f i n i t i o no fp r e d i c a t ei n v a r i a n t ，t h e nw e d e f i n ea n dr e s e a r c hs e v e r a ln e wn o t i o n s i nt h el a s t ，w ec a nr e a c hs o m ec o n c l u s i o n a b o u ti n v a r i a n t i ti sw o r t hp o i n t i n go u tt h a tw ef i n dt h es u f f i c i e n tc o n d i t i o nt o m a k et w o - w a yl a xi n v a r i a n ta n di n v a r i a n tc o i n c i d e ，a n dp r o v et h a tt h eg r e a tl a x i n v a r i a n ti se x a c t l yt h el a r g e s tf i x e dp o i n to fs o n l ( js p e y c i a lf u n c t o re o a l g e b r ai ns e t c a t e g o r y k e y w o r d s ：i n v a r i a n t ，l a xp r e d i c a t el i f t i n g ，l a xi n v a r i a n t ，f i x e dp o i n t ， f i n a lc a t e g o r y 。 2 首都师范大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个人或集体 已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明本人完全意识到本卢明的法律结果山本人承担 学位论文作者签名： 办1 日期：蝴年仁月7 同 首都师范大学位论文授权使用声明 本人完全了解首都师范大学有关保留，使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或其指定机构送交沦文的电子版和纸质版有权将学位 论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位 论文的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版保 密的学位论文在解密后适用本规定 学位论文作者签名： 砌味 1 日期：瀹眸明夕日 余代数中的松弛不变量 o 前言 一直以来，代数理论在计算机安全、程序语义以及处理有限数据类型 等领域有着广泛的应用，而作为代数的对偶概念一余代数，则直到上世纪 后半期才为越来越多的计算机学者所关注在计算机科学中，代数从构 造的角度研究数据类型，而余代数则从观察的角度研究系统及其性质 随着研究的深入，理论计算机科学家等逐渐发现余代数对研究基于状态 的系统，如自动机、进程、对象、软件构造等有独特的优越性利用余代 数的理论以及方法，可以对系统的行为等价，不确定性等从数学上进行 探讨，为这些系统建立形式理论基础，并对其性质进行描述与验证近几 十年，余代数在计算机科学，特别是理论计算机科学中，发挥着越来越 重要的作用，应用越来越广泛，如：余代数方法在自动机理论中的应用 【2 】，在并发模型及其语义研究中的应用 3 ，4 】，在对象语言及其语义研究 中的应用等等其他的应用【5 ，6 ，7 ，8 】，更多的关于余代数的介绍可以参看 9 】 余代数主要是给我们提供状态的一些信息，它允许我们观察系统的某 些状态，也允许我们在特定情况下修改状态，或者移动到下一个状态，但 是我们无法构造新的状态状态的行为就是我们直接或者间接观察到的 东西在这种情况下，可能会发生这样的情况：两个状态有相同的行为， 但是由于我们观察有限，实际上这两状态并不完全相同，此时我们称这 样的两个状态是互模拟由于互模拟的这种性质，互模拟在模态逻辑、 d o m a i n 理论、范畴论等领域有很广泛的应用而不变量本身是状态空间 上的谓词，表示状态空间上关于某种性质封闭，即不变量一旦成立，则无 论系统如何迁移都会成立不变量在系统的建模中起到很重要的作用， 因为不变量经常表示某种隐性的假设，如除法中除数永远不能为零，某 人的岁数永远不能为负等等因此不变量是”安全的性质”，即”坏的” 情况永远不会发生不变量的这种性质使得其在很多方面有很重要的应 3 余代数中的松弛不变量 用【5 ，6 ，1 0 ，1 1 】互模拟和不变量是余代数研究中较为重要的两个概念，关 于互模拟和不变量的详细定义以及相关结论参看 1 1 】 本文主要是基于b a r t j a c o b s 和j e s s e h u g h c s 在文献 1 】中研究互模拟 的基本框架研究不变量的相关性质。在本文中我们只考虑集合范畴上的 情形，其他范畴上的情形类似，且本文所考虑的函子也都是k r i p k c 多项 式函子在此前提下，研究松弛不变量以及双向松弛不变量等的相关性 质，并比较了松弛不变量与模拟之间的关系，并类似于文献1 的思路， 研究了不变量与双向松弛不变量之间的关系，从而得到了使得它们等价 的充分条件 本文分为四章，第一章是本文的预备知识，主要回顾范畴论、余代数 和序的相关概念，介绍了文献【1 】所引入的的集合范畴上带有偏序关系的 函子，及与该函子相关的谓词提升等概念第二章引进了松弛不变量的 概念，研究了松弛不变量与模拟之间的关系，并说明了松弛不变量的作 用此外我们证明了松弛不变量的一些基本性质，例如松弛不变量关于 并封闭( 本文中称之为最大松弛不变量) 在第三章，我们研究了松弛不 变量与函子不动点之间的关系，证明了最大松弛不变量是关于一个特殊 函子余代数的终结余代数。最后，第四章研究了松弛不变量与不变量之 间的关系，给出了两者相同的充分条件。 4 余代数中的松弛不变量 1 预备知识 本章简要介绍在阅读本文时所需要的预备知识，包括范畴论、序以及 余代数中的某些基本概念和结论除个别概念和定理的叙述与通常情形 略有差别外，本章的绝大多数内容都是标准的范畴论、拟序集和单调 映射的内容请参看文献 1 3 ，1 4 】，代数和余代数的内容请参看【1 1 】 1 1 范畴 范畴够由一个对象类d 6 ( 够) 和一个态射类m o r ( 够) 构成，其中d 6 ( 够) 中 的元素称为够的对象，通常用a ，b ，表示对任意对象a ，b d 6 够) ， 有子族够( a ，b ) m o r ( 够) ，其中够( a ，b ) 称为从a 到b 的态射，记为 | ：a _ b 。 对v a ，b ，c d 6 ( 够) ，有一种运算称为态射的合成： 够( a ，b ) xv ( b ，c ) _ 够( a ，c ) ( ，g ) 一go ， 满足以下条件： ( 1 ) 对任何a d 6 ( 够) ，存在态射i d a 够( a ，a ) ，使得： i d s0 = l 0i d a = 其中，：a _ b ( 2 ) 若有，：a _ b ，g ：b _ c ，h ：c d ，则： h 0 ( go ，) = ( h 0g ) 0 ， 1 2 初始对象v s 终结对象 设，d 6 ( 够) ，若v a d 6 ( 够) ，存在唯一的态射! j ：i a ，则称j 为够中 的一个初始对象；对偶地，设t o h ( v ) ，若v a d 6 ( 够) ，存在唯一的态射 t ! ：a _ t ，则称t 为够中的一个终结对象 1 3 函子 5 余代数中的松弛不变量 设够，是两个范畴，称f ：够一为函子，若满足以下条件： ( 1 ) 对任何a d 6 ( 够) ，f ( a ) d 6 矽) ； ( 2 ) 若有，：4 一b ，v a ，b 够， f ：够( a ，b ) _ ( f a ，f b ) ( 3 ) 对任何a d 6 ( 钐) ，f ( i d a ) = i d f a 注：若够，够7 为同一个范畴，我们称作用在其上的函子为自函子 1 4k r i p k e 多项式函子 范畴够上的k r i p k e 多项式函子是包含下列函子的最小族： ( 1 ) 恒同函子i d ； ( 2 ) 常值函子，即f = a ，其中a 是任意的对象； ( 3 ) 乘积函子，即日f 2 ，其中只，玛是任意的k r i p k e 多项式函子； ( 4 ) 和函子，即f 1 f 2 ，其中r ，局是任意的k r i p k c 多项式函子； ( 5 ) 指数函子，即g a ，其中g ，a 是任意的对象； ( 6 ) 幂函子，即汐( g ) ，其中g 是任意的对象； ( 7 ) 序列函子，即9 ，其中g 是任意的对象； ( 8 ) 由上面的函子复合而成的函子； 注：用理论计算机中的b a c k u s n a u r 范式 2 1 ，上述定义可表示为： f ：= i dla ir f 2i 乃+ f 2 lg a l ( g ) ig + 其中f = a 是指常值函子 本文中我们用s e t 表示集合及其映射的范畴，p r e o r d 表示偏序集及 其保序映射的范畴明显地，存在遗忘函子p r e o r d s e t ，使得偏序集成 为一般的集合，保序映射成为一般集合上的映射。 1 5 余代数 设f ：够_ 够是范畴够上的自函子，一个p 余代数是指( x ，c ) ，其中 x d 6 ( 够) ，c ：x _ f x 是范畴够中态射；设( x ，c ) ，( d ) 是f 余代数，称 ，：x _ y 是且余代数的同态，若下列图形交换： 6 余代数中的松弛不变量 f x 一一兰! f y c1卜 且满足以下条件： 对于任意的集合x ，e ( x ) = ( f x ，e x ) ，其中e x 表示f x 上的偏序关 系； 对于集合范畴上的任意集合间的映射厂：x _ y ，带有偏序关系的函子作 用其上为：e ( ，) ：( f x ，e x ) _ ( f e y ) ，且关于e x 和e y 是单调的 用p r e d 表示谓词的范畴，其对象是任意的谓词，即p x ，其中x 是 集合；从谓词p x 到qcx 的态射是使得下图交换的映射厂：x y x 。ly p 了f q 其中，| p 表示，在p 上的限制，k 是投影( 在本文的其他部分k 表示 同样的含义) 1 7 关系提升 在文献【1 1 】中，b a r t j a c o b s 给出了k r i p k e 多项式函子的关系提升和谓 词提升的详细定义，并论述了相关性质： 设f ：s e t _ s e t 是k r i p k e 多项式函子，x ，y 是任意的集合x ，y 上 的二元关系r 的关系提升，记为r e l ( f ) ( r ) ，按照k r i p k e 多项式函子的结 7 余代数中的松弛不变量 构归纳定义如下： ( 1 ) 若f 是恒等函子，则： r e i ( f ) ( r ) = r ( 2 ) 若f 是常值函子，即f ：z _ a ，则： r e l ( f ) ( r ) = e q ( a ) = ( 口，a ) l a a ) ( 3 ) 若f 是乘积函子，即f = f x f 2 ，则： r e i ( f ) ( r ) = ( ( u l ，u 2 ) ，( v l ，u 2 ) ) l ( l ，v 1 ) r e l ( f a ) ( r ) a ( u 2 ，v 2 ) n e l ( f 2 ) ( r ) ( 4 ) 若f 是余乘积函子，即f = f 1 + 玛，则： r e l ( f ) ( r ) = ( 后1 ( 钍) ，k l ( v ) l ( u ，口) r e l ( f 1 ) ( r ) 】u ( 乜( 牡) ，k 2 ( 钉) i ( 札，口) r e l ( j ) ( r ) _ ( 5 ) 若f 是指数函子，即f = g a ，则： r e l ( f ) ( r ) = ( ，g ) l v a a ( ，( n ) ，9 ( n ) ) r e f ( g ) ( r ) ) ( 6 ) 若f 是幂集函子，即f = p ( g ) ，则： r e l ( f ) ( r ) = ( 以v ) l w 以3 v v ( 钍，v ) r e l ( g ) ( r ) a v v k3 u 矿( u ，u ) r e l ( g ) ( r ) ) ( 7 ) 若f 是序列函子，即f = g 宰，则： r e l ( f ) ( r ) = ( ， ) i v 铊( 钍i ，优) 兄电z ( g ) ( r ) ) 在文献 1 】中，b a r t j a c o b s 和j e s s e h u g h e s 还给出了关系提升的一个等 价定义： 设f ：s e t _ s e t 是k r i p k e 多项式函子，x ，y 是任意的集合 r e l ( f ) ( r ) = ( 乱，口) i3 w f ( r ) ，s t ，f ( r 1 ) ( w ) = t ，f ( r 2 ) ( w ) = 钞) ， 8 余代数中的松弛不变量 其中( 7 1 ，7 2 ) ：r _ xxy 1 8 谓词提升 设f ：s e t _ s e t 是k r i p k c 多项式函子，x 是任意的集合x 上的谓 词p 的关系提升，记为p r e d ( f ) ( p ) ，按照f 的结构归纳定义如下： ( 1 ) 若f 是恒等函子，则： w e d ( f ) ) = p ( 2 ) 若f 是常值函子，即f ：z _ a ，则： p r e d ( f ) ( p ) = t a = ( a a ) ( 3 ) 若f 是乘积函子，即f = f 1 f 2 ，则： p r e d ( f ) ( p ) = 【( 仳，v ) l u p r e d ( f 1 ) ( p ) av p r e d ( f 2 ) ( p ) ( 4 ) 若f 是余乘积函子，即f = r + f 2 ，则： p r e d ( f ) ( p ) = ( 后1 ( u ) l 乱p r e d ( f 1 ) ( p ) ) u 尼2 ( ) i u p r e d ( f 2 ) p ) ) ( 5 ) 若f 是指数函子，即f = g a ，则： w e d ( f ) ) = i r a a ( a ) w e d ( g ) ) ) ( 6 ) 若f 是幂集函子，即f = p ( g ) ，则： w e d ( f ) ( p ) = u l w 配u w e d ( g ) ) ) ( 7 ) 若f 是序列函子，即f = g 木，则： p r e d ( f ) ) = i v i 礼乱i p r e d ( a ) ( p ) 命题1 1 1 1 - 】对于任意谓词p x ，设f 是集合范畴上的自函子，则： ( 1 ) r e z ( f ) ( 以( p ) ) = 5 f ( p r e d ( f ) ( p ) ) ，p x ，其中以0 ) = 0 ，p ) ； 9 余代数中的松弛不变量 ( 2 ) p r e d ( f ) ( t r i ( r ) ) = 死( r e f ( f ) ( r ) ) ，r x x ，i = 1 ，2 ，其中几表示投影映 射，下标i 表示投影第i 个分量； ( 3 ) w e d ( f ) ) = 死 r e f ( f ) ( 疋0 ) ) 】，i = 1 ，2 ； ( 4 ) 若任意的i ，其中，是任意的指标集，只x ，则p r e d ( f ) ( 鼽) = np r e d ( f ) ( p t ) ， 即谓词提升保任意交； ( 5 ) 若，：p _ q 是范畴p r e d 中的态射，其中q y , p x ，则有： p r e d ( f ) ( f - 1 ( g ) ) = ( f f ) 以 p r e d ( f ) ( q ) 】 p r e d ( f ) ( f ( p ) ) = ( f f ) 防r e d ( f ) ) 】 1 9 不变量 文献【1 1 】中给出了k r i p k e 多项式函子的不变量的定义： 设( x ，c ) 是f 余代数，即c ：x _ f x ，且p x ，称p 是不变量，若 对于任意的z p ，有c ( x ) p r e d ( f ) ( p ) ，即： 3 w f ( 如( p ) ) ，s t f ( r 1 ) ( w ) = f ( r 2 ) ( w ) = c ( z ) 引理1 2 【1 1 l 设( x ，c ) 是f 余代数，其中f 是集合范畴上的自函子，即 c ：x f x ，且p x 是任意谓词， p 是不变量兮3 w f ( 如0 ) ) ，有：f ( r 1 ) ( 硼) = f ( 您) ( 叫) = c ( z ) 命题1 3 f 1 1 】设p x 是谓词，r x x 是x 上的二元关系，则： ( 1 ) r x y 是互模拟，则m ( r ) ，i = 1 ，2 是不变量； ( 2 ) p x 是不变量，则疋p ) x y 是互模拟； ( 3 ) 对于任意的i j 是不变量，其中，是指标集，则np i 也是不变量； ( 4 ) 若，：x _ y 是f - 余代数同态，且p x ，q y ，p ，q 是不变量，则 ，0 ) ，_ 1 ( g ) 也是不变量 1 0 余代数中的松弛不变量 2 松弛谓词提升和松弛不变量 从本节开始，我们用f 表示带有偏序关系e 的k r i p k e 多项式函子， 且用( x ，c ) ，( y d ) 表示p 余代数 在前一节中我们已经介绍了余代数中不变量的基本定义，下面我们 将带有偏序关系的函子引入到不变量的定义中，引进松弛谓词提升以及 松弛不变量等概念，并比较模拟与松弛不变量的关系 定义2 1 【1 】设五y 是集合范畴上的两个对象，r x y 是一个二元 关系，则r 的松弛关系提升定义如下： r e l e ( f ) ( r ) = ( 让，v ) 1 3 u 7 ，口7 ，ue x 乱7a ( 乱7 ，移7 ) r e l ( f ) ( r ) at ，7e v 钉) ) = e xo r e l ( f ) ( r ) oe v 引理2 2 【1 】对于任意的二元关系r ，我们有： r e i e ( f ) ( r 。p ) = 【r e f 叩( f ) ( r ) 】叩 结合命题1 1 中的( 3 ) ，我们给出谓词提升的一个等价定义： 定义2 3 对任何谓词p x ，f 是集合范畴上的自函子，p 的谓词提升 p r e d ( f ) ( p ) 定义如下： p r e d ( f ) ) = 几【r e f ( f ) ( 瓦p ) ) 】 = 丌i ( ( u ，u ) i3 w f ( r ) ，f ( r 1 ) = f ( r 2 ) = 乱) = 牡i3 w f ( r ) ，f ( r 1 ) ( w ) = f ( r 2 ) ( w ) = u ) 其中r = 如白) 定理2 4 上述定义与上一章中谓词提升的基本定义等价 定义2 5 对于任何谓词p x ，f 是集合范畴上的自函子，p 的松弛( 谓 词) 提升，记为p r e d e ( f ) ) ，定义为： p r e d e ( f ) ( p ) = 乱l3 u 7 w e d ( f ) ) ，ue x 仳7 ) = e xo w e d ( f ) p ) 1 】 余代数中的松弛不变量 其中r = 屯 ) 注：在本文的其他部分，在不致引起混淆的情形下我们将e x 简记为e 引理2 6 对于任意谓词p x ，p 的松弛提升也可以如下定义： p r e d e ( f ) ( p ) = ui3 u 7 = f ( r 1 ) ( w ) = f ( 7 2 ) ( 伽) ，ueu 7 ， 其中w = f ( 以0 ) ) 结合定义2 1 和2 3 ，该引理的证明较为直接，在此省略。 在上一章中我们介绍了关系提升与谓词提升的关系，接下来我们讨 论松弛关系提升与松弛谓词提升的关系 命题2 7 设x 是集合范畴中的任意两个对象，冗是x x 上的二元 关系，则： p r e d e ( f ) ( 7 r l ( r ) ) = 7 r i r e i e ( f ) ( r ) 】 证明：先证明上面等式”c i 成立： 由定义：v u p r e d e ( f ) ( r 1 ( r ) ) ，3 u 7 p r e d ( f ) ( u l ( r ) ) ，s t ueu 7 ；由谓词提升与 关系提升的关系，即：p r e d ( f ) ( u t ( r ) ) = 丌- 【r e z ( f ) ( r ) 】，我们有| u 7 ，s t ( ，口) r e l ( f ) ( r ) ，又显然有钉eu ，( 缸， ) r e l c ( f ) ( r ) 】，故u 7 r 1 r e l e ( f ) ( r ， 则等式”成立 下面证明等式”成立： v ( u ，v ) 【r e l e ( f ) ( r ) 】，3 ( u ，t ，7 ) r e l ( f ) ( r 】，s t t eu 7 ，t ，7e 口，由谓词提升 与关系提升的关系我们可知u p r e d ( f ) ( r - ( r ) ) ，故u p r e d e ( f ) ( 丌l ( r ) ) ， 则等式2 ”成立。 命题2 8 设x 是集合范畴中的任意两个对象，r 是x x 上的二元 关系，则： p r e d e ( f ) ( 7 r 2 ( r ) ) = r 2 r e l e 。p ( f ) ( r ) 】 1 2 余代数中的松弛不变量 证明：由引理2 2 ，以及奴( p ) 的定义我们有： p r e d e ( f ) ( t r 2 ( r ) ) = p r e d e ( f ) ( t r l ( r 0 。p ) ) = n l r e l e ( f ) ( r 。p ) 】 = 7 r 1 r e 延印( f ) ( r ) 】0 p = n 2 r e i e 叩( f ) ( r ) 】 推论2 9 设x 是集合范畴中的对象，p x 是x 上的谓词，则： p r e d e ( f ) ( p ) = l r l n e i e _ ( f ) ( s x ( p ) ) 】 p r e d e , , p ( f ) ( p ) = 7 r 2 n e i e ( f ) ( s x0 ) ) 】 定义2 1 0 设x 是集合范畴中的对象，对任意谓词p x ，称p 是一 个松弛不变量，如果： 比p 兮c ( x ) p r e d e ( f ) 0 ) 定理2 1 1 设x ，y 是集合范畴中的任意两个对象，r 是xxy 上的二 元关系，p ，q 分别是x ，y 上的谓词，且7 1 1 ( r ) = p ，7 r 2 ( r ) = q 则： r 是模拟兮p 是松弛不变量 舻是模拟号q 是松弛不变量 证明：由于上面两等式的证明类似，在此只证明第一个等式： v ( x ，y ) r ，( c ( z ) ，d ( 可) ) r e l e ( f ) ( r ) ，贝i j ：c ( x ) l r l r e l e ( f ) ( r ) 】，由定理 2 7 ，贝0 有c ( x ) p r e d e _ ( f ) ( 丌l ( r ) ) ，即：c ( x ) p r e d c _ ( f ) 0 ) ，即7 1 1 ( r ) 是松 弛不变量，故p 是松弛不变量 推论2 1 2 设x 是集合范畴中的任意两个对象，p 是x 上的谓词， 则： 奴p ) 是模拟锌p 是松弛不变量 1 3 余代数中的松弛不变量 证明：由定理2 1 1 ，则只需要证明： v ( z ，z ) 奴( p ) ，由于p 是松弛不变量，则有c ( x ) p r e d e ( f ) ) ，由推论 2 9 ，( c ( z ) ，c ( z ) ) r e l e ( f ) ( 奴p ) ) = e ，故有奴( p ) 是模拟 引理2 1 3 对任意谓词p x ，称p 是一个松弛不变量，如果： 3 u 7 p r e d ( f ) ( p ) ，s t c ( z ) eu t 且p ： 3 w f ( 屯( p ) ) ，f ( r 1 ) ( w ) = f ( r 2 ) ( w ) 使得： c ( z ) ef ( r 1 ) ( w ) = f ( r 2 ) ( w ) 事实上，很容易验证松弛不变量就是一个f 余代数。和不变量类似， 对于集合范畴上带有偏序关系的自函子f ，松弛不变量有如下性质： 命题2 1 4 ( 1 ) p r e d e ( f ) 是范畴p r e d 上的自函子； ( 2 ) 对于任意的两个集合p ，q ，若p q ，则有p r e d e ( f ) 0 ) gf r e d e ( f ) ( 口) ( 3 ) 松弛不变量关于任意并封闭 ( 4 ) 对范畴p r e d 上的态射，：x _ y ，以及任意两个谓词p y ，q x ， 有： p r e d e ( f ) f _ 1 ) 】( f f ) _ 1 p r e d e ( f ) 0 ) ( 5 ) 对范畴p r e d 上的态射，：x y ，以及任意两个谓词p y ，q x ，有： ( f f ) p r e d e ( f ) ( g ) 】p r e d e ( f ) 【，( q ) 】 证明：( 1 ) 取任意谓词pex ，由松弛谓词提升的定义，p r e d e 作用在p 上显然包含在f x 中，即p r e d e ( f ) ( p ) o b ( p r e d ) ； 再考虑范畴p r e d 上的态射，：p _ s ，断言：取p r e d e ( f ) ( ，) = f y ，则有： p r e d e ( f ) ( ，0 ) ) = p r e d e ( f ) ( ，) op r e d c _ ( f ) p ) - 1 4 余代数中的松弛不变量 而这是因为p r e d e ( f ) 0 ) 的任意元素u 都有： 3 u 7 p r e d ( f ) ) ，s t ue u 用f ，作用可得： ( f f ) ( u ) ( f f ) r e d e ( f ) ) ) ，3 ( f f ) u 7 ( f ，) 眵r e d ( f ) ) 】，( f ，) ( u ) e ( f f ) ( u ) 上式中最后一个偏序关系是由于f ，是单调函数。 由谓词提升的性质( 5 ) 可得： ( f f ) 防r e d ( f ) 渊= p r e d ( f ) f p ) 】 故有 ( f f ) ( u 7 ) p r e d ( f ) f ( p ) 1 - - - 一 m l ( f f ) ( u ) e ( f f ) ( u 7 ) 立即可得： ( f f ) ( u ) p r e d e ( f ) f ( p ) 】p r e d e ( f ) ( s ) 而可以得到结论f r e d e ( f ) 是范畴p r e d 上的自函子 ( 2 ) 取f r e d e ( f ) ( p ) 的任一元素u ，由定义可得：3 u 7 p r e d ( f ) 0 ) ，使得 钍e “7 成立而p q ，由谓词提升的性质有： f r e d ( f ) ( p ) p r e d ( f ) ( q ) 所以u p r e d ( f ) ( q ) ，故由松弛谓词提升的定义得：u p r e d e ( f ) ( g ) 。从 而可以得到f r e d e ( f ) 0 ) p r e d e ( f ) ( q ) 成立 ( 3 ) 设，是任意指标集，p i ，i j 是松弛不变量，下证up i 是松弛不变 量 考虑up i 的任一元素z ，显然存在歹j ，有 i e l c ( z ) p r e d e ( f ) j ) 冬p r e d c _ ( f ) ( u p i ) i g i 】5 余代数中的松弛不变量 最后的包含关系由上述性质( 2 ) 可得。从而有up ；是松弛不变量。 i e i ( 1 ) ( 5 ) 类似于上面的证明，在此省略。 在本节的最后，我们看看松弛不变量的几个例子： 例子1 ：( 1 ) 对集合范畴上的函子s ( x ) = 1 + ( a x ) ，s 的一个余代数c ： x s ( x ) ，谓词p x 是一个松弛不变量当且仅当对任意的z p ，都 有c ( x ) p r e d e ( s ) ) 成立。其中偏序关系e 是例1 中描述的序这意味 着：存在缸p r e d ( s ) ( p ) ，c ( z ) e x 缸如果c ( z ) = 宰，则不能得到任何信息， 但是如果c ( x ) = ( a ，一) ，则有让= ( a ，) = c ( z ) ( 2 ) 考虑函子t ( x ) = x a b ，其中a 是一个集合，b 是一个行为集合， 事实上这个函子描述的就是一个确定性图灵机。集合t ( x ) 带有以下序 e ：对任意的u ，t ，t ( x ) ， ur v v a a ，让( n ) e 钉( n ) 即：若 乱= ， = 则有： 钍e 口咎v a a 如果： x _ ox l ，z ，_ oz 2 那么： z 1ez 2 对t 余代数c ：x _ t ( x ) ，p x 是一个松弛不变量当且仅当z ，e ( x ) p r e d e _ ( t ) ( p ) ，即：假设c ( x ) = ，则存在缸= ， 使得 e ，即：对每一个a a ，如果z _ 口z l ，_ 。 z 2 ，贝i j 有z 1ez 2 1 6 余代数中的松弛不变量 3 。最大松弛不变量 由命题2 1 4 中的( 3 ) 知，余代数x 上任意松弛不变量的并仍然是松 弛不变量特殊地，存在x 上的最大松弛不变量，记为g l i e ( x ) ，在不 会引起混淆的情形下我们用g l i e 简记之 定义3 1 设( x ，c ) 是自函子f - 余代数，定义谓词范畴上的自函子且用 咒表示： ? - i ) = c 一矽e d ( f ) 0 ) ，其中p x 是任意的谓词； 咒( ，) = c 一p r e d e ( f ) ( f ) ，其中，是谓词范畴上的任意态射 定理3 2g l i e 是函子“的最大不动点 证明：首先证明上述函子的所有不动点都是松弛不变量：设p 是上 述函子的任一不动点，则有 p = c p r e d e ( f ) ( p ) 即： c ) = p r e d c _ ( f ) ( p ) 故p 是不变量，显然是松弛不变量 下面证明x 上的g l i e 是上述函子的不动点：由于g l 乇是松弛不变量， 则有 c ( g l i e ) p r e d e ( f ) ( g l i e ) 故只需证明包含关系的另一面： 任取z c - 1 p r e d e ( f ) ( g l i e ) 】，自然地， z z ) ug l i e 由松弛谓词提升的性质有： p r e d e ( f ) ( g l i e ) p r e d e ( f ) f ( z ) ug l i e 】 17 余代数中的松弛不变量 从而有： e ( x ) p r e d e ( f ) x ug l i e 】 故 z ) u g l i e x 是松弛不变量，由g l i e 的最大性，则有：z g l i e 所以 p r e d e ( f ) ( g l i e ) c ( g l i e ) 成立，故g l i e 是最大不动点 推论3 3 终结余代数上的最大松弛不变量是终结w e d e ( f ) 余代数 本文至此，我们都约定只考虑集合范畴上的情形下面我们考虑集合 范畴的一个子范畴一偏序集范畴( p r e o r d ) 上的情形在本章的最后部分 我们约定f 为保偏序关系的自函子 定义3 4 设x 是偏序范畴上的任一对象，p 是x 上的谓词，则有p 的松弛谓词提升的定义如下： p r e d e ( f ) ) = eo w e d ( f ) 0 ) = 乱i3 u w e d ( f ) ) ，ue f xu p 】- 其中第二个等式后的e f x 满足下面条件： 且下面条件也成立： 比，y x ，ze xy 今f xe f xf y v 2 ，y f x ，ze f xy 兮f 一1 ze xf 7 1 y 和前面一样，在不致引起混淆的情况下，我们记e 为e 肷由于下 面的3 4 - 3 7 的证明较为简单，在此省略 引理3 5 设x 是偏序范畴上的任一对象，p 是x 上的谓词，( x ，c ) 是 p 余代数若p 满足下面条件： v z p ，j ，有ze x ，且e ( x 7 ) p r e d ( f ) ( p ) 1 8 余代数中的松弛不变量 则p 为松弛不变量 定理3 6 设x 是偏序范畴上的任一对象，p 是x 上的谓词， p 余代数若p 是不变量，则上p 是松弛不变量 推论3 7 设x 是偏序范畴上的任一对象，p 是x 上的谓词， f - 余代数则g l i e = j ，g l i e 推论3 8 设x 是偏序范畴上的任一对象，p 是x 上的谓词， n 余代数则g l i e 为本章开头的函子咒的最大不动点 ( x ，c ) 是 ( x ，c ) 是 ( x ，c ) 是 1 9 余代数中的松弛不变量 4 双向松弛不变量和不变量 由文献【1 】知道，双向模拟与互模拟的概念并不等价。如下例子所示， 双向松弛不变量与不变量的概念也不等价 例子2 ：考虑例子1 ( 2 ) 中的函子t 以及其上的偏序关系e 对余代数 c ：x _ t ( x ) ， p x 是一个松弛不变量当且仅当z p ，c ( x ) f r e d e ( t ) ) 即：若c ( x ) = ，则存在u = ，使得 e 由e 的定义有： 任意的a a ， 若x 三x l ，z 三z 2 ，贝4 有z lez 2 若取此偏序关系的对偶e 叩，则有： 存在钉= ，使得 e 印 即： 任意的a a ， 若z 三x l , x 3z 3 ，贝i 有z 1e 。pz 3 上例中即使g l i cng l i c _ 叩成立，很容易验证并不是一般的不变量， 所以一般情况下双向松弛不变量并不等价于一般的不变量下面我们证 明在某些条件下双向松弛不变量确实等价于一般的不变量。 定理4 1 设f 是带有偏序关系的函子，c ：x _ f x 是p 余代数，则 如果f 上的偏序关系e 满足以下条件： p r e d e _ ( f ) ( p ) n e d e o p ( f ) ( g ) w e d ( f ) 0ng ) 则有： 2 n 余代数中的松弛不变量 p 是不变量甘c ( p ) w e d ( f ) ) n w e d 叩( f ) ) 证明：左包含兮显然成立 只需证明右包含仁：取p 中的任意元素。，且设c ( x ) p r e d e ( f ) ( p ) n p r e d e 。，( f ) ) ，而由已知条件得： p r e d e ( f ) ( p ) np r e d e o p ( f ) ( p ) p r e d ( f ) ( pnp ) = w e d ( f ) p ) 故有： c ( x ) w e d ( f ) p ) 即p 是不变量 我们有关于最大不变量的下列结论： 推论4 2 设f 是带有偏序关系的函子，c ：x _ f x 是f 一余代数，则 如果f 上的偏序关系e 满足以下条件： p r e d e ( f ) ( p ) np r e d e , , p ( f ) ( q ) w e d ( f ) nq ) 则有： g l i eng l i e 叩是不变量，且是最大不变量 证明：首先证明g l i ena l i c _ 叩是不变量： 对于任意的z g l i eng l i e _ 叩，显然z g l i e ，由于g l i c _ 是松弛不变 量，则由松弛不变量的定义有： c ( x ) p r e d e ( f ) ( g l i e ) 类似的， c ( x ) p r e d e , , p ( f ) ( g l i e 卵) 而由已知： p r e d e ( f ) ( p ) np r e d e 印( f ) ( p ) w e d ( f ) 0np ) 2 】 余代数中的松弛不变量 则可得： p r e d e ( f ) ( g l i e ) np r e d e , , ( f ) ( g l i e 叩) p r e d ( f ) ( g l i eng l i e 叩) 由此可得： c ( x ) p r e d ( f ) ( g l i eng l i e 叩) 根据不变量的定义立即得g l i e ng l i e 叩是不变量 又因为对于任意的不变量p ，显然都是松弛不变量，所以p g l i en g l i e 叩，故g l i en g l i e 印是x 上的最大不变量。 2 2 余代数中的松弛不变量 参考文献 【1 】b j a c o b s ，j h u g h e s ，s i m u l a t i o n si nc o a l g e b r a ，i nh p g u n m ( e d ) ，c o a l g e b r a i cm e t h o d s i nc o m p u t e rs c i e n c e ，e l e c t n o t e si nt h c o r c o m p s c i e l s e v i e r ，a m s t e r d a m ，v 0 1 8 2 ( 1 ) ， 2 0 0 3 ，7 1 1 0 9 【2 】j r u t t e n ，a u t o m a t aa n dc o i n d u c t i o n ：a ne x e r c i s ei nc o a l g e b r a ，i n ：s a n g i o r i g id ，d es i - m o n er ，e d s p r o c e e d i n g so ft h ec o n c u r 9 8 ，l n c s1 4 6 6 ，s p r i n g e r - v e r l a g ，1 9 9 8 ，1 9 4 - 2 1 8 【3 】j w o r r e l l ，o nc o a l g e b r a s a n df i n a l s e m a n t i c s ，p h d t h e s i s ，c o m p u t i n g l a b o r a - t o