（应用数学专业论文）ωcpo上的观察系统及余代数.pdf

摘要 文献 1 】提出了研究观察的一种新观点，从观察结构和观察系统的 角度研究观察主要结果是集合范畴上的每一个非平凡函子都可以自 然的提升到观察结构范畴上，证明了提升得到的函予有唯一不动点， 且这种函子的余代数范畴存在终结余代数文献f 2 将文献【1 】的构造和 相应的概念、结论推广到偏序的情形，给出了有序观察结构和有序蹋 察系统的概念 本文在文献【2 】和翻的基础上，构造了w c p o ：观察结构和观察系 统，定义了n 模拟链，对任意一c p o 观察结构，可以构造一个可离完 备。一c p o 观察系统，并证明了掰一c t o 观察结构及其态射构成的范畴是 笛卡儿闭范畴，把u c 即范畴上非平凡函子f ，提升到一c p o 观察结 构范畴和甜一c p o 可离完备有序观察系统范畴上，分别褥到函子f 纠和 函予f 【】，并证明f h 和f 】存在唯一的不动点 关键词：留一c p o 观察结构，一c p o r 察系统，笛卡，l 闭性，不动点定 理 a b s t r a c t i np a p e r 【1 】，t h ep o i n to fv i e wo fo b s e r v a t i o ns t r u c t u r e sa n do b s e r v a - t i o n ss y s t e m sw a si n v e s t i g a t e d t h em a i nr e s u l ti st h a te v e r yn o n t r i v i a l f u n c t o ro nt h ec a t e g o r yo fs e t sg i v er i s ei nac a n o n i c a lw a yt oaf u n c t o r o nt h ec a t e g o r yo fo b s e r v a t i o ns t r u c t u r e sh a v i n gau n i q u ef i x e dp o i n t i tw a sa l s os h o w nt h a tt h er e s u l t i n gc a t e g o r yo fc o a l g e b r a sh a daf i n a l c o a l g e b r a t h en o t i o n so fo r d e r e do b s e r v a t i o ns t r u c t u r e sa n do r d e r e d o b s e r v a t i o ns y s t e m sw e r ei n t r o d u c e di np a p e r 【2 】 i nt h i sp a p e r ，w ed ot h ef u r t h e rs t u d yb a s e do nt h en o t i o n so f 【2 la n d 3 w ec o n s t r u c tu c p oo b s e r v a t i o ns t r u c t u r ea n do b s e r v a t i o n s y s t e m ，a ts a m et i m ew ed e f i n et h en o t i o no fn - s i m u l a t i o nl i n e s w e a l s oc o n s t r u c tas e p a r a t e dc o m p l e t i o no fu c p oo b s e r v a t i o ns y s t e m f r o ma0 3 c p oo b s e r v a t i o ns t r u c t u r e w es h o wt h a tt h ec a t e g o r yo f u c p oo b s e r v a t i o ns t r u c t u r e si sc a r t e s i a nc l o s u r ec a t e g o r y w ee x t e n d t h en o n t r i v i a lf u n c t o rfo nt h eu c p oc a t e g o r yt oaf u n t o rf 【】o nt h e c a t e g o r yo fu c p oo b s e r v a t i o ns t r u c t u r ea n dt oaf u n t o rf 【】o nt h e c a t e g o r yo fu 一印ds e p a r a t e da n dc o m p l e t eo r d e r e do b s e r v a t i o ns y s t e m w ep r o v et h ee x i s t e n c eo fu n i q u e n e s so ff i x e dp o i n to ft h i st w of u n t o r s k e y w o r d s ：o r d e r e do b s e r v a t i o ns t r u c t u r e s ，u 一印do b s e r v a t i o ns t r u c t u r e s ，c a r t e s i a nc l o s u r e ，f i x e dp o i n tt h e o r e m 首都师范大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果除文中已经注明引用的内容外，本论文不 含任何其他个人或集体已经发表或撰写过的作品成果对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全意 识到本声明的法律结果由本人承担 学位论文作者签名：玄毋翌炙一 日期：a 弼年厂月ze t 首都师范大学位论文授权使用声明 本人完全了解首都师范大学有关保留，使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆被查阅有权将学位论文的内容编入有关数据库进行检 索有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后 适用本规定 学位论文作者签名：彳争碜刃己 日期滞和朋 1引言 余代数在上世纪后半期才被越来越多的计算机学者所关注，它是 从 观察 的角度考察系统及其性质，因而余代数方法对研究基于状态 的系统，翔自动桃，进程，对象等有独特豹优越性。余代数理论已经逐步应 用在自动机理论，并发程序的语义，面向对象程序的规范等领域，成为理 论计算视科学一个特剐重要的研究方离。 余代数方法的主要工具是终结余代数的存在性如果( s ，a s ) 是终结 的b 余代数，则s 麓f ( s ) 如果s 笺f f s ) ，则称s 是f 赡一个不动点有些 函子存在不动点，例如多项式函予有些函子则不存在不动点，例如集合 的幂集蘧子。所以不动点的存在性对研究终结余代数的存在性有很重要 的作用 文献 l 】提出了一种研究观察的耨观点，从观察绻梅和观察系统的焦 度研究观察主要研究函予的不动点和终结余代数的存在性，得到集合 范畴的每一个非平凡函子都可以自然地提升到观察结构的范畴，并证明 得到的函予有唯一的不动点 文献【2 】将文献【1 】的构造和相应的概念，结论推广到偏序的情形，定 义了有序观察结梅和有序观察系统及其态射，并讨论了有序观察系统之 问的逼近映射，证明完备且可离的有序观察系统上的任何逼近的自映射 都有唯一酶不动点。 本文所做的主要工作是在文献【2 】和f 3 】的基础上，把文献【1 】的主要结 论在泌一c p o 观察结构范畴帮嵇一c p o 观察系统的范畴卤进行讨论，定义 了礼一模拟链的概念，得到u c p o 范畴上的每一个非平凡函子都可以自 然的提升到泌一e v o ) 观察结构范畴上，并讨论了一e p o 观察结构范畴的 笛卡j 乙闭性，证明提升得到的函子有唯一的不动点丽勘一e p o 范畴上 的每一个非平凡函子也可以提升到u c p o 观察系统范畴上，证明提升 得到翡函子也有唯一的不动点。 2基本概念和基本知识 2 1范畴 现代数学许多领域的研究都可以概括为对特定的数学对象之间的 映射的研究例如集合及集合之间的映射是集合论研究的主要对象，拓 扑空间及拓扑空间之间的映射构成了拓扑学的主要研究对象，而范畴的 概念正是这些特定的数学对象和映射的概括和抽象 范畴c 由一个对象类o h ( c ) 和一个态射类m a r ( c ) 构成，其中d 6 ( c ) 中 的元素称为c 中的对象，通常用a ，b 表示对于c 中的对象的每个有序 偶( a ，b ) ，对应有唯一的集合h o m c ( a ，b ) m o t ( c ) ，类m a r ( c ) 就是 所有这样的集合h o m c ( a ，b ) 的并m o r ( c ) 中的元素统称为c 中的态 射而对于a ，b o h ( c ) ，h o m c ( a ，b ) 中的元素称为c 中以a 为论域，以 b 为余论域的态射若，h o m c ( a ，b ) ，则记为，：a _ b 或a 与b 对于c 中的三元组( a ，b ，c ) ，对应有一个成为合成的映射 h o m c ( a ，b ) h o m c ( b ，c ) 一h o m c ( a ，c ) ( 厂，夕) h90 ， ( go ，称为，和9 的合成或复合) 要求c 中的态射的合成满足下列公理： ( 1 ) 若( a ，b ) ( c ，d ) ，, 贝t j h o m c ( a ，b ) nh o m c ( c ，d ) = d ( 2 ) 若，h o m c ( a ，口) ，夕h o m c ( b ，c ) ，h h o m c ( c ，d ) ，贝i j ( hog ) o 厂= ho o ，) ( 3 ) v a o h ( c ) ，3 i d a h o m c ( a ，a ) ，使得v ，h o m c ( a ，b ) ，g h o m c ( c ，a ) ，有 0i d a = ，i d a 0g = g i d a 称为a 上的恒等态射 下面是本文用到的几种常用范畴的定义和记号： 9 s e t 表示集合和映射的范畴臣p o b ( s e t ) 是全体集合构成的类，由非空 集合及映射构成的范畴记为s e t + c p 表示u c p o s g 连续映射的范畴，即d 6 ( c p ) 是全体u c p o 构 成的集合 2 1 1函子和不动点 定义1 设c 和d 都是范畴，从c 到d 的共变函子( 反变函子) f ：c d 是指一对函数，一个是对象函数，即将c 中的任意对象a 映为d 中的对 象f ( a ) ；另一个态射函数，即将c 中的态射f ：a _ b 对应于d 中的态 射f ( a ) 一f ( b ) ( 或f ( f ) ：f ( b ) _ f ( a ) ) ，使得 ( 1 ) v a o h ( c ) ，f ( i d a ) = i d f ( a ) ； ( 2 ) v f h o m ( a ，b ) ，夕h o m ( b ，c ) ，f ( g o ，) = f ( g ) o f ( ，) ( 或f ( g o ，) = f ( f ) 0f ( 夕) ) 定义2设c 和d 都是范畴，对于函子f ：c _ d ，若存在s c ，使 得f ( s ) 型s ，则称s 是函子f 的不动点 2 1 2 笛卡儿闭范畴 定义1 范畴c n 做笛卡儿封闭的范畴，如果它满足f 列条件： ( 1 ) 存在一个终对象1 ( 2 ) c 的每两个对象4 和b 有一个积a b 及射影p l ：a x b _ a 署n p 2 ： a b _ b ( 3 ) 对c 的每两个对象a 和b ，存在一个对象陋一矧和一个射e v a l ： 陋一b 】a _ b 及性质：对任何对象c 和任何射，：c a _ b ，存 在唯一的射入，：c _ 阻_ 剀使得合成 c aa 婴a 【a _ b a 掣b 是f 3 若范畴c 有终对象，有限乘积和任意指数对象，则称范畴c 是一个笛 卡儿闭范畴 定理2 【9 】以所有的u 一印。为对象，以保持定向上确界的映 射( s c o t t 连续映射) 为态射形成的范畴c p 是笛卡儿闭范畴 2 1 3范畴的等价 定义设f ：c d 是函子，若存在函子g ：d c 使得g f 竺 i d c 与f g 笺i d d ，则称f ：c _ d 为范畴等价，并称范畴c 和d 是等价的 若范畴c 和d 印是等价的，则称范畴c 和d 是对偶等价的，或简称为对 偶的 范畴之间的等价是自反的，对称的和传递的 定理设f ：c i c 0 是函子，则下列条件等价： ( 1 ) 函子f 是范畴等价的； ( 2 ) 存在一个从c 到d 的伴随( 只g ，叩，) ，使得其单位和余单位都是自然 同构； ( 3 ) 函子f 是完全的和忠实的，并且v b o b ( d ) ，存在a o b ( c ) ，使 得f ( a ) 竺b 2 2 偏序集，拟序集与u c p o 定义2 2 ，l 设s 是集合p 上的一个二元关系，且满足条件：v x ，y ，z p ( 1 ) z z ( 自反性) ， ( 2 ) z y ，y z 兮z z ( 传递性) ， ( 3 ) z y ，y z 兮z = y( 反对称性) ， 则称( p ，) ( 或p ) 是偏序集去掉条件( 3 ) ，称( 只) 是拟序集 4 设( 尸 ) 是一个拟序集，ac p 记 ta = ( 秒p i 孔a ，z 可) 称为p 的子集a 的上集，如果ta 垦a ，即 x a ，y p ，z y 令y a 当( 只) 是偏序集时，这个条件等价于a = ta 下集的情形是对偶 的 设a p z p 若 y a 兮y z ( z y ) 则x 称为a m _ i ：界( 下界) 若tx np = 和) ( izn p - - - - z ) ，即 3 y p z y ( 耖z ) 专y = z 则z 称为p 的一个极小元( 极大元) 若v y p y z ( z 秒) ，则z 称为p 的最大元( 最小元) 一个偏序集 的最小元也称为底，记为上具有最小元的偏序集称为有底的，本文中讨 论的偏序集都是有底的 定义2 2 2 设( 尸e ) 是一个偏序集，aep 且满足条件： v x ，y a ，3 z a 专zez ，ye z 则称a 是p 的一个定向子集 定义2 2 3 设( p e ，上) 是一个偏序集，若u 一链 z 1ez 2e ez ne 3 x p 且z - - - - u x n n n ，则称p 是叫一c p o 定义2 2 4设x ，y 是偏序集，：x _ y 是一个映射，若对于x 中 的任何两个元素z ，y 只要z 掣，就有，( z ) ，( 可) ，则称，是单调函数 定义2 。2 5设x ，y 是定向完备偏序集，是x 至：i j y 的映射，若，是单 调函数且对于x 中的任意定向集都有f ( v a ) = v ，( ) ，则称厂是s c o t t 连续函数 5 2 3观察结构和观察系统 集族0 = ( 0 n ，) 住o 为一个观察结构，仉为死步观察的集合，u n ： o n + 1 _ 0 n 是满射，满射是指如果在第几步能观察到在第几+ 1 步也一定 能观察得到，一般称为从d n + a 至l l o n 的加细 观察结构d 是平凡的，如果d 1 是空集；否则d 是非平凡的 若0 和0 是观察结构，从d 到d 的态射是映射族，= ( 厶：o n d 二) n 2 0 ，如果满足：对任意的n o ，都有 厶。= 以。厶+ l 观察结构及其态射所构成的范畴记为o b s t r ，易证0 6 s 打是笛卡儿闭 范畴非平凡的观察结构及其态射构成的范畴记为o b s t r 观察结构d 上的观察系统是一个二元对( s ，仃) ，其中s 是任意集 合，盯是满映射族g r = ( o - n ) n o ，且满足对任意的n o ，都有 = w n oo n + 1 设( s ，伊) 是o _ k 观察系统，s ，t s n n ，若a n ( s ) = ( 亡) ，则称s 和 是犯一模拟，并记为s 三募t 设( s 口) ，( ，盯) 分别是0 ，0 上的观察系统，：s _ 是一个映 射，称，是从( s ，盯) 到( ，仃7 ) 的态射，如果，保7 1 l 一模拟，即v s ，t s ，佗n ， s 兰嚣t 净，( s ) 三g 巾) 观察系统及其态射所构成的范畴记为o b s y s 设d = ( 0 n ) n o 是观察结构，o n ) n o 称为0 的可观察序列，若满足对 任意n ，0 n 0 n ，都有 ( o n + 1 ) = o n 若( s 盯) 是观察结构0 上的观察系统，s s ，称( n ( s ) ) n o 的完全观 6 2 4观察系统的可离性和完备性 设( s ，盯) 是观察结构d 上的观察系统，( 只盯) 是可离的，指的是对系 统中的任意元素，都可以通过某个观察把他们分开，即对任意8 ，t s ，若8 亡，则一定存在一个礼o ，使得口n ( s ) ( 亡) ( s ，盯) 是完备的，指 的是d 的任意观察序列都是s 中某个元素的完全观察 可离完备的观察系统及其态射构成的范畴记为c s o b s y s 定义2 4 1 设0 ，0 是观察结构，：0 _ 0 是态射，如果对任 意0 ，0 1 d 外l ，若( d ) = ( ) ，则厶+ 1 ( d ) = 厶+ 1 ( d ，) ，称，是逼近态射 定理2 4 2 设0 是非平凡的观察结构，从o n o 的逼近态射s ：0 _ d ，有唯一的不动点，即：存在唯一的观察序列( o n ) n o ，使得 v n 0 ，厶( o n ) = o n 2 5 代数和余代数 设f ：c _ c 是范畴c 上的函子，一个f 一代数是一个二元对( sa s ) ， 其中s c ，a s ：f ( s ) _ s 是态射从f 一代数( sa s ) 至t j ( t ，a t ) 的态射是 一个函数s ：s t ，满足i o a s = o t t o f f 余代数与之对偶，一个f 一余代 数是一个二元对( sq s ) ，其中s c ，a s ：s _ f ( s ) 是态射从f 一余代 数( s ，q s ) 到( zq ? ) 的态射是一个函数，：s t ，满足口? o ，= f f oq s 设( t ，q t ) 是一个f 一代数，若对任意f 代数( s 口s ) ，都存在唯一的 从( t ，q t ) 到( sa s ) 的f 一代数同态，则称( 丁，q t ) 是初始f 一代数对偶可 得，若对任意f 一余代数( t ，0 f t ) ，都存在唯一的从( t ，0 t ) 到( s ，a s ) 的f 一 余代数同态，则称f 一余代数( sq s ) 是终结的， 7 3 u c p o 观察结构和观察系统 以下用表示非负整数的集合，死0 表示一个非负整数 定义3 1 设d = ( d n ，e n ) n 2 0 是一个u c p o 的族，r v n n ，w n ： d 佗+ l 一仇是满映射，则称族d = ( ( 巩，e 扎) ，) n o 是一个u c p o 观察 结构 若d = ( ( d n ，e n ) ，) 几o ，d 7 = ( ( d ：l ，e 二) ，以) n o 是u 一叩d 观察 结构，从d 至i d 的态射是单连续映射族f = ( 厶：队一f i n ) n o ，使 得v n n ， 厶。u n = u 二。厶+ 1 u c p o 观察结构及其态射构成的范畴记为c p o t r 定义3 2 设d = ( d n ，e n ) 礼o 是u c 妒观察结构，d _ k 的w c p o 观 察系统是一个对( s ，盯) ，其中s 是一个任意非空集合，仃= ( 0 n ：s _ d 礼) n o 是满映射族，使得对任意佗n ，有 o n = 0 2 n 0f f n + l 定义3 3 设( s 盯) 是d 上的u c p o 观察系统，8 ，t s ，佗n ，若盯n ( s ) e 礼( 芒) ，则称t 和s 是一个n 一模拟，记为8e 募t 定义3 4 设( s ，仃) 是d 上的有序观察系统， 口m ) m n s ，若o n ( a 1 ) e 口n ( 口2 ) e 仃n ( a 3 ) eo n ( a m ) e ，且( 口) = v 黠1 ( 口m ) ，其 c a s ，称为链 f ( a ) = v ( 9 ，a ) f ( a m ) u 一印。观察系统及其态射所构成的范畴记为c p o y s 定义3 5设( s 盯) ，( 7 - ) 是d 上u 一伽观察系统，如果存在态射，： s t ，g ：t _ s ，满足 f 0 g = i d t g0f = i d s 则称( s ，盯) 和( 正7 - ) 观察结构 9 4 u c p o 观察结构范畴的笛卡儿闭性 定理4 1 c p o t r 是笛卡儿闭范畴 证明分两步： ( 一)考虑以所有的u 一印为对象，以保持定向上确界的映 射( s c o t t 连续) 为态射形成的范畴c 帕，由预备知识可知，范畴c p 0 是笛卡儿闭范畴【9 】 ( 二)由上述已知结果，我们考虑范畴c ? o t r ( 1 ) c p 打范畴存在终对象：d 上= ( 上n ，e n ) n o ( 2 ) 存在范畴积d e ，f l o d e = d n 磊i c _ d ，e 晶) n o d n e k = ( z ，y ) iz d n ，y e k ) 其中d n 玩上的偏序关系按已知所述 其中 呱：风+ 1 _ 队 呶：岛+ 1 一既 f 0 n = u 巩w e ：d ，l + 1 点+ 1 _ d n 点k 为满映射 有投影映射 队卫d n 晶骂既 z n 卜( z t l ，鲰) 一 也即 d 卫d e 马e ( 3 ) 设d = ( ( 巩，e n ) ，) 凡之o ，e = ( ( 磊，e ：1 ) ，以) n 之。是u 一印d 观察结 构 令e d = 【d _ 司= ，= ( 厶：玩_ 晶) ) 其中 ：d n _ 磊是连续的 1 0 并且厶：d n _ 既由上述的结果按逐点序形成一个u c p o 其中 e v a l ：【d _ 明d e 即 【d n _ 岛】xd n 一磊 即存在幂对象 所以d c i p t r 范畴是笛卡儿闭范畴 口 5 u c p o 观察系统的可离性和完备性 我们感兴趣的是可离完备的观察系统，所谓可离指的是我们可以通 过某个观察把系统中任意两个不同的元素区分开；所谓完备是指任意的 观察序列实际上都是系统中某个元素的完全观察 定义5 1 设d = ( ( d n ，e n ) ，) n o 是u c p o 观察结构，( d n ) n o 称 为d 的一个有序观察序列，如果v n n ，厶d n ，如= ( 厶+ 1 ) 定理5 2 设( s ，仃) 是一c p o 观察结构d _ h 的w c p o 观察系统，则v s s ( ( s ) ) 几 o 都是d 的观察序列，称为s 的完全观察 定义5 3 设( s 盯) 是u c p o 观察结构d 上的u e p o 观察系统 ( 1 ) ( s 盯) 称为可离的，如果v s ，t s ，若8 t , 贝1 s n n ，使得a n ( s ) 仃几( t ) ( 2 ) ( s ，口) 称为完备的，如果对d 中任意观察序列d = ( 而) n o ，都存在8 s ，使得v n n ，仃n8 ) = d n 可离完备u 一印。观察系统和其态射构成的范畴记为c s c p o 抄 并不是所有的u e p o 观察系统都是可离完备的，下面我们介绍u e p o 观察系统的可离完备化 定义5 4设( s 仃) 是d 上的任意一个有序观察系统，若8 ，t s ，对v n n ，都有( s ) = ( 亡) ，即s 和t 有相同的观察，称s 和亡满足关 系三，记为s 三t 容易证明 _ 是s _ h 的一个等价关系，酬三是可离观察系统 对任意u c p o 观察结构d = ( ( d n ，e n ) ，) n o ，可以构造一个可离 完备u c p o 观察系统如下： 用d o o 表示d 中的所有有序观察序列的集合，对任意见，定义0 o o n ： d _ 巩为盯n ( ( d n ) n o ) = d n ，其中( d r i ) n o d 由：s _ d n 是满射，故对任意d n d n ，都存在元素8 ，使得( s ) = d n ，从而使 得盯o o n ( ( ( s ) ) n o ) = d n ，即盯o o n 是满射，对d 中的任意元素( 如) ，；o ，有 0 o o 礼( ( 如) n 0 1 = 厶 1 2 = ( 厶+ 1 ) = 0 3 no 盯。o 几+ 1 ( ( d n ) n o ) 即仃o 。n = u n oo o o n + l ，所以( d o o ，口o o ) 是一个u c p o 的观察系统 下面验证( d ，) 是可离完备的，设刁= ( d n ) n o ，d t = ( ) n 2 0 是d 中的任意元素，且d d ，则存在礼，使得d n 畋，即 o o o n ( ( 如) n 之o ) 仃。n ( ( 以) 佗2 0 ) 故( d o o ，仃o 。) 是可离的 下面证明完备性：从定义可以知0 o o n ( ( 如) 竹o ) = d n ，其中( 厶) n o d o o ， 既n ( ( 盯他( s ) ) n o ) = 磊，所以完备性得证 定义5 5 设( s ，盯) ，( t ，丁) 分别是d ，d 7 上的观察系统，若存在单态 射，：s t ，称( s ，盯) 是( t ，r ) 的子观察系统 定理5 6 设( s ，口) 是d - - 的有序观察系统，则( d ，盯) 是包含( s ，盯) 的最小可离完备有序观察系统即：对包含( s ，盯) 的任意可离完备有序 观察系统( l7 - ) ，必存在单同态歹：( d 。o ，) 一( t ，丁) ，使得下图交换( 图 中 ，f 2 是单同态) 称( d ，) 是( s ，盯) 的可离完备化 ( p o o ，伊) 下面给出u c p o 观察结构d n d 7 的态射和u c p o 观察系统( d o 。，仃o o ) 到( d 笔，盯笔) 的态射之问的联系 定理5 7 若( 厶) n _ o 是d n d 7 的态射，其中( 厶) n o 是连续的，则( 厶) n 芝。 可以扩张为d o o 到d 乞的一个态射，使得下图交换，即满足，厶。 盯o o n = o o o i 礼。丘 1 3 d 抛d ， c仃oon，ncf c 盯笔n ，凡。 d 1 1 笔 证明： 定义厶：d 一d 笔如下：对v d = ( 如) n o d ，厶( d ) = ( 厶( 南) ) n o ，由于( 厶) n 2 0 ，是d 到d 7 的态射，所以u 乞。厶+ 1 = 厶ou n ，因而 u 二( 厶+ 1 ( 如+ 1 ) ) = 厶( ( 如+ 1 ) ) “( f n + l ( d n + 1 ) ) = ( u n ( 如+ 1 ) ) = 厶( 磊) 所以( 厶( 如) ) n o 是有序观察序列，即( 厶( 如) ) n o 是d 笔中的元素，因此厶 验证厶保扎一模拟链的并，以下m n ， 若( d 毳) n oe d o o ( ) n oe 2 ( d 孑) n 2 0e 且( 如) n o = v ( d ，仃。) ( d 三) n o ，( 以) n 之o ( 甥) n o ) 则盯住( 如) n o = v a n ( ( 如) 几2 0 ) ，g o o n ( ( 镌) n o ) g o c n ( ( 嘞) n o ) ) 即如兹e 研e 且如= v 畦，兹奶) 又因为v n n ，厶连续，所以保链的并，即 f n ( d n ) = v 厶( 如) ，厶( d 凳) 厶( 研) ) 因为从定义可知v d = ( d n ) n o ，厶( d ) = ( 厶( 如) ) 几o ， 仃笔n 。f ( d n ) = 口乞n of n ( d n ) = 厶( d n ) f c c ( ( d n ) 礼o ) = v f o 。( ( d i n ) n o ) ，厶( ( d 毳) n o ) 氏( ( 四) n o ) ) 即厶保佗一模拟链的并 综上，氏是d o 。到d 笔的态射下面验证图形交换： v d = ( d n ) n o d 。 因为 盯乞no 知( 奶) = 吒竹。厶( 厶) = 厶( 厶) ( 厶) o0 0 0 n ( 如) = 厶( 如) 所以图形满足交换 定理5 8 设d ，d 7 是任意的u c p o 观察结构，厶是d o o 到d 笔的态 射，厶是保n 一模拟链的并，则厶诱导一个从d 到d 7 的态射( 厶) n o ，使得 下图交换，即满足 v 扎，厶oo o o = 盯乞no 丘 d 卫也迎d ， ff ( 盯n ) n 之dl ( 盯笔n ) n o ii d i 正仞笔 证明：首先定义厶：队_ d 乞 取任意d d n ，为了定义厶( d ) ，我们先任意选择一个满足第几个元 素是d 的一个有序观察序列a = ( 如) n o ，把厶( d ) 定义为厶( 西第几个元 素 其次验证厶的定义与衲选择无关 假设矛也是第n 个元素是d 的观察序列，则有孑e n 矛，孑e 几五由厶的 定义，则厶( d ) 也等于厶( 孑) 的第佗个元素，由于氏保死一模拟链的并，所 以厶( 西e n ( 矛) ，k ( 矛) e n 厶( 西，则氏( 西的第死个元素与厶( 矛) 的 第n 个元素相等，故厶的定义不依赖锄选择 最后验证上述定义的厶) 扎 o 是d 到d 7 的态射，即满足条件 “o 厶+ 1 = 厶o 1 5 由定义可以知道厶( ( 南) n 之o ) = ( i n ( 如) ) n 2 0 叱，则 以( 厶+ l ( d n + 1 ) ) = 厶( 如) 由t - - w n ( d 几十1 ) = d n ，两边同时作用厶作用，得到 厶( u n ( d n + 1 ) ) = 厶( 如) 故 皈( 厶+ 1 ( 如+ 1 ) ) = 厶( ( 如+ 1 ) ) 即 以。厶+ 1 = 厶o 这就证明了( 厶) 礼o 是d 至3 j d 7 的态射，容易验证( 厶) n o 使得图形交换口 1 6 6逼近函子的不动点定理 定理6 1设d = ( d ，e ，上) 是一个u c p o ，f ：d d 是u 一连续 的，那么。厂有一个最小不动点( 参看文献【1 3 】) 下面我们讨论不动点定理在本文构造的范畴内的推广 由非空0 3 一c p o 及连续映射构成的范畴为c p o * , 易知c p 0 + 有终对 象，即 o 如下： v n ，d 主= f n 上，u n f = f 他! 其中! ：f 上_ 上是唯一映射，因为! 是满的，所以f n ! 也是满的，故d f 是非 平凡的u c p o 观察结构 17 定理6 2 设f ：c p o 木_ c p o 年是函子，f 】：c p o t r _ c p o t r + 是f 提 升的函子，贝w i d v 是f 】的一个不动点，且在同构意义下是唯一的，即 若d c p o t r * , 满足f d 竺d ，则d 笺d f 证明：因为 f d f 】= f ( d f ，u ) 】 = ( f d f ，f 瞄】) 又因为 d = f n 上，f = f n ! 代入上式有 f i d f 】= ( f ( f n 上) ，f ( f 疗! ) ) = ( f 他+ l 上，p + 11 ) ：d f 所以d f 是f 【】的一个不动点 口 对任意函子f ：c p o + 一c p o * , 还可以定义c s c p o y s 车上由f 提升 的函子 f 】：c s c i m y s 一c s c i p o y s 对任意d = ( ( d 凡，e n ) ，) 礼o 上的可离完备有序观察系统( s ，盯) ，定义 f 【( s 盯) 】= ( f d 】o o ，f 【盯】o o ) 其中f 川o 。n + l = f n ( ：d _ d ) ，容易证明f 【( s 仃) 】是可离完备 有序观察系统设( s ，盯) ，( s 7 ，) 分别是d ，d 7 上的可离完备有序观察系 统，：( s ，伊) _ ( s 7 ，盯7 ) 是态射，由定理5 7 ，存在从d o o 至i j d l 的态射厶，其 中保7 1 l 一模拟链的并再有定理5 8 ，厶可以诱导出一个从d 到d 7 的态 射( 厶) n o ，所以( f 【门n ) n o = ( f a + i ) n o 是f 【d 】到f d ，】 的态射，同时( f 卅n ) n o 可以诱导出从f d 】o o 至a j f d 7 的态射f 【门o 。令 e l f 】= f 【月o o ，贝j j f 】的定义合理 定理6 3 设f ：c p o _ c p o 木是函子，户【】：c s c p o y s 木_ c s c p o y s 枣是由f 提升的函子，则d 蒉是f 【 的不动点，且在同构意义下 1 8 是唯一的，即：若d 上可离完备有序观察系统( s 仃) ，满足户【( s ，仃) 】兰 ( s ，盯) ，则s 笺d 量 证明：由上文可以知道d 是可离完备有序观察系统，再由定理6 1 ， f m f 】= d f 则d 量和f p f 】o o 是相同的可离完备有序观察系统， 因为 户【d 翻= r i d f 】 所以 户【d 三】= d 量 即d 量是函子户 】的不动点 口 1 9 r 电f e r e n c e s 【1 】l m o n t e i r o ，o b s e r v a t i o ns y s t e m ，e l e c t r o n i c n o t e si nt h e o r e t i c a l c o m p u t e rs c i e n c e ，3 3 ( 2 0