（基础数学专业论文）关于归纳半环及相关半环的研究.pdf

西北大学学位论文细设产权声明书 y 8 9 3 9 7 3 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时j 本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 ，、2 学位论文作者签名：! 盎指导教师签名：；i 塾兰至， 如口莎年6 妒月z g 旦年月。日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名： 亏； w 。5 年d i 月l f 日 摘要 本文给出了归纳+ 半环及弱归纳- 一半环概念的推广，即步半环、a 一半 环、+ “半环以及，一* 半环的定义；研究了这些半环的一些基本性质以及它们之 间的相互关系；同时结合形式幂级数及不动点理论，讨论了这些半环关于形式 幂级数构造的封闭性问题。 本文的内容主要分为五章。第一章介绍了半环理论的研究历史和本文的选 题背景及课题意义，简述了本文所取得的主要成果。第二章介绍了本文所需要 的半环、偏序集和不动点方面的相关知识。第三章以归纳+ 一半环为重点，介 绍了归纳+ 半环及弱归纳一半环的概念及基本性质，并讨论了归纳+ 一半环的 形式幂级数半环。第四章给出了肛半环和 半环的定义和基本性质，讨论了 两者的一些内在关系并研究了它们的形式幂级数半环。第五章给出了+ 一肛半 环和，一k 半环的定义和基本性质，讨论了这两类半环之间以及它们与归纳+ 一半 环、弱归纳+ 半环之间的一些内在关系并研究了它们的形式幂级数半环。 关键词：半环；归纳+ 一半环；胪半环；k 半环；+ - a - 半环；形式幂级数 a b s t r a c t ( 英文摘要) i nt h i 8t h e s i s ，w ed e 6 n et h en o t i o n 8o fp s e m i r i n 萨，斗8 e l 试n g s ，+ 一p s e m i r i n 伊 a 1 1 d 丰一a s e m i r i n 9 8w h i c he c t 傩dt h en o t i o n 8o fi i l d u c t i v e 幸一s e n l i r i n 萨w ea 1 8 08 t u d y t h eb 鹪i cp r 叩e r t i 鹤o ft h 膀e m i r i 瑚芦锄dd i s c l l 蹈t h ei n t e r r e l a t i o nb e 佃e 阻t h e m a 1 s o ，w ed i s c u g sw h e t h e rt h e 删n 窜8 r ec 1 0 s e df o rt h ec o 璐t r u c t i o no ff o r m a l p o w e r8 e r i e s 讥aaf i x e dp o i n t t h e o r e t i c 正v i e w p o i n t t h i 8d 主s 8 e r t a t i o nc 衄b ed i v i d e di n t o 矗v ep a r t s t h e 五r s tc h a p t e ri 8 觚i n t r o - d u c t i o nt on l eh i s t o f yo f8 e m i r i n gt h e o r y w ee m p h a s i z et h tt h et h 鹊i si sm a i n l y c o n c e r n 研t h8 e v e r 8 li m p o r t 8 n t m i 血擎缸试n gi nt h e o r e t i c a lc o m p u t e rs c i e n c e t h es e c o dd b b p t e r ，w h i c h8 e r 、髑8 st h eb 够i so fo u rd i u 鹄i o n ，l v 档t h eb 8 8 i c n o t i o 璐啦dr e s u l 七8o f 鲫丑i r 通擎，p c 踺乞sa n d 丘x e dp a m 乞s t h et h i r dc h a p t e ri n t r o - d u c e 8t h en o t i o no fi n d u c t i v e 车一8 e m i r i n 9 8 蹰dw e a ki n d u c t i v e 幸- 删n 庐w bg i v e g o m eb 船i cp m p e r t i o ft h e ma n dd i s c u 鼯t h ef 细l a lp 唧r8 e r i 髑8 e m i r i n g s i n c l l 印t e r4 ，w e 蚴n et h e o t i o n 8o f ，卜8 e m i r i n 9 8 肌dk 8 e m 试n 9 8a n d8 l s os t u d yt h e p r i m a r yp r o p e r t i 皓o ft h e m m o r e a v e r ，骶d i s c l l 锱t h ei n t e e l a t i o nb e t w e e nt h e m a n dt h ef o m 瑚p o w e rs e r i 鹤舳m i 血鳋0 ft h e m mc h a p t e r5 ，w e 谳n et h en o t i o n s o f4 一卢一8 e m i r i n 9 8 蠲w e l l 够4 k s e m 赫n 擎觚da l s os t u d yt h ep r i i i l a r yp r 叩e r t i e so f t h e m w bd i s c u s st h ei n t e r r e l 8 越o nb e h 嘴帕n + 一p 一8 e m i r i n g s 趿d 奉一a s 吼i r i n 9 8 ，a n d t h e i rr e l a t i o nw i t ht h o s es e m i r i n g si n t r o d u c e d0 b o v e i nt h ee n d ，w es 饥l d yt h ef o r - m a lp o w e r r i 船s e m 城n 牮o f + 一片s e m 证n 留舾w e u 船w e a ki n d u c t i v e + 一s 锄i r i 寥 k e y w o r d s ：s 锄i r i n 窜；i n d u c t i 、r e 事一s e m i r i n g s ；p s e m i r i n 9 8 ；k s e m i r 证g s ；幸- k 8 e m i r i n g s ；f b r m 8 lp a w e r r i e s 2 第一章绪论 1 1研究背景与意义 1 8 9 4 年，德国数学家m d l 缸dd e d e k i n d 【1 】在研究交换环的理想时首次定义 了称为半环( s e m i r i n g ) 的代数结构。随后m 8 c a u i a y 和k r u u 等代数学家均从交 换环的理想的角度对半环进行了研究讨论。1 9 3 4 年美国数学家h s 溅v e r 【2 1 在更一般的意义上对半环进行了较为深入的研究。他认为半环作为环与分配格 这两种数学对象的共同推广，是最优美的代数结构之一。为了使半环成为人们 普遍接受的一种基本代数结构，v 缸d i v 目等人进行了艰苦的尝试并取得了一定 的成功。 从1 9 6 0 年代后期开始，人们陆续发现了半环在形式语言与自动机理 论【目【4 】【q 【6 l 、程序分析与算法设计m 【8 l 【9 j 、优化与控制理论【l o j 【1 1 l 【1 2 l 、圈论【1 3 l 、广 义f u z z y 计算【1 4 】f 1 5 i 【1 6 】、离散事件动态系统【l 7 】【18 】以及量子计算【19 j 等诸多领 域的重要应用。在实际应用的有效推动下，半环理论在近几十年间取得了长足 的发展。2 0 0 0 年前后，以色列数学家j s g o k 【2 1 】担2 l 在其专著中全面阐述 了半环的代数理论及其在相关学科中的应用。 我们在研究中发现归纳+ 半环、弱归纳+ 半环及c o n w a y 半环等半环类被 理论计算机科学工作考极为重视和高度关注。为此，本文对归纳+ 一半环及弱归 纳+ 一半环的概念进行了推广，定义了p 一半环、* 半环、+ 一芦一半环及+ 一k 半环并 研究了这些半环类的代数理论及应用。 1 2 主要成果 本文所取得的主要成果包括：给出了归纳+ 半环及弱归纳+ 半环概念的推 广，即p 一半环、a 一半环、4 一p 半环以及+ 一a 一半环的定义：研究了这些半环的一 些基本性质以及它们之间的相互关系；同时结合形式幂级数及不动点理论，讨 论了这些半环关于形式幂级数构造的封闭性问题。证明了任意弱归纳+ - 半环的 5 形式幂级数半环仍是弱归纳+ 一半环，从而对蠡i k 和k u j c h 教授在文献 2 4 】中 提出的一个公开问题给出了肯定的回答。具体而言： 第一章作为绪论简要介绍了半环理论的研究历史和本文的选题背景及课题 意义，强调了本文的特色在于侧重研究理论计算机科学中提出并被广泛关注的 几类半环。此外，绪论部分还简述了本文所取得的主要成果及全文的组织框 架。第二章作为本文研究和讨论的基础，简述了半环、偏序集和不动点方面的 相关知识。第三章以归纳+ 半环为中心，介绍了归纳+ 半环及弱归纳+ 一半环的 概念及基本性质，并讨论了归纳+ 半环的形式幂级数半环。第四章给出了肛半 环和a 一半环的定义和基本性质，讨论了两者之间的一些内在关系并研究了它们 的形式幂级数半环。第五章给出了+ 一胪半环和气a 一半环的定义和基本性质，讨 论了这两类半环之间以及它们与归纳t 半环和弱归纳+ 半环之间的一些内在关 系并研究了它们的形式幂级数半环。 6 2 1半环 第二章预备知识 在本节中我们将给出半环、+ 一半环、序半环和序 半环等基本概念。首 先，我们有如下定义： 定义2 1 ：设s 是非空集合若在s 上定义了一个二元运算“”( 通常称为乘 法) 且满足结合律，即对任意的口，6 ，c s ， 则称( s ，) 是半群 ( 口曲) c = n ( 6 c ) 设s 是半群。对s 中任意的两个元素口与6 ，通常将它们的乘积o 6 简记 为口6 。若存在s 中的元素1 ，使得对任意的d s ，均有 口1 = 1 口= o 则称l 为s 中的幺元素( 或恒等元) ，并称s 是含幺半群( 或独异点) 。一个半 群s 称为交换半群，是指s 上的乘法满足交换律，即对任意的n ，6 s ，均有 n 6 = 阮 定义2 2 ：设s 是非空集合若在s 上定义了两个二元运算“+ ”( 通常称为 加法) 和“”( 通常称为乘法) 以及两个零元运算o ( 零元素) 和l ( 幺元素 或恒等元) ，使得 ( s ，+ ，o ) 是舍幺交换半群； 2 ( s ，1 ) 是合幺半群； 占( v n l 6 ，c s ) ( 口+ 6 ) c = n c + 6 c 和c ( 0 + 6 ) = c o + 西； 7 4 ( v 口s ) 柏= = o ， 则称s = ( s ，+ ，o ，1 ) 是半环 定义2 3 ：设s 是半环若在s 上还定义了一个偏序关系“s ”，使得s 上的 加法和乘法运算均是单调的，即 ( v 口，6 ，c ，d s ) 口6 ，c d 辛n + c 茎6 + d ，n c s 掘 则称s 是序半环 设s 是半环。若在s 上还定义了一个一元运算+ ：s s ( 通常称为星号 运算) ，则称s 是，半环。如果在一个序半环上还定义了星号运算，则称之为 序，半环。需要注意的是，序+ 一半环上的星号运算并不要求是单调的。 2 2偏序集与不动点 设p 是一个偏序集，f ：p p 是p 上的一个映射。称p 中的元素z 是 映射f 的一个不动点( 缸e dp o i n t ) ，是指f ( 。) = 茁。类似地。称z 是f 的一 个前不动点( p r e f i ) ( e dp o i n t ) ，是指f ( 。) 。映射f 的全体不动点和全体前不 动点之集分别记为一z ( f ) 和矿，( f ) 。若p 的子集 。( f ) 在诱导偏序下有最 小元则称之为映射f 的最小不动点( 1 e a s t 缸e dp o i n t ) ，并记为h f ( z ) 。类 似地，可以得到f 的最小前不动点( l e 蠲tp 髓x e dp o i n t ) 的定义，并通常将f 的最小前不动点记为p z f ( 茹) 。由定义易见映射f 至多只有一个最小( 前) 不动 点。 设p 1 ，r 是偏序集。则在集合p 1 ，r 的卡氏积p 1 r 上可 以按照分量的方式引入如下偏序： ( 。1 ，一，) ( ! ，1 ，) 铮( v l ，”) ) z t 玑， 其中，鱼表示偏序集r 上的偏序关系。通常我们称p 1 r 按照如上偏 序所做成的偏序集为偏序集a ，r 的乘积偏序集，并将n 个偏序集p 的乘 积偏序集p p 简记为p ”。 8 设p ，q 是偏序集，f ：p q 是p 到q 的映射。若对任意的$ 1 ，观 p 。 z l s p 功= f ( z 1 ) s o f ( 现) 其中p ，s 口分别是p 和q 上的偏序，则称映射f 是单调的( m o n o t o n e ) 。偏 序集之间的单调映射也称为保序映射( o r d e r _ p r 鹧e r v i n gm 印) 。 下面我们给出与偏序集和不动点相关的几个基本命题，它们的证明可参见 文献【3 7 】。 命爱2 1 ：设p 是偏序集，是p 上的单调映射则舻，( z ) 是，的不动点 事实上，肛，( 。) 是，的最小不动点 龠题2 2 ：设p 是偏序集， ，2 是p 上的单调映射若对任意的z p ， 均有 ( z ) s ，2 ( z ) ，刖肛z 0 ) sp 石，2 ( 。) 命题2 3 ：设p ，q 是偏序集， ：p q ，如：q p 是单调映射 若映射 o ，2 的最小前不动点存在，刺，2o 的最小前不动点也存在， 且p 石( ，2 。 ) = ，2 ( p z ( o 如) ) 在本节的最后，我们介绍一类重要的偏序集，即( 定向) 完备偏序 集( ( d i r e c t e d ) c o m p l e t ep 锵e t ，d c p o ，e p 0 ) 定义2 4 ：设d 是偏序集p 的非空子集若对任意的8 ，6 d ，存在d 中元 素c 使a ，6sc ，则称d 是p 的定向子集 定义2 5 ：设p 是偏序集称p 是完备偏序集，若它满足： p 有最小元； 2 ，p 的任意定向子集d 有上确界 通常记完备偏序集中的最小元为上。此外，若偏序集p 仅满足上面定义中的第 二个条件，则称p 是预完备偏序集( p 降c p o ) 。 定义2 6 ：设p ，0 是预完备偏序集，f ：p q 是p 到q 的映射若对p 9 的任意定向子集d ，均有f ( u d ) = u f ( d ) ，则称映射f 是连续的 由定义知预完备偏序集之间的连续映射是指保持任意定向子集的上确界的 映射。若两个完备偏序集之间的连续映射还保持最小元，则称为严格连续映 射。 命题2 4 ：设p 是偏序集则下列条件等价： j p 的任意定向子集d 有上确界 2 p 的任意子链d 有上确界 占p 的任意良序子链d 有上确界 容易发现，上面的命题事实上给出了完备偏序集的几个等价刻划。下面我 们给出关于完各偏序集的几个不动点定理f 3 8 l 【3 9 l 定理2 l ：设p 是完备偏序集，：p p 是单调映射记o = u ，“( 上) 那 么： ”o 若口，i z ( ，) ，则o = 妇，( z ) 2 若，是连续的，则，的最小不动点存在且a z ，( z ) = o 定理2 2 ：设p 是完备偏序集，：p 一尸是p 上的映射若对p 中任意的元 素z ，均有z ，( 茹) ，则映射，必有不动点 定理2 3 ：设p 是完备偏序集若，：p p 是单调映射，则，必有最小不动 点。 定理2 4 ：设a 是完备偏序桌，n ，p 是非负整数，n 1 刘对任意的单调映 射，：a ”+ p a ”和任意的y = ( y l ，跏) 舻，如下定义的映射： 矗：a “一a “z 一，( z ，可) 丘有最小前不动点 】0 第三章归纳宰半环 3 1归纳幸一半环的定义及基本性质 归纳+ 半环及弱归纳t 半环的概念是由理论计算帆科学领域的著名学者， 匈牙利的幽k 教授和奥地利的k t d c h 教授首先提出并加以研究的。这一概念 与理论计算机科学，特别是语义学中著名的不动点归纳原理( p a r k 归纳原理口q ) 密切相关。此外归纳半环也是理论计算机科学中许多重要研究对象的共同 推广，其中包括k l 代数啪i 矧嘲删，连续半环删p 1 j 倒、q u t 8 l e 呻i 和b h k l e 网【蕊1 等等。 定义3 1 ：一个序t 半环s 称为归纳1 半环，芳s 满足不动点不等式： 口4 + + 1s 矿；( 3 1 ) 以反不动点归纳洼剧： 口z + 6 玉z = 矿6 兰z( 32 ) 命置3 1 ：设占是归纳t 半环剐s 满足不动点等式： 且s 上的星号运算是单调的 n 矿+ l = o ( 33 ) 事实上，在文献【2 4 】中，氐i k 和k u i c h 还证明了任意归纳+ 一半环均满足下 列等式： 列等式： o + 口+ l = 矿 ( n 6 ) = 1 + 8 ( k ) 铀 ( 口6 ) n = 8 ( 6 n ) 4 ( 。+ 砷= ( n + 6 ) + 矿 1 1 ( 3 4 ) ( 35 ) ( 3 ，6 ) ( 3 7 ) 我们通常将等式( 3 4 ) ，( 3 5 ) 和( 3 7 ) 分别称为对偶不动点等式，积星等式 以及和星等式。 定义3 2 ：一个序气半环s 称为弱归纳t 半环，若s 满足不动点等式，和星等 式，以及弱不动点归纳法则： n z + 6 = o = 口+ 6 茁 由定义易见，任意归纳半环是弱归纳+ 一半环。 ( 3 8 ) 定义3 3 一个气半环s 称为n t m f 半环，若s 满足和星等式以及积星等 式 可以证明任意弱归纳+ 一半环满足等式( 3 4 ) ，( 3 5 ) ，( 3 6 ) 以及如下的不等 式： ( n + + s ( 口) + 口+ 因此，我们立即可知任意弱归纳+ 一半环是c o n w 8 y 半环。 3 2归纳木- 半环的形式幂级数半环 设a 是一个由若干符号( 字母) 组成的非空集合( 通常称为字母表) 。称a 上 的任意一个有限符号窜为a 上的一个字( w o r d ) 。不包含任何符号的字称为空字 并记为e 。通常将a 上所有的字组成的集合记为岔，并称”的任意予集为a 上的语言。若在a + 上引入称为“连接”的如下运算“o ”： v o ，材a ，o o 掣= z 则( a + ，o ) 成为一个以e 为幺元素的独异点，称为由a 生成的自由独异点。 定义3 4 ：设s 是半环，小是由字母表a 生成的自由独异点则称到s 的映射 r ：a + s 为a 上的系数在s 中的形式幂级数 1 2 a 上的系数在s 中的形式幂级数r ：钟一s 通常记为如下形式： 其中，( r ，u ) 是牡在映射r 下的象。a 上的系数在s 中的所有形式幂级数的 全体之集记为s a + ) ) 。集合s ( ( 关于按点定义的加法以及如下定义的所 谓c a u c h y 乘积： v n ，r 2 s a + ，v u a ，( r 1 r 2 ，t ) = ( r 1 ，u 1 ) ( r 2 ，地) ， u l “3 生 做成一个半环，称为半环s 的幂级数半环。易见该半环中的零元素是s “ 中系数全为半环s 中的零元的幂级数。而除空字的系数为s 中的幺元，其它系 数全为s 中的零元的幂级数贝眭是s 的幂级数半环中的幺元素。此外，当s 是 序半环时，s 的幂级数半环s “岔在按点定义的偏序下也做成序半环。 如上所述，对给定半环s ，我们定义了s 的幂级数半环s “岔) ) 。而且当s 是序半环时，我们可通过s 上的偏序定义出s ( ( a ) ) 上的一个偏序关系，使的 幂级数半环s ( ( 也成为一个序半环。进一步，若s 是一个+ - 半环，那么s 上的星号运算可按照如下方式诱导出s “岔 上的星号运算： 对s “中任意的幂级数r 以及a 上任意的字t ，若t l ；e ，令 否则 ( r ，t ) = ( v ) + ( ) ( ，”) t d = u ，醇 在文献【4 0 】和【4 l 】中，b 1 0 0 m 和氩汰教授证明了如下事实： 定理3 1 ：若s 是删口半环，则s 也是竹伽口半环 而在文献【2 4 】中，色s i k 和k u i c h 教授进一步指出： 定理3 2 ：若s 是归纳t 半环，则s “也是归纳t 半环 1 3 由上面的定理知任意归纳+ 一半环s 的幂级数半环s ( ( 仍是归纳4 一半环。 那么我们自然会想到对于弱归纳+ 半环，这样的事实是否成立? 而这正是蠡i k 和k u i c h 教授在文献【2 4 l 中提出的一个公开问题。对于这个问题，本文作者和 赵宪钟教授以及韩国的y b 腿gb 脯j u n 教授进行了研究并给出了肯定的回答。 1 4 第四章“- 半环和a - 半环 4 1芦一半环和a 一半环的定义 定义4 1 ：设s 是半环，n ，6 s 称形如，：s s 嚣hn 。+ 6 的映射为s 上 的仿射变换 如前所述，序半环的定义中要求加法及乘法运算均是单调的，那么容易证 明若s 是序半环，则s 上的任意仿射变换也是单调的。根据序半环上仿射变换 的不动点的情况，我们定义如下概念： 定义4 2 ：设s 是序半环若s 上任意的仿射变换，：s s 。一8 z + 6 均 有最小不动点，则称s 为a 半环 定义4 3 ：设s 是序半环若s 上任意的仿射变换，：s sz 一凹+ 6 均 有最小前不动点，则称s 为口半环 命蠹4 1 ：设s 是弘斗环，则s 是入- 半环事实上，此时对s 上任意的仿射 变换，：s sz d z + 6 ，均有a 。，( z ) = p z ，0 ) 证明：设s 是p 半环。则s 上任意的仿射变换，：s sz 一彻+ 6 均有最 小前不动点p 矗，( z ) 。但，是单调映射，那么由第二章中的命题2 1 知肛，( z ) 实际上是，的最小不动点。故s 是 一半环，且对s 上任意的仿射变换，均 有 z ，( 。) = ，膳，( z ) 。 定义4 4 ：设s 是序半环若s 作为偏序集是完备偏序集，则称s 为e p 0 一半 环。 命题4 2 ：若s 是e p 0 半环，则s 是肛一半环 证明：设s 是e p d 一半环。在定理2 4 中，依次取a = s ，n = 1 ，p = 2 ，( z 1 ，z 2 ，z 3 ) = 。2 2 1 + z 3 以及”= ( o ，6 ) s 2 。则，是完备偏序集上的单调 映射且矗( z ) = + 6 有最小前不动点。再由n ，6 的任意性知s 是p 一半环。 1 5 4 2肛半环和a 一半环的基本性质 引理4 1 ：设，是偏序集p 上的单调映射若p r e ( ，) 在p 中的下确界存在， 则p z ，( z ) = p 。p r e ( ，) 证明：设 p 所e ( ，) 存在并记为o 则对映射，的任意前不动点o ，均 有z o n 。但，是p 上的单调映射，于是得 ，( 。o ) s ，( 口) 口 因此，( z o ) 是p r e ( ，) 的一个下界。从而有，( z o ) s 锄，即茁o = p p r e ( ，) 是，的最小前不动点。这就完成了引理4 1 的证明。 上面的引理事实上给出了p 半环的如下刻划： 命最4 3 ：设s 是序半环则下列命题等价： s 是“一半环 2 s 上任意的仿射变换，：s s 茁一簖+ 6 的前不动点之集的下确 界 s p 忱( ，) 存在 证明：首先，若s 是胪半环。则由胪半环的定义，对s 中任意的元素n ，6 ，s 上的仿射变换，：s sz a z + 6 有最小前不动点于是 s p r e ( ，) 存在 且 s - p r e ( ，) 一揖，0 ) 。 反之，若半环s 满足条件2 ，即对s 中任意的元素n ，6 ，s 上的仿射变 换，：s s 。一口。+ 6 的前不动点之集的下确界 s p r e ( ，) 存在。则 由l e m m a4 1 立即可得肛，( 。) = 人s n e ( ，) 。因此，s 是p 半环。这就完成 了命题4 2 的证明。 设p 是偏序集。称p 满足降链条件( d c c ) ，是指对p 中元素组成的任意 下降链 茹1 0 2 - 均存在正整数七，使得茁k = z 女+ 1 一。 】6 命题4 4 ：设s 是序半环若s 满足降链务件，则s 是“一半环当且仅当s 是a 一半环 证明：由命题4 1 知任意胪半环均是k 半环。故只需证明：若s 是* 半环， 且s 满足降链条件，则s 是p 半环。事实上，设s 是满足降链条件的a 半 环。由定义，s 上任意的仿射变换，：s sz o 。+ 6 均有最小不动 点a z ，( z ) 。任取，的一个前不动点跏，由定义知，( 知) 。o 。而由前所述， 仿射变换，是单调的。于是得s 中元素组成的如下降链： 知，( z o ) ，f i ( 觚) r + 1 ( z o ) 则由降链条件知存在正整数，使得产( 嚣o ) = ，+ 1 ( z o ) 。即，( 嚣o ) 是，的一个 不动点。由a z ，( z ) 的最小性得妇，( z ) z o 。再由z o 的任意性知沁，( z ) 事 实上是，的最小前不动点。故s 是抄半环。这就完成了命题4 3 的证明。 4 3抄半环和知半环的形式幂级数半环 在本节中，我们将讨论p 半环和a 半环的形式幂级数半环并证明与之相关 的两个结论。 定理4 1 ：若s 是p 斗环，则s 的j i 级数半环s “ 也是肛半环 证明：设s 是一个p 半环。对s “a + ) ) 上任意的仿射变换，r ，：。一r z + s ，我 们按照如下方式递归定义幂级数伯：钟一s 为： 1 若“一e ，令 ( r o ，e ) = p 。 ( 。) 其中，五( z ) = ( r ，e 如+ ( s ，e ) 是s 上的仿射变换； 2 若“e ，令 ( r 0 ，u ) = 肛丘( 。) ， 其中，厶( 茹) = ( r ，e ) 。+ ( r ，”) ，”) + ( s ，u ) 是s 上的仿射变换。 = u ， 】7 由于s 是p 一半环，易验证r o 是良好定义的到s 的映射，即s “钟* 中的形 式幂级数。接下来，我们将证明r 0 正是幂级数半环s “ 上仿射变换，r 。的 最小前不动点。首先，我们证明r 0 是，r ，。的( 前) 不动点事实上，对a 上任意 的非空字u ， ( ，r 月( r 0 ) ，t 1 ) = ( r 伽+ s ，t 1 ) = ( r r o t ) + ( s ，t ) = ( ) ( r 0 ，t ) + ( r ) ( r 0 ，) + ( 刚) t 口苎u ， = 厶( ( 码，u ) ) = ( r o ，u ) 类似地，对空字e ，我们有 ( 。( r 0 ) ，e ) = ( r r 0 + s ，e ) = ( r ，e ) ( r 0 ，e ) + ( s ，e ) = ，c ( ( r 0 ，f ) ) = ( r o ，e ) 因此，我们证明了 ，r ，。( r 0 ) = r r 0 + s = r 0 ， 即r 0 是，r 的一个( 前) 不动点。下面我们证明r 0 的最小性。设z 1 是 。的 任意一个前不动点。因为，r t 。( 。1 ) = r z l + s z 1 ，则对任意的t 小，均 有( ，r ，。( z 1 ) ，) p 1 ，t ) 。即当t = e 时， ( nf ) ( z l ，e ) + 扣，e ) ( z 1 ，e ) 而当u e 时， ( r ) e ) 0 1 ，“) + ( n ) ( z ，”) + ( s ，) s ( z l ，u ) t n 口= u ， 于是，由r 0 的定义知对任意的u 岔，均有 u p 一 蜡 u m 即伯是 。的最小前不动点。这就完成了定理4 ，1 的证明。 上面我们证明了任意胪半环的幂级数半环仍是p 半环。类似地，对k 半环 我们有如下定理。 定理4 2 ：若s 是 一半环，则s 的幂级数半环s “岔也是 半环 证明：设s 是个* 半环。对s 并上任意的仿射变换二、。：互一w + s ，我 们按照如下方式递归定义幂级数伽：岔一s 为： 1 若n = e ，令 ( r o ，e ) = 妇，f ( z ) 其中，五( z ) = e 扣+ “e ) 是s 上的仿射变换： 2 若u e ，令 ( r o ，“) = h 丘( z ) ， 其中，厶( z ) = ( r e ) +( r ， ) ，蜘) + ( s ，u ) 是s 上的仿射变换。 m 口= u ， 由于s 是a 一半环，易验证r o 是良好定义的小到s 的映射，即s “a + * 中的形 式幂级数。接下来，我们将证明r 0 正是幂级数半环s “a 上仿射变换，r 1 。的 最小不动点。首先，我们证明r 0 是，r 。的不动点。事实上，对a 上任意的非 空字u ， ( 矗。) ，u ) = ( r r o + s ，u ) = ( r r 0 ，t ) + ( s ，钍) = ( r ，e ) ( r o ，t ) +( r ) ( r o ， ) + ( s ，t ) 叫= u ， = ( ( 伽，t ) ) = ( r 0 ，“) 类似地，对空字e ，我们有 ( j ( 伯) ，e ) = ( r + s ，e ) = ( r e ) ( ，e ) + ( s ，e ) 】9 = ( ( r 0 ，e ) ) = ( r 0 ，) 因此，我们证明了 ，r 5 ( r o ) = r r o + s = r o ， 即r 0 是，r 。的一个不动点。下面我们证明r 0 的最小性。设。1 是，r ，s 的 任意一个不动点。因为，r 。( 。1 ) = 馏1 + s = $ 1 ，则对任意的u 岔，均 有( ，。( 茁1 ) ，“) = 扛1 ，) 。即当t 一e 时， 而当u e 时 ( r e ) ( z l ，e ) + ( s ，e ) = ( 。1 e ) p ，e ) 扛- ，u ) + ( r ，”) ( ，伽) + ( s ，u ) = 如l ，u ) = “， 于是，由伽的定义知对任意的t 小，均有 ( r o ，) s ( 。1 ，t ) 即r 0 是 。的最小不动点。这就完成了定理4 2 的证明- 第五章木一p 一半环和水一a 一半环 5 1木- p - 半环和木- a 一半环的定义 在上一章中我们介绍了* 半环和“半环的概念。在本章中我们将研究满足 特定的附加条件的a 半环和抄半环。首先，我们给出如下的定义： 定义5 1 ：设s 是序t 半环若s 上任意的仿射变换，：s s 茁一+ 6 均有最小不动点蛔，( ) 一口6 ，则称s 为t a 一半环 定义5 2 ：设s 是序屯半环若s 上任意的仿射变换，：s s 嚣ho z + 6 均有最小前不动点肛z ，( 。) = 口6 ，则称s 为半环 命曩5 1 ：若s 是t 似一半环，则s 是t a 半环 证明：设s 是+ 一妒半环。则s 上任意的仿射变换，：s so 一口z + 6 均 有最小前不动点p z ，( 童) = o 。但，是单调映射，那么由第二章中的命题2 1 知卢。，( z ) = 矿6 实际上是，的最小不动点蛔，( z ) 。故s 是+ a 半环。 5 2木- p - 半环和木一a - 半环的基本性质 为了进一步说明如上定义的+ 一肛半环及+ 一* 半环的概念与归纳+ 一半环及弱 归纳+ 一半环等概念之间的关系，我们先看下面的命题。 命最5 2 ：设s 是序t 半环则s 是t 入半环当且仅当s 满足不动点等式 0 0 | + 1 = o + 和弱不动点归纳法则 口z + 6 = z = n + 6 茎茁 证明：设s 是+ k 半环。由定义，对s 上任意的仿射变换，：z o z + 6 ，的 最小不动点存在且a z ，( 。) = n 6 。特别地，矿= a + 1 是仿射变换茁一们+ l 2 1 的最小不动点。由此得s 满足不动点等式d o + + 1 = n 。此外，对任意 的o ，6 ，z s ，若o z + 6 = 。，则。是仿射变换，：zhn z + 6 的不动点。又因 为a z ，( z ) = d 6 ，则立即有n + 6 z ，即s 满足弱不动点归纳法则。 反之，设s 是满足不动点等式和弱不动点归纳法则的序 半环。则对s 上 任意的仿射变换，：z o z + 6 ，由s 满足不动点等式得 ，( n 6 ) = 口( n 砷+ 6 = ( d n + + 1 ) 6 = 口+ 6 故矿6 是，的一个不动点。此外，任给，的一个不动点霉o 。由于s 满足弱不 动点归纳法则，则立即得d + 6 如，故k ，( z ) = b 6 。因此s 是+ 一 一半环。这 就完成了命题5 2 的证明 由命题5 2 易知任意+ 一k 半环满足不动点等式和弱不动点归纳法则。进一 步，我们可以证明如下命题。 龠爱5 3 ：任意t a 串环满足对偶不动点等式，积星等式和如下等式 ( a 6 ) 矿= n ( 乩) 证明：设s 是+ a 半环，则s 满足不动点等式和弱不动点归纳法则。那么对任 意的o s ，我们有 n ( n + 口+ 1 ) + l = ( 口凸+ 1 ) n + l = 矿n + l ， 由弱不动点归纳法则得o + 矿n + 1 。又对任意的o ，6 s ， n k ( 6 a ) + + d = 口( k ( k ) + 1 ) = 口( 6 口) + ， 同样由弱不动点归纳法则得( 口6 ) 口so ( 阮) + 。令其中6 = l ，得矿a o 矿。于 是有 口n + l o o + + l = n + 即s 满足对偶不动点等式。 2 2 接下来，我们证明s 满足积星等式。任取s 中两元素d ，6 。如上所述，我 们已经证明了如下不等式： ( k ) 6 6 ( 曲) 于是有 口( 6 口) + 6 + 1s 6 ( n 6 ) + 1 = ( 口6 ) 故只需证明相反不等式成立但事实上，我们有 0 6 ( n ( 6 n ) 6 + 1 ) + 1 = o ( 6 口( 6 口) + + 1 ) 6 + 1 = n ( b 口) 6 + l ， 则由弱不动点归纳法得( 曲) + 口( 6 6 + l ，这就证明了s 满足积星等式。 最后，由上面已经证明的对偶不动点等式和积星等式，我们有 ( n 6 ) o = ( n ( k ) + 1 = n ( ( 乩) + 6 口+ 1 ) = o ( k ) + ， 这就完成了命题5 3 的证明。 由命题5 2 易知任意弱归纳+ 半环是+ k 半环。事实上，一个+ a 半环s 是弱归纳+ 半环的充要条件是s 满足和星等式( 3 7 ) 。特别地，当s 是交换半 环，即s 的乘法满足交换律时。我们有： 定理5 1 ：设s 是序t 半环若s 的乘法是交换的，则下列命题等价： j s 是弱归纳t 半环 2 s 是t a 半环 证明：如前所述，任意弱归纳+ 一半环是+ k 半环。故只需证明若+ 一a 一半环s 的 乘法是交换的，则s 是弱归纳+ 半环。设s 是+ 一片半环，且s 的乘法是交换 的。由命题5 2 知s 满足不动点等式( 3 3 ) 和弱不动点归纳法则，故只需证明s 满足和星等式。此外，由命题5 3 知等式( 3 4 ) ，( 3 5 ) 以及( 3 6 ) 在任意+ - 一半 环中均成立。那么，由等式( 3 3 ) ，( 3 5 ) 以及( 3 6 ) 可得 ( o + 6 ) ( n 6 ) + 口+ + 1= 口( o + 6 ) + + 6 ( d + + 口+ 1 = n n + ( k + ) + + ( 6 0 + ) ( 施+ ) + 1 = 口口( 6 0 + ) + + ( 乩+ ) = ( + + 1 ) ( k ) + = 矿( k ) + = ( 矿b ) n + 于是由弱不动点归纳法则知 ( n + 6 ) + ( o 6 ) + n ( 5 1 ) 下面我们证明( 5 1 ) 的相反不等式也成立。事实上，由不动点等式可得 ( n + 6 ) ( 口+ 6 ) + + 1 = 口( n + 6 ) + 6 ( n + 6 ) + + 1 = ( d + 6 ) ， 于是，由弱不动点归纳法则得 n + ( 6 缸+ 6 ) + + 1 ) s 扣+ 6 ) + ( 5 2 ) 又因为s 的乘法是交换的，我们有 ( n + 6 ) ( 矿( 6 ( o + 砷+ + 1 ) ) + 1 = ( n + 6 ) ( n ( 0 + 6 ) + 矿) + 1 = ( d + 6 ) 口6 ( 0 + 6 ) + + 矿+ b 矿+ 1 = o + 6 ( + 6 ) ( + 6 ) + + o + + o = 矿b ( 如+ 6 ) ( 口+ 6 ) + 1 ) + 矿 = o + 6 ( o + 6 ) + + 口+ = o + ( 6 ( o + 6 ) + + 1 ) 那么，由弱不动点归纳法则立即得 + 6 ) + o + ( 6 + 6 ) + + 1 ) ( 5 3 ) 2 4 由不等式( 5 2 ) 和( 5 3 ) ，我们有 口( 口+ 6 ) + 矿= 矿( 6 ( o + 6 ) + + 1 ) = ( n + 6 ) + 于是由弱不动点归纳法则知 ( 矿6 ) + n s ( 口+ + ( 5 4 ) 由不等式( 5 1 ) 和( 5 4 ) 知s 满足和星等式，这就完成了定理5 1 的证明。 定理5 2 ：设s 是序t 半环则下列命题等价： j s 是归纳t 半环 2 s 是t “半环 占s 是“一半环和t a 斗环 4 s 是肛半环和弱归纳t 半环 证明：( 1 辛2 ) ：设s 是归纳+ 半环。则s 满足不动点等式和不动点归纳法 则。对s 上任意的仿射变换，：。一n z + 6 ，由s 满足不动点等式得 ，( n 6 ) = n ( n + 6 ) + 6 = ( 口矿+ 1 ) 6 = 矿6 故n 是，的一个不动点，当然也就是，的一个前不动点。此外，任绘， 的一个前不动点知。由于s 满足不动点归纳法则，立即知矿6 知。 故p z ，( 。) = 矿6 。因此s 是+ 一胪半环。 ( 2 辛3 ) ：设s 是+ 一卢一半环。由定义知s 是p 半环。再由命题5 1 知s 是+ a 半环。 ( 3 辛4 ) ：设s 是p 半环和+ 一a 一半环。则只需证明s 是弱归纳+ 一半环。 我们证明s 事实上是归纳+ - 半环。对s 上任意的仿射变换，：茁一口z + 6 ， 由s 是肛半环知，有最小前不动点卢$ ，( 茁) 。而另一方面，由s 是+ 一a 一半环 知，有最小不动点a 。，( 。) = 矿6 。但，是单调的，则由命题2 1 知 p 石，( z ) = a z ，( z ) = o + 6 2 5 特别地，矿= 矿1 是仿射变换z 一口z + 1 的最小前不动点。由此得s 满 足不动点不等式n n +