（基础数学专业论文）基于r偏序集的语义域研究初探.pdf

摘要 本文研究对象是带有偏序逼近族的偏序集( 参见文献 1 】) ( 简称 豫偏序集) 我们的目的在于探索兄偏序集这一数学结构能否为语义 域的研究提供一个较好的数学框架本文在欠偏序集上定义了s c o t t 拓 扑，这为在穴偏序集上的逼近、函数的连续性等概念的提出奠定了基 础，为探索冗偏序集作为语义域的数学特性提供了前提文献【2 在带 有等价关系的集合( 简称s f e ) 上重建了基于度量空间的语义域研究的 部分理论髂偏序集是较 序更具普适性的结构本文仿照【2 】中鼍屉上 的结论及a c p o 上t a r s k i 不动点定理的证明，在穴偏序集上建立了逼 近映射的不动点定理和t a r s k i 不动点定理：同时构造了一个新的范畴 灾p o s e t , 建立了范畴灾p o s e 百与范畴g u m s 之间的一个伴随，为从 广义超度量空间角度研究足偏序集提供了思路 关键词傅偏序集，s c o t t 拓扑，不动点，灾一p 0 $ e t a b s t r a c t i nt h ep a p e r , o u rr e s e a r c ho b j e c ta r ep o s e t sw i t hf a m i l i e so f a p p r o x i m a t i n gp a r t i a lo r d e r s ( s e e ni n 1 】) ( c a l l e dr - p o s e o w ed e v o t et o e x p l o r e i ft h em a t h e m a t i c a ls t r u c t u r e r - p o s e t c a nb eab e t t e r m a t h e m a t i c a lf r a m e w o r kf o rr e s e a r c hi ns e m a n t i cd o m a i n s w ed e f i n et h e s c o t tt o p o l o g yo nr - p o s e t ，w h i c hi st h ef o u n d a t i o no fe s t a b l i s h i n gt h e n o t i o n so fa p p r o x i m a t i o na n dc o n t i n u i t yo ff u n c t i o n s ，a n dm a k e s p r e p a r a t i o n sf o re x p l o r i n gt h em a t h e m a t i c a lc h a r a c t e r so nr - p o s e t t h e t h e o r yo fs e m a n t i cd o m a i n sb a s e do nm e t r i cs p a c e sh a sb e e nd e v e l o p e da l o t 【2 】r e c r e a t e sp a r t o ft h et h e o r yo ns e t sw i t hf a m i l i e so f e q u i v a l e n c e s ( f i e ) r - p o s e ta r em o r eg e n e r a l i z e ds t r u c t u r e st h a n 咖w e i m i t a t ep a r to ft h er e s u l t so b t a i n e do n 咖i n 【2 a n dt h ep r o o fo ft a r s k i f i x e d - p o i n tt h e o r e mf o rd c p o w er e c r e a t eaf i x e d p o i n tt h e o r e mf o r a p p r o x i m a t i n gm a p so nr - p o s e ta n d t a r s k i f i x e d - p o i n tt h e o r e m o n 灾- p o s e t a n dw ec o n s t r u c tan e wc a t e g o r y 灾- p o s e t , b u i l d a na d j u n c t i o n b e t w e e n 灾一p o s e ta n dg u m s ，w h i c hs u p p l i e sat r a i no ft h o u g h t sf o r r e s e a r c h i n gt h e 灾一p o n f t f r o mt h es t a n d p o i n to fm e t r i cs p a c e k e yw o r d s r - p o s e & s c o t tt o p o l o g y ，f i x e d - p o i n t ，穴- p o s e t i i 引言 在程序设计语言的指称语义中，程序的意义被取成某个论域中的元素，这 里我们称这个论域为语义域一个语义域是一个数学结构，这个数学结构是由一 个集合和这一集合上元素间的序关系组成的俗称的d o m a i n 理论就是对那些数 学结构的研究不同的语义域对应程序所处理对象的不同类型 在传统的数学框架下，语义域的研究通常是以偏序集和度量空间为数学框 架的，偏序集的结构简单，难以比较复杂信息，而度量空间的结构又稍显复杂，我们 试图寻找一种既能比较复杂信息又较简化的数学结构这里我们的主要目的在于 探索灾偏序集这一数学结构能否为语义域的研究提供一个较好的数学框架，本文 对此进行了初步尝试 求解语义域方程是d o m a i n 理论的一个基本问题而要求解语义域方程，我们 迫切希望某类函数是连续的，使语义域方程有解，这就需要寻求该语义域上的拓 扑，在这种拓扑之下使这类函数连续本文仿照偏序集上及d c p o 上拓扑的定义， 在髂偏序集上定义了s c o t t 拓扑，这为获得连续、逼近等概念，以及探求熙偏序 集作为语义域的应用价值打下基础 文献 2 】中提出了詹这种较度量空间简化的数学结构，且在号角上重建了度量 空问已有的部分理论这为我们对欠偏序集进行研究提供了又一思路 踞的等价关系族( = 。) 。卸族，；。l ；。，体现了逐级分类且分类条件逐级加 强的思想；而船偏序集的偏序逼近族( 。k o ，。g e m ( n 加) 则体现了逐级比较且比 较条件逐级加强的思想，二者有密切关系给定乌，我们可以得到；。= 乌n 孑因此， 我们说岛较毛更具普适性，瘁偏序集是 屉的更一般情形，对船偏序集的研究也更 具普遍意义 本文将【2 】中s f e 上的结果进行了推广文章给出了船偏序集与广义超度量空 问之问伴随，给出并证明了足偏序集上的不动点定理定义了以瘁偏序集为对 象、船单调映射为态射的冗帕s e t 范畴，并给出灾沪o s e t 范畴与以广义超度量空 间为对象、非扩展映射为态射的范畴g 匪j m s 之问的伴随本文推广了 詹上逼近函 数的概念，在炙偏序集上定义了逼近映射；仿照d c p o 上t a r s k i 不动点定理及证 明，得到了佑偏序集上逼近映射的不动点定理和纯偏序集上的t a r s k i 不动点定理 2 第一章预备知识 d o m a i n 理论( 即论域理论) 作为一个数学分支，最初是由d a n as c o t t 于1 9 7 0 年作为程序设计语言的数学理论引入的，她是指称语义学的数学基础最初， d o m a i n 理论就是对程序的语义域所对应的数学结构进行研究；近年来，d o m a i n 理论已广泛渗透到其它数学分支，如动力系统、概率论、随机过程等领域以下 对d o m a i n 理论基础知识做简单介绍，对此部分感兴趣的读者可参照文献【3 】、【4 1 、 【5 】和【7 】进行深入学习 定义i a 1 带有二元关系的集合尸称为一个偏序集，如果v x d , , z e p ，下列条 件成立： ( i ) 血( 自反性) ( i i ) 匈缈幺辛剜传递性) ( i i i ) x c _ y a y f x - jx = y ( 反对称性) 定义1 1 2 设p 是一个偏序集p p 被称为定向集，如果( v ，售d 有限x 3 x d ) y e 砭勺夕d 定义1 1 3p 是一个完备偏序集( 简记c p o ) ，如果p 有最小元，通常记为上， 并且p 的每个定向子集在p 中有最小上界 例1 1 1 设彳是一集合，令4 1 利u ( 上) ，上豇4 是特异元，定义爿i 的序为：正 y yj = 上或x = y 因此，a i 的序包含尽可能少的信息，仅够成为一个c p o 这个c p o 称为平坦c p o 定义1 1 4 设d 是一个c p o 元素a e d 被称为紧的或有限的，如果对任何定 向集a c _ d 且4 e l “，那么存在x e a ，使得a c _ x d 中的紧元素的集合记为d c 定义1 1 5 一个c p od 是代数c p o ，如果对每个x c d ，集合 a p p r o x ( x ) = 口d 。l4 e x ) 是定向集，且x = l - l a p p r o x ( x ) 3 定义1 1 6 一个c p o d 是s c o t t - e r s h o v d o m a i n ，如果 ( i ) d 是一个代数c p o 且 ( i i ) 如果集合 口，b d o 是相容的，那么a l i b = l l a ，b e d 定义h 1 7 设d 是偏序集，若d 中的任何定向子集在d 中都有上确界，则 称d 是定向完备的偏序集，简记为d c p o 定义1 1 8 设，：d - 斗邑d 和e 为d c p o ( i ) 函数，是单调的，如果对每个x , y e d , x e y - - j ( x ) c _ o , ) ( i i ) 函数，是( s c o t t - ) 连续的，如果它是单调的，且v _ 白h d ，都有 ，( l 皤户叫伍棚， 定理1 1 9 ( t a r s k 0 如果p 是一个c p or i ：p 斗p 是单调的，那么，有最小不动 点， y 颤，一l 。o n l 尸( 上) 如果，连续，那么 献，产( 上) 定义1 1 1 0 设( p f i ) 为偏序集，对于x e p 与u c _ p ，规定： t 炉 ，脯 k = ) ，尸l 皿 l v - - u 1 叨j ，卢u k 畦研 当v = t u 时，称己，为上集；当u i 【，时，称u 为下集 1 2 范畴论的基本概念 范畴论是在4 0 年代初发展起来的一个新的数学分支范畴论的思想是把一些 抽象数学结构的内在共性提炼出来进一步加以抽象本节介绍本文涉及的范畴论 的一些概念和结论，供读者阅读时参照对范畴论感兴趣的读者可进一步参见 6 】、 7 】、【8 】和 1 q 来深入学习 定义1 2 1 一个范畴c 由下列内容组成： ( i ) 一个对象类d 6 ( c ) ，优嵋) 的元称为c 中的对象，通常用a , b , - - - 等表示范畴 的对象 4 ( i i ) _ 一个态射 m o r ( c ) ，肘i c ) 中的元称为c 中的态射对于c 中对象的每个有 序偶似皿) 对应惟一的一个集c 【a ，b 】c 丸b 】中的元称为c 中以彳为论域，以口为 余论域的态射 若e c m 捌，则记作，_ 呻口或a l 口 ( i i i ) 对于c 中对象的每个有序三元组a 月，c ) 对应一个称为合成( 或复合) 的映 射 c 阻捌x c b ，c 】斗c 口，c 】 q 办h 铲| g o ，称为，和g 的合成( 或复合) 要求c 中的对象和态射满足下列公理： ( 1 ) 若似，田( c p ) ，则c 即，明n c c , d i = o ( 2 ) 若，c 阻捌，g c b ，c 】，| i c 【c d 】，则 伪o s ) q = h o ( g o d ； o ) v a o h ( c ) ，3 i d a c a 州，使得v f c m , e ，v g e c 【c 卅，有 o f d ：，i d o g = g ， 地称为上的恒同态射 定义1 2 2 设c 和d 都是范畴，一个从c 到d 的共交函子( 或反变函子妒，记作 f c - - m ，是一对操作 f o b ：o b ( c ) - o b o ) ) ， ，i m ：m o r ( c ) - - m o r ( d ) 使得，对于a , s , c o b ( c l i ，_ 专口髫：曰哼c 胁“c ) 最。朋：，o b 口) 丰f 0 b 或 俨k 形) ：f o b ( 功j 如口) ) 或 s 蹦i d a ) = i d v o b ( a ) 实际中，通常省去。，曲的脚标，均记为， 例1 2 1 设c 是范畴，4 o 忧c ) ，则存在一个共变函子 c p - 】：c - - $ e i , v 口d m c ) ，c 搿，一】问口声】s e t v f ：b - - ) b m o r ( c ) ，c 口，一】咿研，力2 ，：c 口周- c 阴1 ， 此处对于| i l c 叫捌，有 t ) 可硝c 出声】 例1 2 2 设c 是范畴，b o n c ) 则存在一个反变函子 q 埘：c 哼s q v o b ( c ) ，c 【- 捌似) = c 即捌e s e t ， v ，_ ，_ 喇em o t ( c ) ，c 捌l 厂捌- 厂：c m j 】川口捌， 此处对于h c a 捌，有 厂( | | i 户 o f c r a ：明 以上例1 2 1 ，例1 2 2 中的函子c 幽 】和c 【- ，明统称为态射函子 定义1 2 2 设e g ：c - - ) d 是函子，那么r f - + g 是从，到g 的自然变换当且仅 当 a ) v 4 o 酞c ) ，r a c d f c a ) ，6 协) 】 b ) v ，c 口，明，r p f ( f ) = 6 l o 定义1 2 3 设f c - - 纠d 是个函子且d o b ( o ) ，那么“：d 一，( 咖d 【破以叻】 妇0 忧c ) ) ，称“：d 一只叻为从d 到，的泛态射，如果 v c e o b ( c ) ，v i e d d , f ( c ) 】，31 i c c a , c 】， 使得 。 = f t r 定义1 2 4 设f c - 纠d 与g d - 纠e 都是函子，若w d 6 ( c ) ，v b e o b ( d ) ，存 在一个双射 尹锄j ：d 【，u ) 声卜屺m ，g ( 回1 使得妒关a , b 是自然的，则称有序三元组( eg 咖为从c 到d 的伴随，或简称序偶 ，g 为一个伴随对，记作n g ：并称，是g 的左伴随，g 是，的右伴随 6 注：锄j 关于a 和曰都是自然的是指：v a o b ( c ) ，朔，是共变函子d 【刚) ，1 到共变 函子c 阴，顶) 】的自然变换，并且任意v b a 1 6 ( d ) ，但j 是反变函子d ( ，( ) ，嘲到 c 【- ，c k b ) 的自然变换 定理1 2 5 设，c d 与g ：d - - - , c 都是函子 ( i ) 若l l ：i d c - - g f 是自然变换，并且任意a e o b ( c ) p l # - 4 g f ( d ) 是从a 到g 的 泛态射，则( e g ，功为从c 到d 的伴随，此处，对于d 中的任意g ：f a - - b ，有 伊g ) f f i g ( g ) o t i a 4 - - g b ( i i ) 若e ：f g - - i d v 是自然变换，并且v b e o b ( d ) , s n ：f g ( b ) - - - ) b 是从f 到曰的泛 态射，则限e 咖是从c 到d 的伴随，此处，对于c 中的任意态射：a - - - g b ，有 矿( f ) = e s o f ( f ) ：f a - b 1 3s c o t t 拓扑及广义超度量空间 1 3 1 序理论 定义1 3 1 集合爿上的一个关系是笛卡尔乘积a x a 的子集c 如果c 是彳上 的一个关系。我们用记号r o y 或k 力c 表示“x x c y 于关系c 中” 定义1 3 2 集合上的一个关系c 被称为一个序关系( 或简单序，或线性 序) ，如果它具有下列属性： ( 1 ) ( 可比性) 对每个x 。v c a , x ：y ，不是x c y 就是y c x ( 2 ) ( 非自反性) 任一x a ，x c x 均不成立 ( 3 ) ( 传递性) 如果x c y 且y c z ，那么x c z 定义1 3 3 给定集合a ，a 上的关系 被称为彳上的严格偏序，如果它具备下 列两个属性： ( 1 ) ( 非自反性) a a 总不成立 ( 2 ) ( 传递性) 若a b 且b c ，则a c 定义1 3 4 设a 是集合， 为4 上的严格偏序如果口为a 的一个子集，4 中的一个元素c 被称为b 的上界，如果v b b 均有 b = c 或b ，s 是集合，a 是一字符集，- c _ s x a x s 定义 s 乌t 甘当j 具有长度s 开的某个轨迹时，t 也有同样的轨迹 甘无论何时撇s 一，且口，4 剧，如果有一个迁移序列 j 虬三l _ s ，那么存在一个相似的序列f 生q ! 。哼f 这样，可得到佤( e 1 ) 。劫 对于a e a 且u c _ s ，设 p o u = 如i ( j f 【d j 生专f ) 是( ，的口一前趋的集合 将这一定义扩展到轨迹， p e u = - u , p 尚聋国， 1 ，为任意轨迹 显然，s 印j 当且仅当s 有轨迹v 设 = 茚iy 的长度为开) ， 所以 u u 饥= p j l l ，的长度s 以) 。 定义 s e d 甘对每个长度5 n 的轨迹v ，s 印毋净f 印j 兮当s 有长度s n 的轨迹v 时，t 也有轨迹v 令， ( e n ) 。卯，n ( e 。) 。卸- 亡，则 跗，灾，参为带有偏序逼近族的迁移系统 例2 1 3 对于s , t s ，设确t ，定义 蠢n + l 艄如果s ! b s ， 那么存在t ，使得 f 旦t r s 磊f t 这种部分模拟可以像上面的迁移系统那样相似地刻划 设哩如= 研且z ，口+ l 是全部肌y 集合，4 4 且y 是w 。中部分成员的非空交集，那 么对应的乌关系恰为部分模拟。 这对于n = 0 是显然的 假设e 。= 矗，让我们首先由6 一i t ，推出s 与一正 为证明j 与州t ，我们必须证明距bt 仉对每个u e - o o u w 时i 对每个u 刨o u u 饥这是正确的 因为蠢l t m s s , t ，由归纳假设_ c n - - - s n ，则有j 写f 为了证明这对，o l 同样成立，考虑z o i 的一个元素儿】，且假设s e p a y , 这意味着 存在一ey ，使得j ! l ，由n i 的定义知，存在，使得f 生啼f tr 4s 毛f t 由 归纳假设，知吐 又，y ，从而f y ，因此f 锄y 所以，s 与州厶 相反地，假设白l t 且j 如l f 不失一般性，假设存在a 和，使得j 生辛，但对于每个满足f 璺_ 寸t 的r 均有 ，蔷n t t 由归纳假设，对于每个如上的t ，t ，也就是说，对每个上述t ，均 存在z 厶的一个成员包含一但不包含该t 。如果r 是这些成员的交，那么有一e y ， 但y 中不含t 的4 后继。因此s p o y ，又胁y z o l 但t 芒- p a y ，这与假设s e 州f 矛 盾，所以我们有s 一1 1 t 2 1 2 欠一偏序集的基本概念 定义2 1 2 t 1 设口，妄，固是纯偏序集，b 已l 凡d ，) n e 是a 中的元素族 若3 n o 甚- _ , 使得 y n , m ，n o m n 辛毛x n ， 则称 翰) 。e ，是a 中的代一链 定义2 1 3 【1 设h ) i i e ，是彳中的终链若髓爿满足以下条件： ( 1 ) j ，l o d ，使得v n ，1 0 肛 而写工； 1 2 ( 2 ) 如果) ，彳也满足条件( 1 ) ，那么母；。 则称工是 ) 。e ，的最小欠上界，并记作垆u 羔，而若4 中的任何熙链关于偏序都 有最小船上界，则称彳是纯完备的 定义2 1 4 【1 】设似，e ) ，慨b ) 分别为船偏序集，分别带有偏序逼近族 口 ，? a - - - - 一h 。a i 弗，) ，屯尸匹一i 以“) ，f ：a 专b 是映射，对任意一d ，若 a , b 已4 ，压：懒圬款6 ) ， 那么称是欠- 单调映射 定义2 1 5 【12 】设口，e ) ，( 只e b ) 均是欠偏序集，分别带有偏序逼近族灾a _ e ：l 盯i ) ，= 晖：f 刀i ) 且均为熙完备的，若f ：a b 是瘁单调映射且设 x d - 是j 哇中的孵链，有 f ( u 鍪驴u 心 则称厂是a ，与o 到( 蜀b ) 的终连续映射 2 2 纪偏序集上的s c o t t 拓扑 定义2 2 1 设彳= 似，写r ) 是他偏序集，口，声为a 中的船链，我们称口印，如 果口c 反 引理2 2 2 设亿偏序集似，挥) 是欠完备的，对任意联翻，均存在以x 为纯 上界的极大豫链( 以后均称以工为船上界的极大船链为p 极大链) 证明：叛4 ，设孚= 粕 剃lu 羔，而可 ，锄，i d 为$ 的一个线性序的子集， 不妨设 口l 口2 c r n ， 则茹啦为 啦) i 剞在8 中的上确界 由z o r n 引理知，男有极大元，即嚣有极大纪链 这里设全部 极大链为慨) 上e 旷“搿) e j ) 拒b 定义2 2 3 设4 = 似，e 翼) 是船完备的，对于形“与u 爿作如下规定： t n z ： y e ai 磊y ) ，俨 y e al 圬z ) t 墨萨ut 。馨，i 鼍萨uk 群， n j 如h* j ，t e l o 这里( 群) * i ) k l d 为a 中弘极大链的全体 t 灾泸 t i x e u ，j 霄泸 i i x e u 当u = t i u 时，称u 为亿上集；当c ，= ，u 时，称【，为熙下集 定义2 2 4 设彳= ，e 固是船完备的 v c ( a ，e ，固是s c o t t 开的，如果 ( a ) 泸p 配 ( b ) ( ) 。d 是似，e ，固中髂链且u ：，l b j 却 而) 。d ，x j e u d c ( a 5 ，固是s c o l t 闭的，如果 ( a ) d = i 物； c o ) 瘁链) 。d c = d 则u ：，而e d 定理2 2 5 设似5 ) ，( b g b ) 均是傅偏序集，分别带有偏序逼近族，h = e ：i n e ，灾萨 亡：i 厅百) 且均为亿完备的， 则f ：a 斗b 是纪连续映射j 它关于a 和口上的s c o t t 拓扑连续 证明：设，：a - - 4 b 是纯连续的，0 为口的一个开子集，欲证，。( d ) 为s c o t t 开的 ：* f 二i l t _ f 一( d ) 是瘁上集若x ef 1 ( d ) ，设“球) 。i ) k 1 0 为弘极大链的全体设 存在某个一，岛使群亡l ，要证：y ef 1 ( d ) 山f f f j r - 单调性知， 厂( 群炳， 又由连续性， 7 垆厂( u 羔，工n ( ”、) - - 一il 孵n e ，( 工，) 则，( y ) t 霞氕刁因删e o ，o 为s c o t t 开的，贝, l j f ( v ) e o ，即y e f 。( d ) 再证条件( b ) 1 4 设) n e i 是一中的髂链，若将元素d - u 孵e ，柚鲥映到0 中，即难，一1 ( o ) ， 欲证存在麓( 埘。l ，使而，- 1 ( d ) f ( x ) = f ( 1 l ：e ，) = u ：，f ( x n ) e o 因f b ) 丑e l 是a 中的灾链，由熙单调性知， f ( x n ) ) 。i 为b 中灾一链，且由于0 为 开的，则一定存在某个f h ) n i ，使f ( x 1 ) o 即而e f l ( d ) 由以上知，。1 ( d ) 是s c o t t 开的j 第三章 r - p o s i f t 与g u m s 间的伴随及不动点定理 3 1 欠p o s l 喊畴与g u m s 范畴间的伴随 定义3 1 1 范畴纯p o s e 碇义如下：其对象为灾偏序集( 绺仨n ) 唧) ，态射 为船偏序集间的舡单调映射 注：在以下的讨论中，如无特殊说明，熙偏序集的偏序逼近族均为，b 已l 力珂 的情形 定义3 1 2 设司分， e d p 为广义超度量空间，函数f ：x 专y 被称为非扩 展映射，如果妖j 7 x 都有 d r 叭曲，f ( x ) ) sd j “，) 命题3 1 3 设删( c ：k o ) ，h y 王y ，仨：) 。劫为他偏序集，在x 上定义度 量如下： 孑i ( j ，y ) = i n f 2 一。ix - c j ，刀巧) ，v x , ye x 则 1 ) 五是z 上的广义超度量， 是广义超度量空间 2 ) f 寸 为非扩展映射，当且仅当，：x y 为灾- 单调映射 证明：1 ) 只需验i 正v x , y ，z x ， ( a ) 五o ，功= 0 ( b ) 五( 工，z ) m a x 瓴“_ ) ，) ，瓦( ) ，z ) ) 2 ) i 殴f 为广义超度量空间，在 上定义偏 序族 ，醅= ( ：) 脚 如下： j = ：) ，vd x ( x , y ) m ， ：， 又 n ( ：) m = 啾 证得( i ) ( i i ) 设，：瓦舳( j ) 。) _ ( y r ( ：) 一) ，为船单调映射v 对于x , x e 五嬲：，毒，：，) v 对于五办似，垮2 4 等d 盯，) ) s 矿 v 对于五a , f f ，) 垮删) v ，： 寸 为非扩展映射 ( i i ) 得证 由命题3 1 5 知，可定义函子 g ：6 u m s - - r - p o s e 丌 如下： v d 6 ( o u m s ) ， o k ) = 电( ：) 口o ) ； v ，s 虹3 u m $ ( ) ， g = ，：( z 一( ：) 瞎o ) - ( l r ，( 。r ) 。卸) 为熙单调映射 命题3 1 6g o f 为欠p o s e 丌上的单位函子 证明：设 g f ( 墨( e ：，) 。卸产心，( ：) n o ) ， 其中i - i ( e ：k o = 矗，n ( = ：) 一o - = ， 显然，z 气兄再证，彳 辅：y v 五“y ) 立4 vi n f t 2 * l x c xy ) 2 4 vn _ s u p a 正f ) ， v ( | 娩功正f ) ， v 正：y 则饼眠仨j k o 产陇仨：) 。劫 对于熙单调映射，：( 墨正：) 。劫叫y r ，仨：) 。卸) ， 则g ：彤河：仨：) d 劫叫聒r ，( 亡： 口 命题3 i 7 函子f 是g 的左伴随 证明：给定自然变换 蒯硒2 捌) s e tj g f v a o b ( r - p o s e t ) ， t a ：a 专g f a 即 嗣d “爿 设m eo b ( 6 u m $ ) ，i 爿_ g m 是灾单调映射，由命题3 1 5 知，存在唯一 g e m o r ( g u m $ ) ， 使得 g 幢产| j g m ， 即 g 追p | ：g f a - - * g m 也就是说，存在唯一 g g u m s ( 尉，岣， 使 1 9 ，= g ( g ) o 耐a - g ( 朗or a , 因此， r l a a - - ) g f a 是从a 到g 的泛态射 因此，只g 是从欠甲o s e 可到0 u m s 的伴随 3 2 不动点定理 定义3 2 1 设粼e 品( e ：k 曲，h y 5 r 仨：k d ) 为灾偏序集，映射，：) 吖被 称为逼近映射，如果对任何 正：y ，x ，y x ， 都有 | 窃r 一- 7 柑l 螨 命题3 2 2 设x , y 为船偏序集，i ：x - + y 为映射 a ) 若，为贤连续映射，则，为逼近映射； b ) 若，为逼近映射，则，为昏单调映射 定理3 2 3 设一= ， ，灾) 是有底且冗- 完备的灾偏序集，h 写) 。o n ，则逼 近映射，利存在一个最小不动点 f i x ( f ) = f 4 ( 上) = u 是。厂4 ( 上) 证明：止( 上) ，因歹为逼近映射，则有 “上) e - 尸( 上) ，2 ( 上) e 矿( 上) ，尸( 上) 与，1 ( 上) 于是，有船链 上e 承上) i 尸( 上) e ( 上) 乌z 歹f c l ) 与l ，”( 上) ( 1 ) 因彳为船完备的，则好链( 1 ) 有最小，卜上界 尸( 上) = u 麓f 1 ( 上) 由超穷归纳知。v a e o r d , f ( 1 ) 为良定义的，且有九上) e 。，”1 ( 上) ，莉一定存在 d o r d ，使 ，。( l ) = ，翻( 上) ， 即 ，。( 上) = u 乏。厂。( 上) 则 ，。( 上) = u 嚣e 。，4 ( 上) 为，的不动点 如果工是，的其它不动点，那么，由_ 【k ，我们得到 | q 驻| 睁x 。产l l 驻& 由超穷归纳知，j 是所有，。( 上) 的上界，显然也为 ，“( 上) ) 。e 刚的亿上界， 则 u ：| o 日，4 ( 上) j 定理3 2 4 ( t a r s k 不动点定理) 如果， 偏序集似5 ，固是有底且， 完备的，_ 争4 是佑连续映射，那么，有 一个帚小不劫点 斛u 麓f ”( d 证明：因，为连续映射，则，为逼近映射，则亦可得定理3 2 3 证明中的熙链 ( 1 ) ，且有 尸( 上户ii 乞厂”( 上) 由连续性知， ，( u f 。( 上) ) = u f ”( 上) 因此， 尸( 上产ii 孵埘f ”( 上) 为，的不动点，且易证其亦为最小不动点 2 1 参考文献 【l 】冀文信息序的逼近与广义链的完备化：【首都师范大学硕士学位论文 中国 北京：首都师范大学，2 0 0 5 【2 】l m o n t e i r o s e m a n t i cd o m a i n sb a s e do ns e t sw i t hf a m i l i e so fe q u i v a l e n c e s e l e c t r o n i cn o t e si n t h e o r e t i c a lc o m p u t e rs c i e n c e v 0 1 1 1 ( 1 9 9 6 ) p r e p r i n t 【3 】vs t o l t e n b e r g - h a n s e n e ta 1 m a t h e m a t i c a l t h e o r yo fd o m a i n s c a m b r i d g e u n i v e r s i t yp r e s s ，1 9 9 4 4 】s a b r a m s k y a n d a j u n g d o m a i n t h e o r y i n ：a b r a m s k ye a 1 ，e d s h a n d b o o k o f l o g i ci nc o m p u t e rs c i e n c e o x f o r d ：c l a r e n d o np r e s s , 1 9 9 4 v 0 1 3 1 、1 6 8 【5 】w m m i s l o v e t o p o l o g y ，d o m a i nt h e o r ya n dt h e o r e t i c a lc o m p u t e rs c i e n c e t o p o l o g ya n di t sa p p l i c a t i o n s ，1 9 9 8 ，8 9 ：3 5 9 【6 】aa s p e r i t i ，gl o n g o , c a t e g o r i e s , 枷a n ds t r u c t u r e s ：a ni n t r o d u c t i o nt o c a t e g o r yt h e o r y f o rt h ew o r k i n gc o m p u t e rs c i e n t i s t s , m i tp r e s s ，1 9 9 1 ，p r e p r i n t 【7 】郑崇友，樊磊，崔宏斌f r a m e 与连续格( 第二版) 中国北京：首都师范大学 出版社，2 0 0 0 r 5 9 【8 b c p i e r c e 鼬f cc a t e g o r yt h e o r y f o rc o m p u t e rs c i e n t i s t s c a m b r i d g e ：m i t p r e s s ，1 9 9 1 9 j j m m r u t t e n e l e m e n t so f g e n e r a l i z e du l t r a m e t r i cd o m a i nt h e o r y t h e o r e t i c a l c o m p u t e rs c i e n c e ，1 9 9 6 ，1 7 0 ：3 4 9 3 8 1 【1 0 j r m u n k r e s t o p o l o g y ( s e c o n de d i t i o n ) p e a r s o ne d u c a t i o n , 2 0 0 0 【1 1 】陆汝钤计算机语言的形式语义科学出版社，1 9 9 2 【1 2 】高泾萍，何伟，樊磊等死偏序集及其上的s c o t t 拓扑中央民族大学学报( 自 然科学版) ，v 0 1 1 5 ( n o 4 ) ，3 3 0 3 3 3 【1 3 j j m m r u t t e n u n i v e r s a lc o a l g e b r a ： at h e o r yo fs y s t e m s t h e o r e t i c a l c o m p u t e rs c i e n c e , 2 0 0 0 , 2 4 9 ：3 “8 0 【1 4 】m m b o n s a n g u e , e r e g e n e r a l i z e dm e t r i cs p a c e s ：c o m p l e t i o n ，t o p o l o g y , a n d p o w e r d o m a i n sv i at h ey o n e d ae m b e d d i n g t h e o r e t i c a lc o m p u t e rs c i e n c e ，1 9 9 8 1 9 3 ：1 5 1 【1 5 j h u g h e s ，b j a c o b s s i m u l a t i o n s 加c o a l g e b r a ，p r e p r i n ts u b m i t t e d t o t h e o r e t i c a lc o m p u t e rs c i e n c e ，2 0 0 4 f 1 6 】r v k o n c h a k o v o n t h es e m a n t i c ao fc o n c u r r e n t p r o g r a m m i n g l a n g u a g e s ：a n a u t o m a t a - t h e o r e t i c a l a p p r o a c h ，p r e p r i n t 【1 7 】樊磊d o m a i n 理论中若干问题的研究：【首都师范大学博士学位论文】中国北 京：首都师范大学，2 0 0 1 【1 8 w i n s k e l ，g 著，宋国新等译程序设计语言的形式语义北京：机械工业出版 社