无限树与迭代：单子、余代数和温和边条件下的完全迭代monoid

1《理论计算机科学电子札记》44卷第1期（2001）网址：http://www.elsevier.nl/locate/entcs/volume44.html26页无限树与迭代Peter Aczel1曼彻斯特大学数学与计算机科学系，联合王国Jir'Ad'amek2，4技术大学理论计算机科学研究所德国布伦瑞克Jir'Velebil3，4捷克共和国摘要无限树的代数是，如C。Elgot，完全迭代，即， 所有理想递归方程都是唯一可解的。 本文证明了这是一个普遍的余代数现象：设H是一个闭函子，使得对于每个对象X，存在H（）+X的最终余代数TX. 则TX是一个完全迭代的单子的对象部分。此外，在满足温和边条件的任何monoidal范畴中，类似的“完全迭代monoid”的逆是可能的关键词：单子，余代数，monoidal范畴1 电子邮件地址：petera@cs.man.ac.uk2 电子邮件地址：adamek@iti.cs.tu-bs.de3电子邮件地址：velebil@math.feld.cvut.cz4.捷克共和国赠款机构根据第2000/2001号赠款提供的支助201/99/0310是感激的承认。2000年1月，出版社dbyElsevierScienceB。 V.操作访问和C CB Y-NC-ND许可证。ACZEL，ADA`MEK，VELEBIL21介绍有各种代数方法可以通过给定的程序来形式化数据的计算，考虑到这种计算可能是无限的。70年代，ADJ群提出了连续代数，即，代数建立在CPO的，使所有的操作是连续的。这里，无限计算是所有有限近似的有向集的连接，参见例如[7]。后来，人们考虑了完备度量空间上的代数，其中无限计算是有限逼近的柯西序列的极限，见例如。[6]。在本文中，我们证明了一种共代数方法可以在没有任何额外（总是有点随意）结构的情况下研究有限计算-也就是说，我们可以简单地在集合范畴Set中工作我们使用一个简单而众所周知的事实：对于集合的多项式内函子H，所有（有限和无限）正确标号树的代数是最终H-余代数。好吧，这是不够的：我们需要的是与给定一个变量集合X，我们处理树，树的内部节点由操作标记，叶子由变量和常量标记这又是一个最终余代数：不是对于原函子，而是对于函子H+CX：设置−→设置其中CX是值为X的常数函子。 我们将展示对于每个多项式函子H：Set−→Set(a) 函子H+CX的最终余代数TX形成一个单子，称为由H生成的完全迭代单子，(b) 每个TX上的H-代数也有一个标准结构，所有这些标准H-代数构成完全迭代单子的Kleisli范畴，和(c) H-代数TX具有所有递归方程理想系统的唯一解。一个令人惊讶的特点，我们证明的结果是它的一般性：这与多项式的H，也没有与基范畴集。事实上，给定一个具有二元余积的范畴ffi的内函子H，并假设每个H+CX都有一个最终余代数，则（a）-（c）成立。此外，完全迭代单子T：ffi −→ ffi，作为内函子范畴[ffi，ffi]的对象，是[ffi，ffi]的以下闭函子H^的最终余代数H^（B）=H·B+1A对所有B：ffi−→ffi。现在[ffi，ffi]是一个monoidal范畴，它的张量积是复合，单位I是1A。 并且H生成的完全迭代单子是么半群在[ffi，ffi]中。因此我们转向更一般的问题：给定一个monoidal范畴B，我们称一个对象H是可迭代的，只要内函子H^：B−→Bgi venbyH^（B）=H<$B+I有一个最终余代数T。假设ACZEL，ADA`MEK，VELEBIL3，，−→]B的二元余积与张量积分布在左边，我们推出T具有幺半群的结构，称为由对象H生成的完全迭代幺半群。回到集合的多项式内函子：上面（c）中提到的方程的解涉及到20世纪70年代广泛研究的一个主题C. C. Elgot [11]，J.[2018 - 07 - 18][2019 - 07][2019 - 07 - 19][2019 - 07] 19：00]X和Y是不相交的变量集，并考虑以下形式的方程：x0= t0（x0，x1，x2，.， y0，y1，y2，.. . ）x1= t1（x0，x1，x2，.， y0，y1，y2，.. . ）.其中xi是X中的变量，yj是Y中的变量，而ti是使用这些变量的树。遵循Elgot，我们称这个系统为理想系统，前提是每棵树ti都不同于任何变量，更确切地说，t i∈T（X+Y）\η [X+ Y]，对于每个i= 0，1，2，.然后证明该系统在TY中具有唯一解。也就是说，存在唯一序列si（y0，y1，y2，. . ）TY中的树，其中以下等式s0（y i）= t0（s0（y i），s1（y i），.，我，.. . ）（一）s1（y i）= t1（s0（y i），s1（y i），.，我，.. . ）.稍等 用范畴表示，理想方程组是态射e：X−→T（X+Y）通过H-代数结构τX+Y：HT（X+Y）−→T（X+Y）上文（b）段所述XeT（X+Y）......(2)、、、，τz，HT（X+Y）e的解由一个态射e†：X−→TY下面的图表Xe†T Y（三）eµYJT（X+Y）T[e]，ηYTTY上下班 (Here，µY：TTY TY是完全迭代单子的乘法。在多项式函子的情况下，这需要一个正确标记的X+YACZEL，ADA`MEK，VELEBIL4∈XX树的叶子再次正确标记的树，它提供了通过忽略内部结构获得的正确标记的树。事实上，态射T[e<$，ηY]取一棵树，其叶子上的变量来自X+Y，用解树e<$（x）代替变量x 的每次出现X.（三）平等，即平等。e<$（x）=μY·T[e<$，ηY]（e（x））对于所有x∈X与上述条件（1）完全一致。现在，在这个范畴公式中，我们可以再次忘记多项式性和集合：如果H对所有函子H+CX都有最终余代数，那么我们证明每个理想方程态射e：X−→T（X+Y）都有唯一解，即，一个唯一的态射e<$：X−→TY，其中（3）是可交换的。相关工作。在完成我们的论文的当前版本之后，我们发现L.”[15]在《易经》中，他的《易经》是《易经》。2闭函子的完全迭代单子假设2.1在本节中，H表示范畴ffi的一个有有限余积的内函子。只要有可能，我们就用inl：X−→X+Y和inr：Y−→X+Y第一次和第二次联合产品注射。注2.2对于函子H（）+CX：ffi−→ffi也就是说，对于H与CX（值X的常数函子）的余积，众所周知，初始（H+CX）-代数X上的无环H(See[4]）更准确地说，假设FX与αX：HFX+X−→FX是一个初始（H+CX）-代数。αX的分支构成H-代数<$X：HFX−→FX和通用箭头η0：X−→FX。也就是说，对于每个H-代数HA−→ A对于每个态射f：X−→A，存在唯一的同态H-代数的f：FX−→Af=f·η0。ACZEL，ADA`MEK，VELEBIL5−→×≡˜例2.3集合的多项式内函子这些是形式的闭函子HZ = A0+ A1×Z + A2×Z×Z +. =An×Znn ω哪里A=（A0，A1，A2，. . ）是成对不相交的集合的序列，称为签名。初始H-代数可以描述为所有有限标号树的代数在这里，一个带标号的树t由一个部分函数t：ω−→Ann ω它的定义域D t是ωn（自然数的所有有限序列的集合）的非空且预闭的子集，使得对于任何i1i2. i r∈ D t，其中t（i1. i r）∈A n，我们有i1i2. i r i∈D t我的I n（对于所有i ω）。现在函子H+CX也是签名因此，我们认为，X=（X + A0，A1，A2，. . ）的。FX可以被描述为所有有限的X-标号树的代数备注2.4(i) 通过对偶化自由H-代数的概念，我们可以研究余自由H-余代数.在ffi的对象X上的一个上自由H -余代数就是在ffi op中X上的一个自由Hop-代数，其中H op：ffiopffiop是明显的闭函子。如果FFI有有限个产品，那么通过对偶2.2，我们可以看到，X上初始（HCX）-代数余自由H-余代数例如：设H是Set上的多项式函子。然后H× CX也是多项式函子，因为（H×CX）Z=X×A n× Z n。n ω这是签名X=（X×A0，X×A1，X×A2，. . ）的。一个上自由H-余代数可以描述为所有（有限和无限）的X-标号树的余代数T X因此，每个节点被标记为（i）来自An的操作和（ii）来自X的变量。ACZEL，ADA`MEK，VELEBIL6X(ii) 除了X上的一个自由H-代数和一个余自由H-余代数之外，我们还有一个与X相关联的第三种结构：H+CX的一个最终余代数。我们将证明它有一个重要的普适性质。定义2.5ffi的内函子H称为可迭代的，条件是对于ffi的每个对象X，H+CX有一个最终的余代数。记法2.6LetTX表示H+CX的最终余代数。余代数映射αX：TX−→H（TX）+X根据Lambek引理[13]，它是一个同构。因此，我们有TX=H（TX）+X联产品注射τX：H（TX）−→TX 和ηX：X−→TX其中[τX，ηX] =α−1：H（TX）+X−→TX。特别地，TX是经由τX的H-代数。我们也可以用期望的方式在ffi的态射f：X−→Y上定义T：我们把TX变成下面的H+CY型余代数：TXαX H（TX） +Xid +fH（TX） +Y并表示为Tf：TX−→TY余代数的唯一同态αXid+f德克萨斯州，，[τX，ηX]TFH（TX）+XH（TX）+YHTf+idJαYJ泰，，[τY，ηY]H（TY）+Y也就是说，Tf是唯一的态射，使得以下平方HTXτX T XXηX T XTFTF TFTFJJ JJ通勤。不久，HTYτY T YYηY T YTf是扩张f的H-代数的唯一同态.很容易验证（由于唯一性）我们得到一个定义良好的函子T：ffi−→ffiACZEL，ADA`MEK，VELEBIL7^˜和自然的转变η：1A−→T例2.7连续函子是可迭代的。这里我们假设ffi具有1. 终端对象12. ωop序列的极限3. 与ωop-极限假设H是ωop-连续的，即，保持ωop-limits。由于3.，所有函子H+CX是ωop-连续的，因此，有一个最终余代数（见[2]）TX = lim（H + CX）n 1。n ω注意函子T也是连续的：事实上，正如我们将在第4节中看到的，T是函子H^：[ffi，ffi]−→[ffi，ffi]在对象上定义为H^（B）=H·B+1A对所有B：ffi−→ffi。Nw[ffi，ffi]满足1.a是连续的，T= limHn（C1）.n< ω这是连续函子的极限，是连续的。例2.8集合的多项式内函子它们是连续的，因此是可迭代的。 最终余代数TX多项式（Polynomial！签名为X的函子H+CX是所有X-标号树的代数。也就是说，不像余代数T X在所有带X-标号的树中，见2.4，其中每个节点带有一个来自X的标号和一个来自An的标号（对于n个孩子的情况），TX中的树有一些节点标记为An，除了叶子：它们标记为X+A0。作为一个具体的例子，考虑一元签名：HZ = A× Z。我们为变量集X定义了三个代数：自由代数FX=A×X在所有的有限树中，对于k=（k，A，k，k， . . . ），余自由余代数TX=（A×X）∞ACZEL，ADA`MEK，VELEBIL8−→−→（其中（）∞表示给定alpha- bet中所有有限和无限词的集合），以及代数TX=A×X+Aω（其中（）ω表示给定字母表中所有无限词的集合例2.9广义多项式函子我们想包括函子，如HZ=ZB，其中B是一个（不一定是有限的）集合：因为这些函子是连续的，TX的描述与前面的情况非常相似。这里我们引入一个广义签名作为集合=（Ai）i∈Card由所有基数索引的两两不相交集合，使得对于某些基数，λ我们有i≥λ意味着Ai=λ。(We假设λ是λ元广义签名;λ=ω的情况是上述情况。）广义签名的广义多项式函子在对象上定义为：和类似的关于态射。HZ=Aj×Zjj λ最后一个余代数又被描述为所有带标号树的余代数，即，部分映射t：λ−→Ajj λ定义在λ的非空的，预定闭子集D t（所有小于λ的序数的有限序列的集合）上，使得对于所有i1i2. i r∈D t，其中t（i1i2. i r）∈A j，我们有i1i2. i r i∈D t我的I j（对于所有i λ）。由于H+CX是签名<$X的广义多项式函子，由<$A通过将A0变为X+A0而得到TX是所有（有限和无限）的X-标号树的余代数。注2.10记U：H-代数为所有H-代数和H-同态范畴的遗忘函子.自由H-代数<$X：HFX FX的泛性质（假设它们存在于ffi的所有对象X上）使U成为右伴随。左伴随是函子X→（FX，X）.给出了H-代数τ X：HTX −→TX的一个相关的普适性质：给定态射s：X−→TY，证明了扩张s的H -代数存在唯一的同胚s^：TX−→TY. 这真有趣ACZEL，ADA`MEK，VELEBIL9^^+YX Y甚至对于Set的多项式内函子的基本情况：这里，一个态射s：X−→TY可以被看作是一个替换规则，用一个带Y-标号的树s（x）替换一个变量x∈X很明显我们有个同性恋-phisms^：TX−→TYextendings：takeeatreet∈TX，substituteevery变量x∈X在t的任意叶子上，通过树s（x）得到一棵树tJ=T s（t）∈TTY超过TY。现在忘记tJ是一棵树的树，并在TY中得到一棵树s（t）。然而，这样的同态是唯一的并不明显。这就是我们现在所证明的：代换定理2.11对于ffi的每个可迭代内函子H和任何态射s：X−→TYinffi存在唯一的同态扩张s^：TX−→TYH-代数也就是说，一个唯一的同态s：（TX，τ X）−→（TY，τ Y），其中s=s^·ηX。证据我们将TX+TY化为H+CY型余代数，如下所示：TX+ TYαX+αYH TX+ X + HTY + Yβ H（TX+TY）+Y其中β的分量（从左到右由β1、β2、β3和β4表示）如下：HTXHinlJH（TX+TY）XS JTyαYHTYJHTYHINR JH（TX+TY），，Y，，，，，，，inl，，，，Hinr+id、、，，，，，，，，，INL，zJ，o，s，H（TX+TY）+YINR存在唯一的同态α+αTX+TY，，H（TX）+X+HTY+Y[τX，ηX]+[τY，ηY]Fβ H（TX+TY）+YHf+IDJαYJ泰，，[τY，ηY]HTY+Y（H+CY）-余代数 等价，唯一态射f=[f1，f2]：TX+TY−→TYACZEL，ADA`MEK，VELEBIL10TyY^−→在FFI中，以下两个正方形HTX+X[τX，ηX]T X[β1，β2]JHTY+Y[τY，ηY]TYH（TX+TY）+Yf1和Hf2+idF2JJHf+ID JJHTY+Y[τY，ηY]HTY+ Y[τY，ηY] T Y通勤。右边的正方形表明f2是最终（H+CY）-余代数的自同态-因此，f2= id。左边的正方形等价于下面两个正方形的交换性（回忆一下β1和β2的定义）：HTXτX T XXηXT XSJTyHF1 Jf1和αYf1JJHTYτY T YHTY+YHf2+id JJHTY+YTY[τY，ηY]左边的正方形告诉我们f1是H-代数的同态和由于f2=id（因此Hf2+id=id），且α−1= [τY，ηY]，右状态f1·ηX=s，即，f1扩展s。这证明了有一个独特的将s推广到同态：设s = f1。✷推论2.12设K表示H-Alg的全子范畴，H-代数（TX，τ X），其中X在ffi.函子n：ffi−→K，X<$→（TX，τX）左伴随于健忘函子U/K：K −→ ffi，（TX，τ X）›→ TX。这个附加物定义了单子在ffi。T=（T，η，μ）事实上在替换定理的符号，自然变换μ：TT T恰好是µY=i^dT Y ：T（TY）−→TY。定义2.13上面的单子T，与任何可迭代的内函子H相关联，称为由H生成的完全迭代单子。ACZEL，ADA`MEK，VELEBIL11∈、、、⊥⊥−→、、、示例2.14(i) 内函子生成的完全迭代单子HZ=A×Z集合是单子TX = A×X + A ω。这可以被描述为代数簇的自由代数单子，(a) 一元运算oa对于a A，(b) 由Aω索引的零操作（即，名称的常量a0a1a2. A ω），和(c) 满足方程o a（a0a1a2.. . ）=aa0a1a2.对于所有的a，a0，a1，. ∈A在这种情况下，T是集合上的无穷单子。(ii) 内函子生成的完全迭代单子HZ=Z×Z是所有叶子索引在X中的二叉树的单子TX。这不是无限的：考虑T的以下元素：、、x1，x2，X3其中所有xi都是两两不同的。(iii) 让、4CPO表示CPO的范畴那些保存和ω-链的连接对于所有局部连续函子H：CPO CPO，即，使得导出的函数CPO（A，B）−→CPO（HA，HB），f›→Hf都是连续的，众所周知，初始H-代数是最终H-余代数，见[17]。由于每个H+CX也是局部连续的，我们推导出局部连续函子是可迭代的，并且在这种情况下外汇交易也就是说，完全迭代单子T就是自由代数单子H的F。∈XACZEL，ADA`MEK，VELEBIL12−→−→˜（b）tx=tx，(iv) 类似地，CMS所有完备度量空间和压缩的：每个局部压缩的内函子H：CMS−→CMS，即，使得导出的函数CMS（A，B）−→CMS（HA，HB），f›→Hf都是收缩的，有一个共同的常数1，有一个固定点，即，<初始H-代数最终H-余代数，见[6]。由于每个H+CX也是局部压缩的，我们再次得到T = F。备注2.15(i) Kleisli类别FfiT−→ Ffi是所有H-代数τX：HTX TX（及其遗忘函子Kffi）的上述范畴K。这是由替代定理得出的。(ii) Eilenberg-Moore范畴FfiT−→ FfiT-代数和T-同态的一个新的构造。如2.14所示，它通常是无限的。例如如果H：设置−→设置，HZ=Z×Z不我们可以描述Set作为二元运算tion（比方说，n）和ω进制运算t（x0，x1，x2，.. . ）对于所有在有限的树木t（x0，x1，x2，. . ）在T {x n|n <ω}满足以下等式：(a) xt=xt，和（c）t（t=0，t=1，t=2， . . . 如果s是由y替换ti得到的树，i< ω，转化为t（x0，x1，x2，.. . ）.3解定理在上面的介绍中，我们提出了以下几点定义3.1设H是ffi的可迭代内函子。(i) 通过方程态射，我们理解FFI中的态射具有以下形式e：X−→T（X + Y），X，Y是ffi的对象。(ii) 一个方程态射被称为理想，如果它分解通过τ X+Y：HT（X + Y）−→ T（X + Y）。ACZEL，ADA`MEK，VELEBIL13，，∈、、、、(iii) 一个方程的解-态射e是态射e†：X−→TY这样，下图Xe†T YeµYJ上下班T（X+Y） T[e]，ηYTTY]示例3.2(i) 考虑下面的内函子HZ=A×Z关于SetwithTX =（Aω×X）+A ω。唯一有趣的方程是x = a1a2. 的n×为 一 单词a1a2... 一个人。这个方程是理想的，如果这个词是非空的。它有一个独特的解决方案：et（x）= a1a2.一个一个二...一个一个二...一个...∈A ω。(ii) 对于函子HZ=Z×Z在集合上，我们把叶子标在X上的所有二叉树的代数记为TX。考虑以下方程组eX1=X2=、、、x2y1、、、x1y2它是理想的。 唯一的解决方案是、、、，， y1e†（x1）=、，，y2、、、y2y1、、、，， y2e†（x2）=、，，y1，， y2y1定理3.3设H是可迭代的内函子。则每个理想方程态射都有唯一解。ACZEL，ADA`MEK，VELEBIL14、、，Σ证据 设e：X −→ T（X + Y）是一个理想方程态射，用e0：X−→HT（X+ Y）表示一个态射，使得三角形X，， 、、、e、eT（X+Y）......，τ，，，z，，X+YHT（X+Y）上下班我们将使用最终（H+CY）-余代数的定义来定义态射h：T（X+Y）+TY−→TY。为此，我们必须首先定义一个（H+CY）-余代数γ：T（X + Y）+TY−→H。T（X+Y）+TY+Y在T（X+Y）+TY上。态射γ被定义为复合T（X+Y）+TYαX+Y+αYH T（X+Y）+X+Y+HTY+YH其中δ的分量如下：δJT（X+Y）+TY +YXe0级 JHT（X+Y）Hinl.JHT（X+Y）Hinl.JH T（X+Y）+TYYINRH T（X+Y）+TY、、INLHTY+Y......，，INL，。，z_、J，S，THinr+idY用h表示（H+CY）-余代数的唯一同态T（X + Y）+TYγH.T（X+Y）+TY+YhHf+idYJHTYJ放：TYαY+Yh1=h·inl：T（X+Y）−→TY和h2=h·inr：TY−→TY上述正方形的交换性（因为αX+Y+αY与[τX+Y，ηX+Y] +[τY，ηY]相反）等于以下四个边的交换性、、H T（X+Y）+TY+Y0.ACZEL，ADA`MEK，VELEBIL15Ty−→图表：HT（X+Y）τX+YT（X+Y）（四）Hh1h1J J公司简介XinlX+YηX+YT（X+Y）e0级（五）JHT（X+Y）Hh1h1JHTYINLJJHTY+Y[τY，ηY]T YYinrX+YηX+YT（X+Y）（六）印度卢比h1JJHTY+Y[τY，ηY]T Y[τY，ηY]（七）HTY+YHh2+idYTYH2JJHTY+Y [τY，ηY]平方（7）断言h2是最终（H+CY）-余代数的自同态，即，h2= id TY。图（4）告诉我们，h1是H-代数的同态，因此，根据替换定理，h1由下式唯一确定：h1·ηX+Y：X+Y−→TY。最后一个态射由它的第一个分量s：XTY，因为使用图（6），我们得出结论，h1·ηX+Y的第二个分量是ηY（=[τY，ηY]·inr）。即h1·ηX+Y=[s，ηY]或等价地H ^1=[s，η Y]。最后，图（5）断言，s=h1·ηX+Y·inl=[τY，ηY]·inl·Hh1·e0=τY·Hh1·e0=h1·τX+Y·e0=h1·e其中我们使用τ的自然性和上面的三角形。ACZEL，ADA`MEK，VELEBIL16^^^我们证明了存在s：X−→TY，s=h1·e ^=[s，η Y]·e.此外，这个s由h= [h1，idY]唯一确定，因此s由e唯一确定。✷4对象的完全迭代幺半群我们可以通过在闭函子范畴[ffi，ffi]中工作而不是在给定的范畴ffi中工作来全局地观察第2节的过程。这里H是一个对象。如果H是可迭代的，那么它定义了另一个对象T和一个态射（自然变换）。α：T−→HT +1 A。这是函子H^：[ffi，ffi]−→[ffi，ffi]在对象上定义为H（S）=H·S+1A（对所有S：ffi−→ffi）和类似的关于态射。下面我们证明T是最终H-余代数。在具有余积的局部小范畴的范围内，我们现在证明，这种整体方法与第2节的方法是等价的命题4.1设ffi是一个有上积的局部小范畴。那么，对于每个闭函子H，下列等价：(i) H是[ffi，ffi]的可迭代对象，即， 存在最终H-余代数。(ii) H是一个可迭代的内函子，即， 所有的最终（H + CX）-余代数都存在.备注。 证明（ii）蕴涵（i）对所有具有二元余积的范畴ffi成立。为了证明（i）蕴涵（ii），只使用了由范畴ffi的hom-set索引的上幂。因此，这个命题也适用于任何偏序集ffi和有限集合的范畴ffi=Setfin证据 （i）蕴含（ii）：对于ffi中的每对对象X，Y，记为KX，Y以下闭函子KX，Y A=YA（X，A）对于对象A，类似地对于态射。 这只是Y的一个左Kan扩张，被认为是沿着X：1−→ffi的函子1−→ ffi。事实上，对于每个函子P：ffi−→ffi，我们都有一个双射KX，Y−→PY−→PXACZEL，ADA`MEK，VELEBIL17−→一−→^在P中自然，它对每个自然变换KX，YP赋予复合YuA（X，X）YXPX其中u是idX-注射。相反，给定态射f：Y−→PX，相应的自然变换f@：KX，Y−→P具有分量f@：.Y−→ PAh：X−→A由YfPXPhPA测定。设α：T−→HT+1A是一个最终H^-余代数. 我们要展示的是αX：TX−→HTX+X是每个X的最终（H+CX）-余代数。事实上，对于每个（H+CX）-余代数，b：Y−→HY+X当组成B时，Hu + id：HY + X−→ H。A（X，X）Y+X=.H^KX，Y+1AX我们得到一个态射Y−→。H^KX，YX这是由于伴随性产生了一个H^-余代数<$b@：KX，Y−→H^KX，Y.设H^-余代数的同态是唯一的KX，Yb@ H^K^HJJTαH T那么对于唯一的f：Y TX，则f =f@YbHY+XHf+idXJJTXαX HTX+X(ii)暗示（i）：上面已经指出（见2.6），如果α X：TX−→HTX+X表示H+ C X的最终余代数，则赋值X<$→TX可以推广到函子T：ffi −→ffi。类似地，我们可以证明所有α X的集合构成一个自然变换α：T − → H · T + 1A。 因此，α使T成为H^-余代数。X为ohϕACZEL，ADA`MEK，VELEBIL18−→一···为了证明α确实是最终H^-余代数，考虑一个ny余代数，β：S−→H·S+1A。对于ffi中的每个X，存在唯一的态射fX：SX−→TX使得平方SXβX HSX+XfXHfX+idJJTXαX HTX+X上下班很容易证明，f X的集合在 X 中 是 自 然 的 ， 并 且 它 定 义了 一 个 唯 一 的 自 然 变 换 f ： S T ，SβHS+1Hf+idJHTJTα+1A上下班✷现在[ffi，ffi]是一个monoidal范畴，其合成为张量积，1A为单位.此外，组成分布与左边的副产品：（H+K）L=（H L）+（K L）。这使我们考虑任意monoidal范畴（B、B、I）具有相干同构（对于B中的所有H，K，L）：lH：IH−→H rH：HI−→H和aH，K，L：H<$（K<$L）−→（H<$K）<$L满足通常的定律，并在以下意义上分配：定义4.2(i) 一个monoidal范畴称为左分配的，如果它有二元余积和标准态射dH，K，L：（H<$L）+（K<$L）−→（H+K）<$L都是同构的(ii) 一个monoidal范畴B的对象H被称为可迭代的，只要内函子H^：B−→B定义为yH^（B）=H<$B+I有一个最终的余代数。(iii) 每个对象都可迭代的左分配monoidal范畴称为 可迭代的类别。示例4.3ACZEL，ADA`MEK，VELEBIL19·^−→−→ −→·(i) 类别连续[集合，集合]连续内函子（即，的那些保持ωop-极限）是可迭代的：我们知道连续函子在(a) 合成（此处：张量积）(b) 单位函子（这里：单位I）和(c) 有限的副产物，故，《易经》是一部《易经》，《易经》是一部《易经现在，正如在2.7节中所观察到的，每个连续函子都是可迭代的，并且完全迭代的单子也是连续的;因此Cont[Set，Set]是一个可迭代的范畴。(ii) 更一般地说，Cont[ffi，ffi]是每个类别的可迭代类别ffi满足条件1.-3. 例2.7。(iii) 类别翅片[套件，套件]所有集合的无穷内函子（即，这些保留过滤colimits）是一个可迭代的类别。事实上，有限函子在复合、恒等函子和有限余积下是封闭的，因此，Fin[Set，Set]是[Set，Set]的分配monoidal子范畴。存在无穷函子H的完全迭代单子T，因为无穷函子总是有无穷余代数，见[8]，定理1.2，并且每个H+CX显然是无穷的。然而，这个单子很少是无穷的，见2.14。(ii)以上我们可以形成Set上的每个单子T的有限部分Tfin（见[14]）：它是通过将底层函子T限制到有限集合的全子范畴Setfin，然后沿着Setfin在Set中的嵌入形成T /Setfin的左Kan扩张而获得的。很容易证明Tfin是闭函子H·（）+ 1组鳍[Set，Set]。实际上，给定任何余代数S−→H·S+ 1集（当然是在S有限的情况下）唯一的H-同态f：S T很容易通过规范态射m：T fin进行因式分解T.也就是说，我们有一个唯一的fJ：ST fin，其中f= mfJ。和FJ是函子H（）+1集的余代数的唯一同态，被认为是Fin[Set，Set]的内函子示例：functorH：设置−→设置HZ=Z×Z具有完全迭代单子T，其中TX是所有二叉树，其叶子索引在X中。而Tfin是无穷单子，其中Tfin X是所有二叉树，其叶子索引在X的有限子集中。(iv) 更一般地说，如果FFI是一个局部有限可表示范畴（见[5]），那么ACZEL，ADA`MEK，VELEBIL20^^H（H！+ id）+id⊗^Fin[ffi，ffi]是ffi的无穷内函子范畴，是可迭代的。论证是相同的：我们在[ffi，ffi]中形成一个完全迭代的单子T，它由[8]中的定理1.2存在（尽管是为集合而制定的，但它在所有局部可表示的范畴中都成立），然后取一个有限部分Tfin，就像上面的（iii）一样。(v) 在形式语言理论中，我们研究了由完全格exp（Γ）的所有子集构成的幺半群范畴B（对于基本字母表Γ）。这里L1L2=语言L1和L2的连接和L1+ L2=语言L1和L2的并集。每个语言L都是可迭代的，T=L（Kleene star）。(vi) Kleene代数，cf. [12]，是分配对称monoidal范畴（B，n，I），其中B是一个联半格，使得每个内函子H=H（）+I都有一个最小不动点Hn。这与我们的概念密切相关，只是我们关心的是最大的固定点。由于Kleene代数的基本动机是形式语言的前一个例子，并且由于这个例子具有H=H（）+I的性质，总是有一个唯一的固定点，最小或最大的选择似乎是相当任意的。(vii) 设B有一个终端对象1和ω op -链的极限，ωop -链与张量积和二元余积都可交换.那么每个对象H都是可迭代的，T是以下可数链的极限1，，！H1 +I，，H！+ IDH（H1+ I）+I，，.例如：以二进制积为和终端对象I为单位的集合范畴是可迭代范畴：（多项式）函子对于每个集合H都有一个最终余代数。H^（Z）=H×Z+IT=H∞而所有小类中的闭类Cat是一个可迭代范畴 每个小范畴H都是可迭代的，T = 1 + H+（H×H）+. +Hω(viii) 设H是一个可迭代的阿贝尔群（这里我们考虑所有阿贝尔群的范畴Ab具有通常的张量积）。则H的最终余代数是给定monoidal范畴中的monoid，如下面4.6节所示，因此，在本例T是戒指。