185ωMMLL∈L LLLLL MMPPP《理论计算机科学电子札记》44卷第1期（2001）网址：http://www.elsevier.nl/locate/entcs/volume44.html20页幺半群标记转移系统H. PeterGumm，TobiasSchr？derPhilipps-UniversitüatMarburg德国马尔堡{gumm，tschroed}@ mathematik.uni-marburg.de摘要给定一个-完备（半）格，我们把-标号转移系统看作是一个函子（-）的余代数，它把所有-模糊子集的集合X与一个集合X联系起来。 我们描述了-余代数的模拟和互模拟，证明了（-）弱保持非空核对，i-L是有限分配的联接（JID）。换作交换幺半群，我们考虑与集合X相关联的函子（−）是包含X的元素的多重性为m M的有限多重集。相应的函子弱保持沿着内射的非空拉回i，0是的唯一可逆元素，并且它保持非空核对i， 是可细化的，在这个意义上，两个相同值的求和表示， r1+... + rm= c1+. + cn，有一个公共的精化矩阵（mi，j），其第k个对于任意1≤k≤m和1≤l≤n，行和为rk，且其第l列和为cl。关键词：余代数，变迁系统，模糊变迁，多重集，弱拉回保持，互模拟，可加细么半群，分配格。1介绍众所周知，转移系统可以被描述为协变幂集函子的余代数。余代数的一般理论自动地提供了同态和互模拟的基本概念。函子行为良好的事实，即它保持（广义）弱回调，保证了有用性质的集合。特别地，互模拟的关系积是互模拟，最大的互模拟是等价关系，同态的核总是互模拟。镜像有限跃迁系统的子类对应于有限幂集函子Pω此外，这个函子是有界的，因此存在一个终结ω-余代数，提供了语义和证明（3）余诱导（coinduction）：有限像跃迁系统的基本原理。2000年1月，出版社dbyElsevierScienceB。 V.操作访问和C CB Y-NC-ND许可证。GUMMANDSCHR？DER186SSP P − P−P→ P P −⊆ ××LLLωMM联系我们∈L L {}P L {}LLL引入标签并不会使情况复杂化。给定一个标号集L，状态集S上的L-标号转移系统是三元关系TSLS.同样，等价的余代数观点作为映射α：S（S）L，即， 作为（）L-余代数，更好地刻画了标记迁移系统的动态特性.上面已经说了-，resp。ω-余代数分别结转到（）L-，（）ω（）L-余代数事实上，L-标号变迁系统只不过是（普通）变迁的集合系统，每个标签一个当标签带有某种代数结构时，情况变得更有趣这种结构是相关的，当弧标签表示，例如，低容量或持续时间。一般来说，我们将假设标签来定义交换幺半群，即具有中性元素0的交换结合运算。这使我们能够一个coalgebrical解释标记的过渡系统作为一个地图，从国家的分级集的后继国家。这种观点将被视为提供一个有趣的交织的coalgebraic结构与代数性质的幺半群。这项工作的另一个动机是et函子的研究在以前的工作（[Gum 98]，[GSb]，[GS 00]）中，我们研究了et-内函子的各种保持性质在这里，我们构造这样的函子，它们由交换幺半群参数化，因此我们可以通过选择具有适当代数的交换幺半群来自定义构建函子。特性.在第一节中，我们从任意完备半格L开始，我们考虑-多重集。一个多重集合S可以被认为是一个集合，每个集合其元素s以某种多重性（概率，确定性）l包含在S中. 有很多自然的选择，，例如01N，或实区间[0， 1]，从而产生了（普通旧）集，袋（多集）或模糊集的标准概念。半格产生一个函子（-），它推广了幂集函子为 = 0， 1。因此（-）-余代数将转移系统推广到多集转移系统和模糊转移系统。我们证明了（-）总是保持沿着内射映射的非空拉回，并且它保持任意非空弱拉回以防万一是在有限分配中加入的，也就是说，有限的满足分布在有限的加入上。在半格中，定义有限和的可能性与幂等律密切相关。在任意的交换幺半群中，我们可以形成无限的只有在有限个被加数都为零的情况下才能求和这导致了一个稍微不同的函子，（−），对于任意交换幺半群. 本文的后半部分对此进行了研究此函子保持沿着内射映射的非空拉回i-幺半群是正的，并且它保持任意映射的非空弱拉回i-此外，幺半群在稍后定义的意义上是可精化的GUMMANDSCHR？DER187A B→⊆ × ⊆×U2基本概念设R一B和SBC是二元关系。 我们用（R;S）表示其组成或相关产品：（R; S）：={（a，c）|b ∈ B。 （a，b）∈ R，（b，c）∈ S}.用R−表示R的逆，即R−：={（b，a）|（a，b）∈R}.我们使用如果A→B是一个映射，那么我们用G（A）表示它的图，即G（n）：={（a，n（a））|a ∈A}。有了这些定义，我们得到：G（）=G（）;G（）。2.1F-余代数与同态设F：Set→Set是从集合范畴到自身的函子。一个F型余代数是一个对A=（A，α），由一个集合A和一个映射α：A→F（A）组成。 A称为载体集，α称为A的结构映射。若=（A，α）和=（B，β）是F-余代数，则称映射A：AB是同态，若β=F（）α，也就是说，如果下图通勤：A组B组αβJF（）JF（A）F（B）F-余代数及其同态构成范畴SetF.众所周知，在SetF中所有的大肠杆菌都存在，并且它们的形成与在SetF中一样。In特别地，一族F-余代数Ai=（Ai，αi）的和i∈IAi有：载体不相交i∈IAi，余代数结构唯一A=i∈IAi），其中αiAi=F（iAi）αi对于所有i∈I，其中每个ιAi是Ai到不相交的正则嵌入联盟i∈I Ai.2.2子余代数子集U<$A称为A=（A，α）的子余代数，只要存在余代数结构ν：U→F（U），使得包含映射<$A：U→A为从U=（U，ν）到A的同态。GUMMANDSCHR？DER188一UU⊆U公司简介→→.A.我们读到同态的定义，即U是A=（A，α）i的子余代数u∈U。 f∈F（U）. α（u）=F（u）（v）.U=总是一个子余代数。如果U= ，则包含映射A有左逆。因此，F（A）也有左逆，特别是它是单射的。因此，如果存在上述结构映射ν，则它是唯一的。由于这个原因，我们使用术语2.3互模拟一个二元关系R<$A×B称为A和B之间的互模拟，如果可以定义一个余代数结构δ：R→F（R），使得投影映射π1：R A和π2：R B是同态。这可以表示通过下面的交换图：A，π1Rπ2BαJF（π）.δβ.JF（π）JF（A），，1 F（R）2F（B）如果R是A和B之间的互模拟，则它的逆R−是B和A之间的互模拟。一个互模拟族的并集又是一个互模拟，所以在余代数A和B之间总是存在一个最大的互模拟A，B。如果A=B，则我们称R为A上的互模拟。 对角线关系A={（a，a）|a ∈ A}始终是互模拟，因此上的最大互模拟 ，记为A，始终是自反的和对称的。但总它不必是可传递的。一个映射<$A：A→B是余代数A和B之间的同态，<$它的图G（<$）是一个互模拟.若R是余代数，且R→A和R→C是同态，则{（R（r），R（r））|r∈R}=（G（）−; G（））是A和B之间的互模拟。因此，A和B之间的互模拟R给出了双模拟R={（iA（a），iB（b））|（a，b）∈R}关于它们的和A + B.3函子L（−）设L是完备半格.L可以通过以下方式变成一个完整的格：对于任何子集S，定义：S={l∈L|s∈S。 l≤s}。GUMMANDSCHR？DER189FP L → PL {}LL对任意集合A，设LA表示所有映射σ：A→ L的集合.每个这样的σ可以被认为是L-多重集的特征函数x∈lσ<$σ（x）= l.给定一个映射f：A→B，我们定义一个映射Lf：LA→ LB，L那么很容易检查：（σ）（b）：={σ（a）|f（a）= b}，引理3.1 L（−）是一个（协变的）Set-endofunctor。证据给定集合A、B和C以及映射f：A→B，g：B→C，我们计算任意σ：A→L，a∈A，c∈C：LidA（σ）（a）={σ（x）|A（x）= A（x）=σ（a）= idLA（σ）（a）。（Lg<$Lf）（σ）（c）={L（σ）（b）|g（b）= c}--{σ（a）|f（a）= b}|g（b）= c}={σ（a）|（g f）（a）= c}=Lg<$f（σ）（c）.显然，当二元格为0， 1时，这个函子自然同构于幂集函子通过η：（−）对 于 任何集合X，定义为 ：ηX（σ）：={x∈X|σ（x）= 1}。还可以直接检查每个保维映射L：L→ LJ在L（−）和LJ（−）之间进行自然变换。3.1L-余代数根据余代数的一般定义，L（−）-余代数是由集合A和映射α组成的对（A，α）：A→LA。给定两个L（−）-余代数（A，α）和（B，β），一个映射α=β，也就是说，如果对所有的a∈A和b∈B，我们有β（α（a））（b）= Lα（a））（b）={α（a）（aJ）|aj∈A，<$（AJ）= b}.在下文中，我们将讨论-余代数而不是（-）-余代数。为了方便起见，可以引入一个FGUMMANDSCHR？DER190LLLLLMMUL系统作为一个速记。我们写a−→l aJi < $α（a）（aJ）= l.显然，L-余代数结构α：A→ LA也可以通过设置α<$（a，AJ）：=α（a）（AJ）而被解释为L-群的代数结构α <$：A×A→当是二元格时，-余代数就是Kripke-框架。在一般情况下，提供了一组度量，用于指示 - 分级关系α，或者，交替地，我们可以确信（a，AJ）是在α中。If单位为v，则α_n只是一个模糊关系。3.2子余代数函子L（−）在[Mos99]中定义的意义上不是标准的，即L（λA）/= λLA。ULU相反，我们总是有：.一U（τ）（a）=τ（a），如果a∈U0，否则。从这一点上，我们可以直接得出：引理3.2U<$A是A=（A，α）i <$u∈U，a∈A。 m/=0。 u−→a=a∈U。证据U是A=（A，α）的子余代数⇐⇒∀u∈U. τ：U→L。α（u）=L<$A（τ）⇐⇒∀u∈U. a∈（A−U）. α（u）（a）=0⇐⇒∀u∈U,a∈A∀m/=0. u−→a=a∈U。对于任意类型F的余代数，已知子余代数在有限交下总是闭的（参见[GSa]）。对于函子F=（−），我们甚至可以从上面得到：推论3.3 L-余代数A的子余代数的任意族（Ui）i∈I的交又是A的子余代数。LGUMMANDSCHR？DER191不S;T→ ABL3.3L-模拟定义3.4我们将A和B之间的模拟定义为关系SA×B，其中对所有（a，b）∈S和所有AJ∈Aa−m→aJ={l|y∈B。b−→是的， aJSy}≥ m。因此，如果a由b模拟，并且如果aJ是a的m个后继者，则必须有b的足够多的l个i个后继者bi，每个后继者模拟aJ，并且一起模拟a j。得到i∈Ili≥ m。我们写A~S 如果S是A和B之间的模拟。然后我们得出结论直接从定义：引理3.5如果A~S B和B~C，然后A~C。所以，一个L -1类，具有模拟箭头的余代数形成一个范畴。3.4L-同态同态原来是余代数之间的映射，加强了分次关系，其逆是一个模拟，即：引理3.6A映射A：余代数=（A，α）和=（B，β）是同态当且仅当对所有a，aJ∈A，所有bJ∈B和所有m∈L满足以下两个条件：a−m→AJ=（a）−m→J（aJ），其中mJ≥m（1）（a）−m→bJ=|x∈A。 a−→x，n（x）=bJ}。（二）证据 同态条件要求对每个a ∈ A和每个bJ∈B，我们有方程β（α（a））（bJ）= Lα（a））（bJ）。使用βi（i（a），bJ）={1|x∈A。a−→lx，则{x（x）= BJ}.这两个同态条件等价于用“≥”和“≤"代替“=”得到的不等式。 从第一个同性恋开始，当vera−→lx且n（x）=bJ时，我们得到βn（n（a），bJ）≥l的物理条件，β（α）（bJ）≥{l|x∈A。a−→lx，n（x）=bJ}。根据这个不等式，我们通过只考虑x=aJ得到第一个同态条件，当vera−→laJ时，得到β<$（<$（a），<$（aj））≥l.第二同态条件与用“≤"代替“=”得到的不等式是明显等价的。LGUMMANDSCHR？DER192AB∈ ∈∈ABLL使用同态和子余代数的描述，现在可以直接检查：推论3.7若A→B是同态，且V≤B是B的子余代数，则<$− [V]是A的子余代数。第一，观察。第二，同态条件是G（n），分别是G（n），G（n），G（n）。G（）−是一个模拟，因此我们得到：推论3.8A映射A：A→B是L-余代数A和B之间的同态当且仅当G（A）和G（B）−都是模拟。3.5L-互模拟我们已经指出，余代数和之间的映射是同胚映射，且它的图是互模拟。然而，即使R和R−是模拟，关系R也不一定是互模拟为了看到连接，我们必须描述互模拟：命题3.9余代数=（A，α）和=（B，β）之间的关系R是互模拟当且仅当对所有（a，b） R和所有的aJA，bJB我们有：a−m→aJ=米卢尔|y∈B。b−→ly，aJRy}=m，以及（3）⇒b−m→bJ=π{1}{ml|x∈A。a−→x，xRb，J}= m。（四）证据 设R是一个互模拟，且（a，b）∈ R，则存在某个τ：δ（a，b）：R→L，α（a）=Lπ1（τ），以及（5）β（b）= Lπ2（τ）。（六）对于aJ∈A，我们有（5）α（a，aJ） =π1（τ）（aJ）={τ（u）|π1（u）= aJ}={τ（aJ，y）|aJRy}。由（6）我们有对于每个y和JRy：βπ（b，y） =π2（τ）（y）为{τ（v）|π2（v）= y}={τ（x，y）|xRy}≥τ（aJ，y）。结合上述内容，我们得到LGUMMANDSCHR？DER193∈Lα（a，aJ） ==≤{τ（aJ，y）|aJRy}{α<$（a，aJ）<$τ（aJ，y）|aJRy}{α<$（a，aJ）<$β<$（b，y）|aJRy}α（a，aJ）.因此，α（a，aJ）= {α<$（a，aJ）<$β<$（b，y）|aJRy}，这是第一个二进制条件第二个是对称的为了证明相反的情况，让互模拟条件（3）和（4）满足。我们需要证明R是互模拟。定义结构图δ：R→ LR，δ（a，b）（x，y）：=α<$（a，x）<$β<$（b，y）。对于任意的aJA，我们有Lπ1（δ（a，b））（aj）={δ（a，b）（u）|π1（u）= a}={δ（a，b）（AJ，y）|aJRy}=α（a，aJ）=α（a）（AJ）。因此Lπ1（δ（a，b））=α（a）=（α<$π1）（a，b），因此Lπ1<$δ=α<$π1，类似地，Lπ2<$δ=β<$π2。因此，R是一个互模拟。注意引理3.6可以从上面推导出来，因为对于一般余代数，同态恰好是那些图是互模拟的映射我们还得到以下推论：推论3.10如果R是互模拟，则R和R −都是模拟。4分配的作用在余代数的应用中，人们经常有满足一个重要技术性质的型函子也就是说，（弱）回调图被转换为弱回调图。余代数理论中的许多结果（例如[Rut 00]）都依赖于这个性质。在[GSa]中证明了函子F保持非空弱拉回当且仅当F-余代数之间的互模拟在复合下是闭的。现在考虑推论3.10。如果它的逆命题为真，则根据引理3.5互模拟将在复合下闭合，因此（−）将保持弱回撤在这一节中，我们将证明这个性质和相关的性质取决于格L上的某种分配性条件。定义4.1[[Gréa98]]格称为有限分配的连接（简称JID），如果它满足定律x{xi|i ∈ I}={x <$xi|i ∈ I}。≤GUMMANDSCHR？DER194LLLL→→→→→→如果L是完备半格，我们说L是JID i，这是L上诱导格的情况。只要是JID，-余代数的双相似条件就收件人：引理4.2如果L是JID，则关系R<$A×B是余代数A和B之间的互模拟当且仅当a−m→aJ=<${l|b−→y，aJRy} ≥m， 以及（7）b−m→bJ=<${l|a−→x，xRbJ} ≥m。（八）下面的定理，除了别的以外，提供了这个引理和推论3.10的逆命题：定理4.3设L是α-半格，则下列等价：(i) L是JID。(ii) R<$ A× B是互模拟，R <$R和R−是模拟。(iii) 互模拟在组合下关闭。(iv) L（−）保持非空弱回调。(v) L（−）弱保持非空核对。(vi) 每个L-余代数上的最大互模拟是传递的.证据 （i）（ii）由引理4.2推出。（ii）（iii）是引理3.5的一个推论。（iii）（iv）对于[GS 00]中的任意函子（四）（v）（vi）可以在[GS 00]中找到，所以我们可以集中精力证明（vi）（i）。设一族（li）i∈I和L的另一个元素m已知，则有显示mi∈Ili≤i∈I（mli），因为反向包含在任何晶格中都成立在片场A：={ai|i ∈ I}<${a，aJ}B：={bi|i∈ I}{b}C：={c，cJ}定义余代数结构α、β和γ，用箭头表示如下：a−→eaJ，其中e：=mlia−l→ib−l→iai，对于所有i∈Ibi，对于所有i∈IcliJ−→ c.使用引理3.6，很容易看出：A→C，定义为A（a）=c，对于所有i∈I，<$（aJ）=<$（ai）=cJ，且<$：B→C由<$（b）=c给出，且GUMMANDSCHR？DER195∈C、ABC→→L我...ajcJbi.BJ、对于所有i，I是同态，则{\displaystyle {\pi}}（bi）= cj。 因此，G（n）和G（n）-是互模拟a， cb，CcCc、、、cc，，c、英中，Lcc，，cccliCcclj，、、、我，cccliCcclj，、、、J，sC C，zzJCZZ现在考虑三个余代数的和++ . 我们还有那个G（）和G（）−是互模拟，特别地，它们包含在最大的互模拟<$A+B+C中。这是一个很好的例子。假设，不一定。命题3.9告诉我们，存在一个子集合（bj）j∈J<$I，LJe≤j∈J{e}|b−→bj} ≤i∈I（e li）.因此mi∈Ili=e≤i∈I（e）=i∈I（mli），完成证明。含义（一）（4）由于S。Pfei Poucher [Pfe99]. 有限晶格是分配格，它不包含特征五元非分配子格M3或N5 中的一个，见（[G réa98]）。通过分别排除这些情况，她还得到了逆（iv）（i）的情况下， 是有限的和分配的。观察到沿着内射映射的非空弱回调，分别。非空回调的任意集合的内射映射，总是保持，而不假设JID。在[GS 00]中，这些条件分别等价于子余代数的同态原像.任意intersection的subcoalgebra，是subcoalgebra再次。因此，这些结果由推论3.7和3.3得出。人们可能会问，一般来说，模拟是否不能仅由3.9的一个条款定义，以便条件（ii）自动对于任意-半格L. 但是，请注意，我们无法证明模拟是封闭的根据组成。5交换幺半群的标号在函子L（-）的定义中，L具有任意上确界是本质的也就是说，L是-完备的。当试图用任意的commu代替L假设幺半群M=（M，+，0），我们不再有无穷和，一GUMMANDSCHR？DER196ωωωωωMωωM∈∈LMω除非几乎所有的被加数都是0。因此，我们必须重新定义函子，只考虑具有有限支集的映射σ：X→M：定义5.1设M=（M，+，0）是交换幺半群。每当X是一个集合，且族（g（x））x∈X的所有无穷多个元素都为0，用（g（x））表示它的和|x∈ X）。给定任意集合X和映射σ：X→M，我们称之为supp（σ）：={x ∈ X |σ（x）/= 0}σ的支持。让MX：={σ：X→M||supp（σ）|<ω}是从X到M的所有有限支集的映射的集合，并且对于任何映射，f：X→Y令Mf是定义在任意σ∈MX上的映射Σ通过：y ∈ Y。 Mf（σ）（y）：=（σ（x）|x ∈ X，f（x）= y）。我们很容易就能检验出f（σ）是一个从Y到M的有限支集映射，因此使用+的结合性和交换性，我们可以像前面一样验证：引理5.2M（−）是一个Set-endofunctor。当M是二元布尔代数（{0， 1}，n，0）时，则M（−）是只有有限幂集函子Pω（−）。类型M（−）的余代数，在续篇中称为M- 余代数，可能再次可以被看作是图与弧标记的元素M，所以我们继续使用在-coalgebras的情况下的箭头符号特别地，如果（A，α）是一个ω-余代数，a，AJA和m M，我们可以在等价符号之间选择α（a）（AJ）=m，或α（a，aJ）=m，或a-m→aJ。对于ω-余代数，基本的余代数结构可以很容易地描述：引理5.3设A=（A，α），B=（B，β）是Mω-余代数，则(i) U∈ A是A的一个子余代数，i ∈ A，对所有u∈ U和所有a∈ A：u−m→a，m/=0=<$a∈U.(ii) A→B是一个同态i∈A，bJ ∈B：（a）−m→bJ|aJ∈A。a−m→JaJ，则n（aJ）=bJ）。推论5.4Mω-余代数A的子余代数的任意族（U）i∈I的交又是A的子余代数。ωGUMMANDSCHR？DER197ωM一MA → B →Bωω| |× ||∈M∈若：是同态，而U B是的子余代数，则−[U]不必是的子余代数。这与格标号余代数的情形（推论3.7）相反因此，函子（−）一般不保持沿着内射映射（[GS 00]）的非空拉回在下一节，我们将研究幺半群上的代数条件，这些条件决定了函子的这些性质我们以互模拟R的特征来结束本节Mω-余代数A与B之间的A×B 为此，我们考虑的元素MA作为向量，|一|许多组件和元素的MR作为一元素来自M的B -矩阵 从互模拟在第2.3节中，我们得到：引理5.5设A =（A，α），B =（B，β）是Mω-余代数. 一个关系R<$A×B是一个互模拟，i∈R，存在一个|一|× |B|- 具有来自M的元素的矩阵（mx，y），使得：• 除了有限个mx，y都是0，• mx，yf= 0意味着（x，y）∈R，• α（ a）是（mx，y）的所有行和的向量，即Σx∈A。α（a，x）=（mx，y|y∈B），• β（ b）是（mx，y）的所有列和的向量，即Σy∈B。β（b，y）= （mx，y|x∈A）。5.1正幺半群任何交换半群都可以通过简单地增加一个新元素0而变成交换幺半群。得到的幺半群是相当特殊的，它可以内部特征在于没有非零元素是可逆的：定义5.6幺半群元素m M称为可逆的，如果存在某个m-m+m−= 0。 幺半群=（M，+，0）称为正的，如果0是唯一的可逆元素。如果一个交换幺半群不是正的，我们可以通过因式分解出可逆元素，或者通过删除除0之外的所有可逆元素来得到一个交换幺半群，因为它很容易检查：引理5.7交换幺半群的可逆元形成群I（M）。通过导出的同余关系因式分解M，得到M的最大正因子。同时，任何交换幺半群都是可逆元子群I（M）M+。GUMMANDSCHR？DER198a1，1 ···a1，nR1.······am，1···am，nrmc1··· cn例5.8下列幺半群是正的：(i)（N，+，0）(ii)（N\{0}，·， 1）(iii) （L，n，0）对于任何具有0的（半）格5.2可再赋幺半群。我们需要考虑一个进一步的幺半群条件，我们称之为refinable。为此，让我们考虑一个幺半群的m×n-矩阵（ai，j）我不知道。 考虑它们的ro w-和ri=1≤j≤mai，j，以及它们的列和cj=1≤i≤nai，j，则根据结合性和交换性，显然有r1+... + rn= c1+. + cm。可重整性只是逆条件，即：定义5.9给定m，n ∈ N，幺半群M称为（m，n）-可精化的，如果对任意r1，.，rm，c1，.，cn∈M其中r1+. + rm= c1+. + cn可以求出M的元素的m× n-矩阵（ai，j），其行和为r1，.，rm且其列和为c1，...， cn.显然，当m= 1或n= 1时，条件是空的。当m >1时，则M是（m，0）-可重构的，且它是正的。对于其余的情况，我们证明：命题5.10对任意m，n>1，我们有：交换么半群是（m，n）-refinable，则它是（2，2）-refinable。证据在r 1 +..的（m，n +1）-精化中，. + rm= c1 +.. . + cn +0，我们可以将最后两行中的相应元素相加，以获得r1+.. + rm= c1+. + cn，所以一个方向是明确的。另一个方向是证明了一个简单的归纳的列数，其次是一个类似的归纳的行数。作为提示，我们展示如何从（2，2）到（3，2）：给定r1+r2+r3=c1+c2，使用（2， 2）精化性质找到一个列和为c1，c2，行和为r1，（r2+r3）的2×2-矩阵（ai，j）现在a2，1+a2，2=r2+r3，所以有另一个行和为r2，r3，列和为a2，1，a2，1的2× 2矩阵：和a1， 1a 1， 2r 1a2， 1a 2， 2r2+r 3c1c2b1， 1b 1，2r 2b 2， 1b2， 2r 3GUMMANDSCHR？DER199Mω··联系我们联系我们ωL∈Na1， 1a 1，2r 1b 1， 1b1 ，2r 2b2 ， 1b 2 ，显然，下面的矩阵解决了原来的问题：作为这个命题的结果，我们可以简单地称一个交换幺半群是可再细的，如果它是（2， 2）-可再细的。可精化性并不意味着正性，因为非平凡阿贝尔群是可精化的，但不是正的。在下一节中，我们将需要以下观察，涉及无限矩阵：引理5.11假设M是可定义的。给定X，Y非空集，σ∈X和τ∈MY，其中（σ（x）|x∈X）<$=（τ（y）|y∈Y）。存在一个| × Σ|Y|- 矩阵（m x，y），具有r个低和（m x，y）|y∈ Y）= σ（x）和c列|y∈Y)=σ(x)andcolumn和（mx，y|x ∈X）= τ（y），其中除了有限个mx，y都是0。命题5.10使得检验例5.8的前两个实例是可重构的变得容易事实上，任何交换幺半群是可消的，并且满足r∈M. x∈M。c=x+r或r=x+c它很容易被认为是可修复的。这也包括（N，+，0）的情况在（N0，， 1）的情况下，可重构性是每个元素都有唯一素因子分解这一事实的结果。可重整性不会延续到次幺半群。例如，考虑前一个例子中的子幺半群（N0， 2，， 1）和精化问题5 6 = 3 10。任何细化都需要素数因子2，而这是不可用的。在格L的情况下，我们得到一个熟悉的性质：引理5.12如果L是一个最小元素为0的格，则（L，n，0）是可再细的当且仅当L是分配的。证据 给定一个分配格和a，b，c，d L，其中ab = c d，然后我们有一个 细化ac ad a b cbdbC d相反，如果L不是分配的，则以下格之一，已知GUMMANDSCHR？DER200ωSωωωω→→MMx y az ubB C作为N5， M3，m必须是L的子格（参见例如，[Gréa98]）：p，p，，N5=b，，、、、，c一M3=一，b、、、、、、、Cqqq在这两种情况下，a=b=c。假设我们有一个改进其 中 x ， y ， u ， v∈L.从 表 中 可 以 看 出 ， u≤b 且 u≤c ， 因 此u≤b<$c=q≤a。此外，y≤a，因此u∈y=c≤a。但在M3和N5中c /≤ a。5.3弱回撤保存现在我们研究函子M（-）弱保持的条件非空内核对、沿注入的回调或任意回调。一个函子F被称为沿着内射映射（弱）保持拉回，对于任意f：XZ和g：Y Z，g是内射，f的（弱）拉回g被F变换为F（f）的弱拉回，F（g）。在[GS00]中，我们证明了 et-闭函子F弱保持沿着内射映射的非空拉回当且仅当任何F-子余代数V ≤ B在同态<$A → B下的原像<$−[V]又是A的子余代数。对于L-余代数，根据推论，这个条件总是满足的。3.7.然而，我们将看到，对于Mω-余代数，情况未必如此。事实上，我们将代数地刻画那些幺半群M，对于这些幺半群M，M（−）沿着内射映射保持弱拉回。最后，我们考虑任意弱回调的保持定理5.13设M =（M，+，0）是交换幺半群.(i)（−）（弱）保持沿内射映射的非空拉回i∈ i。(ii) M（−）弱保持非空核对i ∈ M是可再定义的。(iii) M（−）弱保持非空回调，i ∈M是正的且可重新定义的。证据（i）：设M是正的，设V：A → B是M-余代数的同态，V是B的子余代数.我们需要证明、GUMMANDSCHR？DER201|− →BQ∈| |× ||x为ohx为ohx为ohx为ohA=[V]是A的一个子余代数。 Gi vena∈N−1[V]，aJ∈N−1[V]andnda−m→aJ，我们需要证明m=0。我们知道，由par t，可以得到n（a）∈V，n（AJ）∈/V，s（i）我们得出了<$（a）−→0<$（AJ）。Part（ii）ofthesamelemma则yields n（n an x，则x（x）= x（aJ））= 0。正性迫使每个被加数都是0，特别是m= 0。为了证明其逆，设m1，m2∈M，m1+m2= 0.考虑余代数A，由一个点p和两个到点q1和q2的转移给出，标记为m1和m2。让由两个点r和s组成，转换（所有转换标记为0）。我们得到一个同态<$p，其中<$p（p）= r，<$q（q1）=<$q（q2）= s.现在{r}是B的一个子余代数，并且这个假设强迫<$-1{r}={p}是A的一个子余代数，但是这意味着m1= m2= 0。p，rM1q1sJ，m2vz2ϕ0=BSJ这个构造的一个轻微的修改也给了我们（ii）的向后方向：假设F弱保持非空核对，那么同态的核是互模拟。假设m1+m2=s1+s2，M. 我们像上面一样取A的一个副本AJ，但是我们用s1和s2标记AJ的弧。若BJ是由B通过改变边标号m1+m2=s1+s2得到的，则存在一个明显的同态<$：A+AJ→BJ.它的内核必须是互模拟，也就是引理5.5，为我们提供了一个精化m1+ m2= s1 + s2。我们结合了（ii）和（iii）的给定同态A→ C和B→ C，我们需要证明pb（a，b）：={（a，b）|<$（a）=<$（b）}是A和B之间的互模拟。设（a，b）pb（n，n）为已知。 我们将定义一个AB-矩阵（mx，y）其中M的元素满足引理5.5的条件Rx对于anyc∈<$[A]<$$>[B]，设X：=<$−1（{c}）andrx：=α<$（a，x），即a−→x，对于一个nyx∈X.类似地，对于每个y∈Y，Y：=β <$−1（{c}）和dcy=β<$（b，y）。根据引理5.11，我们得到一个|X| × |Y|行和为（rx）x∈X的矩阵（m c）列和（cy）y∈Y。我们可以做到这一点• 对于几乎所有的c都是（mc0-矩阵• 在每一个（mc）中的所有但有限的条目）为0。最后|一|× |B|- 矩阵（mx，y）通过将所有（mc））一起GUMMANDSCHR？DER202ΣΣ（mJSSωLL M LMM然后用零填充：mx，y：=.cx，y如果n（x）=c=n（y），0否则。通过构造，mx，y0表示（x，y）∈pb（x，y）. 此外，除了m的无穷多个条目x为oh）为零。这是因为a−→raJ。我们需要为了示出第J行和是r，即，（maJ，b|b∈B）= r. Σ令c：=f（a，J）。如果<$-1（{c}）<$，则（maJ，b | b ∈B)=C甲乙丙| b ∈B）=r. 如果-1（{c}）=（这种情况在（ii）中不会发生），我们将调用当r=0时，对sho的积极性。Sp ∈y，对于s，其中n（a）−→scweave（m）|a−m→aJ，<$（aJ）=c）=s=<$（m|b−m→bJ，则n（bJ）=c）=0。因此，对于某个u∈M，r+u= 0，由此r= 0。一个更优雅的方式来看待（iii）是直接从（i）和（ii）得出结论，通过引用第二作者论文中的以下引理引理5.14 [Sch 01] et-闭函子弱保持拉回，其中它弱保持核对和沿着内射映射的拉回。6讨论这项研究的一个动机是提供一个存储库的例子et-endofunctors与特定组合的保存属性。这是通过参数化一类具有代数结构的函子，并将函子的性质转化为相应的代数定律来实现的。例如，定理5.13可以用来得到一个函子弱保持非空核对，但不弱保持非空拉回的例子：简单地选择任何非平凡阿贝尔群。当然，-余代数和（-）-余代数作为-，分别。 - 标记的过渡系统是独立感兴趣的。- 值集合和关系是在[Gog67]中考虑Goguen。在书[FS 90]中，Freyd和Scedrov考虑了关于“L值关系”R：A × B →L和S：B × C → L的以下运算（R<$S）（a，c）：={R（a，b）<$S（b，c）|b∈B}。当L={ 0， 1}时，这与熟悉的关系组合一致。的M···0···0 （mc）x为oh0···0···GUMMANDSCHR？DER203L+联系我们A × C B CAA× ×A B ×× B作者注意到，这个操作是联合的，它是有限分布的连接（JID），在[Bor94]中也称为localeL. 莫斯，在[Mos99]，认为以下翼子函子R（−）：Q（X）：={f：X → R |supp（f）finite，Σx∈Xf（x）= 1}。这个函子的余代数是随机转移系统（[Mos99]，[dVR99]）.Moss提出了R +的“R w/Column-theorem”，即对于每个m，n > 1，R是（m，n）-可重构的(He将行/列定理的证明归功于Saley Aliyari）。我们从代数研究的经典路线中借用了Refinable一词，要求存在唯一的乘积分解，有限代数 如果1.. .mm=1.. .n是两个表示同样的有限代数作为不可分解的乘积，人们会得出m=n和Bi=Aτ（i），对于某些p？很容易找到没有唯一分解的有限代数的例子。 在这种情况下，仍然有可能证明一个重新-最终结果：Gi venthat A1×.. . ×Am=B1×.. . × Bn，则each因子可以进一步分解为更小的代数Qi，j的乘积，直到1在左侧和右侧具有相同的因子Qi，j的集合J.D.H. 史密斯提醒我们B的一个结果。 Jonsson和A. Tarski [JT 47]指出一类代数，其中运算是二元运算+和常数0，它对+是中性的，对所有基本运算都是幂等的，具有（m，n）-精化性质。这意味着所有有限的Jonsson-Tarski代数的类，具有由直积（）给出的幺半群结构和0作为中性元素，是一个可加细幺半群。J′onsson和Tarski需要运算+和0来表示直积作为如果没有这样的假设，一般来说是不可能的，因为refinement意味着cancellability：A×B===. 当有一个1-元素子代数时，可消根据L.Lova′sz（[Lov67]），但除此之外，人们需要用较弱的“isotopy”概念来代替在[GH 79]中证明了同余模簇中代数的一个直到合痕的引用[Bor94] F.鲍索，范畴代数手册1：基本范畴理论，剑桥大学出版社，1994年。E.P. de Vink 和 J.J.M.M.Rutten ， Bisimulation for probabilistic transitionsystems ： a coalgebraic approach ， Theoretical Computer Science（1999），no. 211，271GUMMANDSCHR？DER204[FS90] P. Freyd和A. Scedrov，类别，寓言，爱思唯尔，1990年。[GH79] H.P. Gumm 和 C. Herrmann ， Algebras in modular varieties ： Baerrefinements ， cancellationandisotopy ， HoustonJournalofMathematics5（1979），no. 4，503[Gog67] J.A. Goguen ， L-fuzzy sets ， Journal of Mathematical Analysis andApplications（1967），No. 18，145G. Grtzer，Gene rallatti ceth e or y，Birkhuser
我的内容管理
展开
