你可以通过学习各种各样的例子来真正欣赏范畴。范畴有各种形状和大小,经常出现在意想不到的地方。我们将从一些非常简单的东西开始。
3.1 No Objects
最小的范畴是拥有 0 个对象的范畴。因为没有对象,自然也就没有态射。它本身是一个非常可悲的范畴,但是它在其他范畴的上下文中可能很重要,例如,在所有范畴的范畴中(是的,有这么一个范畴)。如果你认为一个空集是有意义的,那么为什么空范畴就不会有意义呢?
3.2 Simple Graphs
您可以通过用箭头【arrows】连接对象【objects】来构建范畴【category】。您可以想象从任何一个有向图【directed graph】开始,通过简单地添加更多箭头【arrows】,即可以将其变成一个范畴。首先,在有向图【directed graph】的每个节点上添加一个恒等箭头【Identity Arrow】。然后为任意两个首尾相连的箭头(换句话说,即任意两个可组合的箭头)增加一个组合箭头。每次你添加新箭头时,还必须要考虑任意其他箭头(除恒等箭头之外)与其自身的组合。通常会得到无穷多个箭头,但这没关系。
让我们从另一个角度看这个过程,您正在创建一个范畴,对于有向图【directed graph】中的任一节点,范畴都有一个对应的对象【object】,而有向图【directed graph】中由所有可组合的边【edgs】所构成的链【chains】,范畴都有一个对应的态射 (你甚至可以把恒等态射看作为长度为零的链的特殊情况)。
PS:有向图【directed graph】中的“链【chains】”是指连续的边(即首尾相连的边),它使得连接有向图【directed graph】中的两个顶点成为可能。通俗而言,边【edge】即是范畴中对象与对象之间的箭头,链【chains】则是箭头的组合!!
这种由给定的图而衍生出的范畴,被称为自由范畴【 free category】。它是一种自由构造【free construction】的例子,即给定一个结构,并用符合法则(这里指的是范畴的法则)的最小数量的条目来扩展它。我们接下来看到更多这样的例子。
3.3 Orders
现在出现了截然不同的情况!现在有这样一个范畴,它所包含的态射是用来描述两个对象【objects】之间的关系:小于等于的关系。那么我们接下来来检查它是否是一个范畴。
它有恒等态射吗?每一个对象都小于或者等于自身----匹配!它可以组合吗?如果a<=b & b <= c,那么a <= c ----匹配!
具有这种关系的集(合)也被成为预序【preorder,也可称为准序列,即quasiorder】,因此预序本质上是一个范畴
注:
考虑集合 P 及其上的二元关系 <= 。若 <= 具有自反性和传递性,则称 <= 为预序。具体来说,对任意 P 的元素 a,b 和 c,下列性质成立:① a <= a (自反性)② 若 a <= b 且 b <= c,则 a <= c (传递性)带预序的集合称为预序集合。如果一个预序同时满足反对称性(若 a <= b 且 b <= a,则 a = b)的预序被称为偏序。如果一个预序同时满足对称性(若a <= b,则b <= a),则为等价关系PS: 该定义中的 <= 指的是一个二元操作,并非小于等于的意思!!
除此之外,你还可以通过额外施加这样一个条件,即如果a <= b且b <= a,则必须a = b,来得到一个更强的关系,这也被称为偏序【partial order】。
最后,您还可以再施加一个条件,即集合中的任何两个对象都以某种方式彼此关联;这就得到了一个全序【total order,也成为线性序,即linear order】
注:
全序关系即集合 X上的反对称的、传递的和完全的二元关系(一般称其为 <=)。若 X满足全序关系,则下列陈述对于 X中的所有a,b和c成立:① 反对称性:若 a <= b且b <= a则 a = b② 传递性:若 a <= b且 b <= c则 a <= c③ 完全性: a <= b 或 b <= 1满足全序关系的集合叫做全序集合、线性序集合、简单序集合或链。 链还常用来描述偏序集合的全序子集。全序关系的完全性可以如下这样描述:集合中的任何一对元素都是可相互比较的。注意:完全性条件蕴涵了自反性: a <= a,因此全序关系也是(满足“完全性”条件的)偏序关系。
让我们把这些有序的集合描述为范畴。
预序是一个最多只有一个态射(该态射表示的是从任意对象a到任意对象b的映射)的范畴。对于这种范畴还有另外一个名字:瘦【thin】。一个预序也是一个瘦范畴。
在范畴C中,从对象a到对象b的态射集也被成为hom-set,写作𝐂(𝑎, 𝑏),有时候亦写作Hom𝐂(𝑎, 𝑏)。因此预序的hom-set要么是空的,要么就只有一个态射。而对于预序的Hom𝐂(𝑎, 𝑎),即表示从对象a到对象a的态射集,该态射集中有且仅有一个态射,即恒等态射。需要注意的是,预序可以是有环的。而这在偏序中是禁止的!!即偏序是无环的(由其反对称性决定的)。
注:
对于每一个预序,都对应一个有向图,集合的元素对应顶点,对元素之间的序关系则对应顶点之间的有向边。反之则不然:大多数有向图既不是自反的,也不是传递的。通常,预序对应的有向图可能包含循环。但一个反对称的预序中不存在循环;它这时候就是是一个偏序,对应于一个有向无环图。通常,一个预序对应的有向图可能有许多断开连接的组件。
分辨预序【preorders】、偏序【partial orders】、全序【total order】是非常重要的,因为涉及到排序。排序算法,比如快速排序、冒泡排序,归并排序等等,这些都可以在全序上正确执行。但是偏序需要用拓扑排序进行排序。
3.4 Monoid as Set
幺半群【Monoid】是一个非常简单但却非常强大的概念。它是基本算术背后的概念:加法和乘法即可构成一个幺半群。幺半群在编程中无处不在,它们以字符串、列表、可折叠数据结构、并发编程中的future、函数式反应式编程中的事件等形式出现。
习惯上,幺半群被定义为一个伴随一个二元操作的集合,该操作需要保证结合律【associative】,且需要有一个特殊的幺元元素。
例如,包含0的自然数可以在加法上形成一个幺半群。结合律意味着:
(a + b) + c = a + (b + c)
自然数的幺元是0,因为:
0 + a = aa + 0 = a
第二个方程式是多余的,因为加法是满足交换律【commutative】的(即 a + b = b + a)。但是交换律并不属于幺半群的定义。比如字符串联结就不是满足交换律的,但是它仍然组成了范畴。对于字符串联结的幺元是字符串,他可以左联结或者右联结到字符串,而不会改变结果。
在Haskell中我们可以为Monoid定义一个类型类【Type class】,该类型中有一个幺元mempty以及一个称为mappend的二元操作。
// Haskellclass Monoid m wheremempty :: mmappend :: m -> m -> m
// Scalatrait Monoid[M] {def mempty : Mdef mappend ( m1 : M, m2 : M): M}
有两个参数的函数的类型签名:m -> m -> m,乍一看,会感觉很奇怪,但在我们讨论完柯里化后,你就会明白了。
您可以用两种基本方法来解释带有多个箭头的函数签名:
作为多个参数的函数,最右边的类型为返回类型;或者可以看做是带有一个参数(最左边的类型),返回值为函数的的函数。
后一种解释可以通过添加括号来强调(但这是多余的,因为箭头是右结合的【right-associative】),比如:m -> (m -> m)。我们一会儿会再回到这种函数解释。
但是需要注意的是,在Haskell中,我们没有办法来表达mempty和mappend的幺半属性【monoidal properties】(比如mempty是幺元,mappend符合结合律的事实)。确保这些属性满足,是我们程序员的责任。
Haskell类不像c++类那样具有侵入性。当定义一个新类型时,您不必预先指定它所属的类,您可以自由的延迟,并在稍后将给定类型声明为某个类的实例。作为例子,我们实现一个String类型的幺半群,并提供相应的mempty和mappend实现(实际上,这在Haskell的标准库【Prelude】中已经做了):
instance Monoid String wheremempty = ""mappend = ( ++ )}
//Scalaobject Monoid {implicit def stringMonoid : Monoid[String] = newMonoid[String] {↪def mempty : String = ""def mappend ( m1 : String, m2 : String): String = m1 + m2}}}
在这里我们重用的列表的联结操作符(++),因为字符串其实就是一个字符列表。
一言以蔽之Haskell的语法:任何中缀操作符,我们可以通过对该操作符用括弧括起来,就可以将其转换为一个双参数函数。给定两个字符串,我们可以使用++来联结这两个字符串:
"Hello " ++ "world!"
或者将它们作为两个参数传递给加上括弧的(++)函数:
(++) "Hello " "world!"
注意,函数的参数不是用逗号分隔的,也未用括弧括起来的。(这可能是初学Haskell最难的事了)
值得强调的是,Haskell允许您表示函数的相等性,如下所示:
mappend = (++)
从概念上讲,这不同于表示函数所产生的值的相等性,如下所示:
mappend s1 s2 = (++) s1 s2
前者是指Hask范畴(或Set范畴,如果我们忽略bottom的话,bottom指的是永无休止的计算)内的态射相等。这样的等式不仅更简洁,而且通常可以推广到其他范畴。
后者也被称为外延相等【extensional equality】,它表述了这样一个事实:mappend和(++)的输出是相等的。
因为参数的值,也被称为点【Points】(比如:f 在点 x 处的值),因此外延相等也被称为逐点相等【point-wise equality】,没有指定参数的函数等式也被称为point-free(顺便说一下,point-free等式经常涉及到函数的复合/组合,用点【.】来表示,所以这对初学者来说可能有点混乱)
注1:
在逻辑学中,外延性【Extensionality】或外延相等【extensional equality】,他们指的是对象如果存在相同的外部属性,那么该原则用于确认这些对象是否相等。它与内涵性【intensionality】概念相反,内涵性概念关注的是对象的内部定义是否相同。考虑 f 和 g 函数,该函数均表示自然数到自然数的映射,定义如下:1.f(n) = (n + 5) * 2 2.g(n) = n * 2 + 10我们可以说这两个函数是外延相等【extensional equality】,即给定同样的输入,输出总是相等的。但是这两个函数的定义是不相同的。从内涵【intensional】 的意义上讲,函数是不相等的。类似地,在自然语言中,有许多谓词(关系),它们在内涵上不同,但在外延上是相同的。例如,假设一个城镇有一个名叫乔【Joe】的人,他也是镇上最年长的人。然后,两个参数谓词:““have one person named【有一个名为的人】”、“is the oldest person in【是最老的人】”在内涵【intensional】的意义上是不同的,但在外延上是相等的,都表示“Joe”目前在“town”居住。
注2:
罗素公理/wiki/%E7%BD%97%E7%B4%A0%E5%85%AC%E7%90%86%E4%BD%93%E7%B3%BB
下面是C++的Monoid实现:
//C++的说辞不翻译了,没有C++基础,怕翻译错了template<class T>T mempty = delete;template<class T>T mappend(T, T) = delete;template<class M>concept bool Monoid = requires (M m) {{mempty<M> } -> M;{mappend(m, m); } -> M;};template<>std::string mempty<std::string> = {""};std::string mappend(std::string s1, std::string s2) {return s1 + s2;}
3.5 Monoid as Category
我们已经熟悉于以集合和元素来定义的Monoid。但正如你所知,在范畴论中,我们试图摆脱集合(即sets)及其元素,而是讨论对象【objects】和态射【morphism】。因此,让我们稍微换个角度,将二元操作符【binary operator】的应用想象为围绕着集合(即set)“moving”或“shifting”事物。
例如目前有一个操作符,它对自然数做加5运算,因此它将0映射为5,1映射为6,等等。这是一个定义在自然数集上的函数。这很好:我们目前有了一个函数和自然数集合。通常,对于任意数字 n,都会有一个加 n 的函数-----即n的“adder”。
这些 adder 如何组合呢?将+5的函数与+7的函数组合起来,我们得到了一个+12的函数。因此adder的组合等同于加法的规则。这也很好:我们可以用组合函数来代替加法。
等等,这还没有结束:还有一个+0的adder。加0不会带来任何变化,因此它就是自然数集上的恒等函数。
在不丢失任何信息的情况下,我可以给出adder的组合规则,而不是传统的加法规则:
adders的组合是可结合的【associative】,因为函数的组合是可结合的【associative】;我们还有一个0值adder,对应于恒等函数。
精明的读者可能已经注意到,从整数(integer)到adder的映射遵循对mappend类型签名的第二种解释方式,即m -> (m -> m)。它告诉我们,mappend将一个幺半群集合【monoid set】中的元素映射到作用于该集合上的函数。
现在我想让你忘记你正在处理的是自然数的集合,而是将其视为一个单对象【 single object】,一个难以名状的团,且有一大堆态射——即一个个的adders。一个幺半群,是一个单对象的范畴。事实上幺半群【monoid】这个名字来自希腊语mono,意思是单一的。每个幺半群【monoid】都可以被描述为一个单对象的范畴,且具有一组遵循适当组合规则的态射。
字符串连结是一个有趣的用例,因为我们可以选择定义右追加器【right appender】和左追加器【left appender】(也可以称为 预追加器【prependers】,如果你愿意的话)。这两个模型的组合表【composition tables】彼此互为镜像。 您可以轻松地说服自己,在“ foo”之后添加“ bar”对应于在“ bar”之前添加“ foo”。
你可能会问,是否每一个范畴幺半群【categorical monoid】—— 即一个单对象范畴 ——都唯一定义了一个伴随二元操作的集合幺半群【defines a unique set-with-binary-operator monoid】。事实证明,我们总是可以从一个单对象范畴【single-object category】中提取出一个集合【set】。这个集合【set】就是态射集 —— 在我们的例子中指的是adders。换句话说,对于范畴M中的单对象【single object】m,我们都有一个hom-setM(m, m),我们可以很容易的在这个集合中定义二元操作:集合中两个元素的幺半积【monoidal product】是对应于相应态射的组合。如果你给我两个**M(m, m)**中的元素,分别对应于 𝑓 和 𝑔,他们的乘积对应于 𝑓 ∘ 𝑔。这些组合始终存在,因为态射的源类型和目标类型总是一致的。根据范畴的规则,他们是符合结合律的。恒等态射也是肯定存在的。因此,我们总是能够从一个范畴幺半群【category monoid】中复原出集合幺半群【 set monoid】。无论从哪个角度来说,它们都是同一个东西。
PS: 幺半范畴
对于数学家来说,这里还是有点问题:态射不必形成一个集合。在范畴的世界里,有比集合更大的东西。任何两个对象之间的态射构成一个集合的范畴被称为局部小【locally small】。正如我所承诺的,我将主要忽略这些细微之处,但我认为我应该把它们记录在案。
小范畴【small categories】:如果ob(C)和hom(C)实际上都是集而不是真类,则称类别C称为小范畴,否则称为大类别。大范畴【large categories】:同上局部小范畴【locally small】:如果一个范畴的每个hom-sets都是一个small set,也就是说,它是一个集合【set】,而不是一个真类【proper class】,那么这个范畴就被称为局部小。数学中的许多重要范畴(比如集合范畴),虽然不是小范畴,但至少在局部上是小的。由于在小范畴【small categories】中,对象形成一个集合,因此可以将小范畴【small categories】视为类似于幺半群【Monoid】的代数结构,但不需要闭包属性。 另一方面,大范畴【large categories】可以用来创建代数结构的“结构”。
这里需要解释一下类、真类、集合再朴素集合论中,集合的定义存在很多瑕疵,比较著名有罗素悖论。公理集合论是在一阶逻辑的基础上用严谨的语言重整的集合论,试图以此解决朴素集合论中出现的悖论。现代数学通常采用Zermelo-Fraenkel公理系统(ZF),或者加入选择公理后的ZFC系统,作为建立数学大厦的基石。从公理集合论诞生开始,人们不再随意乱用“集合”这个名词。作为替代,我们不把“具有某种特定性质的事物的总体”称作集合,而把它称作“类”(class)。只有当这些“具有某种特定性质的事物的总体”与ZFC公理系统不矛盾(例如不能导出罗素悖论)时,我们才把它称作集合。注意在上面的定义中,类的概念是集合的拓展——即,集合也是一种特殊的类。如果要强调所考虑的类不是集合,则称其为“真类”(proper class)。下面举一些常见的真类的例子:1、全体集合构成一个真类;2、全体线性空间(linear space)构成一个真类;3、全体拓扑空间(topological space)构成一个真类。
范畴论中许多有趣的现象都源于这样一个事实:即hom-set的元素既可以看作是遵循组合规则的态射,也可以看作是集合中的点【point】。 在这里,𝐌中的态射组合被转化为集合𝐌(𝑚,𝑚)中的幺半积【monoidal product】。
如果觉得《范畴论:1.3 大大小小的范畴》对你有帮助,请点赞、收藏,并留下你的观点哦!