单子 (范畴论)

维基百科,自由的百科全书

数学的分支范畴论中,单子(英语:monad),又称三元组(triple, triad)、标准构造(standard construction)、基本构造(fundamental construction[1],是一个内函子英语endofunctor(即由某范畴映到自身的函子),连同满足特定连贯条件英语coherence condition的两个自然变换,三者构成的整体。单子用于研究互为伴随的函子对,并将偏序集上的闭包算子推广到任意范畴。

导论与定义

单子是一类内函子英语endofunctor(连同其他资讯)。例如,若为一对伴随函子的左伴随,则复合是单子。若互为逆函子,则对应的单子是恒等函子。一般而言,伴随关系并不等同范畴的等价,而可以联系不同性质的范畴。为了探讨伴随关系所“保持”的性质,数学家研究单子论。理论的另一半,即藉考虑,以研究伴随关系,是单子论的对偶理论。该类函子称为馀单子(英语:comonad)。

严格定义

本条目中,皆表示某范畴上的单子是函子,连同两个自然变换,分别是单位(其中上的恒等函子)与乘法(其中是复合,亦是的函子),且要满足下列连贯条件英语coherence condition

  • (左右皆为的自然变换)。此处水平复合而得。
  • (两者皆为的自然变换)。此处表示由函子到自身的恒等自然变换。

以上两式,亦可以下列交换图复述:

            

记号的含义,参见自然变换,又或考虑以下更具体的写法,不用水平复合记号,并将各函子作用在任意物件上:

            

定义中,若将当成幺半群的乘法,则第一条公理类似幺半群英语monoid (category theory)乘法结合律,而第二条公理类似单位元的存在性(由给出)。准确而言,上的单子,可以等价地定义为的内函子范畴中的幺半群英语monoid (category theory)。(该范畴的物件是上的内函子,而态射是内函子间的自然变换,幺半结构来自内函子的复合运算。)如此,单子不仅在形式上具有与幺半群相似的公理,甚而单子就是幺半群的特例。

幂集单子

幂集单子集合范畴上的单子。其定义中,函子取为幂集运算,即为集合幂集,而对于函数的子集映至其像集,即。对每个集合,有函数,对每个元素映至单元子集, 并有函数

的若干个子集构成的族,映至该些子集的并集。以上是幂集单子的定义。

两个单子的复合,未必为单子。举例,幂集单子的二次叠代,无法配备单子结构。[2]

馀单子

取上节定义的范畴论对偶英语Dual (category theory),便是馀单子(或馀三元组)的定义。简单复述,范畴上的馀单子,是对偶范畴英语opposite category上的单子。所以,馀单子是由的某个函子,连同馀单位馀乘法(英语:counit and comultiplication)两个自然变换,组成的整体,而三者所要满足的公理,是将原定义中所有态射反转方向而得。

单子之于幺半群,如同馀单子之于馀幺半群。每个集合皆是馀幺半群,且仅有唯一一种方式,所以抽象代数中,较少考虑馀幺半群。然而,在线性代数中,向量空间范畴(配备张量积)的馀幺半群较为重要,以馀代数之名为人所知。

历史

单子的概念最早由罗杰·戈德芒英语Roger Godement于1958年提出[3],当时称为“标准构造”(英语:standard construction)。实际上,该书用到的是馀单子,用作解决某个层馀调英语Sheaf cohomology问题。

其后,单子又出现于彼得·胡伯(Peter Huber)对范畴同伦的研究中。该论文包含由任意一对伴随函子得出单子的证明。[4]

1965年,海因里希·克莱斯利英语Heinrich Kleisli[5],及塞缪尔·艾伦伯格约翰·柯曼·摩尔英语John Coleman Moore二人[6]分别独立证明反向的结论,即每个单子皆可由某对伴随函子产生。后一篇论文中,将单子称为“三元组”。

1963年,威廉·洛维尔英语William Lawvere提出泛代数的范畴论。1966年,弗雷德·林顿(Fred Linton)将该理论用单子的语言表达。[7]单子本身来自拓扑方面的考量,事先似乎比洛维尔的理论更难处理,但已成为用范畴论语言阐述泛代数的方法中,较常见的一个。现今常用的英文名称monad是1971年由桑德斯·麦克兰恩在《现职数学家用的范畴英语Categories for the Working Mathematician》引入,以其类似单子论中的同名哲学概念,即某种能生出其他所有事物的实体。

1980年代,欧金尼奥·莫吉英语Eugenio Moggi理论计算机科学中,利用单子,为电脑程式的若干方面建立模型,包括例外处理、边界情况。[8]此后,有多种函数式编程语言仔细实作此想法,作为一种基本规律,同样称为单子。2001年,若干数学家注意到,用单子研究程式标志语意的方法,与洛维尔的理论,两者之间有关联。[9]。此为代数与语义间的联系,是后来活跃的研究课题。

例子

伴随的复合

若有伴随关系

(即的左伴随,下同),则由此有上的单子。此普遍的构造,取内函子为复合

而单位自然变换来自伴随的单位,乘法自然变换源自伴随的馀单位

反之,给定单子,可以明确找回一对伴随函子,使单子为该对伴随函子的复合。此构造用到下节定义的代数的艾伦伯格-摩尔范畴[10]

两重对偶

给定双重对偶单子(英语:double dualisation monad)源自伴随关系

其中两个函子皆将向量空间映至对偶空间,所以对应的单子将向量空间映至双对偶Kock (1970)对此有更广泛的讨论。

偏序集的闭包算子

偏序集可以视为特殊的范畴,任意两件物件之间有最多一支态射,且有态射当且仅当偏序中。于是,偏序集之间的函子,即是保序映射,而伴随函子对,则组成两偏序集间的伽罗瓦连接,相应的单子是伽罗华连接的闭包算子

自由遗忘伴随

又举例,设群范畴集合范畴遗忘函子,将映至其基集,又设自由函子,由,则的左伴随。此时,对应的单子的作用是,输入一个集合,输出自由群的基集,即字母取自,且无相邻两个字母互为逆元的字串的集合。

该单子的单位变换,由包含映射

给出,该包含映射将的任意元素,看成仅得一个字元的字串,从而是的元素。最后,单子的乘法

串接或“压平”运算,将若干条字串组成的串,映至该串中所有字串前后连接而成的一条字串。至此描述完单子的两个自然变换

前述例子中,自由群可以推广至其他种类的代数结构,即泛代数意义下的任意一英语Variety (universal algebra)代数。如此,每类代数定义了集合范畴上的一个单子。更重要的是,该类代数的范畴,可从单子找回,即单子的艾伦伯格-摩尔代数范畴,故单子可视为泛代数之簇的推广。

另外,尚有一个单子源自伴随关系。在向量空间范畴上,若表示将向量空间映至其张量代数的内函子,则相应有单位自然变换将嵌入到其张量代数,并有乘法自然变换,在处的分量是态射,将张量积之张量积展开化简。

馀密度单子

只要满足某些不强的条件,无左伴随的函子也可以产生单子,称为馀密度单子英语codensity monad。例如,从有限集合范畴到集合范畴的包含函子无法配备左伴随,但其馀密度单子定义在上,将任意集合映至其上所有超滤子集合。 类似例子见于Leinster (2013)。

单子的代数

给定范畴上的单子,可以考虑中的代数物件在该些物件上的作用,与单子的单位与乘法相容。具体而言,代数中的物件,连同态射(称为该代数的结构映射),使得图

皆可交换。

代数间的态射中的态射,且要使

可交换。于是,代数及之间的态射组成范畴,称为艾伦伯格-摩尔范畴(英语:Eilenberg–Moore category),记为.

例子

自由群单子上的代数

为前述自由群单子,则代数是集合,连同由生成的自由群的映射(求值evaluation),且该映射要满足结合律与单位元的公理。换言之,本身就具有群结构,而的映射,是将字串按的群乘法,计算所得的结果

分布单子上的代数

另一个例子是集合范畴上的分布单子(英语:distribution monad,其将集合映至其上所有有限支撑概率分布的集合。该等分布,是函数,仅于有限多个元素处取值非零,而各元素处取值之和为。以符号表示,

可由定义证明,分布单子上的代数,等同于凸集,即集合要配备二元运算(对每个),满足的公理比照欧氏空间中,凸组合具备的性质。[11][12]

对称单子上的代数

另一个有用的单子,是交换环模范畴上的对称代数单子

映到各阶对称张量英语symmetric tensor幂的直和

其中。例如,,左右两边作为模同构。如此,对称代数单子上的代数,是交换代数。类似地,也有反对称张量英语Antisymmetric tensor单子与全张量单子,相应的代数分别是反对称代数与自由代数,故

前者是上添加个生成元的自由反对称代数,而后者则是个生成元的自由代数。

E环谱中的交换代数

对于可交换代数英语Highly structured ring spectrum,亦有类似的构造,[13]:113对于可交换代数,对应单子上的代数是可交换的代数。若表示模的范畴,则可以考虑函子,定义为

其中

此函子是单子,而由该单子上的代数范畴,可以得到可交换代数的范畴

单子与伴随

前文所述,任何伴随关系皆产生单子。反之,每个单子皆可由某个伴随关系产生,即原范畴与代数的艾伦伯格-摩尔范畴之间的自由-遗忘伴随

其中,左伴随的物件映到自由代数,右伴随则将代数遗忘掉,变回。然而,通常有多组不同的伴随关系产生同样的单子,该些伴随关系组成范畴:物件是伴随关系使得,而态射是在一侧为恒等函子的伴随关系态射。如此,艾伦伯格-摩尔范畴的自由-遗忘伴随的终物件,而始物件是克莱斯利范畴英语Kleisli category,定义为中的自由代数组成的完全子范畴,即仅包含形如代数,其中历遍的物件。

单子伴随

设有伴随关系,对应单子为,则函子可分解为

其中是遗忘函子。换言之,对中任意物件,都能赋予自然的代数结构。若分解式中,首个函子给出范畴间的等价,则形容该伴随关系为单子的(英语:monadic)。[14]后亦引申用作形容函子,若函子有左伴随,且该伴随关系为单子的,则亦称为单子的。例如,群范畴集合范畴间的自由-遗忘伴随是单子的,因为相应单子上的代数是群(见前文)。一般而言,若有伴随关系为单子的,则单从的物件及其上的作用,已足以重组出的物件。

贝克单子性定理

贝克单子性定理给出伴随关系在何种充要条件下为单子的。定理有以下简化版:

若满足以下三项条件:

  • 保守函子英语conservative functor,换言之,反映同构(英语:reflects isomorphisms),即对中每一支态射,其为同构当且仅当在作用下的像为中的同构;
  • 馀等化子英语coequalizer
  • 馀等化子英语coequalizer

为单子的。

例如,由豪斯多夫空间范畴集合范畴的遗忘函子是单子的。然而,由任意拓扑空间范畴到集合范畴的遗忘函子则并非单子的,而定理中,保守函子的条件不成立,因为有非紧或非豪斯多夫空间,之间存在连续双射,但不为同胚[15] 贝克定理有对偶版本,刻划馀单子伴随关系,对拓扑斯论及有关下降英语descent (category theory)代数几何课题有用。

馀单子的伴随关系,首先有下列例子:

其中皆为交换环,左伴随用到的张量积的定义中,选定了环同态,而右伴随是遗忘函子。根据贝克定理,当且仅当忠实平坦模时,该伴随为馀单子的。所以,可将配备下降数据(英语:descent datum,即源自伴随关系的馀单子的作用)的模,降成模。所得的忠实平坦下降英语faithfully flat descent理论,广泛应用于代数几何。

用途

函数式编程中,会使用单子表达某类(有时有副作用的)顺序式计算,见单子 (函数式编程)

范畴论逻辑中,藉闭包算子内代数,以及两者与S4模态逻辑直觉主义逻辑的关系,能以单子馀单子理论类比模态逻辑

推广

亦可定义2-范畴中的单子。

参见

参考文献

  1. ^ Barr, Michael; Wells, Charles. Toposes, Triples and Theories [拓扑斯、三元组与理论] (PDF). Grundlehren der mathematischen Wissenschaften 278 (Springer-Verlag). 1985: 82 and 120 [2021-09-17]. ISBN 0-387-96115-1. (原始内容存档 (PDF)于2020-11-25). 
  2. ^ Klin; Salamanca. Iterated Covariant Powerset is not a Monad [共变幂集叠代后不是单子]. Electronic Notes in Theoretical Computer Science. 2018-12-01, 341: 261–276. doi:10.1016/j.entcs.2018.11.013可免费查阅 (英语). 
  3. ^ Godement, Roger. Topologie Algébrique et Théorie des Faisceaux [代数拓扑与层论]. Actualités Sci. Ind., Publ. Math. Univ. Strasbourg 1252. Paris: Hermann. 1958: viii+283 pp (法语).  |issue=被忽略 (帮助)
  4. ^ Huber, Peter J. Homotopy theory in general categories [一般范畴的同伦论]. Mathematische Annalen. 1961, 144 (5): 361–385 (英语). 
  5. ^ Kleisli, Heinrich. Every standard construction is induced by a pair of adjoint functors [每个标准构造皆由某对伴随函子产生]. Proceedings of the American Mathematical Society. 1965, 16 (3): 544–546 (英语). 
  6. ^ Eilenberg, Samuel; Moore, John Coleman. Adjoint functors and triples [伴随函子与三元组]. Am. J. Math. 1965, 9: 301–398 (英语). 
  7. ^ Linton, Fred E. J. Some aspects of equational theories [等式理论的若干方面]. Proc. Conf. on Categorical Algebra at La Jolla. 1966: 84–95 (英语).  参数|journal=与模板{{cite conference}}不匹配(建议改用{{cite journal}}|book-title=) (帮助)
  8. ^ Moggi, Eugenio. Notions on computation on monads [单子上的计算概念] (PDF). [2021-09-25]. (原始内容存档 (PDF)于2011-03-22) (英语). 
  9. ^ Plotkin, Gordon; Power, John. Adequacy for Algebraic Effects [代数效果的适切性]. Proc. FOSSACS 2001. Lecture Notes in Computer Science 2030. 2001: 1–24. doi:10.1007/3-540-45315-6_1 (英语). 
  10. ^ Riehl (2017,162)
  11. ^ Świrszcz, T. Monadic functors and convexity [单子函子与凸性]. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astron. Phys. 1974, 22: 39–42. MR 0390019 (英语). 
  12. ^ Jacobs, Bart. Convexity, Duality and Effects [凸性、对偶、作用]. Calude, C.S.; Sassone, V. (编). Theoretical Computer Science [理论电脑科学]. IFIP Advances in Information and Communication Technology 323. 2010: 1–19. ISBN 978-3-642-15239-9. doi:10.1007/978-3-642-15240-5_1可免费查阅 (英语). 
  13. ^ Basterra, M. André–Quillen cohomology of commutative S-algebras [交换S代数的André–Quillen上同调]. Journal of Pure and Applied Algebra. 1999-12-15, 144 (2): 111–143 [2021-09-18]. ISSN 0022-4049. doi:10.1016/S0022-4049(98)00051-6可免费查阅. (原始内容存档于2022-01-30) (英语). 
  14. ^ MacLane (1978)所用定义中,条件“等价”要再加强为“同构英语Isomorphism of categories”。
  15. ^ MacLane (1978,§§VI.3, VI.9)