代数紧函子与余代数的关系

CC理论计算机科学电子笔记264（2010）47-62www.elsevier.com/locate/entcs关于代数上的余代数阿德里安娜·巴兰1布加勒斯特理工大学数学系亚历山大·库尔茨莱斯特大学计算机科学系摘要我们推广了Barr关于函子的集合单子M的Eilenberg-Moore代数范畴作为提升。作为应用，我们引入了关于单子M的内函子交换对的概念，并证明了在合理的假设下，其中一个内函子的最终余代数可以作为另一个内函子的初始代数生成的自由代数而得到关键词：余代数，单子上的代数1介绍对于任何范畴和任何-内函子H，在H的最小不动点和最大不动点之间，即在它的初始代数和最终余代数之间，存在一个典范箭头，假设它们存在。这些对象存在并重合的函子被巴尔称为代数紧的[6] -例如，如果基范畴在完备度量空间[5]或完备偏序[23]上是丰富的，那么温和的条件确保了内函子是代数紧的。然而，如果这个范畴缺乏任何充实，如Set，这种巧合就不会发生。 但 Barr [7]证明了对于双连续集-闭函子，最终余代数可以实现为其初始代数的完备化。但如果函子不将空集映射到自身，则这是可行的，否则初始代数将为空。因此，一些著名的例子丢失了，比如从幂和乘积得到的函子。将Barr1由皇家学会国际旅行补助金支持1571-0661 © 2010 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2010.07.01348A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）47×/˜presentablecategoriesbyyAd'amek[3，4]，在这个意义上，完备化过程适用于hom-set，而不是对象，关于所有有限可表示的对象。在本文中，我们集中讨论了余代数，其载体是集合单子的代数，不一定是无穷的（例如见[9]，[24]）。我们的兴趣来自以下两个事态发展。首先，由Rutten（[19]，[20]，[21]）开创的流或加权自动机是数学上非常有趣的余代数的例子，尽管类型函子非常简单，在流的情况下只有HX=A X。有趣的结构来自A，在典型的例子中，它具有半环的结构。在本文中，我们将通过提升H到一个半环的模范畴，或者更一般地，提升到一个合适单子的代数范畴，来把这个结构带到前面。第二，在基西格和第二作者最近的工作中，事实证明，将Hasuo-Jacobs-Sokolova [10]的迹语义从交换单子的Kleisli范畴移动到代数的Eilenberg-Moore范畴是有趣的（例如，这允许考虑更广泛的单子类）。同样，对于迹语义，半环单子是特别感兴趣的。在本文的第一部分中，我们证明了Barr我们考虑了集合闭函子H提升到Alg（M）的情形.在一些合理的假设下，我们能够证明最终H-余代数可以作为初始代数的像的Cauchy完备化得到，提升函子，相对于通常的超度量继承的final序列。为此，我们需要更好地理解提升函子的初始代数。 这是本文第二部分的目的，其中展示了初始代数是自由的（作为M-代数）的特殊情况。也就是说，对于Set上的两个闭函子H，T和一个单子M，我们称（T，H）为M-交换对如果存在自然同构HM=MT，其中M是单子。如果H的代数提升和T的Kleisli提升都存在，则温和的要求确保H的代数提升函子H与T到Alg（M）的扩张等价当且仅当它们形成交换对。如果是这种在这种情况下，可以恢复建立在初始T-代数上的提升内函子H自由M-代数为˜A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4749HNT−→...HNT−→◦CL2提升到代数2.1集合闭函子的最终序列考虑闭函子H：Set−→Set。从的唯一箭头t：H1−→ 1我们可以形成序列1，，tH1，，. . .，，Hn1，Hn+11，.（2.1）用L表示其极限，pn：LHn1是相应的锥。当我们在集合，回想一下，极限L可以用乘积的一个子集来标识。Hn1，即n≥0L ={（x n）n≥0|H n t（x n+1）= x n}通过将H应用于序列和极限，我们得到一个锥1，H1，，.、、、Hn1，，...、、pnLHpn−1，，τHLHL→1是唯一映射到单例集。极限性质导致映射τ：HL→L使得pn<$τ=Hpn−1。对于每个H-余代数（C，<$C：C−→HC），它在序列（2.1）上存在一个锥αn：C−→Hn1，归纳地建立如下：α0：C−→1是唯一映射，则如果αn：C−→Hn1已经得到，构造αn+1作为合成C CHαnn+1个−→HC −→H1（2.2）那么唯一映射αC：CL使得pnαC=αn满足下面的代数-余代数图（[18]）：α C，，γCτJHαCHC HL在序列（2.1）上，赋予每个集合Hn1离散拓扑（因此所有映射Hn t将是连续的）。 然后将来自这个序列的初始拓扑[22]放在L和HL上。因此，τ是连续的。 特别地，L上的拓扑由超度量给出：L中任意两点之间的距离是2−n，其中n是满足pn（x）/=pn（y）的最小自然数。锥体50A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）47E−→−→−→ט−→××∈ ××∈∈×−→×−→−→−→−→αn：C−→Hn1在任何余代数上产生一个伪超度量（因此是一个拓扑），唯一映射αC：C−→L关于它是连续的如果H是ωop-连续的，则它保持极限L，因此同构为π=τ−1：LHL使L成为最终的H-余代数. 此外，使用上述拓扑，映射是同胚，并验证了Hpn−1=pn（2.3）2.2单子代数到Eilenberg-Moore范畴的提升设M=（M，M2M M、Idu M）是集合上的一个单子。 用Alg（M）表 示 M- 代 数 的 Eilenberg-Moore 范 畴 ， 用 F M 表 示 M - 代 数 的 Eilenberg-Moore范 畴UM：Alg（M）设置自由函子和遗忘函子之间的附加函数。（A）A（B）A（C）A（D）初始对象，即（M0， M20−m→0 M0），emp ty集合上的自由代数，以及终端对象1，单例，具有由唯一映射给出的代数结构M1−→ 1。对于集合闭函子H，（[12]）证明了H到Alg（M）的提升即Alg（M）上的闭函子H∞使得图Alg（M）HeAlg（M）（2.4）UMU MJHJ我的天通勤，是在one-to-one对应与自然变换λ：MH−→HM满足HuHMH、、M2HMλMHMλM HM2（二、五），λmHHmHu，zJHMJλJMH H M注2.1值得注意的是，提升不是唯一的（因为可能有一个以上的分配律λ：MHHM）。 例如，取G为一组和HX=MX=GX;考虑H是一个内函子，M是一个单子，其自然变换u，m由群结构得到. 这个单子的代数是G-集. 那么很容易看出，一个映射f：G GGG导出一个分配律λ：MHHM，如果它满足f（e，x）=（x，e），其中e代表群 的单位，并且f（μG）=（G μ）（fG）（G f），其中我们用μ表示群乘法。你带f1（x，y）=（xy，x）和f2（x，y）=（xyx−1，x）;这些映射产生两个分配律λ1，λ2：MH HM，它们不给出相同的提升H，因为HX上的G-作用对于λ 1分别是（x，y，z）（xy，x-z） ， 对 于λ 2分别是（x，y，z）（xyx−1，x-z）。这里x，yG，zX和-表示X上的左G-作用。如果A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4751提升是同构的，那么余代数的相关范畴应该是52A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）47−→−→˜˜˜−→−→HMH−→an也是同构的。特别地，注意H是一个余单子（因为任何集合，特别是G，都具有自然的余单子结构），并且两个映射f1，f2实际上分别诱导单子-余单子分配律λ1，λ2。因此，每个提升都带有一个余代数结构，使得提升函子的余代数的相关范畴是余代数的Eilenberg-Moore范畴，并且它们也应该是同构的。 但对于f1，对应的余代数等于G-集（X，-）的端点为映射θ：XG满足θ（g-x）=gθ（x），而对于第二种结构，相容关系产生一个交叉G-集，即. θ（g-x）=gθ（x）g−1。假设从现在开始对的一升降H为Alg（男）存在，给定由λ：MH−→HM。 对任意M-代数（X，x），HX成为一个代数对于任何代数映射（X，x）−→（Y，y），对应的箭头HX−→HY与代数结构有关。 还有，为 任何 H-余代数（C，C<$CHC），MC继承 一个 H-余代数结构真实的 中文（简体） MHCλC HMC。特别地，如果最终余代数（L，L）HL）存在，则存在唯一的余代数映射γ：ML−→L，给定通过：−→MLMMHLλL HMLγHγ（二、六）JLJHL则（L，γ）和（HL，HγλL）是M-代数，且λ：（L，γ）（HL，HγλL）是M-代数映射.利用提升性质H（L，γ）=（HL，HγλL），由于任何H-余代数（其基础集）都是H-余代数的载体，因此（（L，γ），λ）是最终的H-余代数. 因此，尽管提升可能不是唯一的，最终H-余代数的基础集合被保留（但可能具有不同的代数结构，取决于λ）。回到式（2.1）的尾序列，注意任何项Hn1都是M-代数通过：• 1上明显的唯一M-代数结构，a0：M1-→ 1;• 给定an：MHn1−→Hn1，定义an+1为合成MHn+11λHn1n1−H→anHn+1个 1（2.7）此外，序列（2.1）中的所有映射都是由（2.5）得到的M-代数映射. 将M应用于序列会从ML产生一个圆锥。如果我们假设H ωop-连续（因此H：L HL是同构），我们可以更好地理解这个锥构造：引理2.2锥（MLMpnMHn−→Hn1）n≥0 与圆锥体α n：ML−→Hn 1由（2.6）的ML的H -余代数结构诱导。证据感应。对于n= 0，没有什么可显示的，因为1是终端对象A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4753MH..−→、、、、1，1J..oo在设置。 假设αn=an<$Mpn，则在下图MLMpn+1n+1 ¸λHn1HMHn1奥里. . .M. . .MHpnHMpnooooOoo韩恩JMHLλLHMLHαnHn+11左边的三角形与公式2.3交换，中间的图与λ的自然性交换，右边的三角形通过将H应用于归纳假设而交换。因此，αn+1=an+1<$Mpn+1。Q因此，在（2.6）中构造的唯一余代数映射γ：ML-→L也是余代数ML的变形αML：ML-→L。引理2.3投影pn：LHn 1是M-代数态射，其中（2.6）和（2.7）分别给出了L，Hn 1的代数结构。证 据 再 次 归 纳 。 第 一 步 是 微 不 足 道 的 。 假 设 pn 是 一 个 代 数 映 射 ：πn<$γ=an<$Mpn;则我们有以下图MLMpn+1MHn+11、、、、（一）. . ¸. . ............. MHPnMHLλHn1（2）λL（4）γJHMpnJnHMLHγJ（五）HMH1HL，韩恩ξJ（三），H，pn、 znJLpn+1H1其中：（1）通过将M应用于（2.3）进行交换;（2）通过（2.6）进行交换;（3）通过（2.3）进行交换;（4）通过λ的自然性进行交换;（5）通过将H应用于归纳假设。Q恢复以上所有，我们有下面的M-代数和M-代数态射的图，其中下序列是极限的：MPNM1，M，tMH1，，. . . ，，MHn1，MtHntn+1个...MLa0a1，MH1anan+1γJTJnJHntJJ..oo54A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）471，，H1，，. ，，H、、、Hn+11，，.LpnA. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4755−→◦ ◦◦˜−→−→2.3最终余代数从现在起，我们将假设H是ωop-连续的内函子，它允许提升到Alg（M）。记住，在所有的Hn1上，我们已经考虑了离散拓扑.还赋予所有MHn1离散拓扑（直观地，这对应于具有离散拓扑的代数上的运算自动连续的事实），并赋予ML来自锥Mpn的初始拓扑：ML-→MHn1（这与来自锥MLMpnnnn n−→MH1 −→H1，因为an是离散空间之间的连续映射命题2.4在上述假设下，最终H-余代数继承了拓扑M-代数2的结构，即L具有M-代数结构γ：ML使得γ关于L和ML上的拓扑连续。证 据 通 过初 始 拓 扑的 定 义 ， γ 是 连续 的 当 且仅 当 所 有组 合γpn是 连续 的 。 但γpn=anMpn，an是连续的，因为离散集之间的映射和Mpn是ML上的初始拓扑连续的.Q请注意，这个结果在很大程度上依赖于作为序列（2.1）的极限的最终煤岩的构造。 没有它，我们不能仅仅通过假设存在最终H-余代数和提升到Alg（M）来得到命题2.4，因为ML上的拓扑没有明显的选择。命题2.4也可以解释为L上的所有运算都是连续的（因为它们是作为离散代数上运算的极限而得到的注2.5我们可以用有限个闭函子来代替ωop-连续闭函子。 已知[25]最终余代数存在，但前面的极限是不够的。由此，一个补充构造给出了最终余代数。显然，最终余代数具有如式（2.6）所示的M-代数结构。按照Worrell2.4Alg（M）中的初始H∞-代数a与最终H∞-代数a若H是ω-序列的上 则初始H-代数是容易的到 建造， 使用 一 双 程序 到 的一在（2.1）：召回的Alg（男）具有 一个 初始 对象， 即 的 免费 代数 对 的 空 设置，FM0=（M0，M20m0M0）. 为了简化符号，我们将确定所有代数Hn FM0与它们的基础集合Hn M0。初始H-代数是链Alg（M）中的余极限nM0−→！HM0−H→！......这是什么？ −→HnM0H！......这是什么？（2.8）[2]通常拓扑代数的概念指的是一个代数的一些有限的，代数理论，其基础集配备了一些拓扑，使得代数运算是连续的（[13]）。由于集合单子的Eilenberg-Moore代数与（不一定）有限代数理论的代数相同（[1]），我们发现术语拓扑代数最好地表征了目前的情况。56A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）47−→−→1，−→×◦◦−→◦L˜n哪里！：M0HM 0是的独特代数地图表示通过i n：H nM 0I的 大肠菌群 可可酮 我们做不详细Any-更多这 建设 作为 我们 做 为 余代数 作为 它 将 不 被 使用在续集里。 然而，在这方面， 我们 应 需要 的 以下 （其中 需要 在Alg（M）中只存在终止序列的极限（2.1），而不存在初始序列的上极限（2.8））：存在唯一的M-代数态射f：I-→L，使得H n M0 in 我（2.9）HN SHFnJpnJ通勤 为 所有 n（参见 为 例如 [3]， 引理 II.5 为 一 证明）， 其中s：M01是Alg（M）中从初始对象到最终对象的唯一代数映射。 如果M0不为空，那么I也将不为空，因为它带有一个非空域的代数映射的在这一节中，我们将把Barr（[7]）的结果从Set推广到Alg（M），对于Alg（M）-内函子作为Set-内函子的提升而产生的特殊情形，本文给出了一个新的证明.这两个证明使用了与[7]和[3]中的证明类似的思想我们将假设存在一个代数映射j：1 −→M0（2.10）由于M 0是初始值，因此j s=Id。通过Alg（M）中的无穷性1，sj=Id，因此我们可以将M 0和1识别为代数范畴中的零对象。注2.6有一大类单子满足这个条件：列表单子（和交换单子群半环单子），（有限）幂集单子，可能单子，半环k的k-模单子。对于所有这些，具有空生成元的自由代数是建立在单例集上的。但也有单子，其载体的自由代数在空集上有一个以上的元素，作为例外单子或家庭单子，或它是空的，是这种情况下的单子MX=XM，为M幺半群。在这种弱化的假设下，本文的结果是否成立仍我们有！：1 = M0HM 0 =H1和t！=Id，单位为Alg（M）。因此，在最终序列（2.1）中，所有态射都是分裂代数映射，上极限是初始H-代数，极限是最终H（和H ）-余代数：不14H 14... 4 H1！HNT4嗯！H n+114...（2.11）定理2.7设H是集闭函子ωop-连续， M是这样的集认为：(i) H承认一个提升H(ii) Alg（M）中M0= 1;Alg（M）是ω-余连续的;A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4757˜、◦◦◦◦ ◦◦−→则最终H-余代数是初始H-代数在适当的（超）度量下的完备化。证据考虑下图（在Alg（M）中），其中所有涉及的代数都有通过分配律λ定义的结构映射。！...............................n嗨！. . .1，，H1，，，，H1，tt，H，p，，在nn，，I，sL在I上放置最小拓扑，使得f是连续的，其中L具有命题2.4的拓扑代数的结构。这与最初的主题一致-由圆锥IfLpn Hn1给出。而且，I变成了拓扑代数且所有的in都是连续uu−s→algeb−r→a映射，如果在MI上我们讨论y映射Mf：MI−→ML。 特别地，Mf是连续的。 由MI表示我I.代数结构图则f∈=γMf（记住f是al−ge→bra地图）。 由于L是拓扑M-代数，所以f是连续的，因此f是连续的。关于i n：这些是通过构造代数映射（作为Alg（M）中的共限上锥的分量）并且也是连续的，因为H n 1是离散的。我们唯一需要证明的是I（更准确地说，是Imf）在L中的密度。我们首先应用巴尔首先，利用Alg（M）中的极限可以像Set中那样计算得出L是柯西完备的结论：取L中关于初始拓扑（超度量）的柯西序列x（n），并假设对所有m，n都有d（x（n），x（m））2−min（m，n）。<这意味着p nf（x（n））= p nf（x（m））对于所有n< m。因此y=（p nf（x（n）n≥0定义L的一个元素使得lim x（n）= y。接下来，一个与[4]中类似的构造将告诉我们，I在代数态射f下的像在L中是稠密的。为此，考虑态射（h n）n≥0的附加M-代数序列，由下式给出：h：Lpn H n 1 = H n M 0 Hn！ H n+1M 0 in+1IfLn− →我们有pn+1h n=H n！不规则的;现在考虑一个元素x∈L。然后通过构造（y（n）= hn（x））n≥0形成一个位于f的像中的元素序列，我们将看到这个序列收敛于x。实际上，从p n+1（y（n））=嗯！n（x），则pn（y（n））=Hntpn+1（y（n））=HntHn！n（x）=pn（x）序列（y n）n≥0的第n项的第n个投影与元素x的第n个投影重合;因此d（y（n），x）<2 −n意味着lim y（n）= x在L中。 因此，通过正则余限箭头的I的像在L中是稠密的。QF58A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）47→◦ ◦◦˜˜˜×--- -注2.8（i）如果我们考虑初始代数I上的最终拓扑来自ω-链，这正是离散拓扑（和度量），因为所有H n 1都是离散的，因此I将是柯西完备的， f：IL自动连续。 在这种情况下，不能获得I和L之间的感兴趣的信息。(ii) 由式（2.9）和式（2.10），我们有pnfi n=Id，因此fi n是单态的。但所有的态射在上面的序列是分裂代数映射（2.11），因此所有的H n！是单核细胞增多症现在回想一下[3]，在任何局部有限可表示的范畴中，• 由单态形成的ω-链的余极限的上锥是单态，和• 对于由单态形成的链的每一个上锥，从上极限的唯一映射又是单态。如果我们假设M是无穷的，那么代数的Eilenberg-Moore范畴将是局部有限可表示的。因此，代数映射f将是单声道的。但要记住，任何集合单子都是正则的（[1]）。由此可见，我们可以用L的一个子代数来标识I。 代数同构g：IImf也是同胚，如果我们取Imf为L的诱导拓扑。(iii) 如果我们假设M，H为最终。因为，单子是无穷的，健忘函子UM将保持并反映筛选的余极限。但UMH=HUM，因此H与筛余极限，特别是ω-链的余极限可交换。例2.9函子HX=kXA由乘积构成，因此是ω-连续的。H-余代数被称为摩尔自动机.这样的函子总是允许对任何单子M至少有一次提升到Alg（M），只要k进位代数结构提升函子由与H相同的公式给出，其中 这一次，乘积和幂是在代数范畴中计算的特别地，考虑A是一个有限集，k是一个（不一定是交换的）半环，M是它所诱导的单子（如[16]，第VI. 4节，Ex. 2，其中环R由半环k）代替，则Alg（M）是k-模范畴，M0是零模. 最终的H-余代数是kA，所有函数的集合A−→k，也被称为非交换A变量的形式幂级数，而初始H-代数是A k（相同变量的多项式代数）的直和（回想一下，在这种情况下，有限积和上积在Alg（M）中重合）。在相应的ω-序列中的n阶逼近式为Hn 1 = k1 +A+…+An，多项式在（非交换）A-变量的度最多为n。我们将详细说明最简单的情况，其中A是单例t;最终余代数k[[t]]的两个元素之间的距离，即变量t中的两个幂级数f（t），g（t）之间的距离，精确地由2−ord（f（t）−g（t））给出，其中ord（f（t）g（t））是差f（t）的阶 g（t）（t的最小幂）其在差分中具有非零系数）。取一个柯西多项式序列f n（t）=an+an t+.. . ，其中只有有限个an是非零的，对于0 1jA. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4759˜我−→I−→RJJ˜每个n，j∈N。对于每个r≥0，存在一个nr，使得对于每个n≥nr，我们有ord（f n（t）−f n（t））=r;这意味着对于所有j≤r和n≥n r，a n = an n r。让f（t）=an0+an1t+........ One立即证明幂级数f（t）是0 1序列（fn（t））n≥0的极限因此，最终余代数k[[t]]确实是初始H-代数k[t]的完备化。3应用：M-交换内函考虑一个闭函子H和一个单子M，都在集合上。有两种方法可以通过自然变换将闭函子与单子联系起来，如下所示：• λ： MH−→ HM满足式（2.5）， 这与代数提升H相同：Alg（M）−→Alg（M），UMH=HUM;或• *：HM−→MH满足H胡宏明、、hm2的CIMM MHMM M2H（3.1）uH，HmmH，zJJMHHMJMH众所周知，这相当于Kleisli升力的存在，即。闭函子H：Kl（M）−→Kl（M）使得H<$ FM=FMH，其中FM：集合Kl（M）是Kleisli范畴的正则函子， 单子。在这种情况下，我们可以执行以下额外的构造： 通过：Kl（M）Alg（M）比较函子。取由左Kan延拓给出的Alg（M）-闭函子（它存在，因为Alg（M）中的每个代数都以规范的方式作为自由代数的余均衡器出现H<$=LanI（IH）（3.2）由于Kleisli范畴Kl（M）同构于Alg（M）的一个全子范畴，这将产生一个自然同构IH=H<$I。将其与函子F M相比较，我们得到H <$F M = F M H，如下图所示：Alg（M）H<$Alg（M）（3.3）你好，我、、、我FMKl（M）HKl（M）FM、、FM我们会打电话给HSetHSetH到代数的推广。ς60A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）47¯利用上述记号，现在考虑两个集函子T，H，使得H的一个n-代数提升和T的一个Kleisli提升都存在，并且H∈H=T。然后我们就A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4761¯˜¯˜˜× −× −- -2˜∼˜¯˜¯MT=UMFMT=UMT<$FM=UMHFM=HUMFM=HM也就是说，M就像是内函子T和H之间的开关（直到同构）。定义3.1设M=（M，m，u）是集合上的单子。 一对集-闭函子（T，H）满足HM∈=MT称为M-连通对.例3.2在下列情况下可以很容易地得到交换对：• 设T=H=Id或T=H=M且M=（M，m，u）为任意单子;• 考虑T=H=A+（），M=B+（）。那么余积的交换性确保了交换对;对于积也是类似的：T = H = A（），M = B（），此时B是么半群（这在任何么半群范畴中都更普遍）。据我们所知，交换对的概念似乎 以前没有考虑过，尽管上面的例子表明它在数学中自然出现。我们以后会看到更多（非平凡的）例子。 但在此之前，我们回到之前考虑的两个内函子T和H都满足H_∞=T。这意味HFM=TFM=FMT其中HMX=MT是M-代数的n同构，其中HMX的代数结构对于集合X由分配律λ：MH-→HM导出，即下图交换：MHMX=M2TXλMX（3.4）JHM XHmX JHMXm个TXJTX其中，下半部分的总流量是HM = MT，而上半部分的总流量是通过将M应用于此而获得的。相反，如果（T，H）是一个M-交换对，人们可能想知道它们与M-代数范畴的关系。假设H有一个提升H的代数，T有一个Kleisli升力（因此有一个扩张T<$），且HM=MT，则（3.4）式成立;则由HM=MT，HM=HUMFM=UMHFMMT=UMFMT=UMT<$FM¯UMH FM=UMTFM，即H和T在自由空间代数共享（直到双射）相同的底层集合。考虑到HM=MT是M-代数（3.4）的同构，我们得到H=Tonfree代数 现在假设M、T和H是无穷的。 然后，通过构造，T是=M62A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）47˜∼¯˜˜F−→·¯˜× −→×× −→×× −→×由它在有限生成的自由代数上的作用决定，H也是如此（因为它保留了注2.8（iii）中的筛选余极限）。因此，H=T。我们得到了这样的结果命题3.3设H，T是集 合 上 的 闭函子，M是集 合 上 的 单子.假设H有一个代数提升H∈ H，T有一个Kleisli提升，单胞菌M. 用T ′表示相应的左Kan扩张，如式（3 - 2）所示。然后又道：¯(i) 若H∈H=T，则（T，H）构成一个M-可换p空气，且HM∈H=MT是一个代数同构¯(ii) 反之，若M，H，T是任意数且MT=HM作为代数，则H=T。例3.4取TX = 1+ A×X，A为有限集合，M为集合单子。然后存在T的Kleisli提升，即对于每个映射XfMY，取TX MTY是复合的−→ −→TX= 1 +A×X1+A×f1 +A×MY−→1+M（A×Y）−→M1+M（A×Y）−→M（1+A×Y）其中地图1+ A MY1+ M（AY）是由单子的典范强度得到的，而1+M（AY）M1 + M（AY）是利用单子的单位，M1 + M（AY）M（1 + AY）是由余积性质得到的.同样，很容易看出T到M-代数的扩张是T<$X=FM1 +AX，对于每个ch代数X，此时在Alg（M）中计算上积（相应的上幂）。如果M-代数范畴有有限双积（如由半环诱导的单子的情况，见例2.9），则T<$是集合闭函子HX=M1 ×XA到Alg（M）的提升。因此，（T，H）构成交换对。如果我们把前面的命题和定理2.7的主要结果结合起来，我们研究交换对的动机就清楚地显现出来了，得到如下结果：推论3.5假设命题3.3（ii）的假设成立。若H是ωop-连续的，且M0 = 1作为M-代数，则最终H-余代数是建立在初始T -代数上的自由M -代数在适当度量下的 完 备 化 .证据从定理2.7出发，注意到初始T-代数的M-像（当T是无穷的，因此ω-余连续时存在）是初始T<$-代数（通过构造，T是无穷的，因此ω-余连续），而H和H共享相同的最终余代数。Q例3.6我们回到例3.4，取半环k诱导的单子，如例2.9所示。那么初始T-代数是A，所有有限词（包括空词）的幺半群都建立在字母表A上。自由M-代数是A∈ k的副本的直和，即非交换A-变量k[A]中的多项式k-代数（在k-半模范畴中），而最终H-余代数是kA∈ k，非交换幂级数k-代数。A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4763n′M˜˜∈×−→（（M））是强么半群（[11]）。 如果是多项式函子=到目前为止，本节所描述的情况可以如下所示：如果给定两个闭函子T和H，可以搜索适当的单子，使得（T，H）形成交换对。 由于代数之间存在一种特殊的联系，T和H的余代数，尚不清楚任何两个（无穷个）集内函子的一般情况是否有解。但还有另一种可能的方法：只从一个内函子开始，再加上一个（无穷）单子;然后 一个导致克莱斯利（或代数）提升的分配律。 一旦完成了这一点，我们应该在Set上构建第二个内函子（假设这是可能的），利用在Alg（M）上得到的函子，得到一个交换对对于提升到Kleisli范畴，有以下合适的情况：对于所有交换单子M和所有解析函子T，总是可以构造一个分配律TM MT（[17]）。M的交换性也保证了Alg（M）上张量积的存在，使得自由函子FM：（Set，×）−→Alg，BELTTX An ×n≥0X，Kleisli提升的一个明显的选择将给出（扩展）T X=F Ann≥0Xn， 哪里 这次是X Alg（M）。现在回想一下，Alg（M）上的余积和张量积都是作为自反余均衡器获得的，因此，如果我们假设单子不仅是交换的，而且是无穷的（因为本节中的所有结果都依赖于在M的有限性上），可以得出，健忘函子将把任何两个代数（X，x），（Y，y）的上积，分别是张量积，变换成此时在集合中计算的自反上均衡器。特别地，对于多项式函子T，存在对应的交换对（T，H），并且可以由上述参数构造。此外，这样的H通过构造是无穷的。如果H作为代数也是ωop-连续的，且M0=1，则根据推论3.5，最终H-余代数应被实现为建立在初始T-代数（众所周知，初始T-代数是具有分支的有限树的集合）上和由T的签名给出的标记）。然而，提升函子到Eilenberg-Moore范畴似乎更有问题，即使是最简单的多项式函子，如下所示：• 如果H是常数函子，则H的象（集合）必须是M-代数（A，a）的载体;如果是这种情况，可以形成交换对当且仅当如果A是自由代数则T也是常数函子;特别地，推论3.5是真的。• 如果HX=AX，并且A是代数的载体，很容易看出存在提升，因为健忘函子UM保持乘积。反之，如果H是H的提升，则A上存在一个代数结构，即H1。如果范畴Alg（M）有有限双积（例如M是由半环k诱导的单子），A是具有集合生成元B的自由代数的载体，则存在交换对（T，H），TX=B+X。最后的H-余代数是上所有流的集合，而初始T-代数上的M-代数是MB=A的ω-余子。•如果HX=Xn，是有限幂函子，则提升作为遗忘函子UM保持极限;Alg（M）中有限双积的存在性再次是最重要64A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）47·−→CCC找到对应函子的方便方法是上幂TX=n X。但在这种情况下，在初-末（余）代数关系中没有得到相关的答案，因为这些对象是平凡的（空初T-代数，单例末H-余代数）。• 如果HX=A+X或HX=X+X，则没有明显的分配律λ：MHHM，除非单子本身是作为和得到的（如可能的单子MX= 1 + X）。4结论巴尔定理背后的一般图景在概念上更简单： 如果 我们从一个任意的范畴（有初始对象，最终对象和ω-（余）极限）和一个-函子开始，那么这个定理粗略地说，最终序列的ω-极限是初始序列的ωop-上极限的一个完成。当然，需要一个适当的完备化概念;它可以是拓扑性质的（如[7]），也可以是关于有序结构的（[3]）。本文着重讨论了具有代数结构的基范畴，即集合单子的Eilenberg-Moore范畴的拓扑性质（Cauchy完备化）。所考虑的终结函子是从Set中提升得到的，因为我们的动机之一来自以下问题：给定一个连续的Set函子H，H0 = 0，关于最终的H-余代数可以说什么？如果函子不是必然连续的（例如有限幂集函子），则最终序列必须扩展到ω步之外。在这种情况下，Alg（M）上的完成过程会发生什么？ 我们认为，这个问题的答案值得考虑， 未来本文的第二部分介绍了关于单子的可交换的内函子对的概念。这似乎是新的，但需要详细的分析和更多的例子，以更好地理解这种结构（如[8]中展示的互模拟和迹之间的联系）。我们计划在另一篇论文中这样确认作者感谢审稿人提出的宝贵建议，这些建议有助于改进本文的第一版引用[1] Ad'amekJ.，H. Herrli ch和G.- E. Stre cker，&“Abstract and Concrete Categories”，John Wiley Sons，1990.[2] Ad'amek，J. 和j. 罗锡基，遗传多样性与遗传多样性，理论与应用。卡泰格 8（2001），33-53.[3] Ad'amek，J.， 作为初始代数的一个完备集的最终余代数，J. Log. Comput. 12（2002），217-242.[4] Ad'amek，J.， 关于连续函子s的有限代数，Theor. Comput. Sci. 294（2003），3-29.A. Balan，A.Kurz/Electronic Notes in Theoretical Computer Science 264（2010）4765[5] America，P.和J. Rutten，在一类完备度量空间中求解可交换域方程，J. Comput.系统科学39（1989），343-375。[6] Barr，M.，Algebraically compact functors，J. Pure Appl. Algebra82（1992），211-231.[7] Barr，M.，良基集合论中的终端余代数。Comput. Sci. 114（1993），299-315。[8] Bonchi，F.，M. M. Bonsangue，J.J.M.M.Rutten和A.Silva，代数丰富的余代数。2010年提交。[9] Corradini A.，M. Große-Rhode和R. Heckel，结构化变迁系统作为松弛余代数。在“计算机科学中的共代数方法CMCS'98”中计算机科学11（1998），22-41.[10] 哈 苏 岛 ， B. Jacobs 和 A. 索 科 洛 夫 ， 通 用 痕 迹 理 论 . 在 “Coalgebraic methods in computer scienceCMCS'06”中计算机科学164（2006）