初始代数与最终余代数：理论计算机科学笔记（2002）

理论计算机科学电子笔记651（2002）网址：http://www.elsevier.nl/locate/entcs/volume65.html最终余代数与任意内函子StefanMilius2Stefan Milius2StefanMilius3;4德国布伦瑞克技术大学理论计算机科学研究所摘要Set的每个内函子F都有一个初始代数和一个最终余代数，但它们是一般的类因此，由F诱导的类范畴的闭函子F1生成一个完全迭代的单子T。任意保护迭代方程组的解。F存在，并且可以在类TY的自然定义的子集中找到。更一般地说，从任何范畴K开始，我们可以在小的上极限下形成K的自由余完备化K1（例如， 集合1是类的范畴），给出了K的任意闭函子得到类似结果的充分条件。关键词：初始代数，nal余代数，完全迭代单子1引言在进程代数中，系统通常以方程的形式描述s =（s1; a1）或（s2; a2）或者：其中s，s1，s2，. . .是状态（来自期望的状态集合S），并且a1，a2，. . .是行动（从一个给定的集合法案）。因此，该系统由标记的跃迁系统：S ！P（S Act）将右手边所有可能对的集合分配给每个状态s。因此表示at递归方程组，其中\at”1 电子邮件：adamek@iti.cs。t u-b s. De2 电子邮件：milius@iti.cs。t u-b s. De3 电子邮件：velebil@iti.c s. tu-bs. de4 谨此感谢捷克共和国赠款机构提供的第201/02/0148号赠款。c 2002年由Elsevier Science B出版。诉1在CC BY-NC-ND许可下开放访问。Adamek，MiliusandVelebil2指的是P只出现一次，不迭代，在右边。该方程组的“解”是通过对应的（扩展的）树对系统状态的描述，直到双相似性为止是唯一的。在许多自然的例子中，非线性方程是很常见的。F或前-对序列X1; 1; 1;：：自然数的形式可以表示为方程x =（1; x）：使用已建立的集合论对概念，这意味着，x=ff1g;f1;x gg对于S = fxg，这具有（非at）迭代方程S！ PP（S + f1g）本文的目的是研究这类方程，并建立解的存在唯一性的一般结果在我们以前的工作[AAV]和[AAMV]中，我们研究了集合的所有\iteratable”endofunctors H的递归方程，即，所有的闭函子使得H（）+ X对每个集合X都有一个nal余代数。这当然排除了重要的函子，如H =P。Larry Moss [M]也考虑了同样的限制本文证明了以前的结果，即每一个有保护的递归方程组都有唯一解，对集合的所有内函子H都能得到证明。技巧是我们将H扩展为类类和类函数的范畴，得到一个本质上唯一的函子H1：Class！ 类保持小的经筛选的余限（=对所有小的基数都经筛选的大余限）.或者，等价地，在Aczel和Mendler [AM]的术语中，一个基于集合的内函子H1;通过他们的最终余代数定理重新调用，H 1（）+X有一个nal余代数，参见[HL]。 那么H1是可迭代的，因此我们可以使用前面的结果，只是从集合移动到类。但更好的是：没有具体的迭代方程系统实际上需要从Set到Class的这种移动！例如，幂集函子P只有在扩展为P1：Class！ 类（将所有子集的类赋给每个类的函子）。P1的最终余代数是余代数B=，其中B是所有可拓树的余代数，是B上的双相似等价（我们在第5下面）。当然，B是一个真类，B=（因为nal余代数是Lambek引理，但P在集合中没有不动点）。然而，在这方面，Adamek，MiliusandVelebil3每个方程组（有一组变量）都有唯一的解，它存在于B的一个自然小余子代数中。这是因为每一个转移系统对于某个基数都是-分支的。因此，它是一个迭代方程态射X！ P X对于基数小于的所有子集的函子P。并且P是可迭代的（在Set中），其nal余代数是P的自然子余代数.这样做的寓意是：对于每一个转移系统，在B=中有唯一的解，并且该解也存在于一个小的子余代数中（可以忽略它，除非你太反对类）。这一切都与P无关。我们证明了对于每个闭函子H：Set！集合中有一个自然的可迭代扩展H1：Class！ 课如果T1Y表示H1（）+Y的一个最终余代数，则H1的每一个含参数的方程组在T1Y中有唯一解. 现在这一切都与塞特无关！对于每一个余完备范畴K，我们构造K的一个扩张K1，使得K的每一个内函子H自然地扩张到K1的一个可迭代内函子H1。我们，守护方程态射在K1中有唯一解.上述的非标记转移系统的情况是引入非良基集合论的动机之一。因此，我们的论文可以被认为是Michael Barr [B]从进程代数中删除非良基性毫无疑问，在这个过程中有一定的优雅损失，但我们觉得损失比预期的要轻。 我们将在第5节中回到这个问题。集合论假设我们基本上只有一个标准假设： 一个宇宙选择了“小”集合，从而形成了所有小集合的范畴。现在假设宇宙本身是某个更高宇宙中的一个（非小）集合，我们可以表示为@1这个集合的基数这使我们能够识别具有基数小于@1的集合的小和类作为集合，基数ty至多为@1。更确切地说，对于集合论者来说，小集合的单位可以是阶数V（@1）的第1个单位. 不过，我们会说设置Adamek，MiliusandVelebil4一X余积基数ty小于@1的所有集合的范畴（等价于V（@1））。我们认为类所有cardinali集合的范畴小于或等于@1。我们称一个范畴K为局部小范畴，如果所有的对象构成一个类，并且每个hom-setK（A; B）都是小的。2迭代函子在本节中，我们回顾了Larry Moss在[M]和我们的小组[AAV]，[AAMV]中独立获得的结果。在本节中，K表示一个具有二元余积的范畴。定义2.1函子H：K！称K是可迭代的，只要对K的每个对象X，TX（1）函数H（ ）+ X存在。实施例2.2(i) 集合的每个多项式内函子H都是可迭代的。这是一个（可能是一个nitary）签名，即，一组具有规定arities ar（）的操作符号，arities是基数。 H赋给每个集合Xar（）：2这里TX是X上所有（nite或in nite）-标号树的余代数。也就是说，树的叶子由零操作符号或来自X的变量标记，内部节点（n个子节点）由n操作符号标记。(ii) 更一般地说，Set的每一个可访问的（=有界的）内函子都是可迭代的。(iii) 幂集函子P：Set ！Set不可迭代。符号2.3通过Lambek引理，结构箭头TX ！最终余代数TX的HT X+ X也就是说，TX是HT X和X的余积。我们表示为X：HT X！ TX （\TX是H-代数”）和X：X！ TX （\TX contains X”）注射副产物Adamek，MiliusandVelebil5BbB、、SS、SSS、、、、、SS置换定理2.4对于每个态射s：X！TY在K中存在同态s：TX的 唯 一 扩 张 ！H-代数的TY也就是说，一个唯一的同态，其中s =sX。关于证明，请参见[M]中的2.4或[AAV]中的2.11（[AAMV]中的2.17有所改进）。推论2.5TX（对所有对象X）和s（对所有态射s：X！TY）是Kleisli三元组。对应的单子（T;;）有[X= idTX：TTX！所有对象的TX。这个单子T称为H生成的完全迭代单子。定义2.6一个（迭代）方程的态射与变量的对象X和参数的对象Y意味着一个态射e：X！ T（X + Y）。例2.7设为两个二元运算+和的签名。迭代方程（一）对应于态射x1 = x2 + yx2 =yX1e：fx1;x2 g！Tfx1;x2;yg由...+，，x17！ss，，ss，x27！ss，，ss，X2 y这个系统有唯一的解x1y，x2y，即+，y x1ss，，s，，，ysssSs、、、、、、y+，sss、、、x1y =ss，，s，，，yx2y=ys、sss，，ssxy，，sss，，是的，ss1，解定义为态射e y：X ！ Ty具有以下性质：如果我们在（1）的右侧将每个xi替换为xiy（并将参数Adamek，MiliusandVelebil6y替换为相应的树Y（y）），则ey仅为该替换的e。Adamek，MiliusandVelebil7BB. . . .你，，置换态射是s= [ey;Y]：X +Y ！ Ty我们利用替代定理将其扩展为s：T（X + Y）！ T Y：因此，解ey是由以下性质定义的态射：XeyTYe. . . .上下班J. .T（X + Y）现在，在每个单子中，我们有s =Y T s，因此，我们得到以下结果定义2.8通过方程态射e的解：X！T（X + Y）表示态射ey：X！TY使得下面的平方XeyTYeYJ上下班T（X +Y）T[ey;Y]T TY注2.9一些平凡的迭代方程，例如，x = x，有很多解。但是“几乎”所有的迭代方程组都有唯一的解。我们不能排除的情况是方程x=x0，其中右边是来自X的变量。现在给出一个方程态射e：X！ T（X + Y）回想一下，T（X + Y）是HT（X + Y）和X + Y的余积|因此，它是一个副产品，X与注射X在 X + YX+YT（X + Y）中，以及HT（X + Y）+ Y+注射[X+Y;X+Yinr]：HT（X + Y）+ Y！T（X + Y）。这是我们要排除的第一次注射。更准确地说，我们希望e通过后一个因子分解：定义2.10方程态射e：X！ T（X +Y）被称为保护的，只要它通过余积注入HT（X+Y）+Y分解！T（X + Y）：XeT（X + Y），，[X+Y;X+Yinr]z轴HT（X + Y）+YAdamek，MiliusandVelebil8解定理2.11每个守护方程态射都有唯一解。有关证明，请参见[M]中的2.11或[AAV]中的3.3（大大改进了[AAMV]中的3.4{3.8））。注2.12特别地，Set（更一般地说，任何局部可表示范畴）的每个可达内函子都是可迭代的，参见[AAMV]。3所有函子都有初代数和终（共）代数本文证明了Set的每个闭函子F都有一个初始F-代数和一个最终F-余代数，但它们可以是类。更准确地说，我们将类别Set扩展为类和类函数的类别Class然后每个函子F：Set！ Set有一个对小型可访问的仿函数F1的唯一扩展：Class！类（定义见下面的3.1和3.6），并且存在初始F1-代数I和最终F1-余代数T。此外，T由nalityw.r.t. 集合中的所有（小）F -代数对于满足下列假设的一般范畴K，所有这些都是正确的(1) K具有小的共极限（即， K是共同完成的）(2) K是（小）cowellpowered和(3) K是局部小的（即， K的对象构成一个类，K（A; B）是所有对象A，B的小集合。我们形成一个自由的共同完成K1关于KW.R.T.较小的滤过性大肠杆菌限值（见3.1）。可以描述共完成K1（类似于自由共完成Ind（K）w.r.t.Grothendieck [AGV]）作为K.主要的例子是Class=Se t1，参见3.7。则K的每一个内函子F唯一地直到自然同构地扩张到K1的一个小可达（见3.1）内函子F1，并且F1有一个初始代数和一个最终余代数。这两个性质有本质的区别：对于初始F1-代数，I，w是模I = colim F（i） 0i2Ord自然地扩展了众所周知的公式I= colim F（n）0，对于F！-共连续的N2！也就是说，我们在初始对象上，0，@1-manny次（其中，回想一下，@1是第一个大序数，因此，@1是一个弱序类，恰好与所有小序数的类Ord相同），我们得到初始F1-代数。Adamek，MiliusandVelebil9\使得nal F -余代数的正确公式是相反，公式T = lim F（n） 1，对于F！-连续N2！不延伸到T = limi2Ord F（i） 1。这有两个原因：transnite极限不一定存在，如果存在，它不一定是终结F -余代数。然而，对于K=Set，我们使用James Worell [W]的思想来表明，通过形成极限，F（@1）1=limF（i）1的良序范畴。则（Ord+）1是Ord+y的扩张，Adamek，MiliusandVelebil12元素，u，满足i u> for all i 2 Ord.引理3.8每一个局部小的，具有小余限的余幂范畴K在K1中的小余限下是有限的，并且K1具有类索引的d余限（即，diagram 概型中至多 有@1个态射的极限）和满态射的任意多重推出。证据第一个陈述是平凡的，因为K的对象在K1是小可表示的（参见注3.5（a），还记得在小余完备范畴中幂等元分裂）。第二个语句要求只显示K1有小的上极限：因为它有小的经筛选的上极限，那么它有类索引的上极限（给定类索引图D，考虑D的所有小子图的上极限图的小的经筛选的上极限;这是D的上极限小余积在K1中的存在是明显的，因为K1的对象是K的对象的小余限：给出一个小余图Di：Di的小集合！ K1（i2I），形成小网格图Q DiKIK;其中第二部分取K的余积。它的余极限是余极限Di在K1中的余积。类似于c o均衡器：给出一个平行对f;g：colimD！ColimD0inK1，其中D，D0在K中是小的，我们可以和自然变换fi;gi：Di！ 其中f=colimfi和g=colimgi. 通过形成c 0均衡器ci：D0ji！ D0 0i在K中，我们得到一个小的图D 0 0在K中和一个自然变换（ci）：D 0！ D 00。很容易看出，Colim c i是f和g的余均衡器。满态的多重推出的存在性被证明类似于局部可表示范畴是余幂的证明，见[GU]的Theo-rem 2.142注3.9每一 个 F-余代数也 是一个F1-余代数（因为对 所 有 A2 K ，FA=F1A）. 并且每个F1-余代数都是F -余代数的小序余极限. 这已经在[AP1]中得到证明（参见定理IV.2应用于=@1）。3.2初代数与终余代数注3.10设K是一个局部小的、上同幂的范畴，其上极限很小。 利用引理3.8，对每个闭函子F和每个F1-余代数A，存在A上的最大同余，即.例如，a同态e：A！A是由K的满同态所携带的F1-余代数，它满足所有其它满同态f：A！B有一个因子分解f：B！其中f= e。(Viz.、e是所有f的多重推出。定理3.11设K是一个局部小的、具有小极限的余幂范畴。F或K的每一个闭函子F，初始F1-代数a，I，存在，在QDiAdamek，MiliusandVelebil13 一F1I=colim F（i+1） 0 = colim F（i） 0一事实I = colim F（i）0;i2Ord其中0是K中的初始值，Ord是所有小序数的链还有一个nalT = AA2煤 F是所有F -余代数模最大同余的余积的商。备注。关于T的存在性的陈述是[AM]的最终余代数定理的推广，也参见Barr的论文[B]证据（1）在[Ad]的基础上定义了一个序链F（i）0（i2 Ord），其上有连通态射wij：F（i）0！F（j） 0（i;j2 Ord，ij）在K中通过以下Ord上的transnite归纳：F（0）0 = 0; F（1）0 = F 0;且w 01：0！ F 0是唯一确定的。对于孤立步骤，给定F（i） 0和wij，F（i+1） 0 = F（F（i） 0） 和 wi+1;j+1 = F wij：对于极限步骤，假设j是一个小的极限序数，使得链（F（i） 0）i j已经被定义。放F（j） 0 = colim F（i） 0I j加了一个科莱米特可可酮w ij：F（i）0！F（j）0（i

下载后可阅读完整内容，剩余1页未读，立即下载