单子和部分求值构造的研究

可在www.sciencedirect.com在线获取理论计算机科学电子笔记352（2020）129-148www.elsevier.com/locate/entcs单子、部分求值和重写Tobias Fritz1加拿大安大略省滑铁卢圆周理论物理研究所保罗·佩罗内2美国麻省理工学院数学系摘要单子可以被解释为编码形式表达式，或泛代数意义上的形式运算。我们给出了一个构造，它形式化了“部分求值表达式”的概念：例如，“2+3”可以作为“2+2+1”的部分求值来获得。 这个构造可以对任何单子给出，它与著名的bar构造[15，VII.6]相联系，它给出了bar构造的操作解释：bar构造是一个单纯集，它的1-胞是部分求值。研究了一般单子的部分求值的性质。我们证明了，只要单子是弱carbohydrate，部分评估可以组成通过通常的Kan filler性质的单纯集，我们用术语替换的方法来解释它对于概率单子的情形，部分评价对应于概率学家所称的随机变量的条件期望，部分评价关系被称为二阶随机优势。在重写方面，部分评估给出了一个抽象的约简系统，该约简系统是自反的，连续的，并且只要单子是弱可迁的就传递。这份手稿是正在进行的工作的一部分，对酒吧建设的一般重写解释关键词：单子，棒结构，重写，高维重写，单纯集，随机优势。1背景：单子和形式表达式根据泛代数[9]对单子理论的一种解释是，单子就像签名中形式表达式空间的一致选择。这种解释对于集合范畴上的单子是最准确的，但范畴结构一般都有效。更详细地说，monad由以下数据组成。首先，我们有一个函子T：C → C，它由以下赋值组成：1电子邮件：tfritz@pitp.ca2电子邮件：pperrone@mit.eduhttps://doi.org/10.1016/j.entcs.2020.09.0071571-0661/© 2020作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。130T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129(a) 对于每个空间X，我们指定一个新的空间TX，我们认为它包含了X的元素在某个签名中的形式表达式，模由理论指定的方程。 例如，TX的元素可以精确地 是X的元素的形式和。(b) 给 定 两 个 空 间 X 和 Y 以 及 一 个 函 数f： X→Y， 我 们 得 到 一 个 函 数 Tf：TX→TY，我们认为它是逐元素替换。这种分配应保持身份和组成。在形式和的情况下，给定一个函数f：X→Y，我们自动得到一个函数，从X的元素的形式和到Y的元素的形式和，只需举例来说a+ b +2 c<$−→f（a）+f（b）+ 2 f（c）。（1）在形式和的情况下，任何元素x都可以被认为是一个（平凡的）形式和，和。对于一般的单子，这被编码在单位自然变换η：idCT中。此外，形式和的形式和可以简化为形式和，例如：可降至（a+b+c）+（a+b+d）2 a +2 b + c +d。这通常被编码在单子乘法变换μ：TTT中。然后需要单位和乘法变换来满足单子方程TTTXTμTTX TX TXμμTTXμ ημTXTημTXTX（二）对于C中的所有X。一般来说，C类不需要是具体的。因此，我们不看元素，而是看广义元素：一般来说，我们可以解释为让定义1.1设（T，η，μ）是范畴C上的单子，X是对象。X上的一个广义形式表达式是态射p：S→TX，其中S是C的一个对象。如果T存在于Set上，那么对于S，我们可以取一个单例集1，恢复通常的形式表达式。对于许多具体类别也可以这样做。尽管如此，我们将放弃“广义”这个词通常，形式表达式可以计算为结果。例如，表达式3 + 2可以被评估为5。单子的代数是一个对象，其中（广义）形式表达式可以被评估为实际（广义）元素。T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129131ID因此，对于集合上的形式和单子，代数的范畴正是交换幺半群的范畴，因为在交换幺半群中，形式和可以以一种尊重处理和的通常重写规则（即结合性和交换性）的方式被求值为实际元素。形式上，单子T的代数由一个对象A和一个求值映射e组成：TA→A，在制作图的意义上与η和μTTATeηTA A TAμe eTAe A A通勤。通过（2），每个对象TX是关于μ的代数：TTX→TX，X上的自由代数。定义1.2设（A，e）是一个T-代数。 给出一个（广义）形式表达式p：S→TA，我们称它的结果为由e∈p：S→A给出的A的（广义）元.2部分求值和部分分解考虑到总和和三加四加五（3）七加五。（四）它们不仅有相同的结果，而且我们还可以说，通过对表达式进行部分求值，可以从（3）得到和（4）。同样，我们也可以说，通过对表达式中的项进行部分，可以从（4）中得到和（3）。让我们试着把它弄得精确一点。其思想是存在形式和的形式和，即具有一级括号的形式和，使得移除括号产生左边的项，并且使得执行括号中的操作（然后移除括号）产生右边的项那就是：（3 + 4）+（5）删除括号计算括号3+4+5 7 + 5正如我们在第1节中所看到的，“形式和的形式 可以被看作“去掉括号”的映射然后我们可以给出所有单子的部分求值的一般定义132T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129□定义2.1设（T，η，μ）是范畴C上的单子，设（A，e）是T-代数，考虑形式表达式p，q：S→TA。p到q的部分求值，或q到p的部分分解是映射k：S→TTA，或TAμSKTTA TATe2.1基本性质根据定义和三角恒等式，我们立即得到以下结果，这是一种一致性检查：任何表达式都有两个平凡的部分求值，即对自身和对其结果（被视为形式表达式）的求值。命题2.2设（A，e）是如上所述的T-代数，且p：S→TA. 然后又道：(a) p允许对自身进行部分求值(b) p允许对η ∈ φ p的部分求值，我们称之为它的全求值。证明(a) 考虑（Tη）πp：S→TTA。则由单子的右酉性（2）得到μ（Tη）p=p，由T的函性和代数的单位条件得到（Te）（Tη）p=T（eη）p=p因此，（Tη）p给出p到自身的部分求值(b) 考虑ηp：S→TTA。 我们有一张图表ηTA TTAeTeη的TA其通过η的自然性来交换。 现在，μπιπρ=ρ，通过左酉性，单子，和（Te）<$η<$p=η <$e<$p通过上面的图的交换性。因此，ηp给出了p到ηep的部分求值。例2.3考虑Set上的自由交换幺半群单子（或多重集或袋单子），取代数（A，e）为加法下的自然数集合N，设S= 1，终端集。然后，形式表达式是自然数的和，被认为是排列的列表。表达式3 + 4 + 5允许对自身进行部分求值，由下式给出：(3)+（4）+（5）删除括号计算括号微碲3+4+5 3 + 4 + 5pQT. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129133并将部分评估或总评估转化为其结果12，由下式给出（3 + 4 + 5）删除括号计算括号微碲3+4+5 12这里是另一个一致性检查：如果p允许对q进行部分求值，则p和q必须具有相同的结果。命题2.4（全评价定律）考虑形式表达式 p，q：S→TA，并假设存在从p到q的部分求值。那么p和q必然有相同的结果，即 e q = e p。证明T-代数（A，e）的乘法平方是交换图TTATe TAμeTAe A现在假设k：S→TTA给出p到q的部分求值，即 μ k = p，且（Te）k = q。然后，由于通勤上方的广场，eq=e（Te）k=eμk=ep，正如将要展示的那样。□例2.5在例2.3之后，有一个从3 + 4 + 5到7 + 5的部分表达式，由（3 + 4）+（5）证明：（3 + 4）+（5）删除括号计算括号微碲3+4+5 7 + 5这两个形式表达式必然有相同的结果，在这种情况下，12。2.2组成部分评价部分求值还有另一个吸引人的性质，即如果我们可以将p部分求值为q，将q部分求值为r，那么我们期望我们应该能够将p部分求值为r。例2.6再次考虑自然数的和。那么形式和1 + 1 + 1 + 1可以部分地求值为2+ 2，2 + 2可以部分地（和134T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129TeTeμμTeμTeμμTTe总的来说，评价为4。这一点可从以下几个方面得到证明：（1 + 1）+（1 + 1）（2 + 2）1+1+1+1 2 + 2 4为了构造一个从左到右的部分求值，我们需要一个表达式，使得去掉它的方括号得到1 + 1 + 1 + 1，而计算方括号得到4。这个想法是4是由2 + 2得到的，但表达式中的每个2本身都是由1 + 1得到的。因此，我们可以用它是部分求值的项来替换每个项2，换句话说，我们形成位于图中的表达式（（1 + 1）+（1 + 1））：（（1 + 1）+（1 + 1））（1 + 1）+（1 + 1）（2 + 2）微碲1+1+1+1 2 + 2 4为了得到复合部分求值的证明，我们必须通过映射Tμ移除内部嵌套或内部括号。这样得到的元素是（1 + 1 + 1 + 1），正如预期的那样：（（1 + 1）+（1 + 1））Tμ（1+ 1）+（1+ 1）（1+ 1+ 1+ 1）（2+ 2）μμ1+1+1+1TeTe2 + 2 4现在让我们试着概括上面的例子，以及“替代”的作用。首先，让我们介绍一些术语。我们回顾一下卡波单胞菌的定义。定义2.7[例如[13，4.1节]]设（T，η，μ）是范畴C上的单子。monad（T，η，μ）被称为carbohydrate，如果：• 函子T保持回调;• η和μ的所有自然平方都是回调。例2.8Set上的每个由（非对称）操作数产生的单子都是carnival[13， SectionC.1]。正如我们将看到的，对carbohydronads的部分求值表现得特别好。但笛卡尔性也是一个非常严格的条件，因此我们认为μTTeT. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129135它的一个变体，基于弱回调的标准概念定义2.9设C是范畴。 C区的通勤广场FA BGmCn D是弱拉回，如果对于C的每个对象S和一对箭头b：S→B，c：S→C使得m<$b=n<$c，存在箭头a：S→A使得下图可交换：SBMCn D注意，我们不要求映射a是唯一的。 我们用它来推广弱Carnummonad的概念[19，3]从集合到所有范畴。定义2.10设（T，η，μ）是范畴C上的单子。我们说（T，η，μ）是弱carnival，如果：• 函子T保持弱拉回;• η和μ的自然平方是弱回调。例2.11Set上的自由幺半群单子是carnival[3，观察2.1（d）]。Set上的自由交换幺半群单子是弱carnival，但不是carnival[3，例8.2]。我们得到以下结果：命题2.12设T是范畴C上的单子。设（A，e）是一个T-代数，并假设下图是一个弱拉回：TTTATTeTTAμ μTTATe TA（五）然后，在形式表达式C（S，TA）的每一个集合上的部分求值关系是可传递的。证明我们必须证明以下内容：给定p，q，r：S→TA和k，h：S→TTA使得（Te）k=p，μk=（Te）h=q，μh=r。则存在ρ：S→TTA使得Te<$ρ=p和μ<$ρ=r。一B一FCG136T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129现在考虑交换图：QS TAhμTeKTTA TTATTep μrTeTTTA微（6）TATμTATeμTTA（其通过合成、结合性和自然性正方形来交换然后我们有p在左下角，q在右上角，r在右下角，而k在左上角，h在右上角。由于上面的菱形恰好是图（5），假设它是一个弱拉回图，存在a：S→TTTA使得（6）仍然是可交换的。因此ρ：=（Tμ）a使得（Te）ρ = p和μ ρ = r。□由于平方（5）必然是任何弱Carbohydronad的弱回调，我们有推论2.13设T是弱卡波单子。 则对每个T-代数（A，e）和每个对象S，C（S，TA）上的 部分赋值 关系 是传递的。由于自由交换幺半群单子是弱Carnival的，这个构造重现了例2.6。同样地，如果T是carbohydrate，或者仅当μ是carbohydrate，则图（5）是拉回。这使得部分求值的合成成为一个代数运算，如果我们跟踪TTA的元素，它见证了每个部分求值关系。3作为单纯对象图（6）基本上编码了条形结构的前三个层次[15，第VII.6节]。特别地，命题2.12的弱拉回条件，就像范畴神经和更一般的准范畴神经一样，正好是一个适用于小节结构的Kan filler条件。更一般地说，T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129137具有部分求值关系的更高范畴扩展的性质。对它的更高成分性质的研究正在进行中;在本节中，我们将描述到目前为止我们所知道的定义3.1设T是C上的单子，（A，e）是T-代数。（A，e）的横截是T-代数范畴中的单纯对象A·，对于所有i≥0，通过以下赋值给出：• Ai：=Ti+1A;• dj：Ai+1→Aigivenby· Tj μ：Ti+2A→Ti+1A，0≤j i + 1，以及· Ti+1e：Ti+2A→Ti+1A（j=i+1）;• sj：Ai→Ai+1givenbyTj+1η：Ti+1A→Ti+2A，其中0 ≤j≤i.单形恒等式由单子和代数结构以及结构映射的自然性保证成立这意味着，特别是，给定C的对象S，我们得到一个单纯集C（S，A·），具有以下解释：• 单纯集的顶点由TA的（广义）元素给出，（广义）形式表达式;• 1-单形是由部分求值的见证者给出的：因为源和目标图d0，d1：C（S，A1）−→ C（S，A0）是通过应用μ和Te精确给出的，如部分求值关系的定义，定义2.1。因此，我们可以把杆构造的1-单形看作指向部分求值方向的箭头;• 对于每个顶点，或等价的形式表达式，映射s0：C（S，A0）−→ C（S，A1）T η给出了一个“恒等”1-单形，它有正确的源和目标，对应于命题2.2的证明。• 1-单形的合成，当在命题2.12的证明中定义时，由一个2-单形给出，它正好是一个内角的Kan filler。当T是弱可积时，这个填充子总是存在的。当T是范畴时，这个填充器是唯一的，并且由此产生的单纯集甚至是范畴的神经[18]。由于部分求值（或等价地，部分分解）在大多数情况下是内在定向的，这些单纯对象（以及我们通过用对象S证明它们而得到的单纯集）给出了内在定向的“空间”。作为空间，用有向同伦理论的方法和工具来研究它们似乎是最自然的（例如见[8]）。4在重写系统抽象归约系统（ARS）是一个具有二元关系的集合，称为归约关系[1，第1章]。138T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129给定C上的一个单子T，一个T-代数（A，e）和一个对象S，S-指标表达式的部分求值给出C（S，TA）上的一个二元关系。第2节的结果给出了以下结果。命题4.1集合C（S，TA）配备有部分求值关系→给出具有以下属性的ARS• 自反性：对每个s∈ C（S，TA），s→s;• 结论：如果对于s，t，u∈ C（S，TA），我们有St u则存在z∈ C（S，TA）使得St uz特别地z总是可以由第2.4条;• 如果T是弱Carnival，则→是传递的。部分求值的合成可以被认为是然而，至少在这个框架中，更高的重写规则是用单纯形而不是球形来定义的。5示例这里有一些单子的例子，以及它们诱导的部分求值。这里我们只限于Set上的monad和传统元素（比如，从终端集合1→X的箭头，而不是更一般的箭头S→X）。Monoid和group action monads。设G是Set中的幺半群（或群）.同样的例子在广义元的范畴中对内部幺半群（或群）更普遍地适用，但为了简单起见，我们只在Set的情况下解释它赋值X<$→G×X是一个具有单子结构的函子的一部分，其单位和乘法由G的单位和乘法导出，代数e：G×A→A是具有G-作用的对象。设（g，x）和（h，y）是G×A的元素。我们有（h，y）是（g，x）的部分求值，当且仅当存在一个T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129139LLXH元素（h，l，x）∈G×G×A使得hl=g，lx=y.在图片中：Gx gx换句话说，（h，y）是（g，x）的部分求值当且仅当我们可以写g作为复合HL，使得所以（h，y） 如果G是一个群，则无论x和y在同一轨道上，我们可以找到上面的分解，通过设置l=h−1g，并且部分求值关系是对称的：它是通过属于同一轨道而给出的等价关系。相反，如果G只是一个幺半群，那么部分求值关系通常比在同一轨道上更强，并且不需要 是对称的由于这个单子（在集合上）与一个非对称操作数相关联，所以它是一个carbohydronad。因此，部分求值的见证人可以唯一地组成（并且它们的组成由幺半群或群的组成给出）。在这种情况下，其神经是由棒结构产生的单纯集Set（1，A·）的范畴具有如上所述的对（g，x）作为对象，具有如上所述的三元组（h，l，x）作为态射，具有domain（hl，x）和codomain（h，lx）。幂等单子对于幂等单子，很容易检查所有部分求值都是平凡的，因为部分求值关系是相等关系。自由幺半群。这个单子也与一个操作数相关联。因此，也是在这里，部分评价可以被唯一地组合，并形成一个范畴。我们目前还不知道对这一类别的更明确的描述。自由交换幺半群单子。这是一个弱的单胞菌[3]。因此，部分评估证人在TTA仍然可以组成，但组成通常不是唯一的。6概率中的部分求值概率单子的部分求值允许比较概率分布的分布度或随机度。测量概率测度的“随机性”的常用方法是像方差和熵这样的泛函。然而，有一些重要的信息是单个实数无法编码的。直觉上，一个数字只能衡量例6.1例如，考虑R上的概率分布，其密度如下图所示。140T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129.ΣQRp−1 0 1我们可以说p相反，虽然r看起来比q更在偏序中，我们可以说q和r是不可比较的。 在更高的维度中，如果两个分布在同一个中心，情况也是如此。质量之三，但沿着不同的方向。这就是我们所说的事实证明，部分评估可以用来检测这种更精细的随机性概念，并且它们与所谓的二阶随机优势关系有关[4]。在本节的其余部分中，我们将概述这是如何工作的。第二作者的博士论文[ 16，第4章]中已经详细阐述了这一点我们将再次关注集合论元素，而不是广义元素。6.1概率单子在概率论的背景下使用单子的想法，正如我们在这里描述的，可以追溯到Lawvere[12]和Giry[7]。我们已经看到，单子可以用编码可能的“操作”的形式表达式来解释。在概率单子的情况下，所讨论的操作是形式上的凸组合或混合。考虑一个硬币的随机数，其中然后从某种意义说，这是“头”和“尾”凸组合从形式上讲，{“heads”，“tails”}不是定义凸组合的集合，所以不能真正取其元素的实际混合。但是，可以将{heads， tails}嵌入到空间λ“正面”+（1 − λ）“反面”|λ∈ [0，1]，使用地图，“正面”›→ 1“正面”+ 0“反面”，“反面”›→ 0“正面”+ 1“反面”。在这个新的空间中，人们实际上可以采用凸组合：例如，在一个实施例中，1/ 2一般来说，人们不仅要考虑有限凸组合，而且要考虑关于归一化测度的积分，所以我们在Choquet理论[20]的意义上讨论广义但解释是一样的。T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129141• 给定一个对象X，我们可以认为它是一组可能的（确定性的）状态，我们可以形成一个对象PX，它包含• 每一个函数f：X→Y通过凸线性扩张给出一个函数Pf：PX→PY;• X通过映射δ：X→PX嵌入到PX中，映射δ：X → PX映射元素x∈X到平凡形式凸组合x;• 形式混合物的形式混合物可以使用映射E：PPX→PX，如下例所示。例6.2假设你的口袋里有两枚硬币。假设一枚硬币是公平的，一面是“头”，另一面是“尾”;假设第二枚硬币两面都是“头”。假设现在你随机抽到一枚硬币，并将其命名。我们可以用下面的方法来描述概率？硬币1硬币2二分之一二分之一10正面反面正面反面设X是集合{一枚硬币给出了一个定律，根据这个定律，我们将获得既然选择硬币的概率也是随机的（我们也有一个关于硬币的定律），关于硬币的定律决定了PPX的一个元素。通过平均，得到的总概率为？三分之四四分之一正面反面换句话说，有一些空间，例如R，可以取实际的混合物。这些完全对应于P的代数。换句话说，P-代数是一个具有（有限的，也可能是无限的）满足适当方程的凸组合的空间，比如某个向量空间的凸子集取期望值是概率论中最重要的运算之一：可以这样做的空间正是概率单子的代数在实践中如何实现这一点的细节是不同的，这取决于对范畴、单子等的选择，所以特别是，人们可能会得到不同种类的我们在本节中使用的概率单子二分之一二分之一142T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129Σ.XΣmonad，作为代数恰好有Banach空间的闭凸子集（见[6]）。文献中的另一个例子是紧Hausdor空间范畴上的Radon单子：它的代数恰好是局部凸拓扑向量空间的紧凸子集[21，11]。6.2两个例子我们在这里回顾两个概率单子的定义：在理论计算机科学中使用的集合上的分布单子，以及在完备度量空间范畴中可以被认为是可能连续分布的类似物的康托洛维奇单子首先，我们勾勒出分布单子的基本结构，也称为凸组合单子或无限吉里单子。设X是一个集合。 定义DX为元素为函数p：X→[0， 1]的集合使得p（x）0仅对有限个x，且<$x∈Xp（x）= 1。注意到如果不包括所有消失项，则上述总和是有限的DX的元素是称为X上的有限分布或有限支撑概率测度。给定一个函数f：X→Y，我们定义前推函数Df：DX→DY如下。给定p∈DX，则（Df）（p）∈DY是函数y›→x∈f−1（y）p（x）。这使得D成为Set上的内函子。单位映射δ：X→DX将元素x∈X映射到由下式给出的函数δx：X→[0，1]：δ（y）=1y=x;0y/= x。乘法映射E：DDX→DX将函数E ∈DDX映射到函数E∈DX给出E（x）=p（x）（p）.p∈DX映射E和δ满足通常的单子定律。D-代数被称为凸空间，它们的态射被称为凸映射或凸线性映射。 更多细节，请参见[5]和[10]。Kantorovich单子是完备度量空间和短（非扩张）映射范畴CMet上的单子，即函数f：X→Y使得对于每个x，xJ∈X，D. f（x）， f（xJ）≠≤d（x，x，J）。定义6.3设X是完备度量空间。Kantorovich-Wasserstein空间PX是其元素是X上具有有限一阶矩的Radon概率测度的空间，其度量由下式给出d（p，q）：=supf：X→Rdp−dq，T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129143∫Σ⎝Σ⎠其中上确界是所有短映射X→R的上确界。赋值X<$→PX是函子的一部分：我们可以赋值给每个态射f：X→Y是一个态射Pf：PX→PY，由概率测度的前推给出。换句话说，如果p∈PX且A是Y的可测子集，则：（Pf）（p）（A）：=（f<$p）（A）= p（f −1（A））。单子的单位由狄拉克δ映射δ：X→PX给出，它赋予每个x∈X集中在X的狄拉克质量δx。 组合E：PPX→PX由积分给出，如例6.2所示：如果μ∈PPX且A为X的一个可测子集，则（Eμ）（A）：=p（A）dμ（p）。PXKantorovich单子的代数必须是我们范畴，即完备度量空间的所有对象中的第一个。此外，正如我们已经看到的，它们在某种意义上关于凸组合应该是封闭的，例如向量空间的凸区域。Banach空间的闭凸子集是理想的候选：它们是完备度量空间，并且它们是凸的。可以证明[6，5.3节]CMet中的P-代数恰是Banach空间的闭凸子集欲知详情，请参阅[6]和[16]。6.3部分期望、扩张、条件期望现在让我们研究上面提到的两个概率单子的代数的部分求值。 本小节中关于康托洛维奇单子的材料可以在[16，Section 4.2.1]中找到更多细节，特别是，所有的证明都可以在那里找到（模一些术语上的差异）。这一结果与Winkler和Weizzéacker的工作密切相关（见[20]和其中的讨论）。首先，对于两个单子，部分求值关系是传递的。命题6.4考虑函数f：X→Y。下面的交换图是一个弱回调。DDXμDXDDfDFDDYμDY证明设p∈DX，α∈DDY为形式凸组合α：=q∈DYα qδq yδy。y∈Y144T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129ΣΣ⎝Σ⎠ΣΣ设p=<$xpx（x），并假设μ（α）=f<$p，这意味着对任何y∈Y，q∈DYαq qy=x∈f−1（y）px.现在取由下式给出的测度β∈DDX：我们有β：=q∈DYα qδ<$q y·p|是的。y∈Yfβ=α qδqyf（p|y）=α qδqyδy=α。不过，q∈DYy∈Yq∈DYy∈Yμ（β）=μ∈α q<$q y·p|y=α qq y·p|y∈q DY=y y y∈Y q∈DYpx·p|y=（fp）yδ y·p|y= fp·p|y= p。y∈Yx∈f−1（y）y∈Y□Kantorovich单子的类似陈述是下面的结果[16，定理2.6.9]：定理6.5对于每个自然平方TTXE TXTfTTYE TY在乘法变换E：PPP中，弱拉回所需的弱普适性对于单点空间1之外的映射成立。这足以说明Kantorovich单子代数的部分求值关系但更普遍的是，我们不知道：问题6.6康托洛维奇单子的乘法是弱卡里吗？给定一个集合或完备度量空间X，设p，q分别是DX或PX中的从p到q的部分求值背后的直觉是，q比p“更集中”，或者“更接近其质心的δ”从统计学的角度来看，q比p更好地近似于它的期望值，因为p“T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129145ΣΣ同样，逆过程，部分分解，也是有用的概率。这是已知的，它被称为扩张：一个随机映射，直观上“只扩散，但不平移”（想想没有漂移的扩张，或鞅的核）。在统计学中，这大致相当于定义6.7在集合范畴中，设（A，e）是一个D-代数（例如，A=R），设p∈DA.一个p-扩张是一个映射k：A→DA，使得对于p的支撑下的所有a，e（k（a））=a。定义6.8在完备度量空间范畴中，设（A，e）是P-代数。对p∈PA，p-扩张是一个映射k：A→PA，e（k（a））=a，其中p-几乎所有a∈A.简单地说，每个扩张都是p扩张.最平凡的伸缩是D和P的单位分量。命题6.9在集合范畴中，设（A，e）是D-代数，且p，q∈检察官 以下条件是等效的：(a) 存在p到q的部分分解;(b) 存在一个p-扩张k使得E <$Dk（p）= q.证明• （a）n（b）：设r∈DDA是p到q的部分分解，即De（r）=p和E（r）=q。构造一个映射k：A→DA如下。对于每个位于r的支撑中的s∈DA，注意e（s）∈A位于p=De（r）的支撑中现在，对于p的支撑中的每个a，通过“条件”定义k（a）∈DA1k（a）（b）：=p（a）s∈εe−1（a）r（s）s（b）对于所有的b∈A。 在p的支集外k的值可以是任意的，我们得到一个p-伸缩。此外，委员会认为，Dk（p）（s）=p（a）k（a）=r（s），一所以Dk（p）=r，所以E∈Dk（p）=q。• （b）n（a）：定义r：= Dk（p）。我们假设E（r）=q。此外，对于p的支持下的每个a，e（k（a））=a，使得De（Dk（p））（a）=p（a）e（k（a））=p（a），一因此De（r）=p。因此，r是q到p的部分分解。□然后，我们又得到了连续情形的以下结果[16，引理4.2.17]。146T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129GG定理6.10在完备度量空间范畴中，设（A，e）是P-代数，p，q∈PA.以下条件是等效的：(a) 存在p到q的部分分解;(b) 存在一个p-扩张k使得E∈k∈p = q。我们得到了一个额外的解释：在概率的上下文中，p到q的部分分解是一个“添加噪声”的过程相反，我们也可以将部分评估解释为“消除噪音”。在概率论中已经存在一个直观上是“部分期望”的概念事实证明，这两个概念在某种意义上是等价的，至少在康托洛维奇单子的情况下是如此定义6.11考虑一个概率空间（X，F，μ），F的一个子σ-代数G，和可测映射f，g：X→A使得f∈μ和g∈μ有有限个一阶矩。我们说g是给定G的f的条件期望，如果：• 函数g也是G-可测的;• 对于σ-代数G中的每个G，我们有gdμ=为了简洁起见，我们将术语扩展到图像度量本身：定义6.12设p，q∈PA.我们称p到q的条件期望在概率空间（X，F，μ）中分布，并称F的子σ-代数G和映射f，g：X→A，其中fF-可测，gG-可测，使得p=f<$μ，q=g<$μ，g是f给定G的条件期望.下面是主要结果[16，定理4.2.14]：定理6.13设（A，e）是P-代数，p，q∈PA.以下条件是等效的：(a) 存在p到q的部分求值;(b) 分布中存在p到q的条件期望因此，特别地，命题2.4的总评价定律对应于众所周知的随机变量的总期望定律然而，这并不意味着，只要有p到q的部分估值，它们相关的随机变量就处于条件期望的关系中：我们只是在看分布，我们甚至没有将它们视为联合分布：虽然可以证明，p到q的部分估值和分布中的条件期望都确定了联合分布，但仅仅存在任何一种结构都不能。换句话说，T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129147∫∫没有给出结构的等价性（部分求值和条件期望），而仅仅给出了允许这些结构的性质等价是否可以加强到结构的等价，直到合适的同构的问题，目前仍然开放。再一次，可以给出一个额外的解释，连接到二阶随机优势的概念。我们可以将凹函数解释为其原因是，如果积分测度更“集中”，则凸函数的积分更高。定义6.14设（A，e）是一个P-代数，且p，q∈PA.我们说，在二阶随机优势关系中p ≤ q当且仅当对于每个凹函数f：A→ R，fdp ≤f dq。我们有这个顺序再次等价于部分求值顺序[16，定理4.4.9]：定理6.15设（A，e）是P-代数，p，q ∈ PA. 我们有p ≤ q在二阶随机优势当且仅当有一个部分评估从p到q因此，Banach空间上概率分布的部分求值顺序也以一种分类的方式精确地编码了数学金融中使用的随机性的概念，这是该领域固有的确认这篇论文最初是为应用范畴理论2019学校写的我们感谢我们集团和其他集团的与会者的关注、有益的反馈和富有成效的合作。我们还要感谢DirkHofmann 、 Joachim Kock 、 Steve Lack 、 Rostislav Matveev 、 Paige RandallNorth、Sharwin Rezagholi、David Spivak和Tarmo Uustalu，感谢他们富有成果的讨论和有益的建议。本文的大部分内容都是在马克斯·普朗克数学科学研究所（Max Planck Institute forMathematics in the Sciences）撰写的，我们感谢该研究所提供了出色的研究环境。引用[1] 罗纳德五世布克和弗里德里希·奥托。字符串重写系统。Springer，1993年。[2] 阿尔伯特·伯罗尼应用于方程式逻辑的高维文字问题。理论计算。Sci. ，115（1）：43-62，1993.第四届夏季会议的范畴理论和计算机科学（巴黎，1991年）。[3] 玛丽亚·曼努埃尔·克莱门蒂诺，德克·霍夫曼，乔治·贾尼利泽。经典代数的单子很少是弱carnados的。 J. 同伦关系结构。，9：175[4] Peter C.菲什伯恩分布的随机优势和矩。Mathematics of Operations Research，5（1）：94148T. 弗里茨山口Perrone/电子笔记在理论计算机科学352（2020）129[5] 托拜厄斯·弗里茨 凸空间I：定义与实例 arXiv：0903.5522。[6] 托拜厄斯·弗里茨和保罗·佩罗内。概率单子是有限样本空间的余极限。分类理论与应用，34（7）：170-220，2019。arXiv：1712.05363。[7] 我的上帝。概率论的分类方法。 在Cat egori calas pecctsofto polo gyandanalysis，卷915数学讲义。一九八二年[8] M.葛兰迪斯 有向代数拓扑 剑桥大学出版社，2009年。[9] 马丁·海兰和约翰·鲍尔泛代数的范畴论理解：Lawvere理论与单子。ENTCS，172：437-458，2007。[10] 巴特·雅各布斯。从概率单子到可交换的集合Journal of Logical and Algebraic Methods inProgramming，94：200[11] 克劳斯·凯梅尔紧序空间上的概率测度单子及其Eilenberg-Moore代数。拓扑应用，156（2）：227[12] 威廉·劳维尔概率映射的范畴。见https://ncatlab.org/nlab/files/lawvereprobability1962.pdf，1962年。[13] 汤姆·伦斯特高运算，高类别，伦敦数学学会讲义系列第298卷。剑桥大学出版社，2004年。arXiv：math/0305049.[14] 塞缪尔·米姆拉姆三维重写理论。计算机科学中的逻辑方法，10：1[15] 桑德斯·麦克·莱恩 工作数学家的分类。 施普林格，2000年。[16] 保罗·佩罗内。度量空间中的范畴概率和随机优势。博士论文，莱比锡大学，2018年。 可在www.example.com上http://www.paolperrone.org/phdthesis.pdf。[17] M. Rothschild和J.E.斯蒂格利茨风险增加：I。一个定义。Journal of Economic Theory，2：225- 243，1970.[18] 格雷姆·西格尔 空间与谱序列的分类。高等科学研究 Publ. Math. ，34：105-121，1968.[19] 马克·韦伯。泛型态射，参数表示与弱Carnival单子。 Theory and Applications of Categories，13（14）：191[20] 格哈德·温克勒Choquet阶与单形及其在概率模型中的应用。数学讲义。Springer，1985年。[21] 你好，我是萨维奇。一元函子与有限性。 布湖一个cad。波兰人Sci. S'er. Sci. Math. 是的。Phys. ，22，1974.